Lloyd’s $K$-Means Clustering Algorithm is Frank-Wolfe in Disguise

Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-Julien
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1639-1647, 2026.

Abstract

Lloyd’s $K$-means algorithm, also known as naïve $K$-means, is a widely used \emph{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-pokojovy26a, title = { Lloyd’s $K$-Means Clustering Algorithm is Frank-Wolfe in Disguise }, author = {Pokojovy, Michael and Jobe, J. Marcus and Lacoste-Julien, Simon}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1639--1647}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/pokojovy26a/pokojovy26a.pdf}, url = {https://proceedings.mlr.press/v300/pokojovy26a.html}, abstract = { Lloyd’s $K$-means algorithm, also known as naïve $K$-means, is a widely used \emph{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. } }
Endnote
%0 Conference Paper %T Lloyd’s $K$-Means Clustering Algorithm is Frank-Wolfe in Disguise %A Michael Pokojovy %A J. Marcus Jobe %A Simon Lacoste-Julien %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-pokojovy26a %I PMLR %P 1639--1647 %U https://proceedings.mlr.press/v300/pokojovy26a.html %V 300 %X Lloyd’s $K$-means algorithm, also known as naïve $K$-means, is a widely used \emph{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.
APA
Pokojovy, M., Jobe, J.M. & Lacoste-Julien, S.. (2026). Lloyd’s $K$-Means Clustering Algorithm is Frank-Wolfe in Disguise . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1639-1647 Available from https://proceedings.mlr.press/v300/pokojovy26a.html.

Related Material