<p>The answer is right under my noise but I'd failed to see it.</p>
<p>Theorem 7.4 in the book says that:</p>
<p><span class="math-container">$$
\mathbb{P}\lbrace S\sim\mathcal{D}^m: (\forall h\in\mathcal{H}) (L_\mathcal{D}(h)\le L_S(h) + \epsilon_{n(h)}(m, w(n(h))\cdot\delta)) \rbrace \ge 1-\delta.
$$</span></p>
<p>So when <span class="math-container">$L_S(h) + \epsilon_{n(h)}(m, w(n(h))\cdot\epsilon)$</span> is minimized, we have with probability of at least <span class="math-container">$1-\epsilon$</span>, the upper bound of <span class="math-container">$L_\mathcal{D}(h)$</span> is also minimized. This implies the upper bound <span class="math-container">$\epsilon_{est}:=L_\mathcal{D}(h)-\min_{h\in\mathcal{H}} L_\mathcal{H}(h)$</span> is minimized also (with probability <span class="math-container">$\ge1-\epsilon$</span>) because <span class="math-container">$\min_{h\in\mathcal{H}} L_\mathcal{H}(h)$</span> is constant for some hypothesis class <span class="math-container">$\mathcal{H}$</span>.</p>

CC BY-SA 4.0
2023-11-11T06:41:37.630Z
2023-11-11T06:41:37.630Z
Tran Khanh
<p>On p.87 in this online <a href="https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf" rel="nofollow noreferrer">Understanding Machine Learning book</a>, the authors wrote:</p>
<blockquote>
<p>Unlike the ERM paradigm discussed in previous chapters, we no longer just care about the empirical risk, <span class="math-container">$L_S(h)$</span>, but we are willing to trade some of our bias toward low empirical risk with a bias toward classes for which <span class="math-container">$\epsilon_{n(h)}(m, w(n(h))\cdot\epsilon)$</span> is smaller, for the sake of a <strong>smaller estimation error</strong>.</p>
</blockquote>
<p>With the output <span class="math-container">$h$</span> of SRM defined to be:</p>
<blockquote>
<p>Output: <span class="math-container">$h\in\underset{h\in\mathcal{H}}{argmin}\ L_S(h)+\epsilon_{n(h)}(m, w(n(h))\cdot\delta)$</span>.</p>
<p>Where <span class="math-container">$\epsilon_n(m, \delta) := min\ \lbrace\epsilon\in (0, 1): m_\mathcal{H_n}^{UC}(\epsilon, \delta)\le m \rbrace$</span>, <span class="math-container">$w(n)$</span> is a function from <span class="math-container">$n\in\mathbb{N}\to[0, 1]$</span> such that <span class="math-container">$\sum_{n=1}^{\infty}w(n)\le1$</span> and <span class="math-container">$n(h):=min\lbrace n: h\in\mathcal{H}_n\rbrace$</span></p>
</blockquote>
<p>That is the output learner <span class="math-container">$h$</span> will minimize <span class="math-container">$L_S(h)+\epsilon_{n(h)}(m, w(n(h))\cdot\delta)$</span>.</p>
<p>However, <span class="math-container">$\epsilon_n$</span> as defined above is the lowest possible upper bound on the gap between <span class="math-container">$L_S(h)-L_\mathcal{D}(h)$</span> achieved by using a sample of <span class="math-container">$m$</span> examples from the hypothesis class <span class="math-container">$\mathcal{H}_n$</span> , while the estimation error is defined to be:</p>
<p><span class="math-container">$$\epsilon_{est}:=L_\mathcal{D}(h)-\underset{h\in\mathcal{H}}{min} L_\mathcal{D}(h).$$</span></p>
<p>Besides, the Theorem 7.4. in the book shows that:</p>
<p><span class="math-container">$$
\mathbb{P}\lbrace S\sim\mathcal{D}^m: (\forall h\in\mathcal{H}) (L_\mathcal{D}(h)\le L_S(h) + \epsilon_{n(h)}(m, w(n(h))\cdot\delta)) \rbrace \ge 1-\delta,
$$</span></p>
<p>so minimizing <span class="math-container">$L_S(h)+\epsilon_{n(h)}(m, w(n(h))\cdot\delta)$</span> will, with at least <span class="math-container">$1-\delta$</span> probability, minimize <span class="math-container">$L_\mathcal{D}(h)$</span> but it's not the same as to minimize <span class="math-container">$\epsilon_{est}$</span>?</p>
<p>And so I couldn't find the connection between the minimization of <span class="math-container">$L_S(h)+\epsilon_{n(h)}(m, w(n(h))\cdot\delta)$</span> and the smaller estimation error.</p>

