Estimation and Approximation Error

Definition

With $\tilde{f}={\mathrm{argmin}}_{f\in \mathcal{F}}R(f)$ the best function in $\mathcal{F}$: estimation error $R(f_n)-R(\tilde{f})$ (random, depends on the sample), approximation error $R(\tilde{f})-R(f^{\ast })$ (deterministic, depends only on $\mathcal{F}$).

Formula

$$R(f_n)-R^{\ast }=(R(f_n)-R(\tilde{f}))+(R(\tilde{f})-R(f^{\ast }))$$

• Classical regime (no interpolation): a larger $\mathcal{F}$ lowers the approximation error and raises the estimation error; the true risk is U-shaped. Underfitting = large approximation error, overfitting = large estimation error.
• Modern regime: $\mathcal{F}$ interpolates the data, the approximation error is about 0, and some algorithms still have a small estimation error: double descent beyond the interpolation threshold.
• For the squared loss, bias and variance play the same roles pointwise.

Appears in

• Lecture 1.2, definitions
• Lecture 1.2, exam-style task
• Lecture 1.2, classical regime, over- and underfitting
• Lecture 1.2, modern regime and double descent
• Lecture 3, generalization bounds control the estimation error
• Lecture 3, partitioning estimators: both errors as k grows

Related concepts

• Bias-Variance Decomposition
• Empirical Risk Minimization