Quadratic Growth and Center Error From Excess Distortion

Why Excess Distortion Can Control Center Error

In clustering, a codebook is a collection of centers, and its distortion is the expected squared distance from a random observation to its nearest center. A codebook with distortion close to the optimum is not automatically close to an optimal codebook: the risk surface could be very flat near its minimum. A quadratic-growth condition rules out excessive flatness locally. It says that a specified amount of center displacement must cost at least a constant times the squared displacement in distortion.

The conclusion is useful for empirical clustering. If an estimated codebook is known to have small population excess distortion and is in the neighborhood where quadratic growth holds, its distance from the population optimum is bounded. The argument must account for label switching: permuting the labels of a codebook does not change its distortion or its centers as an unordered collection.

Excess Distortion and Codebook Distance

Let $X$ take values in $\mathbb{R}^d$, and fix a number of centers $K$. Let $\mathcal{A}\subset\mathbb{R}^d$ be the allowed set of centers and let $\mathcal{C}\subseteq\mathcal{A}^K$ be the feasible set of ordered codebooks. For $c=(c_1,\ldots,c_K)\in\mathcal{C}$, define its population distortion by

R(c)=E\left[\min_{1\leq j\leq K}\|X-c_j\|^2\right].

Assume the expectation is finite for the codebooks considered. Write $R^*=\min_{c\in\mathcal{C}}R(c)$, and let $c^*=(c_1^*,\ldots,c_K^*)$ be one population-optimal codebook. Even when the optimum is identifiable as an unordered collection, its ordered representations include all permutations of its labels. Accordingly, define the permutation-invariant squared distance

d_{\mathrm{perm}}^2(c,c^*)= \min_{\pi\in\mathfrak{S}_K}\sum_{j=1}^K\|c_j-c_{\pi(j)}^*\|^2,

where $\mathfrak{S}_K$ is the set of permutations of $\{1,\ldots,K\}$. The excess distortion of $c$ is $R(c)-R^*$, a nonnegative quantity. In what follows, identifiability means that the full set of population minimizers consists exactly of the permutations of $c^*$.

Definition: The risk has local quadratic growth at the identifiable optimum $c^*$ if there are constants $\lambda>0$ and $\delta>0$ such that every $c\in\mathcal{C}$ with $d_{\mathrm{perm}}(c,c^*)\leq\delta$ satisfies $$ R(c)-R^*\geq \lambda d_{\mathrm{perm}}^2(c,c^*). $$

The constant $\lambda$ quantifies the local curvature in a risk-based sense; it need not be a second derivative. The condition is about the risk difference itself, and it remains meaningful when the nearest-center objective is not differentiable everywhere.

Worked Example: Two Separated Point Masses

Let $P(X=-2)=P(X=2)=1/2$, take $K=2$, and use the ordered codebook $c=(a,b)$. The codebook $c^*=(-2,2)$ has zero risk and is optimal. Consider $a\in(-3,-1)$ and $b\in(1,3)$. For $X=-2$, the distance to $a$ is less than 1, while the distance to $b$ is greater than 3, so $-2$ is assigned to $a$. Likewise $2$ is assigned to $b$. Therefore

R(a,b)=\frac12(a+2)^2+\frac12(b-2)^2, \qquad R^*=0.

In this neighborhood, the identity permutation gives the minimum matching, so $d_{\mathrm{perm}}^2((a,b),c^*)=(a+2)^2+(b-2)^2$. Thus $R(a,b)-R^*=\tfrac12d_{\mathrm{perm}}^2((a,b),c^*)$: quadratic growth holds with $\lambda=1/2$. The swapped representation $(2,-2)$ describes the same optimal collection and has zero permutation-invariant distance from $c^*$.

Worked Example: Exact Center Error for One Center

Let $P(X=0)=3/4$ and $P(X=2)=1/4$, with one center $c\in\mathbb{R}$. Its mean is $1/2$. Direct calculation gives

R(c)=\frac34c^2+\frac14(2-c)^2 =\frac34c^2+1-c+\frac14c^2 =(c-\tfrac12)^2+\frac34.

