# In learning theory, why can't we use Hoeffding's Inequality as our final bound if the learnt hypothesis is part of $\mathcal{H}$?

This question has similar answers somewhere, but I do not understand them still:

In the notes here, we see the definition of PAC Learning:

Definition 3 (Generalization Gap). Given an sample set $$S=\left(x_i, y_i\right), i \in\{1, \ldots, m\}$$, drawn i.i.d. from $$\mathcal{D}$$, a hypothesis $$h_S$$ learnt on $$S$$, and a specific definition of loss $$l$$, the generalization gap is defined as $$\epsilon_{\text {gen }}\left(h_S\right)=\left|R\left[h_S\right]-\hat{R}_S\left[h_S\right]\right|$$

Definition 9 (PAC Learning). A hypothesis class $$\mathcal{H}$$ is (Agnostic) PAC Learnable if given some arbitrary $$\epsilon, \delta>0$$ there exist an $$m_{\mathcal{H}}(\epsilon, \delta)$$ such that for any $$S$$ with $$|S|>m_{\mathcal{H}}(\epsilon, \delta)$$ we have $$\epsilon_{g e n}\left(h_S\right) \leq \epsilon$$ with probability at least $$1-\delta$$. The "probably" (P) part of PAC corresponds to $$1-\delta$$ while the "approximately correct" (AC) part corresponds to $$\epsilon$$. $$m_{\mathcal{H}}(\epsilon, \delta)$$ is known as the Sample Complexity of the hypothesis class.

We will now show that any finite hypothesis class $$\mathcal{H}$$ is agnostic PAC learnable. We first derive a probabilistic bound on the following distance that holds for any $$h \in \mathcal{H}$$ : $$\left|R[h]-\hat{R}_S[h]\right|$$ We notice that this is just the absolute distance between the empirical average $$\hat{R}_S[h]$$ and its mean since: $$\mathbb{E}\left[\hat{R}_S[h]\right]=\mathbb{E}\left[\frac{1}{m} \sum_{i=1}^m \ell\left(h\left(x_i\right), y_i\right)\right]=\frac{1}{m} \sum_{i=1}^m \mathbb{E}\left[\ell\left(h\left(x_i\right), y_i\right)\right]=R[h]$$ We can use Hoeffding's inequality to decide how many samples we would need to take to guarantee that $$P\left(\left|\hat{R}_S[h]-R[h]\right|<\epsilon\right)>1-\delta$$ If we set $$\delta=\exp \left(-2 m \epsilon^2\right)$$ we can solve to get $$m=O\left(\frac{-\log (\delta)}{\epsilon^2}\right)$$. Note: this is a lower bound on the sample size which guarantees the statement above, (see Sample Complexity in the PAC Learning definition above).

Now, suppose we consider an arbitrary $$h \in \mathcal{H}$$ and a loss function $$\ell$$ with range $$[0,1]$$. For the random variable $$\hat{R}_S[h]$$ we can use Hoeffding's inequality to get: $$P\left(\left|\hat{R}_S[h]-R[h]\right| \geq \epsilon\right) \leq 2 \exp \left(-2 m \epsilon^2\right)$$

Note: We cannot simply replace $$h$$ with $$h_S$$ in this bound because the loss on the data points will not be independent any more, and therefore Hoeffding inequality will not hold.

Subsequently, to bound the generalization bound, a first attempt is to use Union bound:

So to extend this bound for $$\epsilon_{\text {gen }}\left(h_S\right)$$ we will use union bound: \begin{aligned} P\left(\left|\hat{R}_S\left[h_S\right]-R\left[h_S\right]\right| \geq \epsilon\right) & \leq P\left(\max _{h \in \mathcal{H}}\left|\hat{R}_S\left[h_S\right]-R\left[h_S\right]\right|>\epsilon\right) \\ & =P\left(\bigcup_{h \in \mathcal{H}}\left\{\left|\hat{R}_S[h]-R[h]\right|>\epsilon\right\}\right) \\ & \stackrel{(a)}{\leq} \sum_{h \in \mathcal{H}} P\left(\left|\hat{R}_S[h]-R[h]\right|>\epsilon\right) \\ & =2|\mathcal{H}| \exp \left(-2 m \epsilon^2\right) \end{aligned} Where (a) follows using a union bound argument. We can prove this in the case of 2 events and then use induction. In this case $$P(A \cup B)=P(A)+P(B)-P(A \cap B) \leq P(A)+P(B)$$.

My question: I understand that the Hoeffding's Inequality will break if you replace $$h$$ by $$h_S$$ due to i.i.d. assumption being broken, then what is stopping from using $$h_S$$ in the Hoeffding's Inequality since $$h_S$$ is amongst one of the hypothesis in the set $$\mathcal{H}$$? Does the equation below mean/suggest that amongst all the $$h \in \mathcal{H}$$, there is a "worst" $$h$$?

