REVIEW 3 major objections 5 minor
Consistency and inconsistency in $k$-means clustering
T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read K-means clustering can fail to converge even when the population cluster centers exist and are unique, and cluster imbalance is the cause; the paper shows balance constraints restore consistency.
desk verdict The paper identifies the exact boundary of Pollard consistency under finite expectation and shows cluster imbalance is the culprit; the main claims look correct, but the written proof of Lemma 3.4 has a false inequality that must be fixed. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the renormalized excess distortion $D_X(C \mid C') = E[\min_{c \in C} \|c-X\|^2 - \min_{c' \in C'} \|c'-X\|^2]$, which is finite whenever $E\|X\| < \infty$ because the two squared-distance terms cancel in the tails. The paper works with Voronoi partitions of the data and their $\gamma$-balanced versions, where every cluster must contain at least $\gamma$ sample points, and with the quantity $p_{\min}(X, \mathcal V)$ giving the smallest probability of any region in a population Voronoi partition. The key mechanism is the tail condition of Lemma 3.4: the population excess distortion is bounded below exactly when $\|X\|$ is stochastically dominated by a scalar multiple of a $\mathrm{Par}(2)$ variable, and the negative results show that this condition is not enough for empirical stability because a single large sample can dominate a cluster.
What would settle it
Simulate i.i.d. samples from the symmetric distribution with $P(|X| \ge t) = t^{-2}$ and compute exact 2-means centers up to large $n$; Proposition 4.2 predicts that the event $\max(\bar C_n) \ge c \sqrt n / \log n$ or $\min(\bar C_n) \le -c \sqrt n / \log n$ recurs infinitely often, so observing both centers stay bounded for all large $n$ would falsify the claim. A second check: for a distribution where the optimal population partitions have $p_{\min}$ values approaching $\alpha_0(X)$ without attaining it, test whether $\alpha < \alpha_0(X)$ still yields the convergence of Theorem 4.5.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that the classical strong-consistency theorem for $k$-means under finite variance does not extend to the finite-expectation regime, and that the obstruction is a precise, identifiable phenomenon. With $E|X| < \infty$ but $E|X|^2 = \infty$, the population problem is still well-posed after subtracting $\|X\|^2$ inside the expectation, and the distribution $X$ symmetric with $P(|X| \ge t) = t^{-2}$ has the unique population 2-means center set $\{-2, 2\}$. Nevertheless, almost surely for infinitely many $n$, every empirical 2-means center set has $\max(\bar C_n) \ge c \sqrt{n} / \log n$ or $\min(\bar C_n) \le -c \sqrt{n} / \log n$, so the empirical centers do not converge in Hausdorff distance. The paper isolates the cause: heavy-tailed outliers make some empirical cluster nearly empty, so the empirical optimum places a center on the outlier. It then shows that requiring each empirical cluster to contain at least $\gamma_n$ points restores consistency, with $\gamma_n = \alpha n$ for a well-specified $0 < \alpha < 1$ giving Hausdorff convergence of centers and $\gamma_n \ge (\log n)^4$ giving almost-sure convergence of the excess distortion.
Load-bearing premise
The center-convergence result depends on choosing the balance fraction $\alpha$ strictly below $\alpha_0(X)$, the largest minimum-cluster probability over Voronoi partitions of optimal population centers; $\alpha_0(X)$ is distribution-dependent, unknown in practice, and the proof implicitly assumes that some optimal partition attains this supremum instead of merely approaching it.
Editorial extensions
If this is right
- If the claims are correct, the classical finite-variance strong-consistency theorem for $k$-means cannot be extended to $E\|X\| < \infty$ in any direct way; the finite-variance assumption is not merely technical.
- A linear balance constraint $\gamma_n = \alpha n$ with a well-specified $\alpha$ restores almost-sure Hausdorff convergence of empirical centers to the unconstrained population centers.
- A polylogarithmic balance constraint $\gamma_n \ge (\log n)^4$ restores almost-sure convergence of the excess distortion, and $\gamma_n \gg (\log n)^2$ restores convergence in probability.
- Under the same polylog balance, the bounded part of the empirical centers converges to a set of population $k'$-means centers for some $1 \le k' \le k$, while the remaining centers diverge.
- The paper's three-way classification of population problems (solution exists; finite infimum without a solution; infinite infimum) provides a complete map of what can even be asked for under finite expectation.
Reading between the lines
- A natural extension we would draw is that the sharp balance rate is probably problem-dependent: the proof of Theorem 5.4 already lowers the almost-sure rate to $(\log n)^3 (\log\log n)^2$, and calibrating $\gamma_n$ to the actual tail index of $X$ may yield tighter thresholds.
- The cluster-imbalance mechanism suggests that practitioners running $k$-means on data with unbounded second moments should treat any cluster containing very few samples as statistically unreliable; a simple testable extension is to compare ordinary $k$-means with a trimmed or $\gamma$-balanced variant on heavy-tailed benchmarks and check whether the balanced variant's centers track the population
- The renormalized excess distortion is essentially the quantization version of the Fréchet-mean renormalization trick, so the same three-case taxonomy likely governs other least-squares-type estimators under a first moment.
- An open direction implicit in the paper is whether the well-specification of $\alpha$ in Theorem 4.5 can be removed by a data-dependent choice, since $\alpha_0(X)$ is not estimable without knowing the optimal population partitions.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies k-means clustering under the minimal moment assumption E||X||<∞, using a renormalized excess distortion functional. It classifies the population-level problem into three regimes: (i) an optimal center set exists, (ii) the optimal excess distortion is finite but no center set attains it, and (iii) the optimal excess distortion is infinite. The central negative result is Proposition 4.2, which shows that for a symmetric two-sided Par(2) distribution, the unique population 2-means center set is {-2,2}, yet the empirical 2-means centers are, infinitely often, at distance at least c√n/log n from it, so the natural extension of Pollard's strong consistency fails. The paper then proves positive results: a linear balance constraint γ_n=αn recovers Hausdorff consistency (Theorem 4.5), and a polylogarithmic balance constraint recovers consistency of the excess distortion (Theorem 5.4), with a unified partial-convergence statement (Theorem 5.5).
Significance. If the proofs are made fully rigorous, this is a substantial contribution to the asymptotic theory of k-means clustering. It answers a natural question left open by Pollard's theorem, shows that finite expectation is not sufficient for consistency in general, and identifies extreme cluster imbalance as the mechanism of failure. The renormalized excess-distortion framework for E||X||<∞ is natural and the three-case taxonomy is illuminating. The paper's negative result (Proposition 4.2) is supported by a long, detailed event-based proof that appears credible, and the positive balance-constrained results give a concrete remedy, at the cost of a well-specification assumption in Theorem 4.5. The paper does not rely on fitted parameters or circular normalizations; the counterexamples are fully specified. However, two load-bearing proof gaps must be repaired before the claims can be considered established: the proof of Lemma 3.4 contains a false inequality, and the proof of Theorem 4.5 silently assumes that a certain supremum is attained.
major comments (3)
- [Lemma 3.4, proof of (a)⇒(b)] The displayed inequality D_X(C(v,t)|{0}) ≤ −4t² P(vᵀX ≥ t) is false. On the event {vᵀX > t}, the integrand equals 4t(t − vᵀX), which is not bounded above by −4t²; for example, X=1.1v and t=1 give left side −0.4 and claimed upper bound −4. The correct identity is D_X(C(v,t)|{0}) = −4t E[(vᵀX − t)_+], and combining this with M = −inf D < ∞ yields P(vᵀX ≥ 2t) ≤ M/(4t²), which gives the desired polynomial tail bound after absorbing constants. This lemma is foundational: it is reused in Lemma 5.3 and Lemma 5.6. The statement appears salvageable, but the written proof must be replaced.
- [Theorem 4.5, proof] The proof assumes that the supremum α0(X) is attained: it selects a Voronoi partition V′ with pmin(X,V′) ≥ α0(X). If the supremum is not attained, no such partition exists and the displayed comparison between D_X(V) and D_X(V′) is empty. This matters because the conclusion C ∈ C_k(X) relies on comparing with a partition at the boundary of the feasible set. The argument is repairable: for any ε>0, choose an optimal partition V′_ε with pmin(X,V′_ε) > α0(X)−ε; since α<α0(X), for small ε this partition is αn-balanced eventually, and the same chain gives D_X(V) ≤ D_X(V′_ε) = inf_{C∈C_k} D_X(C|C0). This approximation step should be stated explicitly. The final appeal to Lemma 2.8 also needs this boundary argument, since Lemma 2.8 alone does not allow restricting to partitions with pmin ≥ α0.
- [Lemma 5.3, proof] Lemma 5.3 relies directly on Lemma 3.4 to obtain the tail bound P(∥X∥ ≥ t) ≤ r t^{−2}, so the false inequality in the proof of Lemma 3.4 currently leaves Lemma 5.3 without a valid derivation. Since Lemma 5.3 is the technical engine for Theorems 5.4 and 5.5, the correction of Lemma 3.4 must be carried through this proof as well. I found no independent obstacle in Lemma 5.3 beyond this dependency, but the authors should verify the corrected constants propagate correctly through equations (5.6)–(5.17).
minor comments (5)
- [Proposition 3.1] In the r>1 case, the formula for min(C(r)) is missing a minus sign: for a symmetric distribution with support on |x|≥1, E[X|X<r] is negative, so the left center should be −r^{−1}/(1 − (1/2)r^{−2}), not r^{−1}/(1 − (1/2)r^{−2}). Since only the squared center values enter D(r), this typo does not affect the conclusion, but it should be corrected.
- [Section 3, introductory paragraph] The text says the examples take place in 'the simplest possible setting of m = 1 and k = 2'; the dimension variable is denoted d throughout the paper, so this should read d = 1.
- [Proposition 3.5, proof] The statement defines the threshold sequence β_n, but the proof says 'use log n = o(γ_n)' and 'γ_n ≥ c_1 d log n'; these occurrences should refer to β_n.
- [Proposition 4.2, final display] The notation C_{n,2}(X) in the consequence line is undefined; it should be C_2(X), the set of population 2-means center sets.
- [Lemma 5.3, proof before (5.16)] The displayed bound |¯µ_n(V) − µ_X(V)| ≤ 4c_1√n µ_X(V)√¯µ_n(V) appears to have a missing denominator n; as written it is incompatible with the uniform-convergence bound (5.6) and would grow with n. Please check this display and the surrounding derivation.
Circularity Check
No circularity: the central claims are explicit counterexamples and proofs from stated assumptions; the flagged Lemma 3.4 inequality and alpha0 attainment are correctness gaps, not circular dependencies.
full rationale
Walking the derivation chain, every load-bearing step is proved in the paper rather than imported from its own conclusions. Proposition 4.2 and Proposition 5.2 are fully specified counterexamples built from Par(2) samples; their conclusions (failure of Hausdorff convergence and of excess-distortion convergence) are not built into a fitted parameter or a renormalized coordinate system. The positive results (Theorem 4.5, Theorem 5.4, Theorem 5.5) are derived from the stated E||X|| < infinity assumption and balance constraints, with the uniform-convergence work done in Lemma 5.3 and the deterministic approximation in Lemma 5.6. Self-citations [5], [21], [22], [24] are used for standard inequalities, context, or a Skorokhod detail; the technically load-bearing continuity claim is reproved in Lemma 4.4, and Lemma 2.1 is stated as elementary with the renormalization sources used only as explanations. Thus no argument reduces to a self-citation chain. Two mathematical gaps are present but are not circularity: in Lemma 3.4, the proof claims DX({0,2tv}|{0}) <= -4t^2 P(v^T X >= t), which is false (e.g., X=1.1v, t=1 gives -0.4 > -4); the lemma is repairable via the identity -4t E[(v^T X - t)_+]. In Theorem 4.5, the proof chooses V' with pmin(X,V') >= alpha0(X), implicitly assuming the supremum is attained; if not, an approximation argument is needed. Neither issue makes a prediction equal to its input by construction.
Assumptions & free parameters
free parameters (2)
- balance fraction alpha =
0 < alpha < alpha0(X), distribution-dependent and unknown
- balance threshold rate gamma_n =
gamma_n >= (log n)^4 for the a.s. distortion result
assumptions (5)
- standard math Kolmogorov SLLN and Pollard finite-variance strong consistency
- standard math Renormalized excess distortion is finite under E||X|| < infinity (Lemma 2.1)
- domain assumption X has a density with respect to Lebesgue measure in Theorem 4.5
- domain assumption Tail domination by a scalar multiple of Par(2) (Lemma 3.4) where used
- standard math VC dimension bound for intersections of k halfspaces (Blumer et al. 1989) and uniform convergence (Boucheron et al. 2005)
Cite this review
Pith. "Pith review of Consistency and inconsistency in $k$-means clustering." pith.science (2026). https://pith.science/paper/6LZNJ4IW
@misc{pith2026250706226,
author = {Pith},
title = {Pith review of: Consistency and inconsistency in $k$-means clustering},
year = {2026},
howpublished = {\url{https://pith.science/paper/6LZNJ4IW}},
note = {Machine review of arXiv:2507.06226}
}
abstract
A celebrated result of Pollard proves asymptotic consistency for $k$-means clustering when the population distribution has finite variance. In this work, we point out that the population-level $k$-means clustering problem is, in fact, well-posed under the weaker assumption of a finite expectation, and we investigate whether some form of asymptotic consistency holds in this setting. As we illustrate in a variety of negative results, the complete story is quite subtle; for example, the empirical $k$-means cluster centers may fail to converge even if there exists a unique set of population $k$-means cluster centers. A detailed analysis of our negative results reveals that inconsistency arises because of an extreme form of cluster imbalance, whereby the presence of outlying samples leads to some empirical $k$-means clusters possessing very few points. We then give a collection of positive results which show that some forms of asymptotic consistency, under only the assumption of finite expectation, may be recovered by imposing some a priori degree of balance among the empirical $k$-means clusters.
Figures
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.