Uniform Convergence of Bounded-Support Quantization Risks

Why Uniform Convergence Matters

For a fixed codebook, the empirical K-means risk is an average of independent observations, so standard laws of large numbers describe its behavior. But a data-based procedure can select its codebook after seeing the sample. To control the risk of such a selected codebook, it is useful to control the empirical-to-population discrepancy simultaneously over the whole candidate class, not just at one fixed codebook.

Bounded support makes squared-distance distortion bounded, while compactness of the codebook class lets us approximate every candidate by a finite collection of representatives. A Lipschitz bound controls the approximation error. Together, these facts give a finite-sample probability bound and an almost-sure uniform convergence result.

Risks and the Codebook Class

Let \(X,X_1,X_2,\ldots\) be independent and identically distributed random vectors in \(\mathbb{R}^d\). Assume \(P(\|X\|\le R)=1\) for some finite \(R\), where \(\|\cdot\|\) is the Euclidean norm. Fix a positive integer \(k\). A codebook is an ordered tuple \(C=(c_1,\ldots,c_k)\) of centers in \(\mathbb{R}^d\). Let \(\Theta\) be a nonempty compact set of codebooks, and suppose every center in every \(C\in\Theta\) satisfies \(\|c_j\|\le A\) for a finite \(A\).

Equip codebooks with the distance \(d_\infty(C,D)=\max_{1\le j\le k}\|c_j-d_j\|\). Compactness ensures that for each \(\varepsilon>0\), there is a finite \(\varepsilon\)-net: a finite set \(\mathcal{N}_\varepsilon\subseteq\Theta\) such that every \(C\in\Theta\) is within distance \(\varepsilon\) of some \(D\in\mathcal{N}_\varepsilon\). Write \(N(\varepsilon)=|\mathcal{N}_\varepsilon|\) for the size of a chosen net.

A Lipschitz Bound for Distortion

The key regularity fact is that moving every center a small amount changes the distortion by at most a constant times that amount. For any \(x\) with \(\|x\|\le R\) and any centers \(c,d\) with norms at most \(A\), the difference of squared distances obeys

For two lists of real numbers \((a_j)\) and \((b_j)\), \(|\min_j a_j-\min_j b_j|\le\max_j|a_j-b_j|\): each list's minimum is no farther from the other minimum than the largest coordinatewise difference. Applying this fact to the squared distances gives the bound below.

The last two inequalities follow by taking expectations and sample averages, respectively, of the pointwise bound. The distortion is also bounded: since \(\|x-c_j\|\le R+A\), we have \(0\le g_C(x)\le B\), where \(B=(R+A)^2\).

Finite-Net Bound and Uniform Convergence

For a fixed net, deviations at its finitely many codebooks can be controlled with Hoeffding's inequality. In the form used here, if \(Y_1,\ldots,Y_n\) are independent, identically distributed random variables in \([0,B]\), then for \(u>0\), \(P(|n^{-1}\sum_iY_i-E[Y_1]|>u)\le2\exp(-2nu^2/B^2)\). For each fixed \(D\), the variables \(g_D(X_i)\) meet these conditions.

To prove the bound, fix \(C\in\Theta\) and choose \(D\in\mathcal{N}_\varepsilon\) with \(d_\infty(C,D)\le\varepsilon\). The Lipschitz lemma and the triangle inequality give

Thus, if the supremum over \(C\) exceeds \(2L\varepsilon+u\), some net point \(D\) must have \(|R_n(D)-R(D)|>u\). Apply Hoeffding's inequality at each net point and add the resulting probabilities over the \(N(\varepsilon)\) points. This proves the displayed bound.

The bound separates two sources of error. The term \(2L\varepsilon\) is the price of replacing the full class by a net; the exponential term controls random deviations on that finite net. For convergence in probability, choose \(\varepsilon\) small enough to make \(2L\varepsilon\) small, then let \(n\) grow so the finite-net probability tends to zero.

The same assumptions also yield almost-sure uniform convergence. We give the argument because it explains why pointwise laws of large numbers can be upgraded to a statement over the entire compact class.

Proof. For each positive integer \(m\), choose a finite \(1/m\)-net \(\mathcal{N}_m\). The union of these nets is countable. For each fixed \(D\) in this union, \(g_D(X_i)\) are iid and bounded, so the strong law of large numbers gives \(R_n(D)\to R(D)\) almost surely. A countable intersection of probability-one events still has probability one; on that event, convergence holds simultaneously for every net point in every \(\mathcal{N}_m\).

Fix an outcome in this event and an integer \(m\). For any \(C\in\Theta\), choose a net point \(D\in\mathcal{N}_m\) within \(1/m\). The same triangle inequality as above gives

Because \(\mathcal{N}_m\) is finite and convergence holds at each of its points, the maximum on the right tends to zero as \(n\to\infty\). Therefore the limit superior of the left side is at most \(2L/m\) for every positive integer \(m\). Letting \(m\to\infty\) shows that this nonnegative limit superior is zero. The uniform discrepancy consequently converges to zero almost surely. \(\square\)

The supremum in this statement is measurable: for each sample, \(R_n(C)-R(C)\) is Lipschitz in \(C\), and compact \(\Theta\) has a countable dense subset. The supremum of its absolute value over \(\Theta\) equals the supremum over that countable subset, which is a measurable random variable.

Common Pitfall and Practical Meaning

Pitfall: Proving \(R_n(C)\to R(C)\) for every fixed \(C\) and then concluding that \(\sup_{C\in\Theta}|R_n(C)-R(C)|\to0\) is not justified by pointwise convergence alone. The codebook at which the largest discrepancy occurs may vary with the sample and with \(n\). The correction is to control the whole class: compactness supplies finite nets, and the Lipschitz bound transfers control from net points to every codebook.

The result is useful whenever a candidate codebook is chosen by minimizing the empirical objective: uniform risk control applies even when that candidate depends on the observed data. It does not, by itself, identify which population minimizer is selected or establish convergence of the codebook centers; those require additional arguments. The assumptions also matter: unbounded support removes the simple uniform bound \(B\), and a noncompact candidate class need not have finite nets at a fixed resolution.