Why do we have to be concerned about the problem of overfitting on the training set? 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?
 A: 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!
