Approximate Empirical Minimization and Optimization Error

Why Optimization Accuracy Belongs in a Risk Bound

An empirical clustering procedure may not find the exact minimum of its sample objective. An iterative algorithm may stop early, a numerical solver may return an approximate solution, or the empirical minimum may not be attained within the chosen class. The relevant question is then not whether the returned codebook is an exact empirical minimizer, but how far its population risk can be from the best population risk.

Two errors govern that comparison. Sampling error is the discrepancy between empirical and population risks across the candidate class. Optimization error is how far the selected codebook's empirical risk lies above the smallest empirical risk in that class. The main bound adds the optimization tolerance to twice the uniform sampling error. Keeping both terms explicit makes clear which part of a guarantee comes from the data and which part comes from the algorithm.

Risks, Uniform Deviation, and Approximate Minimization

Let $X_1,\ldots,X_n$ be independent observations with common distribution $F$ on $\mathbb{R}^d$, and suppose $E[\|X\|^2]<\infty$. Fix a positive integer $K$. A codebook $C$ is a nonempty set of at most $K$ centers in $\mathbb{R}^d$. Its squared-distance loss at $x$ is the squared distance from $x$ to its nearest center.

\gamma(x,C)=\min_{c\in C}\|x-c\|^2,\qquad R(C)=E[\gamma(X,C)],\qquad R_n(C)=\frac{1}{n}\sum_{i=1}^n\gamma(X_i,C).

The population optimum over a specified class $\mathcal{C}$ is $R^*_{\mathcal{C}}=\inf_{C\in\mathcal{C}}R(C)$. The empirical optimum is $\inf_{C\in\mathcal{C}}R_n(C)$. These infima need not be attained. The finite second-moment condition ensures that each fixed finite codebook has finite population risk; throughout, take $\mathcal{C}$ to contain at least one such codebook.

Definition: The uniform empirical deviation over $\mathcal{C}$ is $$ \Delta_n(\mathcal{C})=\sup_{C\in\mathcal{C}}|R_n(C)-R(C)|. $$ A data-dependent codebook $\hat C_n$ is an $\varepsilon_n$-approximate empirical minimizer if $\varepsilon_n\geq 0$ and $$ R_n(\hat C_n)\leq \inf_{C\in\mathcal{C}}R_n(C)+\varepsilon_n. $$

For random codebooks, assume the selected risks and tolerance are measurable, and that the displayed approximate-minimization inequality holds almost surely. Also assume $\Delta_n(\mathcal{C})$ is measurable; if a supremum requires outer probability, the probability statements below can instead be read in that sense. The deviation may be infinite for some classes, in which case a finite bound is informative only when $\Delta_n(\mathcal{C})<\infty$.

Worked Example: The Optimization Tolerance Can Be the Whole Error

Let $X$ take values $0$ and $2$, each with probability $1/2$. Use the class of singleton codebooks $\mathcal{C}=\{\{0\},\{1\},\{2\}\}$, and consider the observed sample $X_1=0,\ X_2=2$.

For any singleton codebook $\{c\}$, its risk is $E[(X-c)^2]$. Direct calculation gives $R(\{0\})=(0^2+2^2)/2=2$, $R(\{1\})=(1^2+1^2)/2=1$, and $R(\{2\})=(2^2+0^2)/2=2$. The empirical risks for this sample are exactly the same: $R_2(\{0\})=(0^2+2^2)/2=2$, $R_2(\{1\})=(1^2+1^2)/2=1$, and $R_2(\{2\})=(2^2+0^2)/2=2$. Thus $\Delta_2(\mathcal{C})=0$ and the empirical minimum is $1$.

Suppose the procedure returns $\hat C_2=\{0\}$ with tolerance $\varepsilon_2=1$. It satisfies the approximate-minimization requirement because $2\leq 1+1$. Its population excess risk is $R(\{0\})-R^*_{\mathcal{C}}=2-1=1$. The bound $2\Delta_2(\mathcal{C})+\varepsilon_2$ is also $1$. Even with no sampling discrepancy, optimization tolerance can account for the entire excess risk.

The Deterministic Excess-Risk Bound

