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

AI summary

Overview

Research area: Optimization theory for unsupervised machine learning, specifically the convergence analysis of K-means clustering via projection-free (Frank-Wolfe) optimization.

Technical level: Advanced. The paper relies on convex analysis, Clarke subdifferentials, semismooth optimization, and the Frank-Wolfe literature.

Scope: The paper proves that Lloyd's K-means algorithm is a special case of the Frank-Wolfe algorithm with unit step-size, and derives a non-asymptotic O(1/t) convergence rate for the sum-of-squared-errors objective, including the case where clusters become empty.

Published as arXiv:2607.25190v1 [stat.ML] on 28 Jul 2026 by Michael Pokojovy (Old Dominion University), J. Marcus Jobe (Miami University), and Simon Lacoste-Julien (Université de Montréal / Mila), under a CC BY 4.0 license.

What This Paper Is About

Lloyd's K-means is described by the authors as a widely used "ad hoc optimization heuristic" for minimizing the sum of squared errors (SSE) over all K-partitions of a dataset. While K-means clustering is NP-hard (Arthur and Vassilvitskii, 2006), Lloyd's iterative refinement (Lloyd, 1982) remains the shared core of most implementations, and is regarded as one of the Top 10 algorithms in data mining (Wu et al., 2008).

The goal of this paper is to show that Lloyd's greedy clustering step is not merely an informal heuristic but is mathematically identical to a Frank-Wolfe step, which lets the authors import recent convergence machinery for concave Frank-Wolfe optimization and obtain rigorous, non-asymptotic convergence guarantees for K-means — including when clusters become empty.

Key Contributions

1. Lloyd's algorithm identified as Frank-Wolfe. The authors show that Lloyd's algorithm with greedy cluster assignment is a special case of the Frank-Wolfe algorithm with unit step-size, applied to a semismooth concave objective over a polyhedral set. When empty clusters are excluded from the feasible set, the objective becomes smooth, which allows the authors to leverage recent convergence results for concave Frank-Wolfe to establish a non-asymptotic O(1/t) convergence rate (Yurtsever and Sra, 2022).

2. A Frank-Wolfe variant for semismooth objectives. To handle the practically relevant possibility of empty clusters, the authors develop a Frank-Wolfe algorithm for general (semismooth) concave objectives using a new Frank-Wolfe gap based on the Clarke subdifferential. This replaces the less convenient Goldstein's subgradient used in earlier work.

3. Uniformity of the convergence bound. The same non-asymptotic O(1/t) rate is recovered and depends solely on the initial global suboptimality. It holds uniformly in sample size n, space dimension d, and number of clusters K, and involves no coreset considerations — a contrast with ε-coreset-based estimates, which the authors note tend to explode as ε → 0.

4. Self-contained proofs plus empirical illustration. The authors provide self-contained proofs and report that a simulation study was performed to corroborate the results, using spherical Gaussian mixtures and a real-world image segmentation dataset.

Main Findings

• The FW gap equals the SSE decrease exactly. In the non-empty-cluster case, the authors show the Frank-Wolfe gap at step t equals f(w^(t)) − f(w^(t+1)), i.e. the drop in the SSE objective, so the abstract FW stationarity measure has a direct, interpretable meaning for K-means.

• Unit step-size is optimal (Lemma 2). Because the objective is concave, the direction-restricted function φ_t(γ) = f(x^(t) + γ d_t) attains its global minimum at a boundary of [0,1], and the unit step-size γ_t = 1 solves the line search problem min_{γ∈[0,1]} f(x^(t) + γ d_t). This means Lloyd's full reassignment step is the line-search-optimal Frank-Wolfe step, requiring no extra function evaluations.

• Non-asymptotic O(1/t) rate (Theorem 3). For semismooth Frank-Wolfe on concave objectives with unit step-size, the running minimum FW gap satisfies g̃_t ≤ h_0/(t+1) for 0 ≤ t ≤ T−1, where h_0 = f(x^(0)) − min_{x∈M} f(x) is the initial global suboptimality. Concavity improves the rate from the general non-convex O(1/√t) to O(1/t).

