How Far From Optimal Is k-means, Really? Certified Gaps on Real Benchmarks

Every k-means user knows the algorithm depends on where it starts. Lloyd's method alternates between assigning points to the nearest center and moving each center to the mean of its points, and it stops at whichever local minimum is closest to its seeds. A large literature proposes better seeding, and a separate literature proposes convex relaxations that avoid local minima altogether. Yet on real datasets neither literature can say how far any solution is from the true global optimum. Initialization papers compare heuristics against each other or against class labels. Relaxation papers prove optimality only for synthetic, well-separated clusters. As a result, we do not know whether initialization sensitivity on real data costs 0.1% of the objective or 30%. We also do not know whether a method's win reflects better optimization or just luck relative to a weak competitor.

We propose to build a scalable certificate: a provable lower bound on the optimal k-means cost that can be computed on real data, from hundreds to millions of points. With it, we will measure the certified optimality gap of every major seeding and optimization method. The bound comes from the convex semidefinite relaxation of Euclidean k-means, which only exists because squared Euclidean distances come from inner products. We make it cheap through two steps. First, we split the data into random blocks and solve a small relaxation on each block. Second, we repair approximate dual solutions so that every reported number is a valid bound, even when the solver has not converged. The audit then answers a question the field has skipped: on which kinds of real data is initialization actually the bottleneck?

Core Claim

Euclidean structure is useful here less for proving worst-case approximation ratios than for producing instance-specific lower bounds. Those bounds turn "method A beats method B" into "method A is within x% of optimal on this dataset." We claim three things. Random-block relaxation bounds with dual repair can be computed in near-linear total time. They are tight enough, within a few percent, on moderately separated real benchmarks to settle whether seeding improvements matter there. Where the bound stays loose, that looseness itself tracks measurable hardness, namely the separability-collapse regime identified by CHB.

Background and What Is Missing

Two lines of work handle the non-convexity of k-means through convex or near-convex reformulation.

On the tightness of an SDP relaxation of k-means proves that the semidefinite relaxation recovers the exact optimum when clusters are separated balls. A semidefinite relaxation replaces the hard cluster assignment with an $n\times n$ positive semidefinite matrix. The paper evaluates only on synthetic balls and needs $O(n^2)$ variables. Scalable Second-order Riemannian Optimization for K-means Clustering factorizes that relaxation onto a manifold and solves it with Newton-type steps, showing that every second-order critical point is global under separation. However, its log-barrier parameter needs heuristic warm-starts, and it offers no guarantee once clusters overlap.

Both works use the relaxation as a solver. We use it as a measuring instrument. That use survives exactly where their guarantees fail, because a lower bound stays valid whether or not the relaxation is tight.

The initialization literature motivates the audit. A Beyond-Worst-Case Analysis of Greedy k-means++ proves greedy seeding improves to $O((\ln\ln k)^2)$, but only on idealized synthetic regular instances. Systematically and efficiently improving k-means initialization by pairwise-nearest-neighbor smoothing introduces PNN-smoothing, which clusters random subsets and merges their centers agglomeratively. It reports that k-means++ finds the Birch1 ground truth with 0% success while PNNS(km++) reaches 100%. That result is decisive only because Birch1's optimum is essentially known. Data-Driven Clustering via Parameterized Lloyd's Families tunes the seeding exponent and reports CNAE-9 error dropping from about 0.6 to about 0.4. That figure is measured against labels, not against the k-means optimum. None of these works can say how much objective remains on the table for real data.

Two empirical-audit papers constrain the design. An Empirical Evaluation of k-Means Coresets shows that judging summaries by the final Lloyd cost conflates optimizer failure with representation error, which is the same confound we remove. CHB (code) shows that aggregate label agreement hides structural failure. It sorts datasets into regimes with median NMI of about 0.07, 0.53, and 0.70. We adopt its regimes as the stratification axis.

The theoretical Euclidean approximation results include the 5.912 k-means ratio via nested quasi-independent sets, which has no empirical evaluation. These results motivate the gap but are not usable as certificates, since a factor-5.9 guarantee says nothing useful about any single instance.

Research Program

The certifier rests on two observations.

The first observation is that block decomposition gives a valid bound. Partition the points $P$ into disjoint blocks $B_1,\dots,B_m$. The global optimal centers, applied to each block separately, cost at least that block's own optimum. Therefore $\mathrm{OPT}_k(P)\ge\sum_j \mathrm{OPT}_k(B_j)$, and any lower bound on each block's optimum sums to a lower bound on the whole.

Blocks must be random, not spatially coherent. A coherent block holding one true cluster lets $k$ centers overfit it, which makes its optimum and the sum far too small. A random block of size $b$ instead behaves like a subsample, whose optimum is roughly $(b/n)\mathrm{OPT}$ minus an overfitting term that shrinks as $b$ grows relative to $k$. The block size therefore trades tightness against cost. We will measure this trade-off empirically rather than assume it.

The second observation is that dual repair makes inexact solves valid. For each block we use the Peng–Wei relaxation: minimize $\mathrm{tr}(DZ)$, where $D$ holds squared distances, subject to $Z\mathbf 1=\mathbf 1$, $\mathrm{tr}\,Z=k$, $Z\ge 0$ elementwise, and $Z\succeq 0$. An approximate solver, such as the Riemannian method of Xu et al. or a first-order method, returns dual multipliers. These consist of $y$ for the row-sum constraints, $t$ for the trace constraint, and a nonnegative matrix $N$ for elementwise nonnegativity. Clipping $N$ to be nonnegative keeps them dual-feasible except for the semidefinite part. The slack matrix is $S = D - \tfrac12(y\mathbf 1^\top+\mathbf 1 y^\top) - tI - N$. Because $\mathrm{tr}(SZ)\ge \lambda_{\min}(S)\,\mathrm{tr}\,Z = k\,\lambda_{\min}(S)$ for any feasible $Z$, every primal-feasible point satisfies