$$\max _{h \in \mathcal{H}}\left|\hat{R}_S\left[h_S\right]-R\left[h_S\right]\right|$$

EDIT: Here's what I thought;

1. The Hoeffding's inequality does not hold for $$h_S$$ after learning.

2. This means we need to find a bound for $$h_S$$ since it failed to hold in point 1.

3. But we do know the $$\epsilon_{gen}(h_S)$$ is smaller than $$\epsilon_{gen}(h_{worst})$$ where $$h_{worst}$$ is the worst $$h$$ (gives the largest gen gap).

4. This $$h_{worst}$$ can be expressed as a union of all $$h$$'s.

5. So the assumption is not broken if we enumerate all $$h \in \mathcal{H}$$.

• It seems that you are asking multiple questions here. To increase the likelihood of someone answering your questions, it would be a good idea to separate the questions into different posts, so that they are more easily digestible. Feb 28 at 12:27

Does the equation below mean/suggest that amongst all the $$h \in \mathcal{H}$$, there is a "worst" $$h$$?

$$\max _{h \in \mathcal{H}}\left|\hat{R}_S\left[h_S\right]-R\left[h_S\right]\right|$$

The gap differs for different hypotheses.

In particular, a model that is always wrong, will have $$\hat{R}_S\left[h_S\right]-R\left[h_S\right] = 0$$ because it has the same maximum losses for $$\hat{R}_S\left[h_S\right]$$ and $${R}\left[h_S\right]$$

My question: I understand that the Hoeffding's Inequality will break if you replace $$h$$ by $$h_S$$ due to i.i.d. assumption being broken, then what is stopping from using $$h_S$$ in the Hoeffding's Inequality since $$h_S$$ is amongst one of the hypothesis in the set $$\mathcal{H}$$?

The Hoeffding's inequality is applied to the situation where there is a single hypothesis $$h$$. With the learning algorithm you have however multiple hypotheses $$h_1,h_2, \dots, h_n$$ out of which you select the one with the with the lowest empirical risk $$\hat{R}_S(h_i)$$.

The $$\hat{R}_S(h_i)$$ might (and probably will) correlate with the gap $$\epsilon(h_i)$$. For instance, overfitting makes us select a hypothesis with a low risk $$\hat{R}_S(h_i)$$ that is likely gonna be underestimated. The selection for the lowest risk will make the gap probably larger than without the selection.

That is why you can not simply use $$h_S$$ directly in Hoeffding's inequality. The gap of the hypothesis $$h_S$$ can be larger than what we expect from the formula that considers a single hypothesis (and not one that has been selected based on an optimal $$\hat{R}_S$$).

• Thank you, I understood on the correlated part. However, what is bothering me is that in the union bound $P\left(\bigcup_{h \in \mathcal{H}}\left\{\left|\hat{R}_S[h]-R[h]\right|>\epsilon\right\}\right)$ here, the formula gives me the impression that for any arbitrary $h \in \mathcal{H}$, the probability of a bad event (generalization gap) more than $\epsilon$ is less than the $\delta$ (RHS). Then the reasoning I have is, since the final hypothesis chosen by the learner $h_S \in \mathcal{H}$, then does it not mean $h_S$ is also one of the arbitrary $h$? So I don't get the union part here.
– nan
Feb 28 at 13:24
• @nan The $h_S$ is one of the $\mathcal{H}$, but that doesn't make that the situation is not different. Say you repeat the experiment every time. The Hoeffdings inequality is valid when every of those times you use the same single $h$. This is in contrast with the learning algorithm where the $h_S$ is not the same every time, but instead it is selected based on the lowest $\hat{R}_S$ and every time a different one out of one of the arbitrary $h$. This makes that $h_S$ can be prejudiced towards a larger gap. Feb 28 at 13:33
• If you have some $h_S$ and draw a new sample $S^\prime$ then you can place $h_S$ into the formula $$P\left(\left|\hat{R}_{S^{\prime}}[h_S]-R[h_S]\right| \geq \epsilon\right) \leq 2 \exp \left(-2 m \epsilon^2\right)$$ A problem is that for the sample $S$ that had been used to select the hypothesis $h_S$, the gap might be larger. (because the selection process might correlate with the gap, the selected hypothesis is biased to have a low risk for the particular sample that had been used to select it) Feb 28 at 13:44
• For the statement: Say you repeat the experiment every time. The Hoeffdings inequality is valid when every of those times you use the same single $h$. What does the act of experiment refers to? Is it holding a fixed training dataset and a fixed $h$?
– nan
Feb 28 at 14:09
• The act of a repetition of the experiment refers to the act of generating a totally new sample. Feb 28 at 14:10