Unbounded Supports and Moment Conditions

Why Unbounded Support Changes the Argument

For observations on a bounded set, squared distances to a bounded collection of centers are uniformly bounded. On an unbounded support, extreme observations can contribute very large losses, so arguments based on bounded losses no longer apply directly. The central question is whether the distribution’s tails are sufficiently controlled for the population risk to be finite and the empirical risk to approximate it.

For squared-distance clustering, a finite second moment is the basic threshold: it makes the risk of every fixed finite codebook finite. It also provides an integrable envelope for codebooks whose centers lie in a fixed bounded region. Higher moments can give explicit rates at which tail contributions vanish. These facts do not, by themselves, guarantee that unrestricted empirical centers remain bounded; that distinction matters when turning risk convergence into convergence of codebooks.

Definition: Let $X$ take values in $\mathbb{R}^d$, and let $C=(c_1,\ldots,c_K)$ be a codebook of $K$ centers. Its squared-distance loss at $x$ is $$ \phi_C(x)=\min_{1\le j\le K}\|x-c_j\|^2. $$ The population distortion is $R(C)=E[\phi_C(X)]$. For independent, identically distributed observations $X_1,\ldots,X_n$ with distribution $P$, the empirical distortion is $$ R_n(C)=\frac{1}{n}\sum_{i=1}^n\phi_C(X_i). $$ A finite second moment means $E\|X\|^2<\infty$.

A simple sufficient bound explains the role of the second moment. For any fixed center $c$, $\phi_C(x)\leq\|x-c\|^2\leq 2\|x\|^2+2\|c\|^2$, since the nearest-center loss cannot exceed the loss to $c$. Thus $E\|X\|^2<\infty$ implies $R(C)<\infty$ for every finite codebook. In fact, it is also necessary for finite risk at any finite codebook: if all centers have norm at most $A$, then $\phi_C(x)\geq(\|x\|-A)_+^2$, where $u_+=\max(u,0)$. Finiteness of this lower bound’s expectation implies a finite second moment, because $\|x\|^2$ is bounded on $\{\|x\|\leq 2A\}$ and is at most $4(\|x\|-A)^2$ when $\|x\|>2A$.

What Moment Assumptions Say About the Tails

Finite second moment is enough to make the expected squared-loss contribution from sufficiently extreme observations vanish. For $T>0$, the events $\{\|X\|>T\}$ decrease to the empty set as $T$ increases, and the integrable random variable $\|X\|^2$ dominates $\|X\|^2\mathbf{1}_{\{\|X\|>T\}}$. The dominated convergence theorem therefore gives

E\!\left[\|X\|^2\mathbf{1}_{\{\|X\|>T\}}\right]\longrightarrow 0.

A higher moment gives a quantitative bound. If $E\|X\|^{2+\delta}<\infty$ for some $\delta>0$, then on $\{\|X\|>T\}$, $\|X\|^2\leq \|X\|^{2+\delta}/T^\delta$. Consequently,

E\!\left[\|X\|^2\mathbf{1}_{\{\|X\|>T\}}\right] \leq \frac{E\|X\|^{2+\delta}}{T^\delta}.

This inequality is useful for choosing a truncation threshold or bounding a tail remainder. It is a sufficient rate bound, not a requirement that every distribution have a moment strictly higher than two.

Worked Example: A Pareto Tail and the Second-Moment Threshold

Let $X$ be positive with density $f(x)=\alpha x^{-\alpha-1}$ for $x\geq1$, where $\alpha>0$. The density integrates to one because $\int_1^\infty \alpha x^{-\alpha-1}\,dx=1$. Find when squared-distance risk is finite, and calculate its tail contribution when it is finite.

The second moment is $$ E[X^2]=\int_1^\infty x^2\alpha x^{-\alpha-1}\,dx =\alpha\int_1^\infty x^{1-\alpha}\,dx. $$ This integral is finite exactly when $\alpha>2$, in which case it equals $\alpha/(\alpha-2)$. Thus, for $\alpha\leq2$, even a single fixed center has infinite expected squared loss; for $\alpha>2$, every finite codebook has finite distortion.

For $T\geq1$ and $\alpha>2$, the contribution beyond $T$ is $$ E[X^2\mathbf{1}_{\{X>T\}}] =\alpha\int_T^\infty x^{1-\alpha}\,dx =\frac{\alpha}{\alpha-2}T^{2-\alpha}. $$ For example, with $\alpha=3$, this is $3/T$. The tail contribution tends to zero, but only at an inverse-linear rate in this case.

Uniform Convergence on Bounded Codebook Sets

For $M>0$, consider codebooks whose centers all lie in the closed ball $B_M=\{c:\|c\|\leq M\}$. The losses are still unbounded as functions of $x$, but they share an integrable envelope:

0\leq \phi_C(x)\leq(\|x\|+M)^2 \leq 2\|x\|^2+2M^2,\qquad C\in B_M^K.

