Codebook Convergence Under a Unique Optimum

Why Risk Convergence Is Not Yet Center Convergence

In fixed-\(K\) clustering, the risk evaluates a collection of centers by the distance from each observation to its nearest center. If an estimated codebook has risk close to the population minimum, it is natural to expect its centers to be close to the optimal ones. But two details matter. First, nearby risk values imply nearby centers only when the optimum is sufficiently well distinguished from other codebooks. Second, center labels have no statistical meaning: permuting the centers leaves the risk unchanged.

This tutorial makes that implication precise. Compactness prevents sequences of distant codebooks from escaping the parameter space while their risks approach the minimum. Uniqueness of the optimal codebook, allowing for permutations, then ensures that every codebook a fixed distance away has strictly larger risk. The resulting conclusion is convergence after the best possible matching of center labels; it does not assert a rate.

Risk, Codebooks, and Matched Distance

Let \(X\) be a random vector in \(\mathbb{R}^d\) whose distribution is supported on a compact set \(S\). Let \(C\subset\mathbb{R}^d\) be a compact set of allowable center locations, and fix \(K\). A codebook is an ordered tuple \(c=(c_1,\ldots,c_K)\in C^K\). Its squared-distance quantization risk is

The ordering in a tuple is a convenient way to write the centers, not an intrinsic feature of a clustering solution. Write \(\mathfrak{S}_K\) for the set of permutations of \(\{1,\ldots,K\}\), and define the distance between two codebooks after optimal matching by

This distance is zero exactly when the two tuples contain the same centers with the same multiplicities, possibly in a different order. In particular, \(d_{\mathrm{match}}\) is the relevant measure of center error when a codebook is identified only up to permutation.

The compactness assumptions make the risk continuous on \(C^K\), so its minimum is attained. For continuity, if \(c^{(m)}\to c\), then the function \(x\mapsto\min_j\|x-c_j^{(m)}\|^2\) converges uniformly on compact \(S\) to \(x\mapsto\min_j\|x-c_j\|^2\); taking expectations therefore preserves the limit. The result below concerns any measurable, possibly data-dependent codebook \(\hat c_n\in C^K\), and uses its population excess risk \(R(\hat c_n)-R_*\).

A Positive Risk Gap Away From the Optimum

The key step is stronger than saying that the optimum is unique. It says that every codebook at least a fixed positive distance from the optimal codebook has risk bounded away from the minimum by a positive amount. Compactness is what makes the bound uniform over all such codebooks.

Proof. Fix \(\varepsilon>0\), and let \(A_\varepsilon=\{c\in C^K:d_{\mathrm{match}}(c,c^*)\geq\varepsilon\}\). The matched distance is continuous: it is the minimum of finitely many continuous functions, one for each permutation. Thus \(A_\varepsilon\) is closed in compact \(C^K\), and hence compact. If \(A_\varepsilon\) is empty, the implication holds for any positive \(\eta_\varepsilon\). Otherwise, continuity of \(R\) gives a minimizer \(\tilde c\) of \(R\) on \(A_\varepsilon\). Set \(\eta_\varepsilon=R(\tilde c)-R_*\). This quantity is nonnegative because \(R_*\) is the global minimum. If it were zero, \(\tilde c\) would be a population minimizer, and uniqueness up to permutation would give \(d_{\mathrm{match}}(\tilde c,c^*)=0\), contradicting \(\tilde c\in A_\varepsilon\). Therefore \(\eta_\varepsilon>0\), and every \(c\in A_\varepsilon\) has \(R(c)-R_*\geq\eta_\varepsilon\). \(\square\)

Excess Risk Implies Matched Center Convergence

Proof. Fix any \(\varepsilon>0\). By the lemma, there is \(\eta_\varepsilon>0\) such that whenever \(d_{\mathrm{match}}(\hat c_n,c^*)\geq\varepsilon\), the excess risk is at least \(\eta_\varepsilon\). Thus

The right-hand side converges to zero because the excess risk converges to zero in probability and \(\eta_\varepsilon\) is fixed and positive. This holds for every \(\varepsilon>0\), which is precisely convergence in probability of the matched distance to zero. \(\square\)

Interpretation and a Common Mistake

The result gives a useful way to transfer a risk-consistency statement into a statement about center locations. If an empirical quantizer’s population excess risk vanishes in probability, and the population optimum is unique up to permutation under the compactness conditions above, then its centers become close to the optimal collection. The theorem applies to any estimator satisfying the risk condition; it does not require exact empirical minimization.

• Common mistake: comparing centers in their original order. A tuple may have labels swapped and remain the same codebook. Coordinatewise comparison can then report large error even when the codebooks agree exactly. Use the minimum over permutations in \(d_{\mathrm{match}}\).
• Common mistake: treating low risk as sufficient without uniqueness. The proof relies on a positive risk gap away from the optimal orbit. If a different codebook is also optimal, that gap need not exist for distance from one chosen optimum. Uniqueness up to permutation is a substantive hypothesis, not a consequence of small excess risk.
• Common mistake: reading a rate into the conclusion. The argument establishes convergence, not a bound proportional to the square root of excess risk or any other rate. Such bounds require additional local information about how risk grows near the optimum.

The practical distinction is important: excess risk measures predictive or quantization performance, whereas matched distance measures recovery of center locations. Under the stated conditions, the former guarantees the latter asymptotically, but it does not by itself quantify how quickly the centers approach their targets.