{"id":"390397cc-d5f1-433e-a599-5f4092fe9e05","arxiv_id":"2507.06226","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Under just a finite mean, empirical k-means cluster centers can fail to converge even though the population centers are unique; a minimum cluster-size constraint restores some consistency.","lead":"For k-means clustering, a classical result guarantees the cluster centers converge to a target when the data have finite variance. This paper shows that when data only have a finite average size, cluster centers can keep jumping forever, and imposing a minimum-size balance constraint can bring back convergence.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.4's proof contains a false inequality; the correct identity repairs it, but the written argument is invalid.","rationale":"The reader identified the attainment of alpha0(X) in Theorem 4.5 as the weakest assumption. That concern is real but relatively mild: if alpha < alpha0(X), the competitor can be chosen as an optimal partition W with pmin(X,W) > alpha, so the argument can be repaired without changing the theorem. My stress-test found a more concrete and more clearly load-bearing flaw elsewhere: the proof of Lemma 3.4 contains a displayed inequality that is simply false. I verified it with a one-point distribution X=1.1v, t=1. The consequent tail bound is still correct, but only after replacing the invalid step with the exact identity D = -4t E[(v^T X - t)_+]. Because Lemma 3.4 underpins the case (iii) classification and is reused in the Section 5 uniform-convergence lemma and in Lemma 5.6, the written proof needs correction before those results are fully established. This strengthens the case for the reader's CONDITIONAL verdict rather than changing it, since the theorem statements appear salvageable and the central negative Proposition 4.2 is not affected by this particular gap.","tokens_in":34570,"tokens_out":38290,"duration_ms":449544,"concrete_test":"Recompute the displayed inequality in Lemma 3.4 with X=1.1v, t=1: if D=-0.4 and the claimed bound is -4, the inequality is false. Then verify the corrected argument: D_X(C(v,t)|{0}) = -4t E[(v^T X - t)_+]; -inf D < ∞ implies E[(v^T X - t)_+] ≤ M/(4t); since (v^T X - t)_+ ≥ t 1{v^T X ≥ 2t}, one obtains P(v^T X ≥ 2t) ≤ M/(4t^2), yielding the tail bound in Lemma 3.4 after absorbing constants. Check that Lemmas 5.3 and 5.6 rely only on this corrected tail bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Lemma 3.4, direction (a)⇒(b), the paper claims that for C(v,t)={0,2tv} with ||v||=1,\nD_X(C(v,t)|{0}) = E[(||2tv||^2 - 4t v^T X) 1{||X-2tv||<||X||}] ≤ -4t^2 P(v^T X ≥ t).\nThis inequality is false. The indicator condition is v^T X > t, and on that event the integrand equals 4t^2 - 4t v^T X = -4t(v^T X - t), which is not bounded above by -4t^2. A concrete counterexample: take X=1.1v and t=1. Then P(v^T X≥1)=1, the left side equals (1.1-2)^2 - 1.1^2 = -0.4, and the claimed upper bound is -4; since -0.4 > -4, the claimed inequality fails. The correct identity is D_X(C(v,t)|{0}) = -4t E[(v^T X - t)_+]. Since -inf D = M < ∞, we get E[(v^T X - t)_+] ≤ M/(4t); using (v^T X - t)_+ ≥ t 1{v^T X ≥ 2t} yields P(v^T X ≥ 2t) ≤ M/(4t^2), which gives the desired polynomial tail bound after absorbing constants. Thus the lemma's statement appears true, but the proof as written is invalid. Lemma 3.4 is foundational: it characterizes case (iii), and it is reused in Lemma 5.3 and Lemma 5.6. The manuscript must replace the incorrect displayed inequality with the corrected argument before these structural claims can be regarded as proven.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":34890,"tokens_out":13483,"duration_ms":133119,"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":[{"comment":"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.","section":"Lemma 3.4, proof of (a)⇒(b)"},{"comment":"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.","section":"Theorem 4.5, proof"},{"comment":"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).","section":"Lemma 5.3, proof"}],"minor_comments":[{"comment":"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":"Proposition 3.1"},{"comment":"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.","section":"Section 3, introductory paragraph"},{"comment":"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.","section":"Proposition 3.5, proof"},{"comment":"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.","section":"Proposition 4.2, final display"},{"comment":"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.","section":"Lemma 5.3, proof before (5.16)"}],"recommendation":"major_revision","confidential_remarks":"The central negative result and the overall architecture of the paper are credible and novel; I see no reason to question the authors' framing or the completeness of the literature coverage. The two load-bearing gaps (Lemma 3.4's proof and Theorem 4.5's attainment assumption) are repairable within the scope of the manuscript, so I recommend major revision rather than rejection. The authors should also fix the notational slips in Proposition 3.1, Proposition 3.5, and Proposition 4.2 listed in the minor comments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — the short take: this paper maps out exactly where Pollard's k-means consistency theorem breaks down under finite expectation, and shows the failure mechanism is extreme cluster imbalance. The three-case population trichotomy, the explicit non-convergence constructions (Propositions 4.2 and 5.2), and the balance-constrained consistency theorems (4.5, 5.4, 5.5) are genuinely new. The central negative result is supported by a long, detailed proof that I found credible. This is a real contribution.\n\nWhat the paper does well: the renormalized excess distortion setup under E||X||<∞ is clean and natural; the three cases are instructive; the balance-constrained positive results give a meaningful way to recover consistency in cases (i) and (ii). The literature review is accurate, and the self-citation that appears is not loading the dice.\n\nNow the soft spots, in proportion. First: the proof of Lemma 3.4, which characterizes case (iii) and is reused in Lemmas 5.3 and 5.6, contains a false inequality. In the (a)⇒(b) direction, the paper bounds D_X(C(v,t)|{0}) above by -4t^2 P(v^T X ≥ t), but on the event {v^T X ≥ t} the integrand is -4t(v^T X - t), not bounded by -4t^2. A concrete check with X=1.1v and t=1 gives -0.4 > -4, so the bound fails. The correct identity D_X(C(v,t)|{0}) = -4t E[(v^T X - t)_+] fixes the argument and the lemma's statement appears true, but the written proof is invalid until replaced. That is a load-bearing fix.\n\nSecond, Theorem 4.5 picks an optimal Voronoi partition with pmin ≥ α0(X), but attainment of the supremum α0(X) is not shown. This is a minor gap, repairable by an approximation argument or by phrasing the competitor as pmin > α. The sign error in Proposition 3.1 looks like a typo. The abstract's \"well-posed\" claim should be qualified to cases (i) and (ii), since case (iii) is by definition ill-posed; the paper itself acknowledges this.\n\nFor whom: this is for theoretical statisticians and learning theorists working on k-means, quantization, and robust clustering. It deserves a serious referee. My own verdict would be major revision, not rejection: the main claims appear correct, but Lemma 3.4's proof must be corrected, and the minor issues above need attention.","headline":"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.","tokens_in":35503,"tokens_out":2721,"would_cite":true,"duration_ms":25628,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30","60F15","62G20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["k-means clustering","strong consistency","heavy-tailed distributions","Pareto distribution","cluster imbalance","balanced clustering","excess distortion","asymptotic statistics"],"falsifier":"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.","tokens_in":34326,"feed_emoji":"📊","tokens_out":8793,"duration_ms":85345,"temperature":0.7,"pith_summary":"The paper asks whether k-means clustering stays consistent when the population distribution has only a finite mean, not a finite variance. It shows that the population problem can still be given a meaningful definition through a renormalized excess distortion, but that the empirical cluster centers can fail to converge even when the population centers exist and are unique: for a symmetric distribution with $P(|X| \\ge t) = t^{-2}$, the population 2-means centers are $\\{-2, 2\\}$ while, infinitely often, every empirical 2-means center set has a center of magnitude at least $c \\sqrt{n}/\\log n$. The failure mechanism is extreme cluster imbalance, where a single outlying sample takes a cluster of its own. The paper then proves that imposing balance constraints on the empirical clusters, roughly linear balance for center convergence and polylogarithmic balance for distortion convergence, recovers asymptotic consistency. The payoff is a precise map of where the classical finite-variance theory of $k$-means breaks down and what a practitioner must add to restore it.","feed_headline":"K-means clustering can fail even when the target is well-defined","feed_subtitle":"A symmetric heavy-tailed distribution has unique population centers at ±2, yet empirical centers wander to ±√n.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the finite-variance strong-consistency theorem that the paper's negative results show cannot be extended to finite expectation","marker":"[31]"},{"why":"identifies cluster imbalance as the quantity controlling distortion rates and supplies techniques for analyzing balanced k-means","marker":"[24]"},{"why":"provides the centroid condition used to parameterize optimal cluster centers by Voronoi regions","marker":"[32]"},{"why":"gives the Voronoi boundary and centroid facts used throughout the population-level analysis","marker":"[20]"},{"why":"supplies the distortion-continuity lemma that Lemma 4.4 extends from W2 to W1 convergence","marker":"[21]"},{"why":"bounds the VC dimension of intersections of halfspaces, used in the uniform-convergence argument of Lemma 5.3","marker":"[6]"},{"why":"provides the uniform convergence theorem for VC classes used in Lemma 5.3 and Proposition 3.5","marker":"[7]"}],"fun_headline_variants":["K-means can fail even with unique population centers","Infinite variance breaks k-means consistency despite finite mean","Heavy-tailed outliers make k-means clusters imbalanced and inconsistent","K-means centers wander to sqrt(n) when clusters get too few points","Balancing clusters restores k-means consistency under finite expectation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["K-means can fail even with unique population centers","Infinite variance breaks k-means consistency despite finite mean","Heavy-tailed outliers make k-means clusters imbalanced and inconsistent","K-means centers wander to sqrt(n) when clusters get too few points","Balancing clusters restores k-means consistency under finite expectation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000238,"raw_usage":{"total_tokens":1550,"prompt_tokens":1022,"completion_tokens":528,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":638,"completion_tokens_details":{"reasoning_tokens":441}},"tokens_in":638,"tokens_out":528,"duration_ms":5522,"temperature":1.0,"reasoning_tokens":441,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:10:15.907483+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the finite-variance strong-consistency theorem that the paper's negative results show cannot be extended to finite expectation"},{"cited_title":"Klochkov, A","cited_arxiv_id":null,"evidence_quote":"identifies cluster imbalance as the quantity controlling distortion rates and supplies techniques for analyzing balanced k-means"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the centroid condition used to parameterize optimal cluster centers by Voronoi regions"},{"cited_title":"Graf and H","cited_arxiv_id":null,"evidence_quote":"gives the Voronoi boundary and centroid facts used throughout the population-level analysis"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the distortion-continuity lemma that Lemma 4.4 extends from W2 to W1 convergence"},{"cited_title":"Blumer, A","cited_arxiv_id":null,"evidence_quote":"bounds the VC dimension of intersections of halfspaces, used in the uniform-convergence argument of Lemma 5.3"},{"cited_title":"Boucheron, O","cited_arxiv_id":null,"evidence_quote":"provides the uniform convergence theorem for VC classes used in Lemma 5.3 and Proposition 3.5"}],"review_version":1}