Distributional Perturbations of Optimal Quantizers

Why Distributional Stability Needs More Than a Risk Bound

A quantizer replaces each observation with its nearest representative from a finite codebook. If the distribution of the observations changes slightly, it is natural to ask whether the best achievable distortion also changes only slightly. A second, stronger question is whether the locations of the optimal representatives change only slightly. The first question concerns the value of an optimization problem; the second concerns its minimizers. The answers require different assumptions.

We study squared Euclidean distortion with a fixed number of centers. Throughout, $K$ is a nonempty compact subset of $\mathbb{R}^d$, $k\geq 1$, and $P,Q$ are Borel probability distributions supported on $K$. Compactness keeps the possible centers and observations bounded. It also ensures that optimal codebooks exist. The stability results below make explicit how uniqueness and separation of the optimum affect conclusions about center locations.

Definition: An ordered codebook is $C=(c_1,\ldots,c_k)\in K^k$. Its distance function is $d(x,C)=\min_{1\leq j\leq k}\|x-c_j\|$, and its quadratic distortion under distribution $P$ is $$ R_P(C)=\int_K d(x,C)^2\,dP(x). $$ The minimum distortion is $R_P^*=\min_{C\in K^k}R_P(C)$, and the set of optimal codebooks is $\mathcal{C}_P^*=\{C\in K^k:R_P(C)=R_P^*\}$. Codebooks that differ only by a permutation of their centers represent the same unordered codebook.

Write $D=\sup_{x,y\in K}\|x-y\|$ for the diameter of $K$. For probability distributions supported on $K$, their 1-Wasserstein distance is

W_1(P,Q)=\inf_{\pi\in\Pi(P,Q)}\int_{K\times K}\|x-y\|\,d\pi(x,y),

where $\Pi(P,Q)$ is the set of joint distributions (couplings) whose first marginal is $P$ and second marginal is $Q$. The definition says that $W_1$ is the least possible expected distance between paired observations with those marginal distributions.

How Much Can Distortion Change?

Fix a codebook $C$. The distance to $C$ changes by at most the distance between two observations: $ |d(x,C)-d(y,C)|\leq\|x-y\|$. On $K$, both distances are at most $D$. Factoring a difference of squares therefore gives

|d(x,C)^2-d(y,C)^2| \leq \bigl(d(x,C)+d(y,C)\bigr)\|x-y\| \leq 2D\|x-y\|.

This Lipschitz bound converts a coupling of $P$ and $Q$ into a bound on the change in expected distortion.

Theorem: For every codebook $C\in K^k$, $$ |R_P(C)-R_Q(C)|\leq 2D W_1(P,Q). $$ Consequently, optimal distortions satisfy $$ |R_P^*-R_Q^*|\leq 2D W_1(P,Q). $$

Proof. Let $\pi\in\Pi(P,Q)$. Its marginals imply that $R_P(C)-R_Q(C)$ is the integral under $\pi$ of $d(x,C)^2-d(y,C)^2$. Thus

|R_P(C)-R_Q(C)| \leq \int |d(x,C)^2-d(y,C)^2|\,d\pi(x,y) \leq 2D\int\|x-y\|\,d\pi(x,y).

Taking the infimum over couplings proves the first inequality. For the minimum, choose $C_P\in\mathcal{C}_P^*$ and $C_Q\in\mathcal{C}_Q^*$. Then

R_Q^*\leq R_Q(C_P)\leq R_P^*+2DW_1(P,Q), \qquad R_P^*\leq R_P(C_Q)\leq R_Q^*+2DW_1(P,Q).

Together these inequalities prove the claimed bound on the two minimum distortions. Existence of the optimal codebooks used here is justified below. $\square$

Worked Example: A Fixed Codebook Under a Shift

Take $K=[0,1]$, $k=1$, $P=\delta_0$, $Q=\delta_{0.2}$, and the fixed codebook $C=(0.5)$. Here $D=1$, and the only coupling of the two point masses pairs 0 with 0.2, so $W_1(P,Q)=0.2$.

