Approximate Minimizers And Optimization Tolerance

Why Optimization Error Belongs in the Risk Bound

A penalized empirical-risk procedure is often described as minimizing an objective exactly. In computation, the returned predictor may only come close to the smallest attainable objective value. The relevant question is not whether the algorithm has found an exact minimizer, but whether its optimization error is small enough to preserve the statistical guarantee.

The key bookkeeping fact is simple: if the objective value is within $\eta$ of its infimum, comparisons with any fixed candidate incur an additional $\eta$. Under a uniform deviation event, this becomes an additive $\eta$ in the final oracle bound. It does not disappear merely because the statistical argument is otherwise unchanged.

Definition: Let $\mathcal F$ be a nonempty predictor class, $R_n(f)$ an empirical risk, and $\operatorname{pen}(f)$ a penalty. Write $Q_n(f)=R_n(f)+\operatorname{pen}(f)$. For a specified $\eta\geq 0$, an $\eta$-approximate minimizer is a predictor $\hat f_\eta\in\mathcal F$ satisfying $$ Q_n(\hat f_\eta)\leq \inf_{f\in\mathcal F}Q_n(f)+\eta. $$ The infimum need not be attained. When the data or algorithm are random, this inequality is required for the realized output; $\eta$ may itself be a nonnegative random tolerance.

The tolerance is measured in the same units as $Q_n$. If the criterion is an average loss, $\eta$ is on an average-loss scale. If the criterion is a sum of losses, the tolerance is on a sum scale. Dividing one part of an objective by $n$ but not the other changes the interpretation of $\eta$.

The Approximate Basic Inequality

The first step is deterministic. Approximate minimization gives a comparison with every candidate, whether or not there is an exact empirical minimizer.

Theorem: If $Q_n(\hat f_\eta)\leq\inf_{f\in\mathcal F}Q_n(f)+\eta$, then, for every $f\in\mathcal F$, $$ R_n(\hat f_\eta)-R_n(f) \leq \operatorname{pen}(f)-\operatorname{pen}(\hat f_\eta)+\eta. $$

Proof. Since $\inf_{g\in\mathcal F}Q_n(g)\leq Q_n(f)$, the approximate-minimization condition implies $Q_n(\hat f_\eta)\leq Q_n(f)+\eta$. Substituting $Q_n(g)=R_n(g)+\operatorname{pen}(g)$ and rearranging gives the displayed inequality. $\square$

This is the usual basic inequality with one additional term. In particular, setting $\eta=0$ recovers the exact-minimization comparison. For $\eta>0$, a candidate can have a larger empirical risk than the comparator, provided the penalty difference and tolerance allow it.

Worked Example: Comparing Two Candidate Objectives

Suppose a computation considers two predictors, $f_A$ and $f_B$. Their empirical risks and penalties are $R_n(f_A)=0.12$, $\operatorname{pen}(f_A)=0.08$, $R_n(f_B)=0.16$, and $\operatorname{pen}(f_B)=0.02$. The returned predictor is $f_B$, and the optimization tolerance is $\eta=0.02$.

The objective values are $Q_n(f_A)=0.12+0.08=0.20$ and $Q_n(f_B)=0.16+0.02=0.18$. Thus the infimum over these two candidates is $0.18$, and the returned predictor is in fact an exact minimizer here. The approximate basic inequality, comparing $f_B$ with $f_A$, gives $$ R_n(f_B)-R_n(f_A) \leq \operatorname{pen}(f_A)-\operatorname{pen}(f_B)+\eta =0.08-0.02+0.02=0.08. $$ The actual empirical-risk difference is $0.16-0.12=0.04$, so the comparison holds.

Now suppose instead the algorithm returns a predictor with objective value $0.21$, still compared against the same two candidates. Its objective gap is $0.21-0.18=0.03$, so it meets tolerance $\eta=0.03$. A guarantee with $\eta=0.02$ would not follow from these values. The tolerance must cover the actual objective gap, not just the intended stopping threshold.

A Uniform-Deviation Oracle Bound

To pass from empirical risk to population risk, suppose that on an event $\mathcal A$ the deviations are controlled simultaneously over the whole class. This simultaneous condition matters: the selected predictor is data-dependent, so a bound asserted only for a fixed, nonrandom predictor cannot automatically be applied to it.

