Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguise
Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-Julien
stat.ML, cs.LG, stat.CO
Submitted: 2026-07-28
Comments: AISTATS 2026 Poster: https://virtual.aistats.org/virtual/2026/poster/13894
Journal ref: AISTATS 2026, Poster 6
Code: https://github.com/mpokojovy/kmeansFW
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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
Terminology
Abstract
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 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.
Sources
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- Scalable Posterior Uncertainty for Flexible Density-Based Clustering
- A Transport Geometry of Benign Overfitting
- Efficient quadratic entropy with distance sketches