Lloyd's K-means本质是Frank-Wolfe算法，可保证收敛速度
Lloyd's $K$-Means Clustering Algorithm Is Frank-Wolfe in Disguise
- 将K-means视为无投影优化的Frank-Wolfe方法
- 首次证明其在t步内达到O(1/t)收敛率
- 处理空簇问题仍保持相同收敛性，适合理论研究者
Lloyd's K-means算法（又称朴素K-means）是一种广泛使用的启发式优化方法，通过迭代更新聚类中心以最小化所有K-划分下的平方误差和（SSE）。本文揭示了该算法与经典一阶优化方法Frank-Wolfe（FW）之间的新联系：Lloyd算法是FW的一个特例。基于近期针对凹目标函数的FW进展，我们推导出其到SSE局部极小值的非渐近收敛率为O(1/t)。为应对Lloyd算法中可能出现的空簇问题，我们提出一种适用于半光滑目标的FW变体，仍保持仅由初始SSE控制的相同收敛速率。仿真研究使用球形高斯混合数据集，真实图像分割数据集也验证了结论的有效性。
原文摘要 · Abstract (English)
Lloyd's $K$-means algorithm, also known as naïve $K$-means, is a widely used ad hoc optimization heuristic, designed to minimize the sum of squared errors (SSE) across all $K$-partitions of a dataset via iterative cluster refinement. In this work, we establish a novel connection between Lloyd's algorithm and the Frank-Wolfe (FW) algorithm, a prominent first-order method for projection-free optimization. We demonstrate that Lloyd's algorithm is a special case of FW. Leveraging recent advances in FW methods for concave objectives, we derive a non-asymptotic $\mathcal{O}(1/t)$ convergence rate to a local minimum of the SSE objective. To account for empty clusters, an outcome possible under Lloyd's greedy assignment, we develop an FW variant for semismooth objectives while retaining the same convergence rate that is solely controlled by the initial SSE value. We illustrate our findings with a simulation study for spherical Gaussian mixtures and a real-world image segmentation dataset.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。