Theorem: Let $R(f)$ be the population risk. Suppose that on an event $\mathcal A$, for every $f\in\mathcal F$, $$ |R_n(f)-R(f)|\leq b(f), $$ where $b(f)\geq0$. If $\operatorname{pen}(f)\geq b(f)$ for every $f\in\mathcal F$, then every $\eta$-approximate minimizer satisfies, on $\mathcal A$, $$ R(\hat f_\eta)\leq \inf_{f\in\mathcal F} \{R(f)+\operatorname{pen}(f)+b(f)\}+\eta. $$

Proof. Fix any $f\in\mathcal F$. On $\mathcal A$, the deviation bounds give $R(\hat f_\eta)\leq R_n(\hat f_\eta)+b(\hat f_\eta)$ and $R_n(f)\leq R(f)+b(f)$. The approximate basic inequality therefore yields $$ \begin{aligned} R(\hat f_\eta) &\leq R_n(f)+\operatorname{pen}(f)-\operatorname{pen}(\hat f_\eta) +\eta+b(\hat f_\eta)\\ &\leq R(f)+b(f)+\operatorname{pen}(f)+\eta, \end{aligned} $$ because $\operatorname{pen}(\hat f_\eta)\geq b(\hat f_\eta)$. This holds for every $f\in\mathcal F$, so taking the infimum over $f$ proves the result. $\square$

The penalty absorbs the deviation term at the selected predictor; the comparator retains its own penalty and deviation allowance. The optimization tolerance is separate from both. The theorem does not require a unique population minimizer or an attained empirical infimum, but its deviation event and penalty condition must hold for the full comparison class.

Worked Example: Carrying Tolerance Through an Oracle Bound

Consider two candidates $A$ and $B$. On a simultaneous deviation event, suppose their population risks, empirical risks, deviation bounds, and penalties are:

Candidate	$R(f)$	$R_n(f)$	$b(f)$	$\operatorname{pen}(f)$
A	0.12	0.10	0.02	0.02
B	0.35	0.20	0.15	0.15

The deviations are consistent with the stated bounds: $|0.10-0.12|=0.02$ and $|0.20-0.35|=0.15$. Each penalty equals its deviation bound, so the theorem's absorption condition holds. The penalized empirical objectives are $Q_n(A)=0.10+0.02=0.12$ and $Q_n(B)=0.20+0.15=0.35$.

Suppose the algorithm returns $B$ with tolerance $\eta=0.23$. It qualifies because $0.35=0.12+0.23$. Comparing with $A$, the oracle bound gives $$ R(B)\leq R(A)+\operatorname{pen}(A)+b(A)+\eta =0.12+0.02+0.02+0.23=0.39. $$ The actual risk $0.35$ satisfies this bound. If the same candidate were returned with a claimed tolerance of $0.20$, it would not qualify: its objective gap is $0.35-0.12=0.23$. The resulting oracle guarantee cannot be asserted with $\eta=0.20$ on these facts.

Combining Optimization and Comparator Error

An oracle inequality compares the selected predictor with candidate predictors; it does not require that the best candidate be the true target. If a comparator $f^\circ\in\mathcal F$ has risk $R(f^\circ)$, the preceding theorem directly gives $$ R(\hat f_\eta)\leq R(f^\circ)+\operatorname{pen}(f^\circ)+b(f^\circ)+\eta. $$ If risk is measured relative to a reference risk $R_0$, subtracting $R_0$ from both sides leaves the same additive optimization term. Thus the comparator's approximation error, its estimation allowance, its penalty, and the optimization tolerance remain distinguishable rather than being silently combined or discarded.

Worked Example: Adding a Comparator Approximation Allowance

Suppose a reference predictor has risk $R_0=0.08$, and a chosen comparator $f^\circ$ has risk $R(f^\circ)=0.11$. Its excess risk over the reference is $0.11-0.08=0.03$. Assume the comparator's penalty and deviation allowance are $0.02$ and $0.01$, respectively, and the approximate-minimization tolerance is $\eta=0.015$.

The oracle comparison gives $$ R(\hat f_\eta)\leq 0.11+0.02+0.01+0.015=0.155. $$ Subtracting the reference risk gives $$ R(\hat f_\eta)-R_0\leq 0.155-0.08=0.075 =0.03+0.02+0.01+0.015. $$ Here $0.03$ is the comparator's excess risk, $0.02$ and $0.01$ are its penalty and deviation allowance, and $0.015$ is the optimization cost. Keeping these terms visible shows which part of the guarantee could be improved by a better comparator, a different penalty, or more accurate optimization.

