Why do we have to be concerned about the problem of overfitting on the training set?

Question

For a hypothesis set $H=\{h_1,...,h_M\}$, randomly sampled training set $D_{train}$, and a learned hypothesis $g$ using $D_{train}$, the VC-bound of a finite hypothesis set tells us

$$ P[|E_{in}(g)-E_{out}(g)|<\epsilon] \geq 1-2|H|e^{-2\epsilon^{2}|D_{train}|} $$

where $E_{in}(g)$ is the in-sample error of $g$ and $E_{out}(g)$ is the out-of-sample error of $g$.

This result implies that very complex hypothesis set can increase inaccuracy of learning by increasing generalization error $\sqrt{{1 \over 2|D_{train}|}ln{2|H|\over\delta}}$. Ok. It's right.

However, consider following situation.

Given the finite hypothesis set $H=\{h_1,...,h_M\}$, randomly sampled training set $D_{train}$, our empirical risk minimization algorithm(ERM) picks the hypothesis which minimizes $E_{in}$. Suppose that we finally got $h_2$ as the result of this algorithm for this training set $D_{train}$. In other words, suppose that $h_2 = argmin_{h \in H} E_{in}(h)$ for this training set $D_{train}$.

Suppose that there was some person who insisted that $h_2$ is the best hypothesis before looking at the training set $D_{train}$. For this guy, $D_{train}$ is randomly sampled training set regardless of $h_2$.

So he can insist that

$$ P[|E_{in}(h_2)-E_{out}(h_2)|<\epsilon] \geq 1-2e^{-2\epsilon^{2}|D_{train}|} $$

by using Hoeffding's inequality.

This means that for at least probability $1-\delta$,

$$E_{out}(h_2) \leq E_{in}(h_2) + \sqrt{{1 \over 2|D_{train}|}ln{2\over\delta}}\:.$$

If we used really complex hypothesis set, the value $E_{in}(h_2)$ might be really small. Since the term $\sqrt{{1 \over 2|D_{train}|}ln{2\over\delta}}$ is not affected by complexity of hypothesis set $H$, it seems that more complex hypothesis set makes the bound $E_{in}(h_2) + \sqrt{{1 \over 2|D_{train}|}ln{2\over\delta}}$ tighter.

So this result tells us that using complex hypothesis set guarantees that we can find some $h$ which has very tight bound on $E_{out}(h)$. In other words, this result tells us that using complex hypothesis set makes the out-of-sample of learned hypothesis lower.

Then why are people concerned about overfitting?

Where am I doing wrong?

I think I don't fully understand how to apply the inequality $$ P[|E_{in}(g)-E_{out}(g)|<\epsilon] \geq 1-2|H|e^{-2\epsilon^{2}|D_{train}|}\:. $$

If we find some hypothesis $h$ which has really low $E_{in}(h)$, then Hoeffding's inequality always guarantee that $E_{out}(h)$ will be also smaller regardless of the complexity of hypothesis set. Also, complex hypothesis set makes us find the hypothesis which has really low $E_{in}(h)$. So isn't using a more complex hypothesis set always good?

Answer 1

Let's first be clear on the notation. Let's say the empirical risk minimization algorithm (ERM) picks a hypothesis $f\in H$. It's obvious that $f$ depends on the training data, $D_{train}$ (that's why we call it $\textbf{empirical}$ risk minimization). So we say the output of our ERM algorithm is $f(D_{train})$.

Since we don't have infinite training set, we cannot be sure that $f(D_{train})$ will equal to $h_2$, which you defind to be $argmin_{h \in H} E_{in}(h)$.

So it's true that: $$E_{out}(h_2) \leq E_{in}(h_2) + \sqrt{{1 \over 2|D_{train}|}ln{2\over\delta}}\:.$$

This is the error bound of the guy who insisted that $h_2$ is the best hypothesis before looking at the training set $D_{train}$ (but how did he? Did he have infinite secret training data? If that was the case, then yes, over-fitting is way irrelevant!)

Unfortunately, it's not the error bound we get with our ERM algorithm on limited training data because what it outputs is $f(D_{train})$ which could be $h_2$ for some training data sets but could also be $h_1$, $h_3$, etc for some other training data sets.

In fact, we could very likely get $h_1$, $h_3$, that predict very poorly on test data. The more complicated the hypothesis space $H$ is, the less likely ERM output $h_2$ as desired.

In brief, I think what you confuse is that you assume you can find $h_2$ that minimize $E_{in}(h)$ from a $\textbf{limited}$ training set. Remember that with limited training data, what we see is empirical risk, not $\textbf{expectation}$ of any kind and what we try to minimize is sadly an expectation, so don't be over-optimistic!