Why Boundary Mass Matters
A small change in a set of centers does not necessarily change every nearest-center assignment. A point well inside one Voronoi cell stays assigned to that center under a sufficiently small perturbation. Points close to a cell boundary are different: even a small movement of a center can change which center is nearest. Thus, the probability of a changed assignment depends not only on the size of the perturbation, but also on how much probability lies near the boundaries.
The boundary-margin condition quantifies this probability using the distance gap between the nearest and second-nearest centers. A power-law bound on probability near gap zero leads to a corresponding power-law bound on partition disagreement. The condition concerns the distribution of the data around a fixed reference codebook; it is not a claim that all possible codebooks have the same boundary behavior.
The Nearest-Center Gap and the Margin Condition
Let \(X\) take values in \(\mathbb{R}^d\), and let \(c=(c_1,\ldots,c_K)\) be a fixed codebook with \(K\geq 2\) centers in \(\mathbb{R}^d\). For \(x\in\mathbb{R}^d\), order the \(K\) distances \(\|x-c_j\|\), counting equal distances with their multiplicities. Write the two smallest ordered distances as \(D_{(1)}(x;c)\) and \(D_{(2)}(x;c)\), and define the gap
The gap is zero at a tie for the nearest center and is small when the closest two centers are nearly tied. To make labels unambiguous, let \(a_c(x)\) be the smallest index among the centers minimizing \(\|x-c_j\|\). The partition disagreement probability between \(c\) and another indexed codebook \(c'=(c'_1,\ldots,c'_K)\) is \(P(a_c(X)\neq a_{c'}(X))\). The comparison assumes that the indices in the two codebooks correspond; the centers are not relabelled between assignments.
The exponent describes how rapidly the probability of being close to a boundary shrinks as the permitted gap shrinks. A larger exponent means less probability mass in a small-gap region, in the precise power-law sense stated by the condition. The bound is local: it is required only up to \(t_0\).
From Center Perturbation to a Small-Gap Event
Use the maximum center displacement
The key deterministic fact is that a point whose label changes must have had a small gap under the reference codebook.
Proof. Put \(i=a_c(x)\) and \(k=a_{c'}(x)\), so \(i\neq k\). The reverse triangle inequality gives, for every center index \(j\),
Since \(k\) minimizes distance under \(c'\), \(\|x-c'_k\|\leq\|x-c'_i\|\). Therefore
Under \(c\), index \(i\) is a nearest center. Because \(k\neq i\), the distance \(\|x-c_k\|\) is at least the second-smallest distance, including when there is a tie. Thus \(D_{(2)}(x;c)-D_{(1)}(x;c)\leq \|x-c_k\|-\|x-c_i\|\leq 2\delta\), proving the claim. \(\square\)
The Disagreement Bound
Proof. First suppose \(\delta=0\). Then \(c'_j=c_j\) for every \(j\), so the same tie-breaking rule gives \(a_{c'}(x)=a_c(x)\) for every \(x\). The disagreement probability is zero.
Now suppose \(0<\delta\leq t_0/2\). By the lemma, the disagreement event is contained in \(\{\Delta_c(X)\leq 2\delta\}\). Since \(0<2\delta\leq t_0\), the margin condition applies at the positive threshold \(t=2\delta\). Taking probabilities yields
This proves the result. \(\square\)
The factor \(2\) comes from allowing the distance to each of the two competing centers to change by as much as \(\delta\). The theorem is local because the margin condition only controls small gaps up to \(t_0\). When \(\delta>t_0/2\), the conclusion available without further assumptions is just the trivial probability bound of one.
Worked Example: Uniform Data and a Linear Margin
Let \(X\) be uniform on \([0,1]\), with two reference centers \(c_1=0.3\) and \(c_2=0.7\). Their Voronoi boundary is \(0.5\). For \(x\leq 0.5\), the gap is \((0.7-x)-(x-0.3)=1-2x\); for \(x\geq 0.5\), it is \((x-0.3)-(0.7-x)=2x-1\). Hence \(\Delta_c(x)=2|x-0.5|\).
For \(0<t\leq 1\), the event \(\Delta_c(X)\leq t\) is the interval \([0.5-t/2,\,0.5+t/2]\), whose length is \(t\). Uniformity gives \(P(\Delta_c(X)\leq t)=t\), so the condition holds with \(C=1\), \(\alpha=1\), and \(t_0=1\).
Now perturb the centers to \(c'_1=0.32\) and \(c'_2=0.72\). Here \(\delta=0.02\). The new boundary is their midpoint, \(0.52\); the assignment changes on the interval between \(0.50\) and \(0.52\), with probability \(0.02\). The theorem applies because \(2\delta=0.04\leq 1\), and gives the bound \(1(0.04)^1=0.04\). The actual disagreement, \(0.02\), is below this bound.
Worked Example: Less Probability Near the Boundary
Keep the same reference centers, but give \(X\) density \(f(x)=4|x-0.5|\) on \([0,1]\). This is a probability density because \(\int_0^1 |x-0.5|\,dx=1/4\), so its integral is \(4(1/4)=1\). The gap remains \(\Delta_c(x)=2|x-0.5|\).
For \(0<t\leq 1\), the small-gap event is again the interval of radius \(t/2\) around \(0.5\). Writing \(u=x-0.5\), its probability is
Thus the condition holds with \(C=1\), \(\alpha=2\), and \(t_0=1\). For the perturbation \(c'=(0.32,0.72)\), the disagreement interval is \([0.5,0.52]\). Its probability is
The theorem bounds it by \((2\delta)^2=(0.04)^2=0.0016\). Compared with the uniform example, probability near the boundary vanishes faster, and the bound has exponent two rather than one.
Worked Example: An Atom on the Boundary
Let \(X\) equal \(0.5\) with probability \(0.2\), \(0.2\) with probability \(0.4\), and \(0.8\) with probability \(0.4\). Use the centers \(c=(0.3,0.7)\), with ties assigned to the smaller index. At \(X=0.5\), both distances are \(0.2\), so the gap is zero and the point is assigned to center 1.
Perturb to \(c'=(0.28,0.7)\), for which \(\delta=0.02\). At \(X=0.5\), the distances are \(0.22\) and \(0.20\), so the assignment changes to center 2. At \(X=0.2\), the distances are \(0.08\) and \(0.50\), so the assignment remains center 1; at \(X=0.8\), they are \(0.52\) and \(0.10\), so it remains center 2. The disagreement probability is therefore exactly \(0.2\).
For every \(t>0\), \(P(\Delta_c(X)\leq t)\geq 0.2\). No constants \(C<\infty\) and \(\alpha>0\) can make this probability at most \(Ct^\alpha\) for every sufficiently small positive \(t\), because \(Ct^\alpha\) tends to zero as \(t\) tends to zero. The positive-exponent margin condition fails, and a small center perturbation can change the assignments of a fixed positive mass.
Implications and a Common Pitfall
The theorem translates a deterministic center error into a probabilistic partition error. For a sequence of estimated codebooks, suppose their maximum center displacement from a fixed reference codebook is \(\delta_n=O_p(r_n)\), where \(r_n\to 0\), and the reference distribution satisfies the margin condition above. Then the disagreement probability is \(O_p(r_n^\alpha)\). To see this, fix any probability tolerance \(\varepsilon>0\). By \(\delta_n=O_p(r_n)\), choose \(M<\infty\) so that \(P(\delta_n>Mr_n)\) is eventually at most \(\varepsilon\). For sufficiently large \(n\), \(2Mr_n\leq t_0\). On the event \(\delta_n\leq Mr_n\), the theorem gives disagreement at most \(C(2Mr_n)^\alpha\). Since the exceptional probability can be made arbitrarily small, the disagreement is \(O_p(r_n^\alpha)\).
A frequent mistake is to apply the margin condition at \(t=2\delta\) without checking that \(t\) is positive and within its stated range. If \(\delta=0\), the condition does not apply at zero: it was assumed only for \(0<t\leq t_0\). The correct argument handles \(\delta=0\) separately, observing that identical codebooks have identical assignments. For \(\delta>0\), the theorem's restriction \(\delta\leq t_0/2\) ensures that \(2\delta\) is a valid threshold.
Another common error is to use the margin condition for the perturbed codebook without assuming it holds there. The proof needs only the condition at the reference codebook \(c\): the deterministic lemma places every changed point in its small-gap region. The exponent controls the probability of that region under the distribution of \(X\), not a change in the codebook itself.
Check Your Understanding
Use the definitions and bounds above to answer the following questions.
- Why does the disagreement argument use the gap between the two smallest distances, rather than the distance to the nearest center alone?
- For a margin exponent \(\alpha=2\), by what power of \(\delta\) is the local disagreement probability bounded?
- Why must the case \(\delta=0\) be handled separately from applying the margin condition at \(t=2\delta\)?
- In the boundary-atomic example, which part of the margin condition fails as \(t\) decreases toward zero?
- If \(\delta_n=O_p(r_n)\) and the margin exponent is \(\alpha\), what order does the theorem give for partition disagreement?