When Curvature Converts Tolerance Into Parameter Error

An objective-value guarantee can also control distance between parameter estimates, but a curvature condition is needed. The following deterministic fact explains the conversion; it applies to a penalized objective itself when that objective has the stated curvature.

Theorem: Let $\Theta$ be a convex subset of a normed vector space, and let $Q:\Theta\to\mathbb R$ be $\kappa$-strongly convex for $\kappa>0$, meaning that for $x,y\in\Theta$ and $t\in[0,1]$, $$ Q((1-t)x+ty)\leq (1-t)Q(x)+tQ(y) -\frac{\kappa}{2}t(1-t)\|x-y\|^2. $$ If $Q$ has a minimizer $\theta^\star$ and $Q(\hat\theta)\leq Q(\theta^\star)+\eta$, then $$ \|\hat\theta-\theta^\star\|\leq \sqrt{\frac{2\eta}{\kappa}}. $$

Proof. Set $x=\theta^\star$ and $y=\hat\theta$ in the strong-convexity inequality. Since $\theta^\star$ minimizes $Q$, for $0<t<1$ we have $Q(\theta^\star)\leq Q((1-t)\theta^\star+t\hat\theta)$. Combining the two inequalities and subtracting $Q(\theta^\star)$ gives $$ 0\leq t\{Q(\hat\theta)-Q(\theta^\star)\} -\frac{\kappa}{2}t(1-t)\|\hat\theta-\theta^\star\|^2. $$ Divide by $t>0$, then let $t$ decrease to zero. The result is $Q(\hat\theta)-Q(\theta^\star)\geq \frac{\kappa}{2}\|\hat\theta-\theta^\star\|^2$. Using the assumed objective gap, rearranging, and taking square roots proves the claim. $\square$

Worked Example: A Quadratic Objective and Parameter Accuracy

Let $\Theta=\mathbb R$ and $Q(\theta)=(\theta-1)^2$. This objective is $2$-strongly convex: its second derivative is $2$, and its exact difference from the tangent at any $x$ is $(y-x)^2=(2/2)(y-x)^2$. Its minimizer is $\theta^\star=1$, with $Q(\theta^\star)=0$.

If an algorithm returns $\hat\theta=1.2$, its objective gap is $Q(1.2)-Q(1)=(0.2)^2=0.04$. It is therefore an $\eta$-approximate minimizer for $\eta=0.05$. The curvature bound gives $$ |\hat\theta-\theta^\star| \leq \sqrt{\frac{2(0.05)}{2}} =\sqrt{0.05}\approx 0.224. $$ The actual distance, $0.2$, is below this limit. This parameter conclusion requires strong convexity of the objective in the parameter being assessed; an oracle bound on risk alone does not automatically imply a parameter-distance bound.

Common Pitfalls

Dropping the tolerance. From $Q_n(\hat f_\eta)\leq\inf Q_n+\eta$, it is invalid to use the exact basic inequality. The comparison with a candidate has an additional $+\eta$, which carries into the oracle guarantee.
Confusing approximate attainment with attainment. An infimum may not be achieved. The definition only requires the returned objective to be within $\eta$ of it; no exact minimizer should be presumed.
Using pointwise deviations for a selected predictor. A bound that holds separately for each fixed predictor need not hold for a data-dependent selection. The theorem uses a simultaneous deviation event over the class.
Changing objective scale without changing tolerance. If the criterion is multiplied by a constant, its objective gaps and the numerical tolerance must be multiplied by that same constant.
Claiming parameter accuracy without curvature. A small objective gap implies a small parameter distance only under an appropriate curvature condition, such as strong convexity.

Key takeaway: Verify approximate minimization on the stated objective scale, retain $+\eta$ in the basic inequality, and carry it unchanged into the oracle bound. Curvature can translate this objective tolerance into parameter error when its assumptions hold.

Check Your Understanding

Use the definitions and comparisons above to answer the following.

Why does the approximate basic inequality hold even when the empirical objective has no minimizer?
Which simultaneous deviation and penalty conditions are used to obtain the uniform-deviation oracle bound?
If an objective is a sum of $n$ losses rather than their average, what must be considered when specifying its optimization tolerance?
In the two-candidate example, what objective gap would a returned candidate with objective value $0.35$ have relative to the infimum $0.12$?
What additional condition lets an objective-value tolerance imply a parameter-distance bound, and what is the resulting bound?