Failure Modes in Clustering Consistency

When Small Distortion Does Not Guarantee Stability

For a fixed number of clusters, consistency arguments often aim to show that empirical centers approach population-optimal centers, and that the partitions they induce approach a population-optimal partition. These conclusions require more than a small difference in distortion. The objective may not distinguish relabelled centers, may not penalize an unused center, may be infinite, or may assign negligible mass to a cluster. In each case, a plausible-looking convergence claim can fail or become uninformative.

We use squared Euclidean distortion to make the failure mechanisms explicit. Let $X$ take values in $\mathbb{R}^d$, and let an ordered $K$-center codebook be $c=(c_1,\ldots,c_K)$. Its population risk is the expected squared distance to the nearest center. A partition assigns each point to a nearest center, with ties resolved by choosing the smallest index. The examples below distinguish convergence of the risk, the ordered centers, the unordered codebook, and the induced partition.

R(c)=E\!\left[\min_{1\leq j\leq K}\|X-c_j\|^2\right], \qquad \widehat R_n(c)=\frac{1}{n}\sum_{i=1}^{n}\min_{1\leq j\leq K}\|X_i-c_j\|^2.

When the risks are finite, a population-optimal codebook minimizes $R(c)$. An empirical-optimal codebook minimizes $\widehat R_n(c)$. The partition cell for center $c_j$ contains points assigned to index $j$. For two partitions $A=(A_1,\ldots,A_K)$ and $B=(B_1,\ldots,B_K)$, one natural measure of disagreement is $P\{g_A(X)\ne g_B(X)\}$, where $g_A$ and $g_B$ are their label assignments. This measure depends on the labels: swapping two labels changes the assignments even if the geometric cells are unchanged.

Failure Mode 1: Nonidentifiability and Label Switching

A codebook is often represented as an ordered tuple, but the nearest-center objective does not depend on the order of its entries. Thus even a unique optimal unordered set can correspond to several ordered minimizers. A convergence assertion for ordered tuples must either impose a consistent labeling or compare codebooks modulo permutations.

Definition: For codebooks $c,c'\in(\mathbb{R}^d)^K$, their permutation-invariant distance is $$ d_{\mathrm{perm}}(c,c')=\min_{\pi}\max_{1\leq j\leq K}\|c_j-c'_{\pi(j)}\|, $$ where the minimum is over all permutations $\pi$ of $\{1,\ldots,K\}$. This distance compares the centers without treating a change of labels as a change in the geometric codebook.

Worked Example: Two Optimal Codebooks With Opposite Labels

Let $P(X=-1)=P(X=1)=1/2$ and take $K=2$. The codebook $c=(-1,1)$ has risk $$ R(c)=\frac12\min\{(-1+1)^2,(-1-1)^2\} +\frac12\min\{(1+1)^2,(1-1)^2\}=0. $$ Risk is nonnegative, so this is optimal. The codebook $c'=(1,-1)$ also has risk zero, since it contains exactly the same two centers.

Under the stated smallest-index tie rule, no ties occur here. For $c$, the point $-1$ has label 1 and $1$ has label 2. For $c'$, the labels are reversed. The ordered tuples remain a positive distance apart: $$ \max\{|{-1}-1|,\ |1-(-1)|\}=2, $$ whereas $d_{\mathrm{perm}}(c,c')=0$. Consequently, convergence to one fixed ordered tuple is not a label-invariant claim. The unordered codebook does not have this failure.

Result: For every codebook $c$ and every permutation $\pi$, $R(c_1,\ldots,c_K)=R(c_{\pi(1)},\ldots,c_{\pi(K)})$. This invariance also holds for $\widehat R_n$.

Proof. For any fixed $x$, permuting the entries of a finite list leaves its minimum unchanged: $$ \min_j\|x-c_j\|^2=\min_j\|x-c_{\pi(j)}\|^2. $$ Taking expectations gives the population identity whenever the expectation is defined; applying the same equality to each observation and averaging gives the empirical identity. $\square$

