K-Means Clustering Revealed as Frank-Wolfe Optimization in Disguise

Researchers Michael Pokojovy, J. Marcus Jobe, and Simon Lacoste-Julien have established a novel theoretical equivalence between Lloyd's K-means clustering algorithm—a ubiquitous ad hoc heuristic—and the Frank-Wolfe (FW) algorithm, a well-known first-order method for projection-free optimization. In their AISTATS 2026 paper, they demonstrate that Lloyd's iterative cluster refinement is mathematically identical to FW applied to a concave objective. Leveraging recent advances in FW methods, they derive a non-asymptotic O(1/t) convergence rate to a local minimum of the sum-of-squared-errors (SSE) objective. They also address the practical issue of empty clusters (possible under Lloyd's greedy assignment) by developing an FW variant for semismooth objectives that retains the same convergence rate, controlled solely by the initial SSE value. The results are illustrated with simulations on spherical Gaussian mixtures and a real-world image segmentation dataset.

The discovery bridges a gap between heuristic clustering and rigorous optimization theory, offering new theoretical guarantees for a method used daily in data science. Instead of treating Lloyd's algorithm as an ad hoc trick, practitioners can now leverage FW's convergence properties and rich literature. The FW variant for semismooth objectives provides a principled way to handle empty clusters, a common nuisance in practice. While the immediate practical impact may be modest, the foundational insight opens doors to improved convergence diagnostics, faster variants, and connections to other projection-free algorithms. This is a milestone for anyone in machine learning, statistics, or optimization who has ever used K-means and wondered about its theoretical underpinnings.