Localized Risk Bounds Near Optimal Codebooks

Why Local Risk Control Can Improve the Rate

A uniform bound over every candidate codebook must account for the largest empirical fluctuation in the whole class. That can give an excess-risk bound of square-root order in sample size. But an empirical minimizer is not an arbitrary codebook: once it is known to lie near a population optimum, only fluctuations in that neighborhood need to be controlled. If those fluctuations are smaller for codebooks with small excess risk, the resulting bound can be faster.

We make this distinction precise for squared-distance quantization. The key condition is local: the variance of the difference between a candidate's loss and an optimal codebook's loss is at most proportional to the candidate's excess risk. Combined with a suitable bound on localized empirical fluctuations, this condition leads to an excess-risk rate of order complexity divided by sample size.

Risk, Excess Risk, and Localization

Let $X$ take values in a bounded subset of $\mathbb{R}^d$, and let a codebook be $c=(c_1,\ldots,c_K)$. Its pointwise squared-distance loss is

\gamma_c(x)=\min_{1\leq j\leq K}\|x-c_j\|^2.

For independent observations $X_1,\ldots,X_n$ with the same distribution as $X$, write the population and empirical risks as $R(c)=E[\gamma_c(X)]$ and $R_n(c)=n^{-1}\sum_{i=1}^n\gamma_c(X_i)$. Let $c^*$ be a population-minimizing codebook and $R^*=R(c^*)$. As usual for labeled codebooks, permutations of the same centers represent the same quantizer; we work with one representative and understand neighborhoods to include its label permutations.

Definition: The excess risk of $c$ is $\Delta(c)=R(c)-R^*$, which is nonnegative. A codebook is localized near the minimizing set when it lies in a specified neighborhood of that set, for example when its distance to the minimizing set is at most $\rho$. A local variance condition is a bound of the form $$ \operatorname{Var}\bigl(\gamma_c(X)-\gamma_{c^*}(X)\bigr)\leq \beta\,\Delta(c) $$ for codebooks in that neighborhood, where $\beta$ is a finite constant.

The condition controls the random loss difference, not the variance of either loss by itself. When $c$ is close in risk to $c^*$, it says that the difference fluctuates less. This is the feature that a global variance bound misses.

A Fast Bound for a Finite Local Class

First consider a finite class $\mathcal{C}_0$ of candidate codebooks containing $c^*$. Assume every member is in a neighborhood where the local variance condition holds. Let $\hat c$ minimize $R_n(c)$ over $\mathcal{C}_0$, and put $N=|\mathcal{C}_0|$. We also require a uniform bound $M$ on the centered loss differences:

\left| \bigl(\gamma_c(X)-\gamma_{c^*}(X)\bigr)-\Delta(c)\right|\leq M \quad\text{almost surely, for every }c\in\mathcal{C}_0.

Theorem: Suppose $\operatorname{Var}(\gamma_c(X)-\gamma_{c^*}(X))\leq\beta\Delta(c)$ and the centered differences are bounded by $M$ as above. Then for every $r>0$, $$ P\bigl(\Delta(\hat c)\geq r\bigr) \leq N\exp\left(-\frac{nr}{2\beta+2M/3}\right). $$ Consequently, with probability at least $1-\delta$, $$ \Delta(\hat c)\leq \frac{2\beta+2M/3}{n}\log\left(\frac{N}{\delta}\right). $$

Proof. For each fixed $c$, set $g_c(X)=\gamma_c(X)-\gamma_{c^*}(X)$. Its expectation is $\Delta(c)$. If $\hat c=c$, empirical minimization implies $R_n(c)\leq R_n(c^*)$, or equivalently $P_n g_c\leq0$, where $P_n g_c=n^{-1}\sum_{i=1}^n g_c(X_i)$. Thus, when $\Delta(c)>0$, this event requires

(P_n-P)g_c\leq-\Delta(c).

The one-sided Bernstein inequality states that, for independent mean-zero variables bounded in absolute value by $M$, with variance at most $\sigma^2$, the probability their average is at most $-t$ is at most $\exp\{-nt^2/(2\sigma^2+2Mt/3)\}$. Apply it with $t=\Delta(c)$ and $\sigma^2\leq\beta\Delta(c)$. It gives