Partition statements need the same care. Geometric cells can be identical up to relabeling even when the label function differs everywhere except on a tie set. A claim about label disagreement must specify how labels are aligned; otherwise it can report a discrepancy caused only by naming conventions.

Failure Mode 2: An Unused Center Can Escape

A bounded objective does not automatically keep every center in a bounded region. If the distribution places no mass in a center's cell, moving that center may have no effect on risk. This is a failure of control of the codebook, not an optimization error.

Worked Example: An Exactly Optimal Center at Any Distance

Let $P(X=0)=1$ and $K=2$. For each real $M$, consider $c_M=(0,M)$. Since $X=0$ is exactly at the first center, $$ R(c_M)=E[\min\{X^2,(X-M)^2\}]=\min\{0,M^2\}=0. $$ This is the minimum possible risk. In particular, choosing $M_n=n$ gives a sequence of exactly optimal codebooks whose second center diverges.

The same calculation holds for every empirical sample drawn from this distribution: all observations equal zero, so $\widehat R_n(c_M)=0$ for every $M$. No assertion that every empirical minimizer has bounded centers, or converges to a fixed two-center tuple, can follow from risk optimality alone. The second center is unused and is not identified by the data or the objective.

This example also shows why a convention for breaking ties does not solve every identification problem. It determines how a point equidistant from centers is labelled, but it cannot make a center that receives no probability mass identifiable. Conditions such as a unique optimal codebook, or restrictions ensuring each center serves a sufficiently substantial region, address different issues and must not be conflated.

Failure Mode 3: Infinite Second Moments

For squared distortion, finite second moments are important because they ensure finite risk for fixed finite centers and support risk comparisons. If second moments are infinite, the population objective may be infinite for every candidate, so minimizing it does not define a useful finite-risk target. A finite empirical objective cannot repair that defect in the population criterion.

Worked Example: Every Finite Codebook Has Infinite Risk

Let $X$ have a symmetric density on the real line given by $$ f(x)=\frac{3}{4}|x|^{-5/2}\mathbf{1}\{|x|\geq 1\}. $$ It is a probability density: the integral on each tail is $$ \int_1^\infty \frac{3}{4}x^{-5/2}\,dx =\frac{3}{4}\cdot\frac{2}{3}=\frac12. $$ Its second moment is infinite, since $$ E[X^2]=2\int_1^\infty x^2\frac{3}{4}x^{-5/2}\,dx =\frac32\int_1^\infty x^{-1/2}\,dx=\infty. $$

Now fix any finite codebook $c_1,\ldots,c_K$, and put $M=\max_j|c_j|$. If $|x|\geq 2M$, then for every $j$, $$ |x-c_j|\geq |x|-|c_j|\geq |x|/2. $$ Therefore the squared distance to the nearest center is at least $x^2/4$ on that tail. The tail still has infinite second moment, so $R(c)=\infty$ for every finite codebook. The population squared-risk minimization problem cannot distinguish candidates by finite risk. A theorem based on finite population risks or finite excess distortion cannot be applied to this distribution.

The point is not that infinite moments must always make every form of clustering impossible. Rather, conclusions derived from finite squared-risk arguments need their moment hypotheses. One must not treat an empirical average of finite numbers as evidence that the corresponding population expectation is finite.

Failure Mode 4: Vanishing Cluster Mass

Even when every distribution in a sequence has finite support and finite risk, a cluster whose mass tends to zero can have vanishing influence on the objective. The resulting distortion difference may approach zero while an associated center moves arbitrarily far from its population-optimal location. This is a direct obstruction to deriving center convergence from excess-risk convergence uniformly over such distributions.

Worked Example: Vanishing Excess Risk With a Diverging Center