Theorem: Suppose $\Delta_n(\mathcal{C})<\infty$, $\hat C_n\in\mathcal{C}$, and $\hat C_n$ is an $\varepsilon_n$-approximate empirical minimizer. Then, for every realization on which the approximate-minimization inequality holds, $$ 0\leq R(\hat C_n)-R^*_{\mathcal{C}} \leq 2\Delta_n(\mathcal{C})+\varepsilon_n. $$

This is a pathwise inequality: once the data and the selected codebook are fixed, it is an ordinary comparison of risks. In particular, it does not require the empirical or population infimum to be attained.

Proof. By the definition of the uniform deviation, for every $C\in\mathcal{C}$, $R(C)\leq R_n(C)+\Delta_n(\mathcal{C})$, and $R_n(C)\leq R(C)+\Delta_n(\mathcal{C})$. Apply the first inequality to the selected codebook and then use approximate minimization:

\begin{aligned} R(\hat C_n) &\leq R_n(\hat C_n)+\Delta_n(\mathcal{C})\\ &\leq \inf_{C\in\mathcal{C}}R_n(C)+\varepsilon_n+\Delta_n(\mathcal{C}). \end{aligned}

For every candidate $C$, the second deviation inequality gives $R_n(C)\leq R(C)+\Delta_n(\mathcal{C})$. Taking infima preserves this inequality: $\inf_{C\in\mathcal{C}}R_n(C)\leq R^*_{\mathcal{C}}+\Delta_n(\mathcal{C})$. Substitution yields $R(\hat C_n)\leq R^*_{\mathcal{C}}+2\Delta_n(\mathcal{C})+\varepsilon_n$. By definition of the infimum, $R(\hat C_n)\geq R^*_{\mathcal{C}}$. Combining the two inequalities proves the result. $\square$

The factor of two has a specific source: one deviation compares the selected codebook's empirical and population risks, and the other compares the empirical infimum with the population infimum. The optimization tolerance enters only once, at the step where the selected empirical risk is compared with the empirical infimum.

Worked Example: A High-Probability Guarantee for Two Centers

Let $X$ be Bernoulli with $P(X=1)=p=0.4$, and let the class consist of the two singleton codebooks $\{\{0\},\{1\}\}$. Write $\hat p_n=n^{-1}\sum_{i=1}^n X_i$. For center $0$, the loss is $X$, so $R(\{0\})=p$ and $R_n(\{0\})=\hat p_n$. For center $1$, the loss is $1-X$, so $R(\{1\})=1-p$ and $R_n(\{1\})=1-\hat p_n$.

Consequently, both candidate deviations have the same magnitude: \[ |R_n(\{0\})-R(\{0\})|=|\hat p_n-p|, \quad |R_n(\{1\})-R(\{1\})|=|\hat p_n-p|. \] Thus $\Delta_n(\mathcal{C})=|\hat p_n-p|$. Hoeffding's inequality for independent Bernoulli observations gives $P(\Delta_n(\mathcal{C})>t)\leq 2\exp(-2nt^2)$. For $n=100$ and $t=0.15$, this is at most $2\exp(-4.5)\approx 0.0222$.

Suppose the algorithm returns an $\varepsilon_n$-approximate empirical minimizer with $\varepsilon_n=0.05$. On the event $\Delta_n(\mathcal{C})\leq 0.15$, the deterministic theorem gives $R(\hat C_n)-R^*_{\mathcal{C}}\leq 2(0.15)+0.05=0.35$. That event has probability at least $1-0.02222=0.97778$. The guarantee is therefore $P\{R(\hat C_n)-R^*_{\mathcal{C}}\leq 0.35\}\geq 0.97778$. The probability statement controls the population risk of the selected codebook; it does not assert that the selected center is correct on every sample.

From the Bound to Risk Consistency

Corollary: Suppose that for each $n$, $\hat C_n\in\mathcal{C}$ almost surely and $$ R_n(\hat C_n)\leq\inf_{C\in\mathcal{C}}R_n(C)+\varepsilon_n $$ almost surely, where $\varepsilon_n\geq 0$. If $\Delta_n(\mathcal{C})\xrightarrow{p}0$ and $\varepsilon_n\xrightarrow{p}0$, then $$ R(\hat C_n)-R^*_{\mathcal{C}}\xrightarrow{p}0. $$