P\bigl(P_n g_c\leq0\bigr) \leq \exp\left(-\frac{n\Delta(c)}{2\beta+2M/3}\right).

If $\Delta(\hat c)\geq r$, at least one codebook $c\in\mathcal{C}_0$ with $\Delta(c)\geq r$ must satisfy $P_n g_c\leq0$. A union bound over at most $N$ codebooks proves the first inequality. Setting $r=(2\beta+2M/3)\log(N/\delta)/n$ proves the stated probability bound. $\square$

The rate is $1/n$, apart from the logarithm of the class size. The result is local in its assumptions: if the empirical minimizer is only known to lie in the specified neighborhood with probability at least $1-\eta$, the displayed guarantee applies together with that localization event, and the total failure probability is at most $\delta+\eta$.

Worked Example: A Two-Point Distribution and Two Candidate Codebooks

Let $P(X=-1)=P(X=1)=1/2$, take $K=2$, and compare $c^*=(-1,1)$ with $c_1=(-1,1.5)$. At $X=-1$, both losses are zero. At $X=1$, the optimal loss is zero and the candidate loss is $0.5^2=0.25$. Therefore $g_{c_1}(X)$ is zero with probability $1/2$ and $0.25$ with probability $1/2$.

Its mean and variance are

\Delta(c_1)=E[g_{c_1}(X)]=0.125, \qquad \operatorname{Var}(g_{c_1}(X)) =\frac{(0-0.125)^2+(0.25-0.125)^2}{2} =0.015625.

Thus the variance condition holds with $\beta=0.125$, since $0.015625=0.125(0.125)$. The centered difference is bounded in absolute value by $M=0.125$. For the two-codebook class, the theorem gives, at $n=200$ and $\delta=0.05$,

\Delta(\hat c)\leq \frac{2(0.125)+2(0.125)/3}{200}\log(2/0.05) =\frac{1}{600}\log(40) \approx 0.00615

with probability at least $0.95$. Here the only possible positive excess risk is $0.125$, so this bound says that the empirical minimizer selects the optimal codebook except on an event of probability at most $0.05$. In fact, a tie can occur only if all 200 observations equal $-1$, an event of probability $2^{-200}$; choosing $c^*$ in a tie makes the conclusion immediate in this example.

From Local Empirical Fluctuations to a Fast Rate

For a continuous codebook class, a finite union bound is usually not enough. A useful alternative is to assume a localized empirical-process bound. This condition summarizes the complexity of the loss class inside a risk neighborhood. It must be justified for the model at hand; bounded support alone does not automatically give the fast rate.

Theorem: Let $\mathcal{U}$ be a neighborhood of the minimizing set, and suppose an empirical minimizer $\hat c$ belongs to $\mathcal{U}$. Assume that, for some $A>0$, $v\geq0$, and $u>0$, with probability at least $1-e^{-u}$, simultaneously for every $0<t\leq r_0$, $$ \sup_{\substack{c\in\mathcal{U}\\\Delta(c)\leq t}} \left|(P_n-P)(\gamma_c-\gamma_{c^*})\right| \leq A\left(\sqrt{\frac{t(v+u)}{n}}+\frac{v+u}{n}\right). $$ If $\Delta(\hat c)\leq r_0$, then on this event, $$ \Delta(\hat c)\leq (A^2+2A)\frac{v+u}{n}. $$

Proof. Empirical minimization gives $R_n(\hat c)\leq R_n(c^*)$. Subtracting the population risks shows

\Delta(\hat c) \leq \left|(P_n-P)(\gamma_{\hat c}-\gamma_{c^*})\right|.

If $\Delta(\hat c)=0$, the result holds. Otherwise take $t=\Delta(\hat c)$, which is permitted because $\Delta(\hat c)\leq r_0$. The assumed simultaneous bound then yields, with $s=(v+u)/n$,

\Delta(\hat c)\leq A\sqrt{\Delta(\hat c)s}+As.

