Approximation Error (Machine Learning)

machine-learning learning-theory

Definition

Approximation Error

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

for the best-in-class model and for the Bayes risk, it is

It measures a limitation of itself, independent of any data: even with infinitely many samples, no model in can beat . 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 , never by collecting more data.

The excess-risk decomposition

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

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