Rates for Empirical K-Means With Separated Optima

From Empirical Risk to Center Accuracy

An empirical K-means solution minimizes the average squared distance from the observations to their nearest center. But minimizing that sample average does not, by itself, say how close the resulting centers are to a population-optimal codebook. A useful route to such a statement has two parts: bound the difference between empirical and population risks uniformly over codebooks, then use the shape of the population risk near its optimum to translate risk error into center error.

Here the setting is fixed-dimensional and bounded: the observations lie in a ball, the number of centers is fixed, and population optima are separated in the sense that there is only one optimal codebook up to relabeling. The resulting rates are conservative global rates; their value is that each follows from transparent assumptions and a direct argument.

Definition: Let $X_1,\ldots,X_n$ be independent observations with common distribution $F$, supported on the closed ball $B_R=\{x\in\mathbb R^d:\|x\|\le R\}$, where $R<\infty$. A codebook is $\mathbf c=(c_1,\ldots,c_K)\in B_R^K$. Its loss at $x$ is $g_{\mathbf c}(x)=\min_{1\le j\le K}\|x-c_j\|^2$. The population distortion is $R(\mathbf c)=E[g_{\mathbf c}(X)]$, and the empirical distortion is $R_n(\mathbf c)=n^{-1}\sum_{i=1}^n g_{\mathbf c}(X_i)$. Write $R^*=\min_{\mathbf c\in B_R^K}R(\mathbf c)$. The excess distortion is $R(\mathbf c)-R^*$.