The final expression has finite expectation under the second-moment assumption. The following result shows how that bound supports a uniform law of large numbers without assuming bounded observations.

Theorem: Suppose $X_1,X_2,\ldots$ are independent and identically distributed and $E\|X\|^2<\infty$. For fixed $M<\infty$ and fixed $K$, $$ \sup_{C\in B_M^K}|R_n(C)-R(C)|\xrightarrow{a.s.}0. $$

Proof. For codebooks $C=(c_j)$ and $D=(d_j)$ in $B_M^K$, let $\rho=\max_j\|c_j-d_j\|$. The difference between the minima of two finite lists is bounded by the largest difference between corresponding entries. Also, \[ \big|\|x-c_j\|^2-\|x-d_j\|^2\big| \leq \|c_j-d_j\|(\|x-c_j\|+\|x-d_j\|) \leq 2\rho(\|x\|+M). \] It follows that $|\phi_C(x)-\phi_D(x)|\leq2\rho(\|x\|+M)$. The random variable $\|X\|+M$ is integrable: $E\|X\|\leq (E\|X\|^2)^{1/2}$.

For any $\varepsilon>0$, compactness of $B_M^K$ gives a finite $\rho_0$-net $C_1,\ldots,C_q$ in the metric $\max_j\|c_j-d_j\|$. Choose $\rho_0$ small enough that $2\rho_0 E(\|X\|+M)<\varepsilon/4$. The strong law of large numbers applies to each $\phi_{C_l}(X_i)$, which has finite expectation, and to $\|X_i\|+M$. Since there are finitely many net points, almost surely, for all sufficiently large $n$, each net-point risk difference is below $\varepsilon/2$, and $n^{-1}\sum_i(\|X_i\|+M)\leq E(\|X\|+M)+1$. Decreasing $\rho_0$ further if necessary makes the resulting empirical and population approximation errors from the net each smaller than $\varepsilon/4$. For any $C$, select a net point within $\rho_0$; the Lipschitz bound controls both $R_n(C)-R_n(C_l)$ and $R(C)-R(C_l)$. Adding these two errors and the net-point error gives a bound below $\varepsilon$, uniformly over $C$. This holds almost surely for every $\varepsilon>0$, proving the assertion. $\square$

Worked Example: A Fourth Moment Gives an Explicit Tail Bound

Suppose $X\sim N(0,\sigma^2)$ is scalar. Its fourth moment is $E[X^4]=3\sigma^4$. For any $T>0$, on $\{|X|>T\}$ we have $X^2\leq X^4/T^2$. Therefore $$ E[X^2\mathbf{1}_{\{|X|>T\}}] \leq \frac{E[X^4]}{T^2} =\frac{3\sigma^4}{T^2}. $$ For $\sigma=2$ and $T=10$, this bound is $3(2^4)/10^2=48/100=0.48$. It is an upper bound, not the exact Gaussian tail contribution. The calculation shows how a fourth-moment assumption supplies a concrete truncation guarantee.

Consistency on a Compact Parameter Space

Uniform convergence becomes a consistency result when the parameter space is compact and the population risk has a well-separated minimizing set. For clarity, first consider a compact set $\Theta\subseteq B_M^K$ of allowed codebooks. Write $R_*=\min_{C\in\Theta}R(C)$ and $\Theta_*=\{C\in\Theta:R(C)=R_*\}$. The risk is continuous on $\Theta$: the Lipschitz bound in the proof above gives $|R(C)-R(D)|\leq2\rho E(\|X\|+M)$. Thus the minimum exists and $\Theta_*$ is nonempty and compact.

Theorem: Under the assumptions of the preceding theorem, let $\hat C_n$ minimize $R_n(C)$ over compact $\Theta$. Then the empirical excess risk $R(\hat C_n)-R_*$ converges almost surely to zero. In addition, for every open set $U$ containing $\Theta_*$, $\hat C_n\in U$ eventually almost surely.

Proof. Set $\Delta_n=\sup_{C\in\Theta}|R_n(C)-R(C)|$, which tends to zero almost surely by uniform convergence. For any population minimizer $C_*\in\Theta_*$, empirical optimality gives

R(\hat C_n)\leq R_n(\hat C_n)+\Delta_n \leq R_n(C_*)+\Delta_n \leq R_*+2\Delta_n.

Since $R(\hat C_n)\geq R_*$, its excess risk tends to zero. For the location claim, $\Theta\setminus U$ is compact and disjoint from $\Theta_*$. If it is nonempty, continuity and compactness imply that $R$ attains a minimum there, and that minimum exceeds $R_*$ by some $\eta>0$. Once $2\Delta_n<\eta$, the excess-risk bound rules out $\hat C_n\in\Theta\setminus U$. If the complement is empty, the claim holds automatically. $\square$

Worked Example: One-Center Empirical Quantization

