why is Hoeffding's inequality correct in machine learning?

Question

Suppose we are given some training set $D$ of elements $(x_{i}, y_{i})$ and a classifier $h: X \rightarrow Y$. Define the in sample error of $h$ to be

$E_{in}(h) = \frac{1}{n} \sum_{i=1}^{n} 1_{h(x_{i})\neq y_{i}}$

Then Hoeffding's inequality says the following:

$Pr(|E_{in} - E_{out}| \geq \epsilon) \leq 2e^{-2n\epsilon^2}$

Now, suppose I choose $h$ to be the following function:

$h(x) = 1$ if $x$ is in $D$

$h(x) = 0$ otherwise

$E_{in} = 0$

then Hoeffding's inequality says that

$Pr(|E_{out}| \geq \epsilon) \leq 2e^{-2n\epsilon^2}$

however the out of sample error is expected to be very big while what this inequality says is that for large training set the probability that the out of sample is larger than 0 decreases exponentially!

Answer 1

As far as I'm concerned it's not valid since it deals with hypotheses and allows only one try. Think of it this way: You have a data set and you guess the hypothesis. You have only one try. If you have enough data and you want a guess as accurate as $\epsilon$ then your chance can be computed by the right hand side. If it does not satisfy you, solve for $n$ and you know how much data you'll need. This will be a huge number since the equation covers the worst case. It's also obvious that you still have a chance for a bad event.

However if you want to generalize with machine learning you need to pick a lot of hypotheses since ML uses iterations to nudge the parameters in a certain way to achieve an lower in sample Error $E_{in}$ in hope that it will represent the never known out of sample error $E_{out}$. Since you guessing in each iteration a new hypothesis, your worst case probability for a bad event is the union bound. With this rigid assumption you won't be able to learn at all.

To be able to learn you need to switch from hypotheses to dichotomies. This accounts for bad overlapping events. Unfortunately this results in a lot of proofs which need to be done. You need to know about vc dimensions, break points and make sure that your growth function is polynomial or at least bound by a polynomial.

If you did the theoretical part and made a proof for every thing you'll get the VC Inequality, which looks very similar to Hoeffdings equation:

$P\left(\sup_{f \in \mathcal{F}} \left |\hat{R}_n(f) - R(f) \right | >\varepsilon \right) \leq 8 S(\mathcal{F},n) e^{-n\varepsilon^2/32}$

In general it says that the probability that you can generalize, so that the difference between $E_{in}$ and $E_{out}$ is smaller than $\epsilon$ gets higher if you have enough data to learn from.

The VC proof is elegant but nothing really new. Think about arithmetic mean of variables. If you have 9 and 11 the mean is 10 but it's not reliable since you just have two values. If your third measurement is 15, you're doomed. Now if you have a much bigger set, say of 100 or 1000 values your mean value is much more 'secure', reliable or representative, however you want to call it, and is less dependent from individual measurements and thus generalizes the data better.

The right part basically says that for each parameter you want to learn, generalize or fit you need 'approximately' (rule of thumb) more than 10 observations.

There is a good online course from Caltech about machine learning which covers the entire theory.

Answer 2

As $n$ grows, your $h$ changes, and hence it's a different expectation. Hoeffding's inequality doesn't apply.

Answer 3

In the following answer, I assume that the question tries to apply $E_{in}$ as the test error rate and $E_{out}$ as the true error rate. The current question formulation is ambiguous on this issue.

The theorem application is wrong

The cause of the confusion comes from misapplication of Hoeffding's Inequality. Hoeffding's Inequality deals with random variables and probabilities. However the question's set up involves constants, for example, the statement $$Pr(|E_{out}| \geq \epsilon) \leq 2e^{-2n\epsilon^2}$$

doesn't even make sense as $E_{out}$ is a constant.

Starting from the beginning, what one version of the inequality states is :

Hoeffding's Inequality. Let $Z_1, \ldots, Z_n$ be random, independent random variables, such that $0 \leq Z_i \leq 1$. Then,

$$Pr(|\frac{1}{n}\sum_{i=1}^n Z_i - E(\sum_{i=1}^n Z_i)| > \epsilon) \leq 2e^{-2n\epsilon^2}$$

The inequality is a statement about probability that a difference between the RANDOM variable $\frac{1}{n}\sum_{i=1}^n Z_i$ and the constant $E(\sum_{i=1}^n Z_i)$ is larger than some value $\epsilon$.

The question seems to try to substitute the $E_{in}$ term as the random variable. That doesn't work because $\mathbb{1}_{h(x_i) = y}$ is not random - the question's author assumes that a set $\lbrace x_1, \ldots, x_d\rbrace = D$ is given as $h$ is defined on $D$. Also it's not clear how would the true error rate $E_{out}$ relate to that definition of $Z_i$.

To summarize, the statement