Codebooks that differ only by a permutation of their centers represent the same quantizer. Accordingly, define their distance by $d_{\mathrm{perm}}(\mathbf c,\mathbf c')=\min_{\pi}\max_{1\le j\le K}\|c_j-c'_{\pi(j)}\|$, where the minimum is over all permutations $\pi$ of $\{1,\ldots,K\}$. Let $\mathcal C^*$ be the set of population-optimal codebooks. The center error of $\mathbf c$ is $d_{\mathrm{perm}}(\mathbf c,\mathcal C^*)=\inf_{\mathbf c^*\in\mathcal C^*}d_{\mathrm{perm}}(\mathbf c,\mathbf c^*)$.

A Uniform Bound for the Empirical Distortion

The parameter space $B_R^K$ is compact, and the loss is bounded: $0\le g_{\mathbf c}(x)\le4R^2$. It also varies continuously with the centers. For codebooks $\mathbf c,\mathbf c'$, put $\|\mathbf c-\mathbf c'\|_{\max}=\max_j\|c_j-c'_j\|$. Since $\|x-c_j\|$ and $\|x-c'_j\|$ are at most $2R$, and their difference in absolute value is at most $\|c_j-c'_j\|$,

\left|\|x-c_j\|^2-\|x-c'_j\|^2\right| \le 4R\|c_j-c'_j\|.

Taking a minimum over $j$ preserves this bound with $\|\mathbf c-\mathbf c'\|_{\max}$ on the right. Thus the loss is $4R$-Lipschitz in the maximum-center distance.

Result: For every $\delta>0$, every $0<\eta<1$, and a finite $\delta$-net of $B_R^K$ in maximum-center distance with size at most $N_\delta=(1+2R/\delta)^{Kd}$, with probability at least $1-\eta$, $$ \sup_{\mathbf c\in B_R^K}|R_n(\mathbf c)-R(\mathbf c)| \le 4R^2\sqrt{\frac{\log(2N_\delta/\eta)}{2n}}+8R\delta. $$

To verify the net-size bound, cover each copy of $B_R$ by a Euclidean $\delta$-net of size at most $(1+2R/\delta)^d$, then take all $K$-tuples of net points. For any fixed net point, Hoeffding's inequality applies because its losses lie in an interval of length $4R^2$. A union bound gives, with probability at least $1-\eta$, a deviation at every net point no larger than $4R^2\sqrt{\log(2N_\delta/\eta)/(2n)}$. For an arbitrary codebook, choose a net point within $\delta$. The empirical risks differ by at most $4R\delta$, and the population risks differ by at most $4R\delta$, by the Lipschitz bound. Adding these two approximation errors proves the displayed result.

Worked Example: Checking the Lipschitz Bound

Take $R=1$, one-dimensional data $x=0.5$, and a single center that moves from $c=0$ to $c'=0.2$. The losses are $(0.5-0)^2=0.25$ and $(0.5-0.2)^2=0.09$. Their difference is $0.16$. The general bound is $4R|c-c'|=4(1)(0.2)=0.8$, so the computed difference satisfies the bound. The bound is deliberately uniform over all $x,c,c'$ in the ball, rather than sharp for this particular choice.

Worked Example: A Corrected Finite-Sample Bound

Let $R=1$, $d=1$, $K=2$, $n=1000$, and $\eta=0.05$. Choose $\delta=1/\sqrt{1000}$. Then the net-size upper bound is $(1+2/\delta)^2=(1+2\sqrt{1000})^2$. Since $\sqrt{1000}\approx31.6228$, this is approximately $4127.49$, not $1064$. Substitution gives $\log(2N_\delta/\eta)\le\log(2(4127.49)/0.05)\approx12.014$.

The stochastic term in the uniform bound is therefore at most $4\sqrt{12.014/2000}\approx0.3100$. The net-approximation term is $8/\sqrt{1000}\approx0.2530$. Consequently, with probability at least $0.95$, $\sup_{\mathbf c}|R_n(\mathbf c)-R(\mathbf c)|\le0.5630$, up to rounding. This bound is valid but may be too large to be informative at this sample size; a correct finite-sample inequality need not be numerically sharp.

Separated Optima and Quadratic Growth

A local condition on the population risk supplies the link from distortion to center location. Assume there is a unique optimal codebook up to permutation, so $\mathcal C^*$ is one permutation orbit. Assume also that there are constants $\kappa>0$ and $\rho>0$ such that

R(\mathbf c)-R^*\ge \kappa\,d_{\mathrm{perm}}(\mathbf c,\mathcal C^*)^2 \quad\text{whenever}\quad d_{\mathrm{perm}}(\mathbf c,\mathcal C^*)\le\rho.

This is local quadratic growth. It says that, near the optimum, a center displacement of size $r$ costs at least $\kappa r^2$ in population distortion. The uniqueness condition separates the optimum from other, genuinely different minimizers. Compactness and continuity then ensure a positive risk gap outside any fixed neighborhood of the optimal orbit.

Theorem: Suppose the observations are independent with common distribution supported on $B_R$, and the population risk has a unique optimal codebook up to permutation and satisfies the local quadratic-growth condition above. Let $\hat{\mathbf c}_n$ be any empirical minimizer over $B_R^K$. Then $$ R(\hat{\mathbf c}_n)-R^*=O_p\!\left(\sqrt{\frac{\log n}{n}}\right), \qquad d_{\mathrm{perm}}(\hat{\mathbf c}_n,\mathcal C^*) =O_p\!\left(\left(\frac{\log n}{n}\right)^{1/4}\right). $$

Proof. First, the uniform bound implies $\sup_{\mathbf c}|R_n(\mathbf c)-R(\mathbf c)|\xrightarrow{p}0$. For example, take $\delta=n^{-1/2}$ in the bound: $N_\delta\le(1+2R\sqrt n)^{Kd}$, so the stochastic term is $O(\sqrt{\log n/n})$, and the approximation term is $8R/\sqrt n$. Write the supremum as $U_n$.

Empirical minimizers exist because $B_R^K$ is compact and $R_n$ is continuous. For any population minimizer $\mathbf c^*$, empirical optimality gives $R_n(\hat{\mathbf c}_n)\le R_n(\mathbf c^*)$. Hence

R(\hat{\mathbf c}_n)-R^* \le |R(\hat{\mathbf c}_n)-R_n(\hat{\mathbf c}_n)| +|R_n(\mathbf c^*)-R(\mathbf c^*)| \le 2U_n.

This proves the excess-distortion rate. To apply local quadratic growth, fix any $\epsilon>0$. The set of codebooks at permutation distance at least $\epsilon$ from $\mathcal C^*$ is compact. If it is nonempty, continuity and uniqueness imply that the minimum risk excess on it is strictly positive. Since $2U_n\xrightarrow{p}0$, the preceding inequality shows that $\hat{\mathbf c}_n$ lies within distance $\epsilon$ of $\mathcal C^*$ with probability tending to one. In particular, it lies within the radius $\rho$ with probability tending to one. On that event, quadratic growth yields $d_{\mathrm{perm}}(\hat{\mathbf c}_n,\mathcal C^*)^2\le 2U_n/\kappa$. Taking square roots gives the asserted center-error rate. $\square$

Worked Example: Converting a Risk Bound to a Center Bound

Suppose a particular problem has quadratic-growth constant $\kappa=0.5$, and on an event of interest an empirical minimizer has excess distortion at most $0.02$. If it is within the neighborhood where quadratic growth holds, then $0.02\ge0.5\,d_{\mathrm{perm}}^2$, so $d_{\mathrm{perm}}^2\le0.04$, and therefore $d_{\mathrm{perm}}\le0.2$. The square root is essential: a risk bound of size $a$ gives a center bound of size $\sqrt{a/\kappa}$, not $a/\kappa$.

What the Rates Say—and What They Do Not

The global argument gives an excess-distortion rate of order $(\log n/n)^{1/2}$ and a center-error rate of order $(\log n/n)^{1/4}$. The second rate is slower because quadratic growth turns a risk error into its square root. These are rates established by a uniform bound over the entire codebook space. They should not be mistaken for a claim that every distribution or every empirical minimizer has exactly this error, nor for a claim that these rates are sharp.

Worked Example: A Simple One-Center Model

Let $K=1$ and let $X$ equal $1$ or $-1$, each with probability $1/2$. The population risk for a center $c\in[-1,1]$ is $R(c)=E[(X-c)^2]=1+c^2$, so $c^*=0$, $R^*=1$, and the quadratic-growth condition holds with $\kappa=1$.

Consider a sample of size $10$ with six observations equal to $1$ and four equal to $-1$. Its empirical minimizer is the sample mean, $\hat c=(6-4)/10=0.2$. The center error is $0.2$, while the excess distortion is $R(0.2)-R(0)=0.2^2=0.04$. This calculation illustrates the square relationship exactly. The global theorem provides a general guarantee; this particular model and sample allow a direct calculation that is more informative.

Common Mistake

A common mistake is to conclude that a small empirical distortion difference immediately proves that the estimated centers are close. It does not: the conversion requires a condition such as quadratic growth, and with multiple equivalent labelings the comparison must use permutation-invariant distance. A second mistake is to call the global rates optimal. The uniform bound controls every codebook at once and pays for a net over the whole parameter space; it can therefore be conservative. The center rate is also a square root of the risk rate, not the same rate as the risk.

Key takeaway: Bounded support and fixed dimension give a uniform empirical-risk bound. Separation places empirical minimizers near the population-optimal orbit, and local quadratic growth converts their excess distortion into a center-error guarantee.

Check Your Understanding

Answer each question using the assumptions and inequalities developed above.

Why is the loss $g_{\mathbf c}(x)$ bounded by $4R^2$ when both $x$ and every center lie in $B_R$?
In the uniform bound, why does approximating both the empirical risk and the population risk by a net point contribute $8R\delta$, rather than $4R\delta$?
If the excess distortion is at most $a$ and quadratic growth holds with constant $\kappa$, what upper bound follows for the center error?
Why does uniqueness up to permutation not mean that a particular ordering of the centers is identifiable?
What feature of the global net argument can make its rates conservative?