Answers.Body: <p>I think this is best explained by pictures. Please note that <span class="math-container">$h_{S}$</span> is the output of the ERM learner (under the hypothesis class <span class="math-container">$\mathcal{H}$</span>) is denoted by <span class="math-container">$ERM_{\mathcal{H}}$</span>, <span class="math-container">$f$</span> is the target hypothesis or the true labeling function. Also:</p>
  <ol>
  <li>By definition, the approximation error <span class="math-container">$=\epsilon_{app} := \underset{h\in \mathcal{H}}{min}\ L_{\mathcal{D}}(h)$</span> is always less than or equal to the estimation error (or the generalization risk/error) <span class="math-container">$=\epsilon_{est}=\mathcal{L}_{\mathcal{D}}(h_{\mathcal{S}})$</span>.</li>
  <li>The estimation error <span class="math-container">$\epsilon_{est}=L_{\mathcal{D}}(h_{S})$</span> is <strong>NOT</strong> the training error (or empirical risk/error) <span class="math-container">$L_{S}(h_{S})$</span>, rather the estimation error results because of the training error.</li>
  </ol>
  <p>A small hypothesis class (or space) <span class="math-container">$\mathcal{H}$</span> not containing the target hypothesis <span class="math-container">$f$</span>, the hypothesis <span class="math-container">$h_{S} \in \mathcal{H}$</span> found by the <span class="math-container">$ERM_{\mathcal{H}}$</span> learner via training, by some chance - say - small training set size, is not <span class="math-container">$h^{\star}$</span>. Increasing the training set size may often help (i.e. make <span class="math-container">$h_{S}$</span> move closer or even equal to <span class="math-container">$h^{\star}$</span>):</p>
  <p><a href="https://i.sstatic.net/2Itp6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/2Itp6.png" alt="Small hypothesis class" /></a></p>
  <p>Another relatively small but slightly better hypothesis space <span class="math-container">$\mathcal{H}^{'}$</span>: The approximation error (generalization error comes from the best hypothesis) is smaller than that one, i.e. <span class="math-container">$h^{\star}$</span> closely approximates the target function:</p>
  <p><a href="https://i.sstatic.net/8Inkv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8Inkv.png" alt="Better hypothesis class" /></a></p>
  <p>A good hypothesis space <span class="math-container">$\mathcal{H^{''}}$</span>, of course the best hypothesis class is <span class="math-container">$\mathcal{H^{'''}}=\{f\}$</span> but most of the time we don't know what the (class of the) target hypothesis function <span class="math-container">$f$</span> is (if we know the function <span class="math-container">$f$</span> then learning is redundant), and especially under the assumption of agnostic PAC learning, it's often not a labeling function but rather a data generating distribution:</p>
  <p><a href="https://i.sstatic.net/oYmSb.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/oYmSb.png" alt="A good hypothesis class" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-11T14:41:28.517Z
Answers.LastActivityDate: 2023-10-12T02:26:50.743Z
Answers.LastEditDate: 2023-10-12T02:26:50.743Z
Answers.UserDisplayName: Tran Khanh
Answers.Body: <p><a href="https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=64" rel="nofollow noreferrer">Section <strong>5.2 Error Decomposition</strong></a> of the book <em>Understanding Machine Learning: From Theory to Algorithms</em> (2014) gives a description of the <strong>approximation error</strong> and <strong>estimation error</strong> in the context of <strong>empirical risk minimization (ERM)</strong> and, in particular, in the context of the <strong>bias-complexity tradeoff</strong> (which is strictly related to the <strong>bias-variance tradeoff</strong>).</p>
  <h2>Error/risk decomposition</h2>
  <p>The expected risk (error) of a hypothesis <span class="math-container">$h_S \in \mathcal{H}$</span> selected based on the training dataset <span class="math-container">$S$</span> from a hypothesis class <span class="math-container">$\mathcal{H}$</span> can be decomposed into the <strong>approximation error</strong>, <span class="math-container">$\epsilon_{\mathrm{app}}$</span>, and the <strong>estimation error</strong>, <span class="math-container">$\epsilon_{\mathrm{est}}$</span>, as follows</p>
  <p><span class="math-container">\begin{align}
  L_{\mathcal{D}}\left(h_{S}\right)
  &amp;=
  \epsilon_{\mathrm{app}}+\epsilon_{\mathrm{est}} \\
  &amp;=
  \epsilon_{\mathrm{app}}+ \left( L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \right) \\
  &amp;=
  \left( \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)\right) + \left( L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \right) \label{1}\tag{1}
  \end{align}</span></p>
  <h3>Approximation error</h3>
  <p>The <strong>approximation error</strong> (AE), aka inductive bias, defined as</p>
  <p><span class="math-container">$$\epsilon_{\mathrm{app}} = \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h) $$</span></p>
  <p>is the error due to the specific <em>choice of hypothesis class</em> (or set) <span class="math-container">$\mathcal{H}$</span>. So, <span class="math-container">$\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)$</span> is minimal risk/error that can be achieved with a hypothesis class <span class="math-container">$\mathcal{H}$</span>. In other words, if you limit yourself to <span class="math-container">$\mathcal{H}$</span> and you select the &quot;best&quot; hypothesis in <span class="math-container">$\mathcal{H}$</span>, then <span class="math-container">$\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)$</span> is the expected risk of that hypothesis.</p>
  <p>Here are some properties.</p>
  <ul>
  <li><p>The larger <span class="math-container">$\mathcal{H}$</span> is, the smaller this error is (because it's more likely that a larger hypothesis class contains the actual hypothesis we are looking for). So, if <span class="math-container">$\mathcal{H}$</span> does not contain the actual hypothesis we are searching for, then this error could not be zero.</p>
  </li>
  <li><p>This error does <strong>not</strong> depend on the training data. You can see in the formula above that there's no <span class="math-container">$S$</span> (the training dataset), but only on <span class="math-container">$D$</span> (the distribution over the space of inputs and labels from which <span class="math-container">$S$</span> was assumed to have been sampled)</p>
  </li>
  </ul>
  <h3>Estimation error</h3>
  <p>The <strong>estimation error</strong> (EE) is the <em>difference</em> between the <em>approximation error</em> <span class="math-container">$\epsilon_{\mathrm{app}}$</span> and the <em>error achieved by the ERM predictor</em> <span class="math-container">$L_{\mathcal{D}}\left(h_{S}\right)$</span>, i.e.</p>
  <p><span class="math-container">\begin{align}
  \epsilon_{\mathrm{est}}
  &amp;=L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \\
  &amp;= L_{\mathcal{D}}\left(h_{S}\right) - \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h) 
  \end{align}</span></p>
  <p>Here are some properties.</p>
  <ul>
  <li><p>The estimation error depends on the training dataset <span class="math-container">$S$</span>. You can see <span class="math-container">$S$</span> in the formula above.</p>
  </li>
  <li><p><span class="math-container">$\epsilon_{\mathrm{est}}$</span> also depends on the choice of the hypothesis class (given that it is defined as a function of <span class="math-container">$\epsilon_{\mathrm{app}}$</span>).</p>
  </li>
  </ul>
  <h2>Bias-complexity tradeoff</h2>
  <p>If we increase the size and complexity of the hypothesis class, the <strong>approximation error</strong> <em>decreases</em>, but the <strong>estimation error</strong> may <em>increase</em> (i.e. we may have <em>over-fitting</em>). On the other hand, if we decrease the size and complexity of the hypothesis class, the <strong>estimation error</strong> may decrease, but the <em>bias</em> may increase (i.e. we may have <em>under-fitting</em>). 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.</p>
  <h2>Error excess</h2>
  <p>In <a href="https://mitpress.ublish.com/ereader/7093/?preview=#page/61" rel="nofollow noreferrer">section 4.1</a> of <a href="https://mitpress.ublish.com/ereader/7093/?preview=#page/Cover" rel="nofollow noreferrer">this book</a> also describes a similar (but equivalent) error decomposition, which is called <strong>error excess</strong> because it's a difference between the expected risk and the <strong>Bayes error</strong> (which is sometimes called <strong>inherent error</strong> or <strong>irreducible error</strong>), which they denote by <span class="math-container">$R^{*}$</span>, while the other book above, which also points out that there's this equivalent <strong>error excess</strong> decomposition, denote it by <span class="math-container">$\epsilon_{\mathrm{Bayes}}$</span>. So, here's the <strong>error excess</strong></p>
  <p><span class="math-container">$$R(h)-R^{*}=\underbrace{\left(\inf _{h \in \mathcal{H}} R(h)-R^{*}\right)}_{\text {approximation excess}} + \underbrace{\left(R(h)-\inf _{h \in \mathcal{H}} R(h)\right)}_{\text {estimation error}}$$</span></p>
  <p>So, if you take <span class="math-container">$R^{*} = \epsilon_{\mathrm{Bayes}}$</span> from both sides of the equation, you end up with</p>
  <p><span class="math-container">$$R(h)=\underbrace{\left(\inf _{h \in \mathcal{H}} R(h) \right)}_{\epsilon_{\mathrm{app}}} + \underbrace{\left(R(h)-\inf _{h \in \mathcal{H}} R(h)\right)}_{\epsilon_{\mathrm{est}}} \label{2}\tag{2}$$</span></p>
  <p>which is equivalent to equation \ref{1}, where</p>
  <ul>
  <li><span class="math-container">$L_{\mathcal{D}}\left(h_{S}\right)    \equiv R(h)$</span></li>
  <li><span class="math-container">$\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)     \equiv \inf _{h \in \mathcal{H}} R(h)$</span></li>
  </ul>
  <h2>Illustration</h2>
  <p>A nice picture that illustrates the relationship between these terms can be found in figure 4.1 of <a href="https://mitpress.ublish.com/ereader/7093/?preview=#page/Cover" rel="nofollow noreferrer">this book</a> (p. 62).</p>
  <p><a href="https://i.sstatic.net/JA7M7.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/JA7M7.png" alt="enter image description here" /></a></p>
  <p>Here, the red points are specific hypotheses. In this illustration, we can see that the best hypothesis (the Bayes hypothesis) lies outside our chosen hypothesis class <span class="math-container">$\mathcal{H}$</span>. The distance between the risk of <span class="math-container">$h \in \mathcal{H}$</span> and the risk of <span class="math-container">$h^* = \operatorname{arg inf} _{h \in \mathcal{H}} R(h)$</span> is the <strong>estimation error</strong>, while the distance between <span class="math-container">$h^*$</span> and the Bayes hypothesis (i.e. the hypothesis that achieves the Bayes error) is the <strong>approximation excess</strong> in equation \ref{2}.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T10:51:33.710Z
Answers.Text: Could you please elaborate if the training error on my dataset can ever be zero ? Looking at equation above seems no. However I always thought these equations explain why the difference between train and test error can never be zero.
Answers.UserDisplayName: Siddhant Tandon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-14T11:58:32.543Z
Answers.Text: @SiddhantTandon I will try to answer your question later. In the first book, they use $L$ to refer to the training error, while, in the second, they refer to it as the expected risk of the hypothesis. I think that this use of different terminology may cause confusion because here the training error is not defined. The second book actually calls what I called the "approximation excess" the "approximation error", but I was trying to connect the definitions of the two books in this answer. There's also a clear distinction between expected risk and empirical risk.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-03T16:50:58.080Z
Answers.LastActivityDate: 2023-10-27T21:15:28.383Z
Answers.LastEditDate: 2023-10-27T21:15:28.383Z
Answers.UserDisplayName: nbro
Body: <p>I'm unable to find online, or understand from context - the difference between <strong>estimation</strong> error and <strong>approximation</strong> error in the context of machine learning (and, specifically, reinforcement learning).</p>
  <p>Could someone please explain with the help of examples and/or references?</p>
  
Tags: <machine-learning><computational-learning-theory><bias-variance-tradeoff><approximation-error>
Title: What's the difference between estimation and approximation error?
UserDisplayName: stoic-santiago
ThreadText: # What's the difference between estimation and approximation error?
  
  (Asked by: username_0 on 2020-10-02)
  
  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?
  
  **Tags:** machine-learning, computational-learning-theory, bias-variance-tradeoff, approximation-error
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-10-03. Score: 7 | Accepted answer
  
  [Section **5.2 Error Decomposition**](https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=64) 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)** and, in particular, in the context of the **bias-complexity tradeoff** (which is strictly related to the **bias-variance tradeoff**).
  
  ## Error/risk decomposition
  
  The expected risk (error) of a hypothesis $h\_S \in \mathcal{H}$ selected based on the training dataset $S$ from a hypothesis class $\mathcal{H}$ can be decomposed into the **approximation error**, $\epsilon\_{\mathrm{app}}$, and the **estimation error**, $\epsilon\_{\mathrm{est}}$, as follows
  
  \begin{align}
  L\_{\mathcal{D}}\left(h\_{S}\right)
  &=
  \epsilon\_{\mathrm{app}}+\epsilon\_{\mathrm{est}} \\
  &=
  \epsilon\_{\mathrm{app}}+ \left( L\_{\mathcal{D}}\left(h\_{S}\right)-\epsilon\_{\mathrm{app}} \right) \\
  &=
  \left( \min \_{h \in \mathcal{H}} L\_{\mathcal{D}}(h)\right) + \left( L\_{\mathcal{D}}\left(h\_{S}\right)-\epsilon\_{\mathrm{app}} \right) \label{1}\tag{1}
  \end{align}
  
  ### Approximation error
  
  The **approximation error** (AE), aka inductive bias, defined as
  
  $$\epsilon\_{\mathrm{app}} = \min \_{h \in \mathcal{H}} L\_{\mathcal{D}}(h) $$
  
  is the error due to the specific *choice of hypothesis class* (or set) $\mathcal{H}$. So, $\min \_{h \in \mathcal{H}} L\_{\mathcal{D}}(h)$ is minimal risk/error that can be achieved with a hypothesis class $\mathcal{H}$. In other words, if you limit yourself to $\mathcal{H}$ and you select the "best" hypothesis in $\mathcal{H}$, then $\min \_{h \in \mathcal{H}} L\_{\mathcal{D}}(h)$ is the expected risk of that hypothesis.
  
  Here are some properties.
  
  * The larger $\mathcal{H}$ is, the smaller this error is (because it's more likely that a larger hypothesis class contains the actual hypothesis we are looking for). So, if $\mathcal{H}$ does not contain the actual hypothesis we are searching for, then this error could not be zero.
  * This error does **not** depend on the training data. You can see in the formula above that there's no $S$ (the training dataset), but only on $D$ (the distribution over the space of inputs and labels from which $S$ was assumed to have been sampled)
  
  ### Estimation error
  
  The **estimation error** (EE) is the *difference* between the *approximation error* $\epsilon\_{\mathrm{app}}$ and the *error achieved by the ERM predictor* $L\_{\mathcal{D}}\left(h\_{S}\right)$, i.e.
  
  \begin{align}
  \epsilon\_{\mathrm{est}}
  &=L\_{\mathcal{D}}\left(h\_{S}\right)-\epsilon\_{\mathrm{app}} \\
  &= L\_{\mathcal{D}}\left(h\_{S}\right) - \min \_{h \in \mathcal{H}} L\_{\mathcal{D}}(h)
  \end{align}
  
  Here are some properties.
  
  * The estimation error depends on the training dataset $S$. You can see $S$ in the formula above.
  * $\epsilon\_{\mathrm{est}}$ also depends on the choice of the hypothesis class (given that it is defined as a function of $\epsilon\_{\mathrm{app}}$).
  
  ## Bias-complexity tradeoff
  
  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.
  
  ## Error excess
  
  In [section 4.1](https://mitpress.ublish.com/ereader/7093/?preview=#page/61) of [this book](https://mitpress.ublish.com/ereader/7093/?preview=#page/Cover) also describes a similar (but equivalent) error decomposition, which is called **error excess** because it's a difference between the expected risk and the **Bayes error** (which is sometimes called **inherent error** or **irreducible error**), which they denote by $R^{\*}$, while the other book above, which also points out that there's this equivalent **error excess** decomposition, denote it by $\epsilon\_{\mathrm{Bayes}}$. So, here's the **error excess**
  
  $$R(h)-R^{\*}=\underbrace{\left(\inf \_{h \in \mathcal{H}} R(h)-R^{\*}\right)}\_{\text {approximation excess}} + \underbrace{\left(R(h)-\inf \_{h \in \mathcal{H}} R(h)\right)}\_{\text {estimation error}}$$
  
  So, if you take $R^{\*} = \epsilon\_{\mathrm{Bayes}}$ from both sides of the equation, you end up with
  
  $$R(h)=\underbrace{\left(\inf \_{h \in \mathcal{H}} R(h) \right)}\_{\epsilon\_{\mathrm{app}}} + \underbrace{\left(R(h)-\inf \_{h \in \mathcal{H}} R(h)\right)}\_{\epsilon\_{\mathrm{est}}} \label{2}\tag{2}$$
  
  which is equivalent to equation \ref{1}, where
  
  * $L\_{\mathcal{D}}\left(h\_{S}\right) \equiv R(h)$
  * $\min \_{h \in \mathcal{H}} L\_{\mathcal{D}}(h) \equiv \inf \_{h \in \mathcal{H}} R(h)$
  
  ## Illustration
  
  A nice picture that illustrates the relationship between these terms can be found in figure 4.1 of [this book](https://mitpress.ublish.com/ereader/7093/?preview=#page/Cover) (p. 62).
  
  [![enter image description here](https://i.sstatic.net/JA7M7.png)](https://i.sstatic.net/JA7M7.png)
  
  Here, the red points are specific hypotheses. In this illustration, we can see that the best hypothesis (the Bayes hypothesis) lies outside our chosen hypothesis class $\mathcal{H}$. The distance between the risk of $h \in \mathcal{H}$ and the risk of $h^\* = \operatorname{arg inf} \_{h \in \mathcal{H}} R(h)$ is the **estimation error**, while the distance between $h^\*$ and the Bayes hypothesis (i.e. the hypothesis that achieves the Bayes error) is the **approximation excess** in equation \ref{2}.
  
  > **Comments:**
  > **username_3**: Could you please elaborate if the training error on my dataset can ever be zero ? Looking at equation above seems no. However I always thought these equations explain why the difference between train and test error can never be zero.  
  > **username_2**: @SiddhantTandon I will try to answer your question later. In the first book, they use $L$ to refer to the training error, while, in the second, they refer to it as the expected risk of the hypothesis. I think that this use of different terminology may cause confusion because here the training error is not defined. The second book actually calls what I called the "approximation excess" the "approximation error", but I was trying to connect the definitions of the two books in this answer. There's also a clear distinction between expected risk and empirical risk.  
  
  ---
  
  ### Answer by username_1 on 2023-10-11. Score: 1
  
  I think this is best explained by pictures. Please note that $h\_{S}$ is the output of the ERM learner (under the hypothesis class $\mathcal{H}$) is denoted by $ERM\_{\mathcal{H}}$, $f$ is the target hypothesis or the true labeling function. Also:
  
  1. By definition, the approximation error $=\epsilon\_{app} := \underset{h\in \mathcal{H}}{min}\ L\_{\mathcal{D}}(h)$ is always less than or equal to the estimation error (or the generalization risk/error) $=\epsilon\_{est}=\mathcal{L}\_{\mathcal{D}}(h\_{\mathcal{S}})$.
  2. The estimation error $\epsilon\_{est}=L\_{\mathcal{D}}(h\_{S})$ is **NOT** the training error (or empirical risk/error) $L\_{S}(h\_{S})$, rather the estimation error results because of the training error.
  
  A small hypothesis class (or space) $\mathcal{H}$ not containing the target hypothesis $f$, the hypothesis $h\_{S} \in \mathcal{H}$ found by the $ERM\_{\mathcal{H}}$ learner via training, by some chance - say - small training set size, is not $h^{\star}$. Increasing the training set size may often help (i.e. make $h\_{S}$ move closer or even equal to $h^{\star}$):
  
  [![Small hypothesis class](https://i.sstatic.net/2Itp6.png)](https://i.sstatic.net/2Itp6.png)
  
  Another relatively small but slightly better hypothesis space $\mathcal{H}^{'}$: The approximation error (generalization error comes from the best hypothesis) is smaller than that one, i.e. $h^{\star}$ closely approximates the target function:
  
  [![Better hypothesis class](https://i.sstatic.net/8Inkv.png)](https://i.sstatic.net/8Inkv.png)
  
  A good hypothesis space $\mathcal{H^{''}}$, of course the best hypothesis class is $\mathcal{H^{'''}}=\{f\}$ but most of the time we don't know what the (class of the) target hypothesis function $f$ is (if we know the function $f$ then learning is redundant), and especially under the assumption of agnostic PAC learning, it's often not a labeling function but rather a data generating distribution:
  
  [![A good hypothesis class](https://i.sstatic.net/oYmSb.png)](https://i.sstatic.net/oYmSb.png)
  
  
  ---
  
  