Then Hoeffding's inequality says the following: $Pr(|E_{in} - E_{out}| \geq \epsilon) \leq 2e^{-2n\epsilon^2}$

doesn't even make sense.

Correct application

A correct application of the inequality would look as follows.

Let $h$ be a classifier defined on a finite domain $X$. Let $Z_i, i \in \lbrace 1, \ldots, n\rbrace$ be a collection of i.i.d. variables, such that $Z_i = 0$ if $h(x)$ correctly classifies a random sample $x \in X$ and $Z_i = 1$ if the classification is incorrect. Note that $E(Z)$ is the true error rate of the classifier $h$.

You can check that all conditions of the Hoeffding's lemma occur. Therefore

$$Pr(|\frac{1}{n}\sum_{i=1}^n Z_i - E(\sum_{i=1}^n Z_i)| > \epsilon) = Pr(|\frac{1}{n}\sum_{i=1}^n Z_i - E_{out}| > \epsilon) \leq 2e^{-2n\epsilon^2}$$

If you were now to get a random sample of size $n$: $(x_i, y_i) \in D$, and calculate $h$'s error rate on that test data, then the theorem guarantees that the chance that your measured error is different from the true error by more than $\epsilon$ is less than $2e^{-2n\epsilon^2}$. Note that the crucial point here is that the test data was chosen randomly from the domain space.

Answer 4

I think there might be a flaw in the computation. The $h$ you have defined is $1_{D}$. But we have no conditions on $y_i$, so there is no reason to expect that $y_i = 1 \;\forall i$, thus I don't see why $E_{in}(h) \rightarrow 0$.

The bigger issue, however, is you are breaking the some of the assumptions required for the Hoeffding inequality. I've considered the same problem here. The following is a treatment that might make it clearer as to why this choice of $h$ fails.

Instead of your $h$, lets consider the one I think you "meant" to pick. $$ h(x_i)= \begin{cases} y_i \;\forall x_i \in D,\\ 0\text{ otherwise} \end{cases} $$

This infact yields $E_{in}(h)=0$ for the $E_{in}$ definition given. The problem is that if you do this your $h$ now depends on the choice of $D$ (as Memming mentions).

This gets confusing because there are 2 sets of "samples" to be considered. The dataset $D$ and samples from the binary RV created by assessing if $h(x) \neq y \;\forall x \in X$, lets call it $B$. How is $B$ defined?
$$ B(x)= \begin{cases} 1\text{ if }h(x) \neq y,\\ 0\text{ otherwise} \end{cases} $$

What we are actually trying to minimize is $P(B(x) = 1)$. First note that $P(B(x) = 1) = P({x \in X| h(x) \neq y}) = E(1_{h(x) \neq y}^{X})=E_{out}(h)$ where $1_{h(x) \neq y}^{X}$ is the indicator for $h(x) \neq y$ on $X$. Additionally $E_{in}(h) = E(1_{h(x) \neq y}^{D})$. Here the samples being considered are samples of $B$. When $h$ is picked before the samples, the samples of $B$ are independent. However, if $h(x_i)$ is picked to match $y_i$, each sample of $B$ is no longer distributed the same as the previous sample of $B$.

To see why this is true, note that the distribution on $B$ is a function of the distribution on $X$. If you consider the set $S = \{x \in X| h(x) \neq y\}$, we can form a partition of $X = S \bigcup S^c$. Note that under this choice $P(B = 1) = P(x \in S)$. In the case where $h$ is picked before $D$, $S$ is fixed, and $P(S) = E_{out}(h)$ is constant.

In the adaptive case where we choose $h$ as we go, this is not the case. Before the first sample of $X$ is drawn, $S = \emptyset$. As $D$ grows (we take more samples), so does $S$. For a given $D$ and this adaptive $h$, we have that $S \supset D$ (it may be that some $y$'s are zero in which case this $h$ would get them correct by accident). As noted $E_{out}(h) = P(S) = P(B=1)$ which now changes with $D$. The RV $B$ can be looked at as picking an $x$ from $X$, and determining if it's in $S$. For each sample added to $D$ we get a new distribution on $B$. Let's name the $B$ for the given sample depth $n$, $B_n$.

Fix an $n$ and considerer the $B_n$. Let us take $n$ samples of this $B$ and compute the sample mean, call it $\bar{B_n}$. If we take another sample of $X$, we'll need to update our $h$ and thus our $B$. We now have a problem, because all the previous samples were from $B_n$ which is distributed slightly differently than our new $B_{n+1}$. So this next sample of $B_{n+1}$ is not identically distributed to the previous of $B_n$ used to compute $\bar{B_n}$. As we take samples of $X$, the RV that we want to sample from, $B$, is changing.

The TLDR summary is changing $h$ before samples breaks the IID requirement of Hoeffding.