The unique optimum is $c^*=1/2$, with $R^*=3/4$. At $c=11/10$, the center error is $c-c^*=3/5$, and the excess distortion is $R(c)-R^*=(3/5)^2=9/25$. The squared center error is also $9/25$, so the bound holds with equality and $\lambda=1$. In fact, this identity holds for every $c$, not just locally.

The Center-Error Bound

Theorem: Suppose $c^*$ is a population-optimal codebook and the risk has local quadratic growth there with constants $\lambda>0$ and $\delta>0$. For any codebook $c$ satisfying $d_{\mathrm{perm}}(c,c^*)\leq\delta$, $$ d_{\mathrm{perm}}^2(c,c^*)\leq\frac{R(c)-R^*}{\lambda}. $$

Proof. The assumed growth condition gives $R(c)-R^*\geq\lambda d_{\mathrm{perm}}^2(c,c^*)$. Since $\lambda>0$, division by $\lambda$ preserves the inequality and yields the stated bound. $\square$

This result is direct, but its hypotheses matter. It is a local statement: a small excess distortion gives the center-error conclusion only when the codebook is already within the specified neighborhood, unless a separate argument puts it there. It is also a population-risk statement. An empirical-risk difference cannot simply be substituted for $R(c)-R^*$.

From Empirical Risk to Population Center Error

For observations $X_1,\ldots,X_n$, define the empirical distortion

R_n(c)=\frac1n\sum_{i=1}^n\min_{1\leq j\leq K}\|X_i-c_j\|^2.

Suppose the feasible codebook space is fixed, $c^*\in\mathcal{C}$, and the uniform discrepancy $\Delta_n=\sup_{c\in\mathcal{C}}|R_n(c)-R(c)|$ is finite. An empirical approximate minimizer with tolerance $\eta_n\geq0$ satisfies $R_n(\hat c_n)\leq\inf_{c\in\mathcal{C}}R_n(c)+\eta_n$. The next result compares its population excess distortion with the uniform discrepancy.

Proposition: Under these conditions, $$ R(\hat c_n)-R^*\leq 2\Delta_n+\eta_n. $$ If, in addition, $d_{\mathrm{perm}}(\hat c_n,c^*)\leq\delta$ and local quadratic growth holds with constant $\lambda$, then $$ d_{\mathrm{perm}}^2(\hat c_n,c^*)\leq\frac{2\Delta_n+\eta_n}{\lambda}. $$

Proof. By the definition of $\Delta_n$, $R(\hat c_n)\leq R_n(\hat c_n)+\Delta_n$. Approximate minimization and feasibility of $c^*$ imply $R_n(\hat c_n)\leq R_n(c^*)+\eta_n$. Applying the discrepancy bound again gives $R_n(c^*)\leq R(c^*)+\Delta_n=R^*+\Delta_n$. Combining these inequalities yields $R(\hat c_n)-R^*\leq2\Delta_n+\eta_n$. When $\hat c_n$ is in the quadratic-growth neighborhood, the center-error theorem then gives the second inequality. $\square$

Worked Example: A Sample Center and Its Population Error

Let $X$ put probability $1/3$ on each of $-1,0,1$, and use $K=1$ with feasible centers $\mathcal{C}=[-1,1]$. Its population mean is zero, and

R(c)=\frac13\{(-1-c)^2+c^2+(1-c)^2\} =c^2+\frac23.

Thus $c^*=0$, $R^*=2/3$, and the growth condition holds everywhere on $\mathcal{C}$ with $\lambda=1$. Consider the realized sample $X_1=0,X_2=1$, which has positive probability under this distribution. Its empirical risk is

R_2(c)=\frac12\{c^2+(1-c)^2\} =(c-\tfrac12)^2+\frac14.

The empirical minimizer is $\hat c_2=1/2$. Its population excess distortion is $R(1/2)-R^*=(1/4+2/3)-2/3=1/4$, exactly equal to its squared center error $(1/2-0)^2=1/4$.

