Approximate ERM and Optimization Tolerance

Why Optimization Accuracy Belongs in a Risk Bound

Empirical risk minimization is often described as choosing a hypothesis that minimizes the empirical risk. In practice, an algorithm may stop before reaching the exact minimum, or the minimum may not be attained. The relevant question is then not whether optimization was exact, but how far its error can move the statistical guarantee.

An additive optimization tolerance gives a direct answer. It measures how much larger the empirical risk of the returned hypothesis is allowed to be than the smallest empirical risk in the class. The basic inequality shows that this tolerance adds directly to the usual statistical error contribution. Thus computation and sampling error can be compared on the same risk scale.

Approximate Empirical Risk Minimization

Let $Z_1,\ldots,Z_n$ be observations, and let $P$ denote their common distribution. For a hypothesis $h$ with loss $\ell(h,z)$, define its population risk and empirical risk by

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

Assume these risks are finite for the hypotheses under consideration. The hypothesis class is denoted by $\mathcal H$, and its best population risk is $R^*_{\mathcal H}=\inf_{h\in\mathcal H}R(h)$. This infimum need not be attained.

Definition: For a tolerance $\delta\geq 0$, a hypothesis $\hat h$ is a $\delta$-approximate empirical risk minimizer if $$ R_n(\hat h)\leq \inf_{h\in\mathcal H}R_n(h)+\delta. $$ The tolerance is measured in the same units as the empirical risk. It may depend on the observed data, in which case it is written $\delta_n$.

When $\delta=0$, this definition includes an exact empirical minimizer whenever one exists. When the infimum is not attained, an exact minimizer may not exist, but approximate minimizers can still satisfy the displayed inequality. The definition concerns the objective value, not distance between hypotheses: two very different hypotheses can have nearly identical empirical risks.

The Basic Inequality with Optimization Tolerance

For a fixed data set, define the uniform deviation between empirical and population risk by

U_n=\sup_{h\in\mathcal H}|R_n(h)-R(h)|.

In a probabilistic statement, we assume this supremum is measurable, or that the probability bounds are interpreted using an appropriate measurable upper bound. The following inequality is deterministic: once $U_n$ and the approximate minimizer condition hold, no additional probability argument is needed.

Theorem (Approximate ERM basic inequality): If $\hat h$ is a $\delta$-approximate empirical risk minimizer and $U_n<\infty$, then $$ R(\hat h)-R^*_{\mathcal H}\leq 2U_n+\delta. $$ More generally, for every $h\in\mathcal H$, $$ R(\hat h)-R(h)\leq 2U_n+\delta. $$

Proof. Fix any $h\in\mathcal H$. Add and subtract the empirical risks of $\hat h$ and $h$:

\begin{aligned} R(\hat h)-R(h) &= [R(\hat h)-R_n(\hat h)] + [R_n(\hat h)-R_n(h)] + [R_n(h)-R(h)]. \end{aligned}

The first and third bracketed terms are each at most $U_n$, by the definition of the supremum. By approximate minimization, $R_n(\hat h)\leq \inf_{g\in\mathcal H}R_n(g)+\delta\leq R_n(h)+\delta$, so the middle term is at most $\delta$. Therefore $R(\hat h)-R(h)\leq 2U_n+\delta$. Taking the infimum over $h\in\mathcal H$ gives the stated bound relative to $R^*_{\mathcal H}$. This last step does not require an $h$ attaining the infimum. $\square$

The two copies of $U_n$ arise from comparing the empirical and population risks at both the returned hypothesis and a comparator. The optimization tolerance is a separate term: it does not get multiplied by two in this argument.

Worked Example: A Small Model Class with an Inexact Choice

Suppose $Y$ is Bernoulli with $P(Y=1)=0.4$, and the class consists of constant predictions $c\in\{0,0.5,1\}$ with squared loss $\ell(c,y)=(y-c)^2$. The observed sample is $0,1$, so $n=2$.