Let $X$ have the Pareto distribution in the earlier example with $\alpha=3$, and take $K=1$. Direct integration gives $E[X]=3/2$ and $E[X^2]=3$, so the population risk at center $c$ is $$ R(c)=E[(X-c)^2]=3-3c+c^2 =(c-3/2)^2+3/4. $$ The unique population-optimal center is $3/2$, with distortion $3/4$.

For any sample, expanding the empirical squared loss around its sample mean $\bar X_n=n^{-1}\sum_iX_i$ gives $$ R_n(c)=\frac{1}{n}\sum_{i=1}^n(X_i-\bar X_n)^2+(c-\bar X_n)^2. $$ Hence the empirical minimizer is $\hat c_n=\bar X_n$. Because $E|X|<\infty$, the strong law gives $\bar X_n\xrightarrow{a.s.}3/2$; because $E[X^2]=3<\infty$, it also gives $n^{-1}\sum_iX_i^2\xrightarrow{a.s.}3$. Therefore the minimized empirical risk $n^{-1}\sum_iX_i^2-\bar X_n^2$ converges almost surely to $3-(3/2)^2=3/4$, matching the population optimum.

Truncation and the Limits of Moment Assumptions

For codebooks in $B_M^K$, the part of the risk contributed by observations outside a ball of radius $T$ satisfies

E\!\left[\phi_C(X)\mathbf{1}_{\{\|X\|>T\}}\right] \leq E\!\left[(\|X\|+M)^2\mathbf{1}_{\{\|X\|>T\}}\right].

The right side tends to zero under a finite second moment: $(\|X\|+M)^2$ is integrable and dominates its own tail restriction. Thus one can analyze the bounded region and separately control the omitted tail. For the empirical tail at any fixed $T$, the strong law applies to $\phi_C(X)\mathbf{1}_{\{\|X\|>T\}}$, since it is bounded by an integrable envelope. Higher moments give the quantitative bounds described earlier. A truncation level that changes with $n$ requires its own argument; a fixed-threshold strong law alone does not justify an arbitrary sequence of thresholds.

A crucial qualification is that the uniform convergence and compact consistency results above concern codebooks in a fixed compact parameter space. Finite second moment does not itself impose such a restriction on every unrestricted empirical minimizer. In particular, an unused center can be placed arbitrarily far away without changing the empirical risk. Even when a chosen minimizer has no unused centers, a small number of extreme observations can affect its location. To infer convergence of unrestricted codebooks, an argument must also ensure that relevant minimizers are localized, or impose suitable additional assumptions. This is separate from convergence of risk values.

Worked Example: Why Risk and Center Convergence Are Different Claims

Consider a one-center problem with finite second moment and empirical minimizer $\hat c_n=\bar X_n$. Its empirical risk converges to the population minimum under the strong law, as in the previous calculation. Now instead describe the same one-center codebook as a two-center codebook $(\bar X_n,b_n)$, where $b_n$ is any point farther from every observed value than $\bar X_n$ is. The second center is never nearest, so this two-center representation has exactly the same empirical risk as $(\bar X_n,\bar X_n)$. Choosing $b_n=n$ can make a center diverge even though the empirical risk is unchanged.

This example does not show that every empirical optimizer is poorly behaved. It shows why a risk statement alone cannot imply convergence of every listed center: the objective may not identify inactive centers. Codebook consistency needs a specified parameter space and conditions that exclude or control such irrelevant center movement.

Common Pitfall

Wrong reasoning: “The observations are identically distributed, so the empirical risks converge uniformly over all codebooks.” The ordinary strong law gives convergence for each fixed integrable loss, not automatically uniform convergence over an unrestricted parameter space.
Correction: For centers in a fixed bounded set, use the integrable envelope $2\|X\|^2+2M^2$ and a finite-net argument to obtain uniform convergence. For unrestricted empirical quantizers, establish localization separately before applying a compact argmin argument.
Wrong reasoning: “Finite second moment gives a rate for every tail.” It guarantees that the second-moment tail tends to zero, but does not specify a universal rate.
Correction: A finite $2+\delta$ moment gives the explicit $T^{-\delta}$ bound. Without that stronger assumption, use the actual tail behavior or the qualitative convergence from dominated convergence.

Key takeaway: For squared-distance quantization, a finite second moment ensures finite population distortion and provides an integrable envelope on bounded sets of codebooks. Truncation controls extreme observations, and uniform convergence yields consistency on compact parameter spaces. Convergence of unrestricted centers needs localization in addition to moment control.

Check Your Understanding

Use the definitions and arguments above to answer the following questions.

Why does $E\|X\|^2<\infty$ imply finite distortion for every fixed finite codebook?
If $E\|X\|^{2+\delta}<\infty$, derive an upper bound for $E[\|X\|^2\mathbf{1}_{\{\|X\|>T\}}]$.
What role does the fixed radius $M$ play in the uniform convergence theorem?
Why does uniform convergence on a compact parameter space imply that empirical minimizers approach the population minimizing set?
Explain why a finite second moment alone does not guarantee that every center in an unrestricted empirical minimizer converges.