On p.87 in this online Understanding Machine Learning book, 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.


1 Answer 1


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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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