Diagnosing Partition Convergence With Boundary Mass

Why Center Convergence Needs a Boundary Check

A codebook records the locations of cluster centers; a partition records which center receives each observation. If estimated centers converge to their target locations, it is tempting to conclude that the resulting assignments converge as well. That conclusion needs a qualification: an observation close to a Voronoi boundary can change its assigned center after a very small movement of the codebook.

The relevant diagnostic is the probability mass near the boundaries of the target partition. When that mass shrinks to zero as the neighborhood narrows, small center errors cannot affect much probability. When a boundary itself carries positive probability, even vanishing center errors can switch the assignments of a nonvanishing fraction of observations.

Assignments and the Boundary Gap

Let \(c=(c_1,\ldots,c_k)\) be a codebook of \(k\geq 2\) distinct centers in Euclidean space, and let \(X\) have distribution \(P\). For squared-Euclidean quantization, write \(q_j(x;c)=\|x-c_j\|^2\). Define \(a_c(x)\) to be the index of a nearest center, resolving ties by choosing the smallest index. This fixed rule makes the assignment well-defined even on boundaries.

At each \(x\), sort the \(k\) squared distances from smallest to largest, counting ties, and let \(\Delta_c(x)\) be the second-smallest distance minus the smallest. Thus \(\Delta_c(x)=0\) exactly when the nearest center is tied. These points form the Voronoi boundary of the partition, including any boundary points with more than two tied centers. The quantity \(P\{\Delta_c(X)\leq t\}\) measures the probability mass within distance-gap \(t\) of that boundary.

Definition: For two ordered codebooks \(c\) and \(d\), their assignment disagreement probability under \(P\) is \(R(c,d)=P\{a_c(X)\ne a_d(X)\}\). Codebooks are compared in the same label order; if labels are identifiable only up to permutation, first align them. Boundary mass at the target codebook means \(P\{\Delta_c(X)=0\}\).

The distance gap is not itself a Euclidean distance to the boundary, but it is the quantity that directly controls whether the nearest-center identity can change. This makes it useful even when the distribution is discrete or has no density.

Worked Example: A Boundary Atom Causes Persistent Disagreement

Let \(P(X=1)=0.4\) and \(P(X=-1)=0.6\), and take the target codebook \(c=(0,2)\). The Voronoi boundary is the midpoint \(x=1\). At \(x=1\), both squared distances equal \(1\), and the tie rule assigns the observation to center 1. At \(x=-1\), the squared distances are \(1\) and \(9\), so the assignment is also to center 1.

Now take \(d_\varepsilon=(0,2-\varepsilon)\), where \(0<\varepsilon<1\). The codebook error is \(\max_j|d_{\varepsilon,j}-c_j|=\varepsilon\), which tends to zero. At \(x=1\), however, the distances under \(d_\varepsilon\) are \(1\) and \((1-\varepsilon)^2\). Since \((1-\varepsilon)^2<1\), this point is assigned to center 2. At \(x=-1\), the distances are \(1\) and \((3-\varepsilon)^2>1\), so its assignment does not change.

Consequently, \(R(c,d_\varepsilon)=P(X=1)=0.4\) for every such \(\varepsilon\). The target boundary has mass \(0.4\), so the assignment error does not vanish even though the centers converge.

A Perturbation Bound

The next result gives a direct link between center error and probability mass near the boundary. Suppose \(X\) is supported in the ball \(\{x:\|x\|\leq R\}\), and all centers in the target codebook satisfy \(\|c_j\|\leq M\). If \(\max_j\|d_j-c_j\|\leq\varepsilon\), then

R(c,d)\ \leq\ P\!\left\{\Delta_c(X)\leq 2\varepsilon\bigl(2(R+M)+\varepsilon\bigr)\right\}.

Theorem: Under the support and center bounds just stated, the displayed inequality holds for every codebook \(d\) whose corresponding centers are within \(\varepsilon\) of those of \(c\).

Proof. For each center \(j\), the change in its squared distance at \(x\) is bounded by

