Approximate Empirical Minimizers And Optimization Error

Why Approximate Minimization Matters

A finite-dictionary selection guarantee compares the selected predictor with the best candidate in a collection. In practice, a procedure may not find the exact empirical minimizer: an iterative algorithm may stop early, or a numerical solver may return a candidate whose empirical risk is close to the minimum. The relevant question is how much this imperfection changes the guarantee.

For bounded losses, the answer is direct. If the returned candidate's empirical risk is at most $\varepsilon$ above the empirical minimum, its oracle bound incurs an additional additive term $\varepsilon$. This is separate from the statistical term, which accounts for the discrepancy between empirical and population risks.

Setup and Definition

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations with common distribution $P$. Let $\mathcal G=\{g_1,\ldots,g_M\}$ be a nonempty finite collection of fixed candidates, and let $\ell(g,z)$ be a measurable loss satisfying $0\leq \ell(g,z)\leq 1$ for every $g\in\mathcal G$ and observation $z$. Define the population risk and empirical risk by

R(g)=E[\ell(g,Z)], \qquad R_n(g)=\frac{1}{n}\sum_{i=1}^n \ell(g,Z_i).

For each fixed candidate, its loss on one observation, $\ell(g,Z_i)$, is a bounded random variable. Its empirical risk $R_n(g)$ is the average of the $n$ independent bounded loss random variables. A candidate returned by a data-dependent procedure can be random, even though the dictionary itself is fixed.

Definition: A candidate $\hat g\in\mathcal G$ is an $\varepsilon$-approximate empirical minimizer if $$ R_n(\hat g)\leq \min_{g\in\mathcal G}R_n(g)+\varepsilon, $$ where $\varepsilon\geq 0$ is the optimization tolerance. The condition is understood to hold for the realized data; $\varepsilon$ may also be a data-dependent bound if the procedure certifies the displayed inequality.

When $\varepsilon=0$, this definition gives an exact empirical minimizer. The tolerance measures how far the returned candidate's empirical risk lies above the smallest empirical risk in the dictionary. It is not a bound on population risk, nor does it itself describe sampling variability.

Worked Example: Computing a Tolerance from Empirical Risks

Suppose a solver evaluates three candidates and obtains empirical risks $0.21$, $0.17$, and $0.24$. It returns the first candidate. The empirical minimum is $0.17$, so the returned candidate's optimization gap is

$$ 0.21-0.17=0.04. $$

Thus it is a $0.04$-approximate empirical minimizer. It is also an $\varepsilon$-approximate empirical minimizer for any $\varepsilon\geq 0.04$, but not for $\varepsilon=0.03$. This conclusion is about the three observed empirical risks; by itself, it says nothing about which candidate has the smallest population risk.

A Finite-Class Oracle Inequality

The statistical part of the argument comes from a uniform deviation bound. For a fixed candidate, Hoeffding's inequality applies to the average of its $n$ independent losses in $[0,1]$. Applying that inequality to all $M$ candidates and using the union bound gives, for every $a>0$,

P\left(\max_{g\in\mathcal G}|R_n(g)-R(g)|>a\right) \leq 2M\exp(-2na^2).

In particular, for $0<\delta<1$, set $a=\sqrt{\log(2M/\delta)/(2n)}$. The probability that the maximum deviation exceeds this value is at most $\delta$. This is a uniform statement over the dictionary: on the event it describes, the deviation bound holds for every candidate at once, including whichever candidate a data-dependent procedure returns.

Theorem: Assume the observations are independent and identically distributed, $\mathcal G$ is a fixed finite dictionary of size $M\geq 1$, and the measurable loss takes values in $[0,1]$. Let $0<\delta<1$, and suppose $\hat g\in\mathcal G$ satisfies $R_n(\hat g)\leq \min_{g\in\mathcal G}R_n(g)+\varepsilon$. Then, with probability at least $1-\delta$, $$ R(\hat g)\leq \min_{g\in\mathcal G}R(g) +\varepsilon +2\sqrt{\frac{\log(2M/\delta)}{2n}}. $$

Proof. Let $a=\sqrt{\log(2M/\delta)/(2n)}$. By the deviation bound, with probability at least $1-\delta$, the event

|R_n(g)-R(g)|\leq a \quad \text{for every }g\in\mathcal G

holds. Fix any data set in this event, and choose $g^\star\in\mathcal G$ attaining $\min_{g\in\mathcal G}R(g)$; such a candidate exists because the dictionary is finite and nonempty. On this same event, the deviation inequality applies both to $\hat g$ and to $g^\star$. Therefore,

\begin{aligned} R(\hat g) &\leq R_n(\hat g)+a\\ &\leq \min_{g\in\mathcal G}R_n(g)+\varepsilon+a\\ &\leq R_n(g^\star)+\varepsilon+a\\ &\leq R(g^\star)+\varepsilon+2a\\ &=\min_{g\in\mathcal G}R(g)+\varepsilon+2a. \end{aligned}

The first and last inequalities use the uniform deviation event; the second uses approximate empirical minimization. Since that event has probability at least $1-\delta$, the claimed bound follows. $\square$

Worked Example: Evaluating the High-Probability Bound

Suppose $n=200$, the dictionary contains $M=8$ candidates, the desired failure probability is $\delta=0.05$, and the algorithm certifies $\varepsilon=0.01$. The statistical term in the theorem is