Under $P$, the observation is always 0, giving $R_P(C)=(0-0.5)^2=0.25$. Under $Q$, it is always 0.2, giving $R_Q(C)=(0.2-0.5)^2=0.09$. The absolute difference is $0.16$, while the bound is $2DW_1(P,Q)=0.4$, so the inequality holds.

For this example each distribution can place its single center at its point mass, making both minimum distortions zero. Thus the theorem bounds the change for every fixed codebook as well as the change in the optimum value; those changes need not be equal.

Existence and Stability of Optimal Codebooks

The center space $K^k$ is compact. To establish existence, it remains to check continuity of $R_P(C)$ as the centers vary. For two ordered codebooks, define their permutation-invariant distance by

\Delta(C,C')=\min_{\sigma}\left(\sum_{j=1}^k\|c_j-c'_{\sigma(j)}\|^2\right)^{1/2},

where the minimum is over permutations $\sigma$ of $\{1,\ldots,k\}$. Pairing centers according to a minimizing permutation shows that $|d(x,C)-d(x,C')|\leq\Delta(C,C')$. Since both distances are at most $D$, it follows that

|R_P(C)-R_P(C')|\leq 2D\Delta(C,C').

In particular, the distortion is continuous on the compact space $K^k$, so it attains its minimum. This argument permits repeated centers; no distinctness assumption is needed for existence.

For stability of center locations, use the permutation-invariant distance $\Delta$, rather than comparing labels attached to centers. Call the optimum identifiable if $\mathcal{C}_P^*$ consists of exactly one codebook up to permutation. If $C_P^*$ is a representative of that optimum, write $\Delta(C,C_P^*)$ for distance to its permutation class.

Theorem: Suppose $K$ is compact and $P$ has a unique optimal codebook up to permutation. For any sequence $Q_m$ supported on $K$ with $W_1(P,Q_m)\to 0$, every choice $C_m\in\mathcal{C}_{Q_m}^*$ satisfies $\Delta(C_m,C_P^*)\to 0$.

Proof. By the minimum-distortion bound, $R_{Q_m}^*\to R_P^*$. For each $m$, optimality under $Q_m$ and the fixed-codebook bound give

R_P(C_m) \leq R_{Q_m}(C_m)+2DW_1(P,Q_m) =R_{Q_m}^*+2DW_1(P,Q_m) \leq R_P^*+4DW_1(P,Q_m).

Since $R_P(C_m)\geq R_P^*$, the excess $R_P(C_m)-R_P^*$ tends to zero. If the claimed convergence failed, some subsequence would have $\Delta(C_m,C_P^*)\geq\varepsilon$ for a fixed $\varepsilon>0$. Compactness of $K^k$ gives a further subsequence converging to a codebook $C_\infty$. Continuity of $R_P$ and the vanishing excess imply $R_P(C_\infty)=R_P^*$. Uniqueness up to permutation then gives $\Delta(C_\infty,C_P^*)=0$, contradicting the lower bound $\varepsilon$ along that subsequence. $\square$

Uniqueness ensures qualitative convergence, but does not itself give a rate for center error. A quadratic-growth condition supplies one. In the following statement it is assumed only in a neighborhood of the optimum, which suffices once qualitative convergence has been established.

Theorem: Under the compactness and uniqueness assumptions above, suppose there are $r>0$ and $\lambda>0$ such that $$ R_P(C)-R_P^*\geq\lambda\Delta(C,C_P^*)^2 \quad\text{whenever }\Delta(C,C_P^*)\leq r. $$ Then for all sufficiently large $m$, every $C_m\in\mathcal{C}_{Q_m}^*$ satisfies $$ \Delta(C_m,C_P^*)\leq \sqrt{\frac{4D W_1(P,Q_m)}{\lambda}}. $$

Proof. The preceding theorem implies that eventually $\Delta(C_m,C_P^*)\leq r$. The excess-risk inequality proved there and the assumed quadratic growth therefore give

\lambda\Delta(C_m,C_P^*)^2 \leq R_P(C_m)-R_P^* \leq 4DW_1(P,Q_m).

Divide by $\lambda>0$ and take nonnegative square roots to obtain the result. $\square$

Worked Example: Exact Center and Risk Changes for One Center

