📊 statistics

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

This paper establishes that Lloyd's $K$ -means algorithm is a special case of the Frank-Wolfe method, thereby deriving a non-asymptotic $\mathcal{O}(1/t)$ convergence rate to a local minimum for the sum of squared errors objective and extending this analysis to handle empty clusters via a semismooth variant.

Original authors: Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-Julien

Published 2026-07-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-Julien

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but instead of fingerprints, you have thousands of scattered clues—dots on a map, pixels in a photo, or words in a book. Your job is to group these clues into meaningful piles based on how similar they look. This is the heart of clustering, a superpower in the world of machine learning that helps computers find hidden patterns in messy data without a teacher telling them what to look for.

One of the oldest and most famous ways to do this is called K-means. Think of it like a game of musical chairs with a twist: you pick a few "captains" (centers) for your groups, and every data point runs to the captain it feels closest to. Then, the captains move to the average spot of their new team, and everyone runs again. You keep doing this until everyone stops moving. It's a greedy, step-by-step process that usually works great, but for decades, mathematicians have been scratching their heads about exactly how fast it finds the best solution and why it sometimes gets stuck in a loop.

Enter the Frank-Wolfe algorithm, a different kind of optimization tool used by mathematicians to solve complex problems without needing to bounce off walls (a technique called "projection"). It's like a hiker who always chooses the steepest path down a hill, taking giant steps until they reach the bottom. For a long time, these two methods—K-means and Frank-Wolfe—seemed to live in different neighborhoods. But a new paper suggests they are actually the same person wearing different hats.

The Great Reveal: K-means is Frank-Wolfe in Disguise

In this paper, the authors, Michael Pokojovy, J. Marcus Jobe, and Simon Lacoste-Julien, pull back the curtain to show that Lloyd's K-means algorithm (the standard version everyone uses) is actually a special, sneaky version of the Frank-Wolfe algorithm.

To understand the magic, imagine you are trying to organize a massive party. You want to group guests so that people who like the same music sit together.

The Old Way (K-means): You pick a few tables (centers), ask everyone to sit at the closest table, then move the tables to the center of the people sitting there. You repeat this until the tables stop moving.
The New Insight: The authors realized that when K-means moves a table to the center of its guests, it is mathematically doing the exact same thing as the Frank-Wolfe algorithm taking a giant step down a hill.

Why does this matter? Because the Frank-Wolfe algorithm is a well-behaved, mathematically "clean" tool with a known speed limit. By realizing K-means is just Frank-Wolfe in a party hat, the authors can use the clean math of Frank-Wolfe to prove exactly how fast K-means will finish its job.

The "Empty Chair" Problem

There is one tricky part to the K-means game: sometimes, a table ends up with no one sitting at it. In the party analogy, a captain might be left standing alone because everyone ran to a different table. In math terms, this creates a "gap" or a rough spot in the smooth hill that Frank-Wolfe usually rolls down.

The authors didn't ignore this problem; they tackled it head-on. They developed a new, slightly more flexible version of the Frank-Wolfe algorithm that can handle these "empty chair" moments (which they call semismooth objectives). They proved that even when clusters go empty, the algorithm doesn't get confused or slow down. It keeps rolling down the hill, just as efficiently as before.

How Fast is Fast?

The most exciting finding is the speed. The authors proved that the K-means algorithm converges to a good solution at a rate of O(1/t).

Let's break that down with a simple metaphor: Imagine you are walking toward a treasure chest.

If you were walking at a rate of O(1/√t), you would take a big step at first, but your steps would get smaller and smaller very quickly, like you were wading through thick mud.
But because K-means is actually Frank-Wolfe, it walks at a rate of O(1/t). This means your steps get smaller, but you are guaranteed to get closer to the treasure much more predictably.

Crucially, the authors showed that this speed depends only on how far away you started from the best possible solution. It doesn't matter if you have a million data points (a huge party) or just a few; the speed guarantee holds true. This is a big deal because previous theories often got messy and complicated when the number of data points grew.

Testing the Theory

To make sure this wasn't just a pretty math trick, the team ran massive simulations.

They created fake data that looked like "blobs" of points (like colorful clouds of confetti) and ran the K-means algorithm thousands of times.
They also tested it on a real-world dataset of image segmentation, where the goal is to group pixels in a photo to separate the sky, grass, and buildings.

In every test, the "gap" between where the algorithm was and where it wanted to be shrank exactly as the math predicted. When they plotted the results on a graph, the line went down with a slope of -1.0, which is the mathematical signature of the O(1/t) speed. Even when the data was messy or the clusters were weirdly shaped, the algorithm kept its cool.

A New Way to Stop the Algorithm

One of the most practical takeaways is how to know when to stop the party. Usually, computers stop K-means when the centers stop moving much. But the authors suggest a better way: stop when the "Frank-Wolfe gap" (the difference in the score between the current arrangement and the next possible arrangement) gets small enough.

This new stopping rule is like having a fuel gauge that tells you exactly how much "work" is left to do. It's more reliable than guessing, and it gives a hard limit on how many steps the algorithm will ever need to take.

The Bottom Line

This paper doesn't invent a new way to do K-means; instead, it reveals that the old, trusted way we've been using for decades is actually a disguised version of a powerful, modern mathematical tool. By connecting these two worlds, the authors have given us a clear, proven speed limit for K-means and a better way to know when the job is done. It's a reminder that sometimes, the most familiar tools in science are just wearing a different costume than we thought.

