3
$\begingroup$

I'm unable to find online, or understand from context - the difference between estimation error and approximation error in the context of machine learning (and, specifically, reinforcement learning).

Could someone please explain with the help of examples and/or references?

$\endgroup$
0
3
$\begingroup$

Section 5.2 Error Decomposition of the book Understanding Machine Learning: From Theory to Algorithms (2014) gives a description of the approximation error and estimation error in the context of empirical risk minimization (ERM), so in the context of learning theory. I will just summarise their definition. If you want to know more about these topics, I suggest that you read that section. If you are looking for the definitions of these topics in other contexts (e.g. reinforcement learning), you should ask a new question and provide more context (i.e. a paper or book that uses those terms in RL), because I also don't intend to extend this answer, although it is possible that these definitions below apply to other contexts too.

Approximation error

The approximation error (AE), aka inductive bias, denote as $\epsilon_{\mathrm{app}}$, is the error due to the specific choice of hypothesis class (or set) $\mathcal{H}$.

Here are some properties.

  • The larger $\mathcal{H}$ is, the smaller this error is (this should be intuitive!)

  • This error does not depend on the training data

Estimation error

The estimation error (EE) is the difference between the approximation error $\epsilon_{\mathrm{app}}$ and the training error $L_{\mathcal{D}}\left(h_{S}\right)$, i.e.

$$\epsilon_{\mathrm{est}}=L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}}$$

Here are some properties.

  • The EE arises because the empirical risk is just a proxy for the expected risk (i.e. the true risk, which is not computable because we don't know the underlying probability distribution that generated the labeled data).

  • The EE depends on the

    • training data (given that it is defined as a function of the training error, which depends on the training data), and

    • the choice of the hypothesis class (given that it is defined as a function of $\epsilon_{\mathrm{app}}$).

Bias-complexity tradeof

If we increase the size and complexity of the hypothesis class, the approximation error decreases, but the estimation error may increase (i.e. we may have over-fitting). On the other hand, if we decrease the size and complexity of the hypothesis class, the estimation error may decrease, but the bias may increase (i.e. we may have under-fitting). So, we have a bias-complexity trade-off (where the bias refers to the approximation error or inductive bias) and the complexity refers to the complexity of the hypothesis class.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.