Proof Workshop for Quantizer Consistency

Why a Consistency Proof Needs Several Checks

For a fixed number \(K\) of centers, empirical quantization chooses a codebook that makes the observed distortion small. Consistency asks whether such a codebook also performs nearly optimally under the population distribution. A proof must connect two different objectives, the empirical risk and the population risk, and must account for the possibility that the population optimum is not unique.

The argument has four essential parts: the feasible codebook space is compact; empirical risk converges uniformly to population risk on that space; the selected codebook approximately minimizes empirical risk; and population risk is separated from its minimum away from the full minimizing set. The last step is what converts small excess risk into proximity to an optimum.

Setup and Definitions

Let \(X_1,\ldots,X_n\) be independent and identically distributed random vectors in \(\mathbb{R}^d\), with common distribution \(P\). Assume there is a nonempty compact set \(C\subset\mathbb{R}^d\) such that \(P(X\in C)=1\). Both observations and centers are restricted to \(C\), and \(K\geq 1\) is fixed. An ordered codebook is \(c=(c_1,\ldots,c_K)\in C^K\). For squared Euclidean distortion, define

Here \(R(c)\) is the population risk and \(R_n(c)\) is the empirical risk. Write \(R^*=\inf_{c\in C^K}R(c)\), and define the population minimizing set

Use the product maximum metric \(\|c-c'\|_{\max}=\max_j\|c_j-c'_j\|\), and let \(\operatorname{dist}(c,\mathcal{M})=\inf_{m\in\mathcal{M}}\|c-m\|_{\max}\). This distance treats the ordered coordinates as written; if permuting centers gives an equivalent codebook, the minimizing set includes those permutations.

Compactness and Uniform Convergence

Let \(D=\sup_{x,y\in C}\|x-y\|\), which is finite by compactness. The distortion is bounded by \(D^2\). It also varies continuously with the codebook, uniformly over \(x\in C\). Indeed, for \(u,v,x\in C\), \(|\|x-u\|^2-\|x-v\|^2|\leq 2D\|u-v\|\). The difference between two minima is at most the largest difference between corresponding entries, so

Taking expectations shows that \(R\) is continuous. Since \(C^K\) is compact, \(R\) attains its minimum and \(\mathcal{M}\) is nonempty and compact.

Proof. Fix a positive tolerance \(a\). For any \(\eta>0\), compactness of \(C^K\) gives a finite \(\eta\)-net \(c^{(1)},\ldots,c^{(J)}\) in the product maximum metric. For any \(c\), choose a net point \(c^{(j)}\) with \(\|c-c^{(j)}\|_{\max}\leq\eta\). The Lipschitz bound, applied once to the empirical average and once to the expectation, gives

If \(D=0\), every observation and center coincide and the result is immediate. Otherwise choose \(\eta\) so that \(4D\eta<a/2\). At each of the finitely many net points, \(\rho_{c^{(j)}}(X_i)\) are independent, identically distributed, and bounded random variables. The weak law of large numbers therefore implies \(P(|R_n(c^{(j)})-R(c^{(j)})|>a/2)\to0\). A union bound over the \(J\) points shows that the maximum of these deviations exceeds \(a/2\) with probability tending to zero. The displayed inequality then bounds the supremum by \(a\) except on an event whose probability tends to zero. The supremum is measurable: the risk difference is continuous in \(c\), so its supremum over the compact space equals its supremum over a countable dense subset. This proves the claim. \(\square\)

Separation and the Consistency Argument

Uniform convergence alone does not say that low-risk codebooks must be close to an optimum. The required bridge is a separation property: for any fixed positive distance from \(\mathcal{M}\), population risk must exceed \(R^*\) by a positive amount. Here that property follows from compactness and continuity, not from an additional curvature assumption.

Proof. Define \(\Delta_n=\sup_{c\in C^K}|R_n(c)-R(c)|\). The uniform-convergence result gives \(\Delta_n\xrightarrow{p}0\). For any \(\delta>0\), let \(A_\delta=\{c\in C^K:\operatorname{dist}(c,\mathcal{M})\geq\delta\}\). The distance to a nonempty compact set is continuous, so \(A_\delta\) is compact. If it is nonempty, continuity of \(R\) gives a minimum of \(R\) on \(A_\delta\). This minimum is strictly greater than \(R^*\): equality would put a minimizer in \(A_\delta\), contradicting its distance of at least \(\delta\) from \(\mathcal{M}\). Thus there is a number \(\gamma_\delta>0\) such that

If \(A_\delta\) is empty, the event \(\operatorname{dist}(\hat c_n,\mathcal{M})\geq\delta\) is impossible. Otherwise, take any population minimizer \(c^*\in\mathcal{M}\). On the event where \(\hat c_n\in A_\delta\), the approximate-minimization inequality and the definition of \(\Delta_n\) imply

Combining this upper bound with the separation inequality yields \(\varepsilon_n+2\Delta_n\geq\gamma_\delta\). Therefore

This holds for every \(\delta>0\), proving convergence in probability to the minimizing set. \(\square\)

Common Pitfall and Practical Meaning

A common mistake is to conclude that small empirical risk, or even small excess population risk, automatically implies convergence to one particular labelled codebook. The argument proves convergence to \(\mathcal{M}\), which may contain several optima, including permutations of the same centers. A unique-codebook conclusion needs an actual uniqueness condition (or a distance that identifies permutations); it does not follow merely from empirical minimization.

A second mistake is to check empirical convergence only at each fixed codebook and then use it as though it were uniform. A selected \(\hat c_n\) depends on the sample, so pointwise convergence does not by itself control the risk at that random choice. The finite-net argument supplies the uniform control needed in the comparison. Finally, compactness matters twice: it ensures an optimum exists and makes risk levels away from the minimizing set positively separated. Without compactness, a sequence can drift while its risk approaches the infimum, so this separation argument may fail.