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

arXiv: https://arxiv.org/abs/2607.25190 · HTML: https://mlsanity.com/paper/2607.25190/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 66 references that are in the map.
- First posted on arXiv 28 Jul 2026.

## Builds on (most cited first, 16 of 16)

- [Unsupervised Learning from Narrated Instruction Videos](https://mlsanity.com/paper/1506.09215/) (2015)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [Is Bang-Bang Control All You Need? Solving Continuous Control with Bernoulli Policies](https://mlsanity.com/paper/2111.02552/) (2021)
- [Convergence guarantees for a class of non-convex and non-smooth optimization problems](https://mlsanity.com/paper/1804.09629/) (2018)
- [A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe](https://mlsanity.com/paper/1702.06457/) (2017)
- [Linearly Convergent Frank-Wolfe with Backtracking Line-Search](https://mlsanity.com/paper/1806.05123/) (2018)
- [Barrier Frank-Wolfe for Marginal Inference](https://mlsanity.com/paper/1511.02124/) (2015)
- [The Frank-Wolfe algorithm: a short introduction](https://mlsanity.com/paper/2311.05313/) (2023)
- [CCCP is Frank-Wolfe in disguise](https://mlsanity.com/paper/2206.12014/) (2022)
- [Theoretical Analysis of the k-Means Algorithm - A Survey](https://mlsanity.com/paper/1602.08254/) (2016)
- [A Deterministic Nonsmooth Frank Wolfe Algorithm with Coreset Guarantees](https://mlsanity.com/paper/1708.06714/) (2017)
- [Active set complexity of the Away-step Frank-Wolfe Algorithm](https://mlsanity.com/paper/1912.11492/) (2019)
- [Robust Trimmed k-means](https://mlsanity.com/paper/2108.07186/) (2021)

## Abstract (arXiv)

Lloyd's K-means algorithm, also known as na"ive 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.