For $c=0$, the empirical risk is $(0^2+1^2)/2=0.5$. For $c=1$, it is $(1^2+0^2)/2=0.5$. For $c=0.5$, both squared losses are $0.25$, so the empirical risk is $0.25$. The empirical minimum is therefore $0.25$. Returning $c=1$, whose empirical risk is $0.5$, satisfies the approximate-minimizer condition with $\delta=0.25$.

The population risk at a constant $c$ is $R(c)=0.4(1-c)^2+0.6c^2=c^2-0.8c+0.4$. Thus $R(0)=0.4$, $R(0.5)=0.25$, and $R(1)=0.6$. The best population risk in this class is $0.25$, and the returned hypothesis has excess risk $0.6-0.25=0.35$.

The empirical-population differences are $0.1$ at $c=0$, $-0.1$ at $c=1$, and $0$ at $c=0.5$, so $U_n=0.1$. The basic inequality gives $2(0.1)+0.25=0.45$. The actual excess risk, $0.35$, is indeed no larger than this bound.

Finite-Sample Guarantees from a Deviation Bound

The basic inequality becomes a finite-sample result as soon as a bound on $U_n$ is available. It is useful to keep the statistical bound abstract: the relevant deviation result may depend on the model, the loss, and the assumptions used to control risk fluctuations. The translation from that result to approximate ERM is always the same.

Theorem (Finite-sample tolerance transfer): Suppose that, for some $a\geq0$ and $\alpha\in(0,1)$, $P(U_n\leq a)\geq1-\alpha$. If $\hat h$ satisfies the approximate ERM condition with a fixed tolerance $\delta$, then $$ P\!\left(R(\hat h)-R^*_{\mathcal H}\leq 2a+\delta\right)\geq1-\alpha. $$ If instead the tolerance is random and $P(\delta_n\leq d)\geq1-\beta$, then $$ P\!\left(R(\hat h)-R^*_{\mathcal H}\leq 2a+d\right)\geq1-\alpha-\beta. $$

Proof. In the fixed-tolerance case, on the event $U_n\leq a$, the basic inequality gives $R(\hat h)-R^*_{\mathcal H}\leq2U_n+\delta\leq2a+\delta$. This event has probability at least $1-\alpha$. For a random tolerance, on the intersection of $U_n\leq a$ and $\delta_n\leq d$, the same inequality gives an excess risk at most $2a+d$. By the union bound, the intersection has probability at least $1-\alpha-\beta$. $\square$

Worked Example: Adding the Tolerance Without Rounding Error

Suppose a finite-sample deviation result guarantees, with probability at least $0.95$, that the statistical contribution $2U_n$ is at most $1.6\sqrt{\log(40)/n}$. At $n=10{,}000$, calculate this contribution before adding the optimization tolerance.

Since $\log(40)\approx3.688879454$, $3.688879454/10{,}000\approx0.0003688879454$, and its square root is approximately $0.0192064$. Therefore $1.6\sqrt{\log(40)/10{,}000}\approx0.0307303$, which rounds to $0.03073$ at five decimal places. Keeping the unrounded value for addition avoids a rounding discrepancy.

With tolerance $\delta=0.1$, the excess-risk bound is approximately $0.0307303+0.1=0.1307303$, or $0.13073$ to five decimal places. With tolerance $\delta=0.0001$, it is approximately $0.0307303+0.0001=0.0308303$, or $0.03083$. Both bounds hold with probability at least $0.95$, under the stated deviation guarantee.

The statistical contribution is unchanged between the two calculations; only the optimization tolerance changes. In the first case it dominates the bound. In the second, it makes only a small addition to the statistical term.

There is also an expectation version when $U_n$ and $\delta_n$ are measurable and integrable, and the approximate-minimizer condition holds almost surely. Taking expectations in the pointwise basic inequality gives

E[R(\hat h)-R^*_{\mathcal H}] \leq 2E[U_n]+E[\delta_n].