2\sqrt{\frac{\log(2M/\delta)}{2n}} =2\sqrt{\frac{\log(16/0.05)}{400}} =2\sqrt{\frac{\log(320)}{400}}.

Since $\log(320)\approx 5.7683$, the term is $2\sqrt{5.7683/400}\approx 2(0.1201)=0.2402$. Thus, with probability at least $0.95$,

R(\hat g)\leq \min_{g\in\mathcal G}R(g)+0.01+0.2402 =\min_{g\in\mathcal G}R(g)+0.2502.

The optimization tolerance contributes $0.01$; the larger $0.2402$ contribution comes from the displayed finite-sample deviation bound. These are different sources of error, even though both appear additively in the oracle inequality.

Reading the Bound and Checking a Realized Example

The theorem has three distinct ingredients: the oracle risk $\min_{g\in\mathcal G}R(g)$, the optimization tolerance $\varepsilon$, and the finite-sample term. For fixed $M$ and $\delta$, the displayed statistical term decreases as $n$ grows. The optimization term does not automatically decrease with sample size: its size depends on the accuracy achieved and certified by the optimization procedure.

The following example checks the empirical gap and the risk comparison directly. The numerical deviations are a property of this particular realized sample; unlike the theorem, the calculation alone does not establish a probability guarantee.

Worked Example: Verifying the Pathwise Comparison

Consider three candidates with population risks $0.30$, $0.34$, and $0.50$. On a sample of five observations, their respective per-observation losses are $(0.2,0.4,0.2,0.4,0.3)$, $(0.4,0.2,0.4,0.2,0.4)$, and $(0.6,0.4,0.6,0.4,0.5)$. The empirical risks are

R_n(g_1)=\frac{1.5}{5}=0.30,\qquad R_n(g_2)=\frac{1.6}{5}=0.32,\qquad R_n(g_3)=\frac{2.5}{5}=0.50.

If the procedure returns $g_2$, its empirical gap is $0.32-0.30=0.02$, so it meets tolerance $\varepsilon=0.02$. The absolute deviations between empirical and population risks are $0$, $0.02$, and $0$, respectively. Hence the maximum deviation on this sample is $a=0.02$. The comparison in the proof gives

R(g_2)\leq \min_j R(g_j)+\varepsilon+2a =0.30+0.02+2(0.02)=0.36.

Indeed, $R(g_2)=0.34\leq 0.36$. The example shows how both the optimization gap and the deviations enter the argument; it does not replace the theorem's high-probability control of those deviations.

Worked Example: Choosing an Optimization Tolerance

Suppose $n=1000$, $M=4$, and $\delta=0.10$. The statistical term in the theorem is

2\sqrt{\frac{\log(2M/\delta)}{2n}} =2\sqrt{\frac{\log(80)}{2000}} \approx 2\sqrt{\frac{4.3820}{2000}} \approx 2(0.04681)=0.09362.

If a procedure certifies $\varepsilon=0.005$, the total excess-risk term is approximately $0.005+0.09362=0.09862$. If its only available certificate is $\varepsilon=0.20$, the theorem still applies, but its bound becomes approximately $0.29362$. This calculation shows why a valid optimization guarantee can matter: a loose tolerance may dominate the bound even when the statistical term is unchanged.

Common Pitfalls and Practical Interpretation

Confusing a loss with an empirical risk. The single-observation loss $\ell(g,Z_i)$ is a random variable. The empirical risk $R_n(g)$ is the average of the $n$ losses; Hoeffding's inequality is applied to that average.
Dropping the optimization term. A finite-class result for an exact empirical minimizer does not automatically apply unchanged to an approximate one. The additive $\varepsilon$ records the allowed empirical suboptimality.
Using an unverified stopping rule as a certificate. An algorithm's stopping criterion supports the theorem only if it establishes the stated empirical-risk gap. A small change between successive iterations, by itself, need not prove that the current value is close to the global empirical minimum.
Applying the finite-dictionary bound to an unaccounted candidate. The theorem requires $\hat g\in\mathcal G$. A candidate outside the dictionary needs a deviation guarantee that also covers that candidate; the finite union bound over $\mathcal G$ alone does not provide one.
Reading a probability bound as a guarantee for every sample. The theorem holds on a specified event of probability at least $1-\delta$, not necessarily on every realized data set. A pathwise calculation such as the preceding example is a separate, sample-specific check.

The result is useful whenever empirical selection is performed by an imperfect optimizer: it separates the cost of sampling from the cost of not minimizing exactly. If a sharper finite-class selection guarantee is available under additional assumptions, the same comparison can often incorporate an approximate-minimization tolerance as an additive term, provided the assumptions and the empirical gap condition for that sharper result are satisfied.

Check Your Understanding

Answer these questions by identifying which part of the definition or bound applies.

A returned candidate has empirical risk $0.18$, while the minimum empirical risk is $0.15$. What is the smallest tolerance for which it qualifies as an approximate empirical minimizer?
Why does the uniform deviation event cover a candidate selected after observing the data, provided that candidate belongs to the fixed dictionary?
In the theorem, which term is due to imperfect optimization, and which term controls empirical-to-population deviations?
For a fixed dictionary and confidence level, what happens to the displayed statistical term as $n$ increases?
Why is a stopping rule based only on small changes between successive iterates not necessarily a certificate of approximate empirical minimization?