Separating Approximation and Estimation Error

Why Separate the Two Sources of Error?

An empirical risk minimizer is selected from a class of candidate predictors using a finite sample. Its performance can therefore be limited in two distinct ways. The class may be too restricted to represent a good predictor, and the sample may lead the learner to select a predictor whose population risk is not the best available in that class. Separating these effects clarifies what a bound on excess risk does—and does not—guarantee.

The first contribution is approximation error: the difference between the best risk in the chosen class and the unrestricted optimum. The second is estimation error: the difference between the selected predictor’s population risk and the best risk in the class. The decomposition is an identity; controlling the estimation term requires additional information about empirical and population performance.

Risks and the Decomposition

Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$. For each predictor $h$ in a set $\mathcal G$, let $\ell_h(Z)$ be a measurable loss, and assume its expectation is finite. Write the population and empirical risks as

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

Let $\mathcal H\subseteq\mathcal G$ be the candidate class. The unrestricted optimal risk and the best risk available within the class are the infima

R^*=\inf_{h\in\mathcal G}R(h),\qquad R_{\mathcal H}^*=\inf_{h\in\mathcal H}R(h).

No minimizer is assumed to exist: an infimum is enough for the definitions and decomposition below. Since $\mathcal H\subseteq\mathcal G$, $R_{\mathcal H}^*\geq R^*$. For a selected $\hat h\in\mathcal H$, define

A(\mathcal H)=R_{\mathcal H}^*-R^*,\qquad E_{\mathcal H}(\hat h)=R(\hat h)-R_{\mathcal H}^*.

Definition: $A(\mathcal H)$ is the approximation error of the class relative to $\mathcal G$. $E_{\mathcal H}(\hat h)$ is the selected predictor’s estimation error within $\mathcal H$. When $\hat h\in\mathcal H$, this estimation error is nonnegative. Their sum is the excess risk $R(\hat h)-R^*$.

Theorem: For every $\hat h\in\mathcal H$, $$ R(\hat h)-R^* = \bigl(R_{\mathcal H}^*-R^*\bigr) + \bigl(R(\hat h)-R_{\mathcal H}^*\bigr) = A(\mathcal H)+E_{\mathcal H}(\hat h). $$

This identity follows by adding and subtracting $R_{\mathcal H}^*$:

R(\hat h)-R^* = R(\hat h)-R_{\mathcal H}^* + R_{\mathcal H}^*-R^*.

The order of the terms is useful: the class determines the approximation error, while the selected predictor and data determine the estimation error. The identity itself does not say either term is small.

Worked Example: A Class That Cannot Represent the Target

Let $X$ be equally likely to be 0 or 1, and let $Y=X$. Use zero-one loss, $\ell_h(X,Y)=\mathbf 1\{h(X)\ne Y\}$. Suppose $\mathcal G$ contains the rule $h^*(X)=X$, while $\mathcal H$ contains only the two constant classifiers $h_0(X)=0$ and $h_1(X)=1$.

The unrestricted rule is always correct, so $R^*=0$. The constant-zero rule errs when $X=1$, which has probability $1/2$, and the constant-one rule errs when $X=0$, also with probability $1/2$. Therefore $R_{\mathcal H}^*=1/2$ and $A(\mathcal H)=1/2-0=1/2$.

For a sample with three observations having $Y=0$ and two having $Y=1$, the empirical risks are $R_n(h_0)=2/5$ and $R_n(h_1)=3/5$. ERM selects $h_0$. Its population risk is still $1/2$, so $E_{\mathcal H}(h_0)=1/2-1/2=0$. The total excess risk is $1/2=1/2+0$: in this case all of it comes from approximation, not estimation.

Bounding the Estimation Error of ERM

The empirical risk is observable from the sample; the population risk is not. To connect them uniformly across the candidate class, define the empirical-to-population deviation

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

For a realized sample, whenever this supremum is finite, it bounds the discrepancy for every $h\in\mathcal H$. A probabilistic use of $\Delta_n(\mathcal H)$ as a random variable additionally requires the relevant supremum to be measurable, or an appropriate measurable upper bound.

Theorem: Suppose $\hat h\in\mathcal H$ satisfies $R_n(\hat h)\leq\inf_{h\in\mathcal H}R_n(h)+\tau$ for some $\tau\geq 0$. If $\Delta_n(\mathcal H)<\infty$, then $$ R(\hat h)-R^* \leq A(\mathcal H)+2\Delta_n(\mathcal H)+\tau. $$ In particular, the within-class estimation error is at most $2\Delta_n(\mathcal H)+\tau$.

Proof. Fix any $g\in\mathcal H$. By the definition of $\Delta_n(\mathcal H)$, the empirical-risk condition, and the definition of $\Delta_n(\mathcal H)$ again,

R(\hat h) \leq R_n(\hat h)+\Delta_n(\mathcal H) \leq R_n(g)+\tau+\Delta_n(\mathcal H) \leq R(g)+\tau+2\Delta_n(\mathcal H).

This holds for every $g\in\mathcal H$, so taking the infimum over $g$ gives $R(\hat h)\leq R_{\mathcal H}^*+\tau+2\Delta_n(\mathcal H)$. Subtract $R_{\mathcal H}^*$ to bound the estimation error, then use the exact decomposition to obtain the stated excess-risk bound. $\square$