• Clarke-based stationarity measure. The authors introduce the Clarke Frank-Wolfe gap g_C(x) := min_{r∈∂f(x)} max_{y∈M} ⟨y−x, −r⟩, which is nonnegative and equals zero if and only if x is Clarke stationary.

• The SSE objective is concave with a negative semidefinite Hessian (Lemma 6). The gradient is ∂{w_ik} f(w) = ||x_i − x̄_k^w||², and the Hessian entry ∂{w_ik}∂_{w_jl} f(w) equals −(2/n_k^w)·1{k=l}·(x_i − x̄_k^w)·(x_j − x̄_k^w). Because the Hessian is negative semidefinite, f is concave in the interior of M and, by Bauer's minimum principle (Kružík, 2000), attains a global minimum at an extreme point M_0.

• The gradient does not extend continuously. The paper notes that ∇f cannot be continuously extended to M, so the smooth Frank-Wolfe algorithm cannot be applied directly over M — motivating the semismooth treatment.

• Bounded curvature in the admissible case (Remark 7). On M^adm, ||∇²f(w)|| ≤ 2R² with R = max_{i,j=1,…,n} ||x_i − x_j||, giving a bounded curvature constant C_f = 4n (max_{i,j} ||x_i − x_j||²). The general non-convex approach of Lacoste-Julien (2016) is therefore applicable, but yields an inferior O(1/√t) rate.

• Lloyd's iterates coincide with FW iterates (Theorem 8). Assuming w^(t) ∈ M_0^adm for all t, the membership vector produced by Lloyd's K-means coincides with the t-th iterate of the Frank-Wolfe Algorithm 1 applied to minimizing f over M^adm, so min_{0≤τ≤t} ΔSSE_τ ≤ h_0/(t+1) for t = 0, …, T−1.

• Initial suboptimality is bounded and interpretable. The constant is independent of sample size n, dimension p, and initial clusters. The initial gap satisfies h_0 ≤ (n−1) tr(S_n) = Σ_{i=1}^{n} ||x_i − x̄||², using the standard SSE identity (Johnson and Wichern, 2007, p. 693), where x̄ and S_n are the sample mean and unbiased sample covariance of the full dataset. Under i.i.d. sampling from a squared-integrable distribution with covariance Σ, h_0 = (n−1) tr(Σ) + o_P(n) almost surely as n → ∞, uniformly over arbitrary initial cluster choice (Remark 9).

• Cost and termination. For any given run, the usual O(ndKT) complexity and O(nd + Kd) storage hold. If M is a convex polytope conv(M_0), the FW algorithm must terminate in |M_0| steps or less.

• Empty clusters: two routes. Lloyd's greedy assignment can produce empty clusters. One option is to solve the linear minimization exactly, which guarantees an admissible allocation; no closed-form solution exists, but Thorup's version of the Hungarian algorithm computes it in O(nK² + K² log log K) time. The authors note this approach is disfavored — even clusters with d+1 or more points in general position are not guaranteed to produce well-conditioned covariances (García-Escudero et al., 2008), so cluster-size constraints are often viewed as ineffective. The authors instead analyze Lloyd's algorithm directly through the semismooth Frank-Wolfe framework, arguing that any rule for choosing an "ephemerous" center for an emptied cluster (reusing the previous center, random sampling from the dataset, or another strategy) corresponds to selecting an element of the Clarke subdifferential of the extended semismooth concave objective, yielding the same O(1/t) rate. The provided paper text is truncated mid-derivation at this point; the remaining derivation, the spherical Gaussian mixture simulation, and the image segmentation dataset results are not reported in the available content.

Methodology in Plain English