<machine-learning><lg.learning>
Why is the estimation error smaller in Structural Risk Minimization
Tran Khanh
# Why is the estimation error smaller in Structural Risk Minimization

(Asked by: username_0 on 2023-11-11)

On p.87 in this online [Understanding Machine Learning book](https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf), the authors wrote:

> Unlike the ERM paradigm discussed in previous chapters, we no longer just care about the empirical risk, $L\_S(h)$, but we are willing to trade some of our bias toward low empirical risk with a bias toward classes for which $\epsilon\_{n(h)}(m, w(n(h))\cdot\epsilon)$ is smaller, for the sake of a **smaller estimation error**.

With the output $h$ of SRM defined to be:

> Output: $h\in\underset{h\in\mathcal{H}}{argmin}\ L\_S(h)+\epsilon\_{n(h)}(m, w(n(h))\cdot\delta)$.
>
> Where $\epsilon\_n(m, \delta) := min\ \lbrace\epsilon\in (0, 1): m\_\mathcal{H\_n}^{UC}(\epsilon, \delta)\le m \rbrace$, $w(n)$ is a function from $n\in\mathbb{N}\to[0, 1]$ such that $\sum\_{n=1}^{\infty}w(n)\le1$ and $n(h):=min\lbrace n: h\in\mathcal{H}\_n\rbrace$

That is the output learner $h$ will minimize $L\_S(h)+\epsilon\_{n(h)}(m, w(n(h))\cdot\delta)$.

However, $\epsilon\_n$ as defined above is the lowest possible upper bound on the gap between $L\_S(h)-L\_\mathcal{D}(h)$ achieved by using a sample of $m$ examples from the hypothesis class $\mathcal{H}\_n$ , while the estimation error is defined to be:

$$\epsilon\_{est}:=L\_\mathcal{D}(h)-\underset{h\in\mathcal{H}}{min} L\_\mathcal{D}(h).$$

Besides, the Theorem 7.4. in the book shows that:

$$
\mathbb{P}\lbrace S\sim\mathcal{D}^m: (\forall h\in\mathcal{H}) (L\_\mathcal{D}(h)\le L\_S(h) + \epsilon\_{n(h)}(m, w(n(h))\cdot\delta)) \rbrace \ge 1-\delta,
$$

so minimizing $L\_S(h)+\epsilon\_{n(h)}(m, w(n(h))\cdot\delta)$ will, with at least $1-\delta$ probability, minimize $L\_\mathcal{D}(h)$ but it's not the same as to minimize $\epsilon\_{est}$?

And so I couldn't find the connection between the minimization of $L\_S(h)+\epsilon\_{n(h)}(m, w(n(h))\cdot\delta)$ and the smaller estimation error.

**Tags:** machine-learning, lg.learning

---

## 1 answers

### Answer by username_0 on 2023-11-11. Score: 0

The answer is right under my noise but I'd failed to see it.

Theorem 7.4 in the book says that:

$$
\mathbb{P}\lbrace S\sim\mathcal{D}^m: (\forall h\in\mathcal{H}) (L\_\mathcal{D}(h)\le L\_S(h) + \epsilon\_{n(h)}(m, w(n(h))\cdot\delta)) \rbrace \ge 1-\delta.
$$

So when $L\_S(h) + \epsilon\_{n(h)}(m, w(n(h))\cdot\epsilon)$ is minimized, we have with probability of at least $1-\epsilon$, the upper bound of $L\_\mathcal{D}(h)$ is also minimized. This implies the upper bound $\epsilon\_{est}:=L\_\mathcal{D}(h)-\min\_{h\in\mathcal{H}} L\_\mathcal{H}(h)$ is minimized also (with probability $\ge1-\epsilon$) because $\min\_{h\in\mathcal{H}} L\_\mathcal{H}(h)$ is constant for some hypothesis class $\mathcal{H}$.


---

