Approximation, Estimation, And Optimization Error

Why Separate the Sources of Excess Risk?

A fitted predictor can have risk above the best possible risk for several distinct reasons. The chosen candidate class may not contain a good approximation to the target; the observed sample may make empirical risk differ from population risk; and an algorithm may fail to minimize its penalized empirical objective exactly. A useful risk guarantee keeps these contributions visible rather than hiding them in one remainder term.

The separation is useful for diagnosis. A large approximation error calls for a richer candidate class. A large estimation contribution calls for better control of sample fluctuations or a less complex class. A large optimization tolerance calls for a more accurate computation. The penalty also matters: it influences which comparator is suitable and appears explicitly in the guarantee.

Risk, Comparator, and Approximation Error

Let \(Z_1,\ldots,Z_n\) be independent observations with common distribution \(P\), and let \(Z\) denote a generic observation from \(P\). For a predictor \(g\) and loss \(\ell(g,z)\), define its population risk and empirical risk by

Let \(\mathcal F\) be the target class and \(\mathcal G\subseteq\mathcal F\) the candidate class used for fitting. We use nonnegative losses, assume \(\mathcal F\) and \(\mathcal G\) are nonempty, and assume each class contains at least one predictor with finite risk. These conditions ensure that

In particular, the difference defining approximation error is well-defined and finite. Individual predictors with infinite risk may exist, but they do not make either infimum infinite under these assumptions.

An infimum need not be attained. Thus a comparator \(g\in\mathcal G\) can be chosen with risk arbitrarily close to \(R_{\mathcal G}\), even when there is no single best member of \(\mathcal G\). This distinction matters when deriving bounds: the argument should apply to every comparator, not assume that a minimizer exists.

A Penalized Estimator and Its Error Decomposition

Let \(p:\mathcal G\to[0,\infty)\) be a finite-valued penalty, and let \(\hat g\in\mathcal G\) be a measurable fitted predictor. On the event considered below, suppose its empirical risks are finite and it satisfies the approximate penalized minimization condition

The tolerance \(\varepsilon\) measures optimization error. Exact minimization corresponds to \(\varepsilon=0\). For random quantities, assume the risks of the selected predictor are measurable and that the deviation bounds used below hold on a measurable event. If a supremum over \(\mathcal G\) is not measurable, a measurable upper bound for it can be used instead.

The inequality holds on any event where the empirical risks are finite and the displayed quantities are defined. In particular, its left side is finite when \(R(\hat g)<\infty\); this holds, for example, if the selected predictor is known to have finite risk. If it does not, the statement can instead be read as a bound for finite-risk selections.

Proof. Approximate minimization implies, for every \(g\in\mathcal G\),

Now add and subtract the empirical risks of \(\hat g\) and \(g\):

Bound the middle empirical-risk difference by the preceding optimization inequality, and bound each of the other two differences by its absolute value. This gives the claimed result. \(\square\)

The comparator term is the excess risk of the chosen \(g\) over the target-class optimum. The two absolute deviations are the estimation contribution for this particular comparison. They are not automatically small; a separate argument must control them. The penalty difference can help or hurt: if the comparator is more heavily penalized than the fitted predictor, it increases the bound.

Uniform Deviation and a Three-Part Bound

A common way to control the estimation contribution is with a uniform deviation over the candidate class. Define

Assume this quantity is measurable (or replace it with a measurable upper bound) and finite on the event of interest. Then both deviations in the theorem are at most \(\Delta_n(\mathcal G)\).

Proof. Apply the theorem and use \(|R(\hat g)-R_n(\hat g)|\le\delta\) and \(|R_n(g)-R(g)|\le\delta\). Adding the two bounds gives \(2\delta\). \(\square\)

Because \(p(\hat g)\ge0\), one may discard its negative contribution to obtain a simpler bound. Taking the infimum over comparators then gives

This form separates three main sources: comparator approximation, sample-based estimation, and optimization. The penalty adds a comparator charge. More explicitly, the infimum in the display equals \(A_{\mathcal G}+B_{\mathcal G}(p)\), where

Since \(R(g)\ge R_{\mathcal G}\) and \(p(g)\ge0\), this penalty charge is nonnegative. It allows the bound to use a comparator that may have slightly greater risk than the best-in-class risk in exchange for a more favorable penalty. When \(p\) is identically zero, the bound reduces to approximation error plus estimation error plus optimization error.

Three Worked Perspectives on the Contributions

Common Pitfall and Practical Interpretation

A common mistake is to call every gap between fitted and optimal risk “estimation error.” That description can conceal two different sources: the best member of \(\mathcal G\) may already be worse than the best member of \(\mathcal F\), and the algorithm may not have minimized its empirical objective accurately. The comparator inequality keeps these distinct.

• Approximation: \(R_{\mathcal G}-R_*\) is a population-level limitation of the candidate class.
• Estimation: deviations between empirical and population risk reflect sampling and require a separate control.
• Optimization: \(\varepsilon\) records how far the computed fit may be from minimizing the penalized empirical objective.
• Penalty: \(p(g)-p(\hat g)\) records how the comparator's penalty affects the comparison; dropping \(-p(\hat g)\) is valid only because the penalty is nonnegative.

Another error is subtracting two risk infima without checking they are finite. Nonnegative losses and at least one finite-risk member in each relevant class ensure the infima here are finite. Without such conditions, even individually defined risks need not make a difference of infima well-defined. State the assumptions before interpreting the decomposition.