The authors recast K-means in the language of Frank-Wolfe optimization. Instead of viewing a clustering as a hard 0/1 assignment, they encode it as a matrix w whose rows are "one-hot" vectors indicating cluster membership, then take the convex hull of all such matrices. On this convex set, the SSE objective can be written down continuously as a function of w, and its Hessian turns out to be negative semidefinite — the function is concave, not convex.

Frank-Wolfe works by repeatedly calling a linear minimization oracle (LMO) that finds the feasible point best aligned with the negative gradient, then stepping toward it. The authors show that for the K-means objective, this LMO step is exactly Lloyd's assignment rule: each point is sent to the nearest current centroid. Moreover, since the objective is concave, the optimal step size is always the full step (γ = 1), so the algorithm jumps all the way to the new assignment — precisely Lloyd's update. Because the objective's gradient blows up or becomes undefined when a cluster empties, the authors switch to Clarke subdifferentials, which generalize gradients to nonsmooth functions, define a matching stationarity measure and Frank-Wolfe gap, and reprove the O(1/t) rate under that weaker smoothness assumption. The proof accumulates the objective decrease across iterations: every step reduces the objective by at least the Frank-Wolfe gap, and total decrease cannot exceed the initial suboptimality h_0, forcing some gap in the first t+1 steps to be at most h_0/(t+1).

Why This Matters

Impact on research. K-means has been studied through many lenses — combinatorial programming, mixed integer nonlinear programming, expectation maximization, smooth and nonsmooth optimization, and matrix factorization (Bagirov and Mohebi, 2015; Bauckhage, 2016; Bottou and Bengio, 1995). This paper adds a new one. It also closes a gap in the Frank-Wolfe literature by developing a Frank-Wolfe method for concave semismooth objectives, using Clarke subdifferentials instead of Goldstein's subgradient, while retaining the smooth-case O(1/t) result. Unlike ε-coreset approaches (Clarkson, 2010; Har-Peled and Kushal, 2007; Ravi et al., 2019), which are described as involved and whose bounds explode as ε → 0, the new rate depends only on initial suboptimality and holds uniformly in n, d, and K. The framework requires no polytope structure or combinatorial arguments, which the authors argue makes it robust to modifications and extensions.

Real-world applications:

• Image segmentation — the paper illustrates its findings on a real-world image segmentation dataset.
• Robust cluster analysis — the authors expect implications for robust clustering designed to handle outliers and model violations (Dorabiala et al., 2022; García-Escudero et al., 2008).
• Gaussian mixture modeling — both spherical and non-spherical mixture settings are discussed, including the failure of cluster-size constraints to guarantee well-conditioned covariances.
• Gaussian trimmed likelihood estimation — the paper positions this work alongside a prior application of the same Frank-Wolfe strategy to that problem (Pokojovy and Jobe, 2022).

Industry relevance. Because Lloyd's algorithm is the shared core of most K-means implementations and is nearly ubiquitous across application fields, any theoretical guarantee about its convergence carries directly over to deployed systems. The paper also frames the result as providing "a practical error control mechanism": the FW gap is computable as the SSE decrease, so practitioners can monitor a quantity that is provably bounded by h_0/(t+1). The authors further note the work is potentially relevant wherever greedy variants of the linear minimization oracle can destroy smoothness.

Future Directions

• Completing the empty-cluster analysis. The provided content cuts off mid-derivation of the general semismooth case; formally establishing that every ephemerous-center selection rule yields an element of the Clarke subdifferential — and the full O(1/t) bound under that regime — is the paper's remaining technical program.

• Extension to robust clustering. The authors explicitly anticipate implications for robust cluster analysis accounting for outliers and model violations, an area with limited convergence results due to combinatorial challenges (Bernholt and Fischer, 2004).

• Generalizing beyond K-means. Because the framework needs no polytope structure or combinatorial arguments

Authors’ abstract

Lloyd's $K$-means algorithm, also known as naïve $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 $\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.