Nonunique Population Minima and Set-Valued Consistency

Why Consistency Must Target a Set

An empirical clustering procedure can be statistically consistent even when its codebook does not settle on one particular arrangement of centers. A population distribution may admit several distinct codebooks with exactly the same minimum distortion. Sampling fluctuations or the optimization procedure can select different members of this collection at different sample sizes. In that setting, asking whether the estimator converges to one prescribed codebook is generally too strong. The appropriate target is the entire set of population minimizers.

We make this precise for squared-distance quantization. Let $K$ be a compact subset of $\mathbb{R}^d$, let $k$ be a positive integer, and represent a codebook by an ordered tuple $c=(c_1,\ldots,c_k)$ in $\mathcal{C}=K^k$. For an observation $x$, its squared-distance loss is the squared distance to its nearest center. We assume the distribution of $X$ is supported on $K$, and define the population risk $D(c)$ and its empirical counterpart $D_n(c)$ below.

\gamma(x,c)=\min_{1\leq j\leq k}\|x-c_j\|^2,\qquad D(c)=E[\gamma(X,c)],\qquad D_n(c)=\frac{1}{n}\sum_{i=1}^n\gamma(X_i,c).

The observations $X_1,\ldots,X_n$ are assumed independent and identically distributed with the same distribution as $X$. The argument also applies under any conditions that provide the uniform convergence stated below. Write $D^*=\min_{c\in\mathcal{C}}D(c)$. We use the product Euclidean metric on $\mathcal{C}$, so $\|c-c'\|^2=\sum_{j=1}^k\|c_j-c'_j\|^2$.

Definition: The population-optimal set is $$ \mathcal{C}^*=\{c\in\mathcal{C}:D(c)=D^*\}. $$ For any $c\in\mathcal{C}$, its distance to this set is $$ \operatorname{dist}(c,\mathcal{C}^*)=\inf_{c^*\in\mathcal{C}^*}\|c-c^*\|. $$ An estimator $\hat c_n$ is set-valued consistent if $\operatorname{dist}(\hat c_n,\mathcal{C}^*)\xrightarrow{p}0$.

The estimator $\hat c_n$ is still a codebook; “set-valued” describes its target, not the estimator’s output. The definition allows the estimator to approach any member of $\mathcal{C}^*$. It does not require its chosen member to be the same at every sample size.

What Compactness Gives

On a compact support, the parameter space $\mathcal{C}=K^k$ is compact. The loss $\gamma(x,c)$ is continuous in $c$: each squared distance is continuous, and the minimum of finitely many continuous functions is continuous. It is also bounded when both $x$ and the centers lie in $K$. Consequently, $D$ is continuous, and a population minimum is attained. These facts ensure that $\mathcal{C}^*$ is nonempty and compact.

The key implication is stronger than merely saying that minimizers exist: any codebook a fixed positive distance from $\mathcal{C}^*$ must have a strictly larger risk. This is a qualitative separation statement; it does not assert a particular rate or a quadratic lower bound.

Theorem: Suppose $\mathcal{C}$ is compact and $D:\mathcal{C}\to\mathbb{R}$ is continuous, with nonempty minimizer set $\mathcal{C}^*$. For every $\varepsilon>0$ such that $$ A_\varepsilon=\{c\in\mathcal{C}:\operatorname{dist}(c,\mathcal{C}^*)\geq\varepsilon\} $$ is nonempty, there is a number $\gamma_\varepsilon>0$ for which $$ D(c)-D^*\geq\gamma_\varepsilon\quad\text{for every }c\in A_\varepsilon. $$