|q_j(x;d)-q_j(x;c)| \leq \|d_j-c_j\|\bigl(2\|x-c_j\|+\|d_j-c_j\|\bigr) \leq \varepsilon\bigl(2(R+M)+\varepsilon\bigr)=\eta.

The first inequality follows by writing the difference of squared norms as an inner product and applying the Cauchy–Schwarz inequality. The second uses \(\|x-c_j\|\leq\|x\|+\|c_j\|\leq R+M\).

Fix an \(x\) for which \(\Delta_c(x)>2\eta\), and let \(j\) be its unique nearest center under \(c\). Every competing center \(l\) has \(q_l(x;c)-q_j(x;c)\geq\Delta_c(x)>2\eta\). The perturbation bound gives

q_l(x;d)-q_j(x;d) \geq q_l(x;c)-q_j(x;c)-2\eta>0.

Thus \(j\) remains the unique nearest center under \(d\). Disagreement is possible only when \(\Delta_c(x)\leq2\eta\); taking probabilities proves the result. \(\square\)

When Convergence Implies Assignment Convergence

The perturbation bound yields a useful sufficient condition. If the target boundary has zero probability mass, then \(P\{\Delta_c(X)\leq t\}\) tends to zero as \(t\) decreases to zero. Indeed, the events \(\{\Delta_c(X)\leq t\}\) decrease to \(\{\Delta_c(X)=0\}\), and continuity of probability for decreasing events gives the claim.

Corollary: If \(X\) has bounded support, the target centers are fixed, and a deterministic sequence \(c_n\) satisfies \(\max_j\|c_{n,j}-c_j\|\to0\), then \(P\{a_{c_n}(X)\ne a_c(X)\}\to0\) whenever \(P\{\Delta_c(X)=0\}=0\).

Justification. Apply the theorem with \(\varepsilon_n=\max_j\|c_{n,j}-c_j\|\). Its threshold \(2\varepsilon_n(2(R+M)+\varepsilon_n)\) tends to zero. The boundary-neighborhood probabilities therefore tend to the boundary mass, which is zero. The theorem bounds the disagreement probability by those probabilities, so the disagreement tends to zero. \(\square\)

The same reasoning applies when the estimated codebook is random and converges in probability to \(c\). On the event that its center error is at most a fixed \(\varepsilon\), the theorem bounds its conditional disagreement probability by the boundary-neighborhood mass at the corresponding threshold; the complementary event has probability tending to zero as the codebook error vanishes. If the target boundary has zero mass, first choose \(\varepsilon\) small enough to make the neighborhood mass small, then use convergence in probability to make the complementary event small. This gives convergence in probability of the conditional disagreement probability.

Worked Example: Uniform Data Give Linear Boundary-Mass Decay

Let \(X\) be uniform on \([-2,2]\), with target centers \(c=(-1,1)\). The boundary is \(0\). For \(x\geq0\), the second center is nearest, and for \(x<0\), the first is nearest. The difference between the two squared distances in absolute value is

\left|(x+1)^2-(x-1)^2\right|=4|x|.

Thus \(\Delta_c(x)=4|x|\), and for \(0\leq t\leq4\),

P\{\Delta_c(X)\leq t\} =P\{|X|\leq t/4\} =\frac{t/2}{4} =\frac{t}{8}.

Now move the second center from \(1\) to \(1+\varepsilon\), with \(0<\varepsilon<2\). The new boundary is the midpoint \(\varepsilon/2\). Assignments differ exactly for \(0<x<\varepsilon/2\), apart from endpoints of probability zero. Therefore

R\bigl((-1,1),(-1,1+\varepsilon)\bigr) =P(0<X<\varepsilon/2) =\frac{\varepsilon/2}{4} =\frac{\varepsilon}{8}.

Here the disagreement vanishes linearly with the center displacement. The boundary has zero mass, and the explicit calculation shows how quickly nearby mass accumulates.

Zero Boundary Mass Does Not Specify a Rate

A continuous distribution can have zero probability on the boundary yet place much more mass near it than a distribution with a bounded density. The boundary-mass criterion guarantees convergence, not a particular rate. The next calculation illustrates why the neighborhood probabilities should be evaluated rather than assumed to be linear in their width.

