Argmin Consistency for Empirical Quantizers

Why Empirical Minimizers Need a Set-Valued Guarantee

A clustering algorithm minimizes distortion on the observed sample, while the statistical target is to minimize expected distortion under the data distribution. The key question is whether minimizing the sample objective also brings a codebook close to the population optimum. Uniform convergence of the two risks answers this question when the population risk has a positive separation gap away from its minimizing set.

The conclusion is deliberately set-valued. The population risk may have several minimizers, so consistency means approaching the set of all optimal codebooks, not necessarily converging to one preselected codebook. No uniqueness assumption is needed.

Population and Empirical Quantization Risk

Let \(X\) be an \(\mathbb{R}^d\)-valued random vector with distribution \(P\), supported on a compact set \(\mathcal X\). Fix a positive integer \(K\), and take the codebook space to be \(\mathcal C=\mathcal X^K\). A codebook is \(c=(c_1,\ldots,c_K)\). For \(x\in\mathcal X\), its squared quantization distortion is the squared distance to its nearest center:

The population risk is \(R(c)=E[q_c(X)]\). For independent observations \(X_1,\ldots,X_n\) drawn from \(P\), the empirical risk is \(R_n(c)=n^{-1}\sum_{i=1}^n q_c(X_i)\). Write \(R^*=\min_{c\in\mathcal C}R(c)\) and \(\mathcal M=\{c\in\mathcal C:R(c)=R^*\}\). For a codebook \(c\), define its distance to this set by \(d(c,\mathcal M)=\inf_{m\in\mathcal M}\|c-m\|_{\max}\), where \(\|c-m\|_{\max}=\max_{1\le j\le K}\|c_j-m_j\|\).

Compact support gives a compact codebook space and bounded distortions. The earlier result on uniform convergence of bounded-support quantization risks supplies the condition used below:

This is uniform convergence in probability: with probability tending to one, the empirical risk is close to the population risk simultaneously over every codebook. The proof below also uses continuity of \(R\). To see it here, suppose \(\|x\|\le B\) and all codebook centers have norm at most \(B\). For any centers \(a,b\) in the support, \(|\|x-a\|^2-\|x-b\|^2|\le(\|x-a\|+\|x-b\|)\|a-b\|\le4B\|a-b\|\). Taking minima over corresponding centers gives \(|q_c(x)-q_{c'}(x)|\le4B\|c-c'\|_{\max}\), and taking expectations gives the same bound for \(|R(c)-R(c')|\). Thus \(R\) is continuous. Compactness then ensures that \(\mathcal M\) is nonempty and compact.

Separation of the Population Minimizing Set

Continuity and compactness imply a strict risk gap outside any fixed neighborhood of \(\mathcal M\). This deterministic fact is the bridge from uniform risk approximation to consistency of minimizers.

Proof. The distance to a nonempty set is continuous, so \(A_\epsilon\) is closed in the compact space \(\mathcal C\) and is therefore compact. The continuous function \(R(c)-R^*\) attains a minimum on \(A_\epsilon\). If that minimum were zero, some \(c\in A_\epsilon\) would satisfy \(R(c)=R^*\), hence \(c\in\mathcal M\). But then \(d(c,\mathcal M)=0\), contradicting \(d(c,\mathcal M)\ge\epsilon\). The attained minimum is therefore strictly positive; call it \(\Delta_\epsilon\). \(\square\)

Argmin Consistency Theorem

Proof of minimizing-set consistency. Fix \(\epsilon>0\). If \(A_\epsilon\) is empty, then every codebook is within \(\epsilon\) of \(\mathcal M\), so \(P(d(\hat c_n,\mathcal M)\ge\epsilon)=0\). Otherwise, let \(\Delta_\epsilon>0\) be the separation gap from the lemma and define \(\delta_n=\sup_{c\in\mathcal C}|R_n(c)-R(c)|\). Choose any \(m^*\in\mathcal M\). If \(\hat c_n\in A_\epsilon\), then

These inequalities cannot both hold when \(2\delta_n<\Delta_\epsilon\). Therefore \(P(d(\hat c_n,\mathcal M)\ge\epsilon)\le P(\delta_n\ge\Delta_\epsilon/2)\to0\). This holds for every \(\epsilon>0\), proving \(d(\hat c_n,\mathcal M)\xrightarrow{p}0\).

Proof of vanishing excess distortion. The excess is nonnegative because \(R^*\) is the minimum population risk. Again take any \(m^*\in\mathcal M\). By empirical optimality,

Since \(\delta_n\xrightarrow{p}0\), the nonnegative excess distortion also converges to zero in probability. \(\square\)

Common Pitfall and Interpretation

A tempting but incorrect argument is: “The empirical risk converges to the population risk at each fixed codebook, so the empirical minimizer must converge to a population minimizer.” Pointwise convergence alone does not control the risk at a codebook that changes with the sample; a sample-dependent minimizer could exploit a location where the empirical risk is unusually low. The correction is to use uniform convergence, which bounds the discrepancy at every codebook at once, and then use separation to rule out codebooks a fixed distance from the population minimizing set.

The theorem establishes consistency of the optimizing set and vanishing population excess distortion. It does not require a unique population optimum, nor does it assert convergence to a particular representative when several optima exist. Compactness, continuity, and uniform convergence each have a distinct role: they ensure an optimum exists, create a positive gap away from its set, and make the empirical objective uniformly close enough to preserve that gap.