Here the expectation includes the randomness of the sample and, if the algorithm is randomized, its randomness as well. This form makes clear that a data-dependent stopping error contributes through its expected size.

When Is the Tolerance Negligible?

Let $s_n$ denote the size of the statistical contribution in a finite-sample bound, so that the bound has the form $s_n+\delta_n$. The optimization tolerance is negligible relative to this statistical error when $\delta_n/s_n\to0$. If the ratio stays bounded, optimization and statistical error are on comparable scales; if it grows, the optimization tolerance eventually dominates.

Worked Example: A Tolerance Compared with Two Statistical Scales

Suppose an available statistical bound has contribution $s_n=3/\sqrt n$, while the optimization tolerance is $\delta_n=n^{-3/4}$. Their ratio is $\delta_n/s_n=(1/3)n^{-1/4}$, which tends to zero. At $n=100$, $s_n=3/10=0.3$ and $\delta_n=100^{-3/4}=1/31.6228\approx0.03162$, giving a total of about $0.33162$. At $n=10{,}000$, $s_n=3/100=0.03$ and $\delta_n=10{,}000^{-3/4}=0.001$, giving a total of $0.031$. The tolerance is becoming less important relative to this statistical term.

Now compare the same tolerance with a faster statistical contribution $s_n=3/n$. The ratio is $\delta_n/s_n=n^{1/4}/3$, which grows rather than tends to zero. At $n=100$, the statistical term is $0.03$ and the tolerance is about $0.03162$. At $n=10{,}000$, they are $0.0003$ and $0.001$, respectively. The tolerance is no longer negligible. Thus a stopping rule that is adequate for one statistical scale may be too loose for another.

A practical target is to choose the optimization tolerance below the statistical contribution at the sample size of interest. To make optimization error asymptotically negligible, choose a tolerance of smaller order than that contribution. In particular, if a guarantee has a statistical term proportional to $n^{-1/2}$, a tolerance of order $n^{-1/2}$ remains comparable; a smaller-order tolerance is needed for negligibility. The same reasoning applies if a different analysis yields a faster statistical scale.

Common Mistakes and Practical Interpretation

Ignoring the optimization error. Applying the exact-ERM inequality to an output that only approximately minimizes empirical risk drops a real term. Include $\delta$ in the excess-risk bound.
Doubling the tolerance. The decomposition has two empirical-population deviations, each bounded by $U_n$, and one empirical optimization gap bounded by $\delta$. The result is $2U_n+\delta$, not $2U_n+2\delta$.
Comparing incompatible objective scales. If an algorithm minimizes the sum $\sum_{i=1}^n\ell(h,Z_i)$ and is within $\varepsilon$ of its infimum, its average empirical risk is within $\varepsilon/n$. The tolerance must be converted before adding it to a bound expressed in average-risk units.
Calling a tolerance negligible without specifying a rate. A fixed tolerance does not vanish as the sample grows. Whether a shrinking tolerance is negligible depends on its ratio to the statistical term, not merely on whether the tolerance itself is small.

Key takeaway: Approximate ERM preserves the basic excess-risk argument with one additional additive term: $R(\hat h)-R^*_{\mathcal H}\leq2U_n+\delta$. A useful optimization target is therefore determined by the statistical error scale and expressed in the same units as the empirical risk.

Check Your Understanding

Use the definitions and inequalities above to answer these questions.

If $U_n\leq0.04$ and the empirical optimization tolerance is $0.01$, what excess-risk bound follows from the basic inequality?
Why does the approximate ERM bound use two copies of $U_n$, but only one copy of $\delta$?
If an algorithm is within $6$ of the minimum summed loss on a sample of size $n=300$, what is its additive tolerance when the empirical risk is defined as an average?
If a statistical contribution has order $n^{-1}$, is a tolerance of order $n^{-1/2}$ negligible relative to it? Explain using the ratio of the two terms.
Does the comparator form of the basic inequality require the best population-risk hypothesis to exist? Why or why not?