For exact ERM, $\tau=0$. The factor of two arises because the comparison crosses from population risk to empirical risk at $\hat h$, and then back to population risk at a class competitor. The proof does not require the best population-risk predictor or the empirical-risk infimum to be attained: the inequality holds for every $g$, and therefore for their infimum.

Worked Example: Estimation Error Can Add to Approximation Error

Let $P(X=1)=0.3$, with $X\in\{0,1\}$, and suppose $Y=X$ with probability $0.9$ conditional on either value of $X$. Under zero-one loss, the rule $h^*(X)=X$ has risk $0.1$, so $R^*=0.1$. Let $\mathcal H$ again consist of the two constant classifiers.

The marginal probability of $Y=1$ is $P(Y=1)=P(X=0)P(Y=1\mid X=0)+P(X=1)P(Y=1\mid X=1)=0.7(0.1)+0.3(0.9)=0.34$. Thus $R(h_0)=0.34$ and $R(h_1)=P(Y=0)=0.66$. Consequently $R_{\mathcal H}^*=0.34$ and $A(\mathcal H)=0.34-0.1=0.24$.

Consider a sample of size three with two labels equal to 1 and one equal to 0. Its probability is $3(0.34)^2(0.66)=0.228888$, so the event is possible. The empirical risks are $R_n(h_1)=1/3$ and $R_n(h_0)=2/3$, and ERM selects $h_1$. Its population risk is $0.66$, giving estimation error $0.66-0.34=0.32$. The total excess risk is $0.66-0.1=0.56=0.24+0.32$. The class restriction and the sample-driven choice both contribute.

Approximate Optimization and the Two Errors

An algorithm need not find an exact empirical minimizer. If its output is within $\tau$ of the smallest empirical risk in the class, the preceding result adds $\tau$ to the estimation-error bound. This tolerance is an optimization contribution to the bound; it does not change the definition of the class’s approximation error.

Worked Example: A Nonzero Optimization Tolerance

Take a deterministic observation, so empirical and population risks agree. Let $\mathcal G$ contain a predictor with loss 0, and let $\mathcal H=\{h_0,h_1\}$, where the losses of $h_0$ and $h_1$ are respectively 0.2 and 0.4. Then $R^*=0$, $R_{\mathcal H}^*=0.2$, and $A(\mathcal H)=0.2$.

Suppose an algorithm returns $h_1$. It satisfies $R_n(h_1)=0.4\leq 0.2+0.2=\inf_{h\in\mathcal H}R_n(h)+\tau$ with $\tau=0.2$. Here $\Delta_n(\mathcal H)=0$, and the within-class estimation error is $0.4-0.2=0.2$, exactly the allowed tolerance. Its total excess risk is $0.4=0.2+0.2$. The theorem’s upper bound is $A+2\Delta_n+\tau=0.2+0+0.2=0.4$.

Interpreting the Bound

The bound separates two questions that are often conflated. The approximation term asks whether the class is capable of achieving low risk. The deviation term asks whether sample-based empirical comparisons are reliable within that class. Increasing the sample size may reduce the deviation, but it cannot, by itself, reduce a fixed class’s approximation error. Conversely, choosing a richer class may reduce approximation error while making empirical comparisons harder to control.

For a sequence of classes $\mathcal H_n$ and corresponding outputs $\hat h_n$, the same inequality applies at each sample size. In particular, if $A(\mathcal H_n)\to 0$, $\Delta_n(\mathcal H_n)\xrightarrow{p}0$, and the optimization tolerances $\tau_n\to 0$, then the excess risk converges to zero in probability. Indeed, for every $\varepsilon>0$, eventually $A(\mathcal H_n)+\tau_n<\varepsilon/2$, and

P\{R(\hat h_n)-R^*>\varepsilon\} \leq P\{2\Delta_n(\mathcal H_n)>\varepsilon/2\} \longrightarrow 0.

This is a sufficient condition obtained directly from the decomposition and bound; it is not a claim that either condition is necessary in every problem. For example, a particular estimator can have small excess risk even when a uniform deviation bound is loose.

Common Mistake

A common mistake is to infer that low empirical risk, or successful empirical minimization, means the selected predictor has low population excess risk. Empirical minimization only compares candidates using the observed sample. It says nothing by itself about the class’s approximation error, and without a control on empirical-to-population deviations it may not even identify the best population-risk candidate within the class.

The correction is to state the comparison explicitly: $R(\hat h)-R^*=A(\mathcal H)+E_{\mathcal H}(\hat h)$. Then assess approximation error separately and control estimation error using a justified deviation or other suitable argument. The decomposition is exact; the usefulness of a numerical bound depends on the assumptions that make its terms small.

Check Your Understanding

Use the definitions and results above to answer these questions.

Why is approximation error nonnegative when $\mathcal H\subseteq\mathcal G$?
In the first worked example, what would have to change for the approximation error to be zero?
Where does the factor of two in the uniform-deviation bound enter the proof?
How does the bound change if an algorithm returns an exact empirical minimizer?
Can increasing the sample size alone guarantee that a fixed class’s approximation error goes to zero? Explain.