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?


1 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!


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.