Let $K=[0,3]$, $k=1$, and let $P$ put probability $1/2$ at each of 0 and 2. Let $Q$ put probability $1/2$ at each of 0 and 2.2. The coupling that leaves the first atom fixed and moves the second by 0.2 has cost $0.5(0)+0.5(0.2)=0.1$; it is optimal, so $W_1(P,Q)=0.1$.

For two equally weighted points $a,b$, squared-error distortion is minimized at their mean $(a+b)/2$, and the minimum is $(b-a)^2/4$. This follows by expanding

\frac{(a-c)^2+(b-c)^2}{2} =\left(c-\frac{a+b}{2}\right)^2+\frac{(b-a)^2}{4}.

Thus $P$'s optimal center is 1 and its minimum distortion is 1. $Q$'s optimal center is 1.1 and its minimum distortion is $2.2^2/4=1.21$. The center moves by 0.1 and the minimum distortion increases by 0.21. The general distortion bound is $2DW_1=2(3)(0.1)=0.6$, which correctly bounds that increase. Moreover, for $P$, excess distortion at center $c$ is exactly $(c-1)^2$, so the quadratic-growth condition holds with $\lambda=1$.

When the Optimum Is Not Identifiable

Without uniqueness, compactness still prevents optimal codebooks from escaping, and the excess-risk argument still shows that their $P$-distortion approaches $R_P^*$. Every convergent subsequence of perturbed optima therefore has a limit in $\mathcal{C}_P^*$. What can fail is convergence to one preselected member of that set: a small change in distribution can select a different optimum.

Worked Example: Small Perturbations Select Different Optima

On $K=[0,1]$, take $k=2$ and $P=\delta_0$. Every codebook containing 0 has zero distortion under $P$, including $C_P=(0,0)$ and $(0,1)$. Hence $P$ has many optimal codebooks. For $0<\varepsilon<1$, let $Q_\varepsilon=(1-\varepsilon)\delta_0+\varepsilon\delta_1$. The coupling that moves only the $\varepsilon$ mass from 0 to 1 has cost $\varepsilon$, so $W_1(P,Q_\varepsilon)=\varepsilon$.

The codebook $(0,1)$ has zero distortion under $Q_\varepsilon$, and is therefore optimal. Choosing it for every $\varepsilon$ gives a sequence of perturbed optima whose distance from the particular representative $(0,0)$, even after the best permutation, is 1. Thus convergence to that selected representative is false. The chosen codebook is still optimal for $P$; what fails is identification of a unique target.

Common Mistake and Practical Interpretation

Mistake: concluding that a small Wasserstein distance forces every optimal center to be close to one arbitrarily chosen optimum. The risk bound controls objective values, not center locations by itself. Distinct optima can have the same risk, as in the two-center point-mass example.
Correction: First establish compactness and convergence to the optimal set. To conclude convergence to a particular permutation class, require uniqueness. To obtain a quantitative center bound, also require a growth condition such as quadratic growth near that optimum.
Mistake: comparing centers by their labels. Reordering an unchanged codebook can produce a large coordinate-wise difference. Use a permutation-invariant distance such as $\Delta$.

The compact-support assumption also makes the constants and existence argument transparent: all observations and centers lie within diameter $D$. For $W_2$, the same conclusions follow from $W_1(P,Q)\leq W_2(P,Q)$ when the distributions have finite second moments, by the Cauchy–Schwarz inequality applied to any coupling and then taking infima. Thus the distortion difference is at most $2D W_2(P,Q)$ as well. These bounds explain two distinct forms of robustness: a small distributional perturbation controls the optimal distortion value directly, while reliable center recovery additionally depends on how distinctly the original distribution identifies its optimum.

Check Your Understanding

Use the definitions and conditions in this tutorial to answer the following.

Why is the squared-distance loss for a fixed codebook $2D$-Lipschitz on $K$?
Which part of the proof that optimal codebooks exist uses compactness, and which part uses continuity?
What conclusion about perturbed optimal codebooks remains valid if $P$ has multiple optima?
How does a quadratic-growth condition turn an excess-distortion bound into a center-error bound?
In the two-center point-mass example, why does the sequence of perturbed optima fail to converge to the selected representative $(0,0)$, even though every limit is optimal for $P$?