Proof. The distance function is continuous: for any $c,c'$, the triangle inequality gives $\operatorname{dist}(c,\mathcal{C}^*)\leq\|c-c'\|+\operatorname{dist}(c',\mathcal{C}^*)$, and reversing $c,c'$ bounds the absolute difference of the two distances by $\|c-c'\|$. Thus $A_\varepsilon$ is closed in compact $\mathcal{C}$, so it is compact. The continuous function $D(c)-D^*$ attains its minimum on $A_\varepsilon$. That minimum cannot be zero: if it were, a point attaining it would belong to $\mathcal{C}^*$, whose distance to itself is zero, contradicting membership in $A_\varepsilon$. Its minimum is therefore a positive number $\gamma_\varepsilon$, proving the claim. $\square$

The theorem converts a statement about risk into one about location. If the excess risk $D(c)-D^*$ is small enough, $c$ cannot be far from the optimal set. The size of $\gamma_\varepsilon$ can depend on $\varepsilon$ and the problem; without further assumptions, the theorem supplies no explicit rate.

Worked Example: Two Distinct Optimal Codebooks

Let $X$ take the values $-2,0,2$, each with probability $1/3$, and take $k=2$ with codebooks in $K=[-2,2]$. Consider $c^{(1)}=(-2,1)$. The nearest-center losses at $-2,0,2$ are $0,1,1$, respectively, so $$ D(c^{(1)})=\frac{0+1+1}{3}=\frac{2}{3}. $$ For $c^{(2)}=(-1,2)$, the losses are $1,1,0$, giving $D(c^{(2)})=2/3$ as well.

To check optimality, assign each of the three support points to a nearest center. At least two points must be assigned to the same center. For any two equally weighted points $a,b$, the smallest possible sum of their squared distances to one common center is attained at their midpoint: $$ \min_z\{(a-z)^2+(b-z)^2\}=\frac{(a-b)^2}{2}. $$ After multiplying by their probabilities $1/3$, assigning an adjacent pair (distance $2$) contributes at least $2/3$ to risk. Assigning the pair $-2,2$ contributes at least $8/3$. Since all other contributions are nonnegative, no codebook has risk below $2/3$. Both codebooks are therefore optimal and distinct, so $\mathcal{C}^*$ contains more than one point.

Consistency for Approximate Empirical Minimizers

Let $\hat c_n$ be a measurable codebook-valued estimator. It need not be an exact empirical minimizer. Suppose its optimization error is represented by a nonnegative random variable $r_n$ satisfying $$ D_n(\hat c_n)\leq\inf_{c\in\mathcal{C}}D_n(c)+r_n, \qquad r_n\xrightarrow{p}0. $$ Also suppose that the empirical risk converges uniformly in probability to the population risk: $$ \Delta_n=\sup_{c\in\mathcal{C}}|D_n(c)-D(c)|\xrightarrow{p}0. $$ For bounded-support squared-distance quantization, this is the uniform convergence result established in the earlier material on quantization risks. Here it is the input to the set-valued consistency argument.

Theorem: Under the compactness and continuity conditions above, if $\Delta_n\xrightarrow{p}0$ and $\hat c_n$ satisfies the approximate-minimization inequality with $r_n\xrightarrow{p}0$, then $$ \operatorname{dist}(\hat c_n,\mathcal{C}^*)\xrightarrow{p}0. $$

Proof. Since $D$ attains its minimum, choose any $c^*\in\mathcal{C}^*$. By the definition of $\Delta_n$, for every codebook $c$, $D(c)\leq D_n(c)+\Delta_n$ and $D_n(c)\leq D(c)+\Delta_n$. Therefore, sample by sample,

\begin{aligned} D(\hat c_n) &\leq D_n(\hat c_n)+\Delta_n\\ &\leq \inf_{c\in\mathcal{C}}D_n(c)+r_n+\Delta_n\\ &\leq D_n(c^*)+r_n+\Delta_n\\ &\leq D(c^*)+r_n+2\Delta_n\\ &=D^*+r_n+2\Delta_n. \end{aligned}

Because $\hat c_n\in\mathcal{C}$, its risk is at least $D^*$. Hence $0\leq D(\hat c_n)-D^*\leq r_n+2\Delta_n$, and the right-hand side converges to zero in probability. Fix $\varepsilon>0$. If $A_\varepsilon$ is empty, the distance is always less than $\varepsilon$. Otherwise, the separation theorem gives $\gamma_\varepsilon>0$. On the event that $\operatorname{dist}(\hat c_n,\mathcal{C}^*)\geq\varepsilon$, it follows that $D(\hat c_n)-D^*\geq\gamma_\varepsilon$. Thus $$ P\{\operatorname{dist}(\hat c_n,\mathcal{C}^*)\geq\varepsilon\} \leq P\{r_n+2\Delta_n\geq\gamma_\varepsilon\} \longrightarrow 0. $$ This holds for every $\varepsilon>0$, which is exactly convergence in probability of the distance to zero. $\square$

The proof has two distinct ingredients. Uniform convergence and approximate minimization make the population excess risk small; compactness and continuity ensure that small excess risk forces proximity to the optimal set. The optimization tolerance must vanish in probability, but it need not be identically zero.

Worked Example: Applying the Risk Bound

Suppose that, for a given sample, $\Delta_n\leq 0.03$, and the algorithm returns a codebook with $r_n\leq 0.02$. The proved inequality gives $$ D(\hat c_n)-D^*\leq r_n+2\Delta_n \leq 0.02+2(0.03)=0.08. $$ If the separation gap for codebooks at least $\varepsilon=0.5$ from $\mathcal{C}^*$ is $\gamma_{0.5}=0.10$, then this output cannot be at least $0.5$ from the optimal set: such a codebook would have excess risk at least $0.10$, contradicting the upper bound $0.08$. The conclusion uses the specified gap; a small excess-risk bound alone does not give a numerical distance without such information.

Label Switching and Failure of Representative Convergence

Our codebooks are ordered tuples, so permuting the centers can produce distinct points in $\mathcal{C}$ with the same risk. If $c=(c_1,\ldots,c_k)$ and $\pi$ is a permutation of $\{1,\ldots,k\}$, then the nearest-center loss is unchanged by replacing $c$ with $(c_{\pi(1)},\ldots,c_{\pi(k)})$. Consequently, whenever one ordered codebook is optimal, all its label permutations are optimal too. The optimal set automatically includes these alternatives.

Worked Example: An Alternating Sequence of Exact Optima

Use the distribution and two codebooks from the first example. Suppose an estimator returns $c^{(1)}=(-2,1)$ for even $n$ and $c^{(2)}=(-1,2)$ for odd $n$. Each returned codebook has population risk $2/3=D^*$, so its distance to $\mathcal{C}^*$ is zero for every $n$. The sequence does not converge to either displayed codebook: along even sample sizes it equals $c^{(1)}$, while along odd sample sizes it equals the distinct $c^{(2)}$. Thus set-valued consistency can hold even when convergence to a selected representative fails.

If the center labels alone are switched, a distance that minimizes over permutations can also be useful for describing unlabeled codebooks. But with the ordered-tuple metric used here, no special adjustment is needed for the theorem: all label permutations are members of $\mathcal{C}^*$, and the distance is already measured to the full set.

Common Pitfall and Practical Meaning

A common mistake is to prove that the empirical risk is close to its minimum and then conclude that the estimator converges to a particular population-optimal codebook. The risk comparison only implies that the estimator approaches the set of all minimizers. In the presence of multiple optima, there may be no statistical or mathematical basis for preferring one representative, and an empirical procedure can alternate among equivalent alternatives.

Set-valued consistency is a meaningful conclusion: it rules out codebooks that remain a fixed positive distance from every population optimum. A stronger claim—convergence to a specific representative—requires additional structure, such as a unique optimum under the chosen parameterization or an explicit rule for selecting among minimizers. The compactness argument itself provides neither that rule nor a rate of convergence.

Check Your Understanding

Use the definitions and arguments above to answer these questions.

Why is the distance to the full minimizer set an appropriate target when the population risk has several global minimizers?
Which parts of the consistency proof use uniform convergence, and which use compactness and continuity?
Explain why the separation gap for a fixed $\varepsilon$ need not provide a rate for $\operatorname{dist}(\hat c_n,\mathcal{C}^*)$.
If $r_n$ does not converge to zero, which step in the excess-risk bound prevents the stated theorem from applying?
Why does including label permutations in $\mathcal{C}^*$ avoid requiring convergence to one arbitrary ordering of the centers?