Proof. The deterministic theorem applies almost surely for each $n$, so the nonnegative excess risk is bounded above by $2\Delta_n(\mathcal{C})+\varepsilon_n$. For any $\eta>0$, if this upper bound exceeds $\eta$, then at least one of $2\Delta_n(\mathcal{C})>\eta/2$ or $\varepsilon_n>\eta/2$ holds. Therefore

P\{R(\hat C_n)-R^*_{\mathcal{C}}>\eta\} \leq P\{\Delta_n(\mathcal{C})>\eta/4\} + P\{\varepsilon_n>\eta/2\} \longrightarrow 0.

The two terms tend to zero by the assumed convergence in probability. This proves the claim. $\square$

The approximate-minimization condition is essential to this corollary. Membership $\hat C_n\in\mathcal{C}$ merely says that the procedure returned an allowed candidate; it says nothing about that candidate's empirical risk. Vanishing deviation and vanishing tolerance cannot control a choice that is not within the tolerance of the empirical infimum.

Worked Example: Checking the Approximate-Minimization Condition

Let $X=0$ almost surely and $\mathcal{C}=\{\{0\},\{1\}\}$. Then for every sample and every $n$, $R_n(\{0\})=R(\{0\})=0$ and $R_n(\{1\})=R(\{1\})=1$. Hence $\Delta_n(\mathcal{C})=0$, and the population optimum is $R^*_{\mathcal{C}}=0$.

If a procedure always selects $\hat C_n=\{1\}$ while setting $\varepsilon_n=0$, its excess risk is always $1$, not a quantity tending to zero. Crucially, the approximate-minimization inequality fails: $R_n(\hat C_n)=1$, whereas $\inf_{C\in\mathcal{C}}R_n(C)+\varepsilon_n=0+0=0$.

If the procedure instead uses $\varepsilon_n=1$, then $\{1\}$ is indeed an $\varepsilon_n$-approximate empirical minimizer, since $1\leq 0+1$. But this tolerance does not vanish, and the bound correctly gives excess risk at most $2(0)+1=1$. This example shows why the selection condition and the vanishing-tolerance assumption have separate roles.

Interpreting and Using the Bound

The deterministic inequality is useful when an empirical optimizer is approximate for practical reasons. It lets an analysis retain the numerical or algorithmic tolerance instead of silently treating an approximate solution as an exact minimizer. It also gives a direct design principle: to make population excess risk small, both the uniform deviation and the optimization tolerance must be small.

The bound concerns risk values. By itself it does not prove that the centers converge to a particular optimal codebook, that the partitions converge, or that the estimated labels are stable. Such conclusions need additional conditions connecting low excess risk to the relevant geometric or structural error. A small risk gap can coexist with multiple optimal codebooks or with nearly equivalent solutions.

A common mistake is to write $R(\hat C_n)-R^*_{\mathcal{C}}\leq 2\Delta_n(\mathcal{C})+\varepsilon_n$ after assuming only that $\hat C_n$ belongs to $\mathcal{C}$. The proof's second line would then have no justification: the inequality $R_n(\hat C_n)\leq\inf_C R_n(C)+\varepsilon_n$ is exactly what permits the selected empirical risk to be replaced by the empirical infimum. State and verify that condition before using the bound.

In applications, the guarantee can be organized into three checks:

Specify the candidate class and the population risk being compared.
Control the uniform empirical deviation over that same class.
Verify that the algorithm's returned codebook satisfies the approximate-minimization inequality with a stated tolerance.

Only after all three checks are in place does the excess-risk conclusion follow. If the tolerance or deviation is random, their probability behavior must also be included when claiming convergence or a high-probability guarantee.

Check Your Understanding

Answer each question using the definitions and bounds above.

In the excess-risk inequality, why are there two copies of the uniform deviation but only one copy of the optimization tolerance?
Does the deterministic bound require the empirical risk infimum to be attained? Explain the role of infima in the proof.
Suppose $\Delta_n(\mathcal{C})\xrightarrow{p}0$, but $\varepsilon_n=0.2$ for every $n$. What does the theorem imply, and what does it not imply?
In the Bernoulli example, derive the expression for $\Delta_n(\mathcal{C})$ from the two candidate risks.
Why is membership of $\hat C_n$ in $\mathcal{C}$ insufficient for the risk-consistency corollary?