Worked Example: An Integrable Density Gives Slower Decay

Let \(X\) have density \(f(x)=1/(4\sqrt{|x|})\) for \(0<|x|\leq1\), and density zero elsewhere. This is a probability density because

\int_{-1}^{1}\frac{1}{4\sqrt{|x|}}\,dx =\frac{1}{4}\left(2\int_0^1x^{-1/2}\,dx\right) =\frac{1}{4}(2\cdot2)=1.

Use the target centers \((-1,1)\) and perturb them to \((-1,1+\varepsilon)\), with \(0<\varepsilon<2\). As in the uniform example, the assignments differ on \(0<X<\varepsilon/2\). The target boundary has zero probability because \(X\) has a density, but the disagreement probability is

R\bigl((-1,1),(-1,1+\varepsilon)\bigr) =\int_0^{\varepsilon/2}\frac{1}{4\sqrt{x}}\,dx =\frac{1}{2}\sqrt{\frac{\varepsilon}{2}} =\frac{\sqrt{\varepsilon}}{2\sqrt{2}}.

This tends to zero, as the zero-boundary-mass condition predicts, but at order \(\sqrt{\varepsilon}\), not order \(\varepsilon\). The density is integrable but unbounded near the boundary, so the probability accumulated in a short interval is comparatively large.

How to Diagnose a Convergence Claim

For a proposed codebook-convergence argument, the central question is not merely whether the limiting Voronoi boundary is geometrically small. It is whether the data distribution places little probability near that boundary. A geometric boundary can have zero volume and still carry positive probability under a discrete distribution. Conversely, an absolutely continuous distribution assigns zero mass to a hyperplane boundary, but its mass in narrow neighborhoods can still shrink slowly.

Fix the target partition.
Specify the limiting codebook, the label alignment, and the tie-breaking rule.

Measure the nearest-center gap.
Evaluate or bound \(P\{\Delta_c(X)\leq t\}\) for small \(t\). This includes any probability mass exactly on a Voronoi boundary.

Compare the gap with center error.
Use the perturbation bound, or an exact boundary calculation, to identify which observations can change assignment.

State the strength of the conclusion.
Zero boundary mass gives a sufficient condition for vanishing disagreement; the rate depends on how quickly boundary-neighborhood mass vanishes.

Positive boundary mass is a warning, not an automatic proof of failure. If a particular perturbation moves the boundary away from an atom without changing which side contains that atom, its assignment may remain unchanged. What fails is the general guarantee based on center convergence alone: an arbitrarily small perturbation can move an atom across a boundary, as the discrete example showed.

Common Mistake

Incorrect reasoning: “A Voronoi boundary is a lower-dimensional set, so it has probability zero; therefore center convergence implies assignment convergence.” The first claim is about geometric volume, not probability under an arbitrary distribution. A discrete distribution may place positive mass directly on that set.

Correction: Check \(P\{\Delta_c(X)=0\}\) under the actual data distribution. If it is zero, boundary-neighborhood mass vanishes, giving a sufficient convergence guarantee under the stated conditions. If it is positive, calculate how perturbations affect those boundary observations rather than inferring convergence from geometric dimension alone.

Key takeaway: Codebook convergence controls partition error through probability mass near the target Voronoi boundaries. Zero boundary mass is sufficient for assignment convergence, while the rate—and whether a particular perturbation succeeds when boundary atoms exist—requires a distribution-specific calculation.

Check Your Understanding

Use the distance-gap and boundary-mass ideas to answer these questions.

Why does \(P\{\Delta_c(X)=0\}=0\) imply that \(P\{\Delta_c(X)\leq t\}\) tends to zero as \(t\) decreases to zero?
In the discrete example, which support point changes assignment, and why does its probability prevent disagreement from vanishing?
For the uniform example, calculate the disagreement probability if the second center moves from \(1\) to \(1+\varepsilon\).
Why does the singular-density example have vanishing disagreement but a slower rate than the uniform example?
Does positive boundary mass prove that every perturbation changes assignments? Explain the distinction between a failed general guarantee and a specific perturbation.