For each $n$, let $$ P_n(X=0)=1-\varepsilon_n,\qquad P_n(X=1)=\varepsilon_n, \qquad \varepsilon_n=\frac{1}{n+1}, $$ and take $K=2$. The codebook $c^*=(0,1)$ has risk zero and is optimal. Consider instead $c_n=(0,n+3)$. For $X=0$, its nearest-center squared distance is zero. For $X=1$, the distances squared are $1$ and $(n+2)^2$, so the nearest squared distance is $1$. Hence $$ R_{P_n}(c_n)=(1-\varepsilon_n)0+\varepsilon_n(1) =\frac{1}{n+1}. $$ The excess risk tends to zero, but the distance from the distant center to the optimal center at 1 is $n+2$, which diverges.

Thus a sequence of near-minimizers need not approach the optimal codebook when the minimum cluster mass is allowed to vanish. For each $n$, the point at 1 has positive mass and can be served at zero distortion by $c^*$; in the alternative codebook, the distortion cost for that point is only $\varepsilon_n$. As the mass decreases, that cost becomes too small to control the center location.

Takeaway: Excess risk controls center error only when the assumptions linking risk to center displacement remain effective. A lower bound on relevant cluster masses can be part of those assumptions; without it, a center devoted to a rare component may move substantially at negligible risk cost.

Risk Convergence and Partition Convergence Are Different

A partition can be close in probability under the full distribution and still be unstable on a rare component. For example, in the preceding mixture, the entire component at 1 has probability $\varepsilon_n$. Changing its assignment changes the disagreement probability by at most $\varepsilon_n$, which tends to zero. The global partition error can therefore be small even if the assignment on that component changes completely.

This is not a contradiction: probability-weighted disagreement deliberately gives little weight to events of little probability. But it means that small global partition error does not establish accurate classification within a rare cluster. If the scientific goal is to preserve that cluster, a conditional or component-specific criterion is needed in addition to global disagreement.

There is another distinction between boundary behavior and low cluster mass. When a point is near a Voronoi boundary, a small movement of a center may change its assignment. Even if the centers converge, partition convergence requires control of how much probability lies near those boundaries. That issue is different from a cell having negligible mass: boundary mass concerns points whose labels are sensitive to small perturbations, while vanishing cluster mass concerns how little the objective weighs an entire cluster. Neither issue is fixed merely by proving that distortion converges.

Common Mistakes

Wrong reasoning: “The risk has a unique geometric minimizer, so the ordered centers must converge in their stated order.” Correction: The objective is permutation-invariant. Align labels or formulate convergence using a permutation-invariant distance.
Wrong reasoning: “The risk is bounded, so every center in an empirical minimizer is bounded.” Correction: An unused center can move without changing risk. Bounded objective values do not imply bounded codebooks.
Wrong reasoning: “Every observed squared distance is finite, so the population squared risk is finite.” Correction: Finite sample values do not imply a finite expectation. Check the moment assumptions for the population distribution.
Wrong reasoning: “Excess risk tending to zero forces all centers to converge, even if a cluster has tiny mass.” Correction: The vanishing-mass example has excess risk tending to zero while a center diverges. Uniform center control needs assumptions that rule out this mechanism.
Wrong reasoning: “Small disagreement probability means every cluster assignment is stable.” Correction: A complete change on a rare component can contribute very little to global disagreement. State which error criterion matches the intended goal.

Before applying a consistency conclusion, check what object is meant to converge and under what metric. Then verify that the population risk is finite, that the target is identifiable under the chosen labeling convention, and that no center can escape at negligible cost. For partition claims, also check whether the chosen error measure can detect changes in the clusters that matter scientifically.

Check Your Understanding

Use the examples and distinctions above to assess each claim.

Why do the codebooks $(-1,1)$ and $(1,-1)$ have zero permutation-invariant distance but differ as ordered tuples?
For $P(X=0)=1$ and $K=2$, calculate the risk of $(0,M)$. What does this show about boundedness of empirical minimizers?
In the heavy-tailed density example, why is the risk infinite for every finite codebook, not just for the codebook containing zero?
For the mixture with mass $\varepsilon_n$ at 1, calculate the risk of $(0,n+3)$ and explain why it tends to the optimal risk while a center diverges.
How can partition disagreement tend to zero while assignments on a rare component remain completely unstable?