For this feasible interval, $R_2(c)-R(c)=-c-1/6$. Its absolute value has supremum $7/6$ on $[-1,1]$: at $c=1$ it is $7/6$, and at $c=-1$ it is $5/6$. The proposition with $\eta_2=0$ therefore gives the valid, but loose, upper bound $d_{\mathrm{perm}}^2(\hat c_2,c^*)\leq2(7/6)=7/3$. The exact center error $1/4$ confirms the bound while illustrating that a uniform-error guarantee need not be sharp.

When a Local Bound Becomes Global

A compact parameter space and an identifiable optimum can extend a local quadratic-growth bound to all feasible codebooks, provided the risk is continuous. This is a deterministic consequence of compactness, not an automatic source of a useful numerical constant.

Theorem: Suppose $\mathcal{C}$ is compact, $R$ is continuous on $\mathcal{C}$, and the minimizers of $R$ are exactly the permutations of $c^*$. If local quadratic growth holds at $c^*$, then there is a constant $\lambda_0>0$ such that for every $c\in\mathcal{C}$, $$ R(c)-R^*\geq\lambda_0d_{\mathrm{perm}}^2(c,c^*). $$

Proof. Let $\delta>0$ be a radius for which local growth holds. The set $\mathcal{C}_{\mathrm{out}}=\{c\in\mathcal{C}:d_{\mathrm{perm}}(c,c^*)\geq\delta\}$ is compact, because the permutation-invariant distance is continuous. If this set is nonempty, it contains no minimizer. Continuity and compactness therefore imply that $\gamma=\min_{c\in\mathcal{C}_{\mathrm{out}}}\{R(c)-R^*\}>0$. Also let $D^2=\max_{c\in\mathcal{C}}d_{\mathrm{perm}}^2(c,c^*)$, which is finite. If the outer set is nonempty, $D>0$, and on it $R(c)-R^*\geq\gamma\geq(\gamma/D^2)d_{\mathrm{perm}}^2(c,c^*)$. Inside the radius-$\delta$ neighborhood, the assumed inequality holds with $\lambda$. Thus the global inequality holds with $\lambda_0=\min\{\lambda,\gamma/D^2\}$. If the outer set is empty, the local inequality already covers all of $\mathcal{C}$, so take $\lambda_0=\lambda$. $\square$

Although the extension proves existence of a global constant, the compactness argument may give a very small $\gamma$, and hence a weak bound. For empirical applications, it is often more informative to use consistency to ensure the estimated codebook eventually enters the local neighborhood and then apply the local constant directly.

Common Mistakes and Practical Interpretation

Ignoring label permutations. Comparing the coordinates of two codebooks in their given order can report a large error even when they represent exactly the same centers. Use the minimum over matchings in $d_{\mathrm{perm}}$.
Reversing the inequality. Quadratic growth says excess risk is at least $\lambda$ times squared distance. Dividing by $\lambda$ bounds squared distance from above; it does not say risk is at most a constant times distance.
Using empirical excess as if it were population excess. Empirical minimization alone does not justify that replacement. The discrepancy argument explicitly pays for the two comparisons between $R_n$ and $R$, producing $2\Delta_n$, and for approximate optimization, producing $\eta_n$.
Assuming every unique optimum has quadratic growth. Uniqueness rules out other exact minima, but does not rule out an arbitrarily flat risk surface near the optimum. Quadratic growth is an additional condition.

The practical chain of reasoning is therefore precise: establish population-risk control, ensure the estimated codebook is in the quadratic-growth neighborhood (or use the compact global extension), and then convert excess distortion into squared center error. The bound concerns matched centers; translating it into partition error requires additional reasoning about assignments and boundaries.

Check Your Understanding

Work through these questions using the definitions and results above.

Why is the minimum over permutations included in the codebook distance?
If $\lambda=1/4$ and the population excess distortion is $0.02$, what upper bound does local quadratic growth give for squared codebook distance?
In the empirical-risk proposition, identify the two terms that contribute $\Delta_n$ and explain why both are needed.
Which assumptions allow a local quadratic-growth bound to extend to the full feasible codebook space?
Why does uniqueness of the population-optimal codebook, by itself, not imply the center-error bound?