Technical Summary: Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguise

Problem Statement
Lloyd's K-means algorithm (naïve K-means) is a ubiquitous heuristic for minimizing the Sum of Squared Errors (SSE) across $K$ -partitions of a dataset. Despite its widespread use, the theoretical understanding of its convergence remains limited, particularly regarding non-asymptotic rates that hold uniformly across sample size ( $n$ ), dimension ( $d$ ), and cluster count ( $K$ ). Existing convergence analyses often rely on $\epsilon$ -coresets, where bounds tend to explode as $\epsilon \to 0$ , or focus on asymptotic behavior. Furthermore, standard optimization frameworks struggle with the "greedy" nature of Lloyd's assignment, which can lead to empty clusters, rendering the objective function non-smooth (semismooth) and difficult to analyze using standard smooth optimization tools.

Methodology
The authors establish a novel theoretical connection by demonstrating that Lloyd's K-means algorithm is a special case of the Frank-Wolfe (FW) algorithm (also known as conditional gradient descent) applied to a concave objective over a polyhedral set.

Formulation as Continuous Optimization: The discrete K-means partitioning problem is encoded using a "one-hot" vector $w \in \{0, 1\}^{n \times K}$ . The SSE objective $f(w)$ is extended continuously to the convex hull of these partitions, $M = \text{conv}(M_0)$ .
Concavity and Semismoothness: The authors prove that the extended SSE objective is a concave function. Crucially, while the function is smooth within the interior of the feasible set (where all clusters are non-empty), it becomes semismooth when clusters become empty.
FW Equivalence:
- Non-Empty Clusters: When all clusters are non-empty, Lloyd's greedy assignment step corresponds exactly to an FW step with a unit step-size ( $\gamma_t = 1$ ) over the polytope of admissible partitions.
- Empty Clusters: To handle empty clusters, the authors develop a variant of the FW algorithm for general semismooth concave objectives. They utilize the Clarke subdifferential (rather than Goldstein's subgradient) to define a generalized FW gap. They show that Lloyd's strategy of retaining the previous centroid for an empty cluster corresponds to selecting an element from the Clarke subdifferential of the extended objective.
Convergence Analysis: Leveraging recent advances in FW methods for concave objectives (specifically Yurtsever and Sra, 2022), the authors derive a non-asymptotic convergence rate. They define a stationarity measure based on the Clarke FW gap, $g_C(x)$ , and prove that the minimal gap encountered after $t$ iterations satisfies $\tilde{g}_t \leq h_0 / (t+1)$ , where $h_0$ is the initial global suboptimality.

Key Contributions

Theoretical Unification: The paper proves that Lloyd's algorithm with greedy assignment is a special case of the FW algorithm with unit step-size for a semismooth concave objective over a polyhedral set.
Convergence Rate: The authors establish a non-asymptotic $O(1/t)$ convergence rate to a local minimum of the SSE objective. This rate is controlled solely by the initial SSE value ( $h_0$ ) and is uniform with respect to $n$ , $d$ , and $K$ . It avoids the dependence on $\epsilon$ -coreset parameters that plague previous analyses.
Handling Empty Clusters: A new FW variant for semismooth concave objectives is developed, utilizing the Clarke subdifferential. This allows the theoretical framework to accommodate the practically relevant scenario of empty clusters without sacrificing the convergence rate.
New Error Measure: The work proposes the FW gap (equivalent to the decrease in SSE, $\Delta SSE_t$ ) as a stopping criterion. Unlike the standard centroid movement metric, this measure is affine-invariant and comes with a theoretical guarantee on the maximum number of steps required to reach a specific tolerance.

Results

Simulation Study: The authors conducted extensive Monte Carlo simulations on synthetic spherical Gaussian mixtures ("blobs") and a real-world image segmentation dataset.
- Synthetic Data: Across various configurations of $n$ , $d$ , and $K$ , the worst-case FW gap decayed monotonically. Regression analysis of the log-log plots confirmed a slope consistent with $-1$, supporting the $O(1/t)$ rate.
- Real-World Data: On the UCI image segmentation dataset (which violates Gaussian and spherical assumptions), the empirical convergence rate also supported the $O(1/t)$ bound, with the null hypothesis of a slope of $-1$ not being rejected.
Theoretical Bounds: The derived bound $h_0/(t+1)$ provides a concrete estimate for the initial suboptimality, which scales linearly with $n$ and the trace of the sample covariance matrix.

Significance and Claims
The paper claims that viewing Lloyd's K-means through the lens of semismooth FW optimization provides a "new simple, yet powerful tool" that offers:

Convergence Guarantees: Rigorous, non-asymptotic $O(1/t)$ rates that hold uniformly across problem dimensions, a significant improvement over previous heuristic analyses.
Practical Error Control: A theoretically grounded stopping rule based on the FW gap (SSE decrease) rather than arbitrary centroid movement thresholds. This allows for the calculation of a maximum number of iterations required to achieve a desired precision.
Robustness: The approach is robust to modifications and extensions, such as trimmed K-means or robust cluster analysis, because it relies on general convex geometry rather than specific polytope structures or combinatorial arguments.

The authors note that while the results are significant for standard and robust K-means, extensions to online/stochastic settings and general elliptic mixtures remain open challenges. The work is presented as a foundational step in applying projection-free optimization techniques to combinatorial clustering problems.