Approximation Error

machine-learning learning-theory

Definition

Approximation Error

The approximation error is the gap between the risk of the best model a hypothesis class $\mathcal{H}$ can express and the lowest risk attainable by any predictor. Writing

$$h^{\star }=\arg \underset{h\in \mathcal{H}}{\min }R(h)$$

for the best-in-class model and $R^{\star }$ for the Bayes risk, it is

$$R(h^{\star })-R^{\star }.$$

It measures a limitation of $\mathcal{H}$ itself, independent of any data: even with infinitely many samples, no model in $\mathcal{H}$ can beat $h^{\star }$. A class too restrictive for the target leaves a large approximation error, the learning-theory counterpart of bias and the source of underfitting. It is reduced only by enlarging or changing $\mathcal{H}$, never by collecting more data.

The excess-risk decomposition

The risk of a learned model $\hat{h}$ — the empirical-risk minimiser — above the Bayes optimum splits into a part the class cannot avoid and a part the finite sample adds:

$$R(\hat{h})-R^{\star }=\underset{\text{estimation error}}{\underbrace{R(\hat{h})-R(h^{\star })}}+\underset{\text{approximation error}}{\underbrace{R(h^{\star })-R^{\star }}}.$$

The first term is the estimation error, driven by the sample and the capacity of $\mathcal{H}$; the second is the approximation error above, fixed by the choice of class. Enriching $\mathcal{H}$ lowers the approximation error but typically raises the estimation error, which is the bias-variance tradeoff stated at the level of risk.