Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper reveals that Lloyd's $K$-means algorithm is fundamentally a special case of the Frank-Wolfe (FW) algorithm, linking a widely used clustering method to a robust first-order optimization framework. By leveraging recent advancements in FW methods, the authors establish a non-asymptotic convergence rate of $\mathcal{O}(1/t)$ for Lloyd's algorithm, ensuring efficient minimization of the sum of squared errors (SSE) even in the presence of empty clusters. The findings are validated through simulations on spherical Gaussian mixtures and real-world image segmentation tasks, highlighting the practical implications of this theoretical connection.
Lloyd's $K$-means algorithm achieves a surprising $\mathcal{O}(1/t)$ convergence rate by being a special case of the Frank-Wolfe algorithm, even when dealing with empty clusters.
Lloyd's $K$-means algorithm, also known as na\"{i}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.