$$ \mathrm{tr}(DZ)\;\ge\;\mathbf 1^\top y + k\,t + k\,\min\{0,\lambda_{\min}(S)\}. $$

The right-hand side is therefore a certified lower bound. It needs only one extreme-eigenvalue computation, regardless of how well the solver converged. Blocks of a few thousand points are tractable, and the number of blocks grows linearly with $n$, so USCensus's 2.4 million points become embarrassingly parallel.

The audit then runs every competitor on each benchmark and reports two quantities. The first is the certified gap, defined as (cost − bound)/bound. The second is the gap between the best-found solution and the bound, which caps how much any future initialization method could gain. We also test one practical consequence: a gap-adaptive restart rule that stops drawing new seeds once the certified gap falls below a tolerance.

Baselines

The naive reference point is the current practice of treating the best cost from many k-means++ restarts as "the optimum." We run 1,000 restarts per dataset with the same compute budget as the certifier. This baseline yields no guarantee, and Birch1 shows it can be badly wrong. The certifier beats it if it identifies datasets where best-of-1,000 is provably within 1% of optimal, which the proxy cannot claim. It also beats it if it identifies datasets where a different method finds a lower cost, so the proxy was provably not optimal.

The strongest optimizer competitor is the Riemannian second-order solver of Xu et al., the only method in the file that targets the global optimum at scale. The paper reports reaching the global optimum on synthetic GMMs in roughly 150 iterations, against over 80,000 for nonnegative low-rank factorization. The paper's summary gives no cost figure for CIFAR-10 or CyTOF. We run it with its recommended warm start and a fixed barrier-tuning budget equal to the budget given to PNNS's hyperparameters. The question is not whether we beat it as a solver. The question is whether its solutions are certifiably optimal on overlapping real data, where its theory is silent.

The strongest seeding competitors are PNNS, which reports 100% Birch1 success where k-means++ gets 0%, and greedy k-means++. Both are run through Baldassi's KMeansPNNSmoothing.jl with default settings. We also include the $(\alpha,\beta)$-Lloyds family, tuned on held-out samples as in Balcan et al.

For certified optimality gaps on any of these benchmarks, we found no reported result on Lacuna. That absence is the gap.

The key ablation removes dual repair. It reports the raw approximate dual objective, to show how often unrepaired bounds would be invalid, and it reports subsample relaxation values without the block sum. A second ablation swaps random blocks for spatially coherent ones, which the decomposition argument predicts will loosen the bound sharply.

Why not just…?

Why not just run many restarts and call the best one optimal? Restarts produce only upper bounds. On Birch1, k-means++ never found the ground truth (PNNS paper), so "best found" can be far from optimal without any sign that this is so. Our experiments report how often the certified bound shows the restart proxy to be non-optimal. If that never happens on real data, this negative result is itself informative and cheap to state.

Why not just evaluate against ground-truth labels with NMI or ARI? Labels are not the k-means optimum. A method can raise NMI while raising the objective, and CHB shows label agreement collapses for structural reasons unrelated to optimization. We report label metrics alongside certified gaps and test whether they rank methods differently. Disagreement would show that the labels-based literature measures something other than optimization quality.

Why not just solve the full relaxation on a subsample? A single subsample's relaxation value is not a bound on the full objective. It estimates a scaled quantity with unknown bias and sign. The block-sum is what makes it a bound. This alternative is a genuine threat on accuracy, though, since a subsample estimate could be close in practice. We therefore report it as a point estimate next to our bound to see whether validity costs much tightness.

Why not just rely on the separation theory of the relaxation? The exact-recovery theorem requires inter-center distance above $2 + k^2/\mathrm{Cond}(\gamma)$ for unit balls. Real data in CHB's Regime A violates any such condition. A dual certificate remains valid whatever the separation, and that is precisely why we use it.

Proposed Experiments

The first experiment is calibration on Birch1 and Birch2. Here the planted solution is essentially optimal, so the bound should close to within a small gap of the PNNS solution. Failure here would mean the block bound is too loose to be useful, and we would stop or redesign.

The second experiment is a tightness sweep. We vary block size from 500 to 5,000 points and $k$ from 10 to 100 on Pendigits, MNIST, and CIFAR-10 features. We fit how the gap shrinks with block size to choose a default. We predict that tightness degrades as $k$ grows at fixed block size, since overfitting per block scales with $k$.

The main audit computes certified gaps for k-means++, greedy k-means++, PNNS, tuned $(\alpha,\beta)$-Lloyds, and the Riemannian solver. It covers Birch1/2, Bridge, USCensus, Dermatology, Ecoli, Pendigits, Texture, Wisc, CNAE-9, MNIST, KMNIST, FMNIST, and CIFAR-10 features, with each dataset fingerprinted by CHB into its regime.

The decisive check is whether certified gaps for plain k-means++ with restarts are already small, say under 2%, in Regime C but large in Regimes A and B. If so, initialization research should target the hard regimes specifically. If gaps are small everywhere the bound is tight, much of the seeding literature is optimizing noise on real data. If gaps are large everywhere, there is real headroom and a ruler for future methods, including an eventual implementation of the nested quasi-independent-set algorithm.

Finally, the gap-adaptive restart rule is compared with fixed 50- and 1,000-restart budgets on total distance computations at equal final certified gap.