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

Lloyd's algorithm is the standard heuristic for K-means clustering, yet its theoretical convergence properties are often studied in isolation. This paper investigates the optimization landscape of K-means by establishing a formal mathematical equivalence between Lloyd's algorithm and the Frank-Wolfe (FW) algorithm, a projection-free method for constrained optimization. The authors aim to leverage this connection to provide rigorous convergence guarantees for K-means.

The researchers reformulate the K-means sum of squared errors (SSE) objective as a concave optimization problem over a convex hull of partitions. By treating the cluster assignment step as a linear minimization oracle (LMO) within the Frank-Wolfe framework, they demonstrate that Lloyd's algorithm is essentially a Frank-Wolfe iteration with a unit step-size. To address the practical issue of empty clusters—which can cause the objective to become non-smooth—the authors extend the FW framework to handle semismooth concave objectives using the Clarke subdifferential.

The study establishes that Lloyd's algorithm achieves a non-asymptotic O(1/t) convergence rate to a local minimum of the SSE objective. This rate is notable because it is controlled solely by the initial suboptimality and remains uniform across sample sizes, dimensions, and the number of clusters. By utilizing the Clarke subdifferential, the authors ensure that this convergence guarantee holds even when the greedy assignment strategy leads to empty clusters, providing a robust theoretical foundation for the algorithm's performance.

This work bridges the gap between heuristic clustering practices and formal optimization theory. By framing K-means as a special case of Frank-Wolfe, researchers gain access to a powerful toolkit for analyzing convergence and error control. This perspective is particularly valuable for robust cluster analysis and provides a clear, mathematically elegant explanation for why Lloyd's algorithm behaves as it does, potentially informing the development of more stable clustering variants in the presence of outliers or model violations.