The inequality $A\sqrt{\Delta(\hat c)s}\leq \Delta(\hat c)/2+A^2s/2$ follows from the nonnegativity of $(\sqrt{\Delta(\hat c)}-A\sqrt{s})^2$. Substitution and rearrangement give $\Delta(\hat c)\leq(A^2+2A)s$, as claimed. $\square$

The theorem isolates two tasks. First, one must ensure that the empirical minimizer is in the neighborhood where the local bound applies. Second, one must establish the localized empirical-process inequality for the codebook class. In finite-dimensional settings, bounds of this form can follow from control of the size of the loss class at increasingly fine scales, together with local variance control. The theorem does not assert that every clustering problem satisfies those conditions.

Worked Example: A Continuum of Perturbed Two-Center Codebooks

Return to the distribution with equal mass at $-1$ and $1$. For $0\leq a\leq1$, let $c_a=(-1,1+a)$. At $X=-1$, the loss difference from $c^*=(-1,1)$ is zero. At $X=1$, the nearer center is $1+a$, so the difference is $a^2$. Hence $g_{c_a}$ equals zero or $a^2$, each with probability $1/2$, and

\Delta(c_a)=\frac{a^2}{2}, \qquad \operatorname{Var}(g_{c_a}(X))=\frac{a^4}{4} =\frac{a^2}{2}\Delta(c_a) \leq\frac12\Delta(c_a).

This verifies a uniform local variance condition with $\beta=1/2$ over the entire interval $0\leq a\leq1$. It also displays the central point of localization: as $a$ decreases, both the excess risk and the variance of the loss difference decrease. This calculation verifies the variance condition, not the empirical-process condition needed to apply the preceding theorem to a general continuous class.

Worked Example: Solving a Localized Rate Bound

Suppose a problem has a localized empirical-process inequality with $A=2$, $v=5$, and $n=10{,}000$. Take failure probability $0.05$, so $u=\log(1/0.05)=\log 20\approx2.996$. Provided the minimizer is localized in the stated neighborhood, the theorem gives

\Delta(\hat c) \leq (2^2+2\cdot2)\frac{5+\log20}{10{,}000} =8\frac{7.996}{10{,}000} \approx0.00640.

For comparison, a global deviation bound with the same illustrative complexity quantity and leading constant 2 would have square-root scale $2\sqrt{(5+\log20)/10{,}000}\approx0.0566$. These constants are illustrative rather than a universal comparison: the point is the order. Local control can turn a square-root dependence on complexity divided by $n$ into a linear dependence on complexity divided by $n$, when the required local conditions hold.

What the Local Condition Does—and Does Not—Say

The variance condition is not a consequence of optimality alone. For any random loss difference $g_c$, its mean is $\Delta(c)$, but a small mean does not by itself force its variance to be small. The condition must be verified from properties of the distribution, the loss, and the neighborhood being considered. In the two-point example, it was verified by calculating both quantities exactly.

A common mistake is to observe that squared-distance losses are bounded on bounded support and conclude that the local $1/n$ rate follows. Boundedness can control large deviations, but it does not supply the variance-to-excess-risk relation or the localized complexity bound. Without the local variance reduction, a global empirical-process bound may still yield only a square-root rate. Another mistake is to apply a local theorem before establishing that the empirical minimizer is in the neighborhood. Localization is a separate requirement, not part of the variance calculation.

Key takeaway: A fast localized risk bound requires both a reason to restrict attention near the population minimizing set and control of empirical fluctuations within that set. When the local variance scales with excess risk and the localized class has manageable complexity, solving the resulting inequality yields an excess-risk rate of order complexity divided by sample size.

Check Your Understanding

Use the definitions and arguments above to answer these questions.

Why is the relevant variance in a local variance condition the variance of $\gamma_c(X)-\gamma_{c^*}(X)$, rather than the variance of $\gamma_c(X)$ alone?
In the finite-class theorem, which empirical event must occur if a particular codebook with positive excess risk is selected over $c^*$?
For the two-point example with $c_a=(-1,1+a)$, calculate the excess risk and variance when $a=0.4$, and verify the stated variance condition.
What two distinct conditions are needed to use the localized empirical-process theorem for a continuous codebook class?
Why does bounded loss by itself not establish a rate of order $1/n$?