Is Learning Feasible? Hoeffding Inequality

This article explores the question: Is learning feasible? To do that, we first developed an intuition and then use the Hoeffding Inequality to formarly explain our inution.

The learner $\mathcal{A}$, in principle, only have limited data (training set) to pindown the theorical entire target function $f(x)$. However, this limited data set could reveal enough information or not depending of the prespective (discrete or probabilitic), and we will describe these prespectives later.

First, it's important to define what we understand for feasible learning. Our notion of learning in this context is the following:

• Learning: A learner is learning if it is able to tell us anything outside of training set ($\mathcal{T}$).
• Memorization: A learner is only memorizing if it only knows the target $f$ for all points in our training set.

Why learning something outside $\mathcal{T}$ is challenging in a discrete perspective?

In a discrete prespective, we expect that our learner is able to learn all the in-samples and out-samples. However, that is not practically possible because our limited training set cannot tell us something concrete (or certain) about something outside our training set.

Illustrated with an example, using the following training set, we are interested in learning an optimal function $g$, such that $g = f$; or in other words $g$ must be able to correctly predict all in-samples and out-samples.

Picking any of those candidates ($f_1, f_2, \cdots, f_8$) could be a possible optimal $g$ because they predict correctly our in-samples.

However, these candidates don't give us a concrete (certain) information outside the dataset (out-samples). Any possible value in ?'s can be acceptable in theory because we don't know what is actually happening outside the dataset.

Nevertheless, although the discrete case is not possible, the training set can still give us a probabilitic approximation. We are able to infer something outside $\mathcal{T}$ using only $\mathcal{T}$, but in a probabilitic way using Hoeffding Inequality.

Hoeffding Inequality is a concentration inequality, which provides an exponential bound on the probability that the sample mean deviates significantly from the true expected value.

Let $z_1, \cdots, z_N$ be random independent indentically distributed random variables, such that $0 \leq z_i \leq 1$.

where,

• $\nu = \frac{1}{N}\sum^N_{i=1}z_i$ is the sample mean
• $\mu = E_{z\sim p}[z]$ is the expected value (or population value)

Important Takeways

1. It is not a tight bound because is bounded by 2, and probability can't be greater than 1.
2. The only quantity that is random is $\nu$ (it a random variable), $u$ is unknown but not random.
3. The size of the population (bin) doesn't matter. The population could be small or large, finite or infinite.
4. iid condition: The fact that the sample is iid draw from the population is a necessary condition to apply Hoeffding Inequality.

In order to use our Hoeffding Inequality in Machine Learning, we focused in the simple Supervised Learning Framework, where we try to predict $g: \mathcal{X} \rightarrow \mathcal{Y}$, such that $g$ approximates the true target function $f: \mathcal{X} \rightarrow \mathcal{Y}$.

In this framework, we can additionally distinguish in-sample and out-sample examples, which will be consider to calculate the errors:

• in-sample examples are the training examples.
• out-sample examples are all the other examples that are not training examples, but belongs to $\mathcal{X}$.

We can replace the respective sample mean and expected value from Hoeffding Inequality with our equivalence in Machine Learning, where

1. $\nu = E_{in}$ is our in-sample error (or training error).
• It is our random variable because it depends on a training set.
• We can calculate this error because we know $f(x^{(i)})$ (our label from training set).
2. $\mu = E_{out}$ is our out-sample error (or generalization error) calculated across all possible examples.
• It is unknown but not random.
• We can't calculate it because we don't known $f(x)$

We can notice that using $E_{in}$ (or sample mean) tell us something about our $E_{out}$ (or expected value). Specifically, it tell us the our training error $E_{in}$ can approximate our $E_{out}$

In other words and to understand it better

1. In order to use the Hoeffding inequality, we have to guarantee that the sample is drawn iid.
2. However, in the Supervised Learning framework, we first choose $g$ using our training set.
   
   If we train our model, find a $g$, fix that $g$, and finally calculate $E_{in}(g)$. This error will not be calculated on iid examples anymore because the error is indirectly influenced by $g$ which was found using the same training set. Then, Hoeffding is invalid, and we need to come up with other bound.

The way to solve this problem is to bound $P(|E_{in}(g) - E_{out}(g)| > \epsilon)$ in a way that doesn't depend on which $g$ the learning algorithm picks.

This result, also called Uniform Hoeffding Inequality, is an overestimation of the LHS probability. It because as we can see in *, we are taking into account all the fixed $h_i$'s. With this bound, intuiively, we are trying to simultaneously approximate the LHS with all the RHS corresponding to each $h_i$, which in some situations is not the best we can do, but for now it's great.

In this way, the new bound show us two things:

1. Our LHS comes from picking $g$ after training, normally as
   Expand
2. But our RHS takes into account the whole hypothesis set, where it is guaranteed to draw iid examples to calculate each $E_{in}(h_i)$
   Expand

IMPORTANT

However, it stil important to assume the iid condition to use this bound:

When using $g$ to approximate $f:\mathcal{X} \rightarrow \mathcal{Y}$

1. A training and test examples are draw iid from $p(x)$.
2. A training and test examples are all coming from the same target function $f$.

When using $g$ to approximate $p(x|y)$

1. Training and test examples are draw iid from $p(x,y)$.

The training set $\mathcal{T}$ can only tell us something likely about $f$ outside $\mathcal{T}$.

1. $\uparrow \epsilon \Rightarrow$ $\downarrow \text{RHS} \Rightarrow$ $\downarrow$ probable that the difference $|E_{in}(g) - E_{out}(g)|$ was too high
   
   $\Rightarrow$ it's more probable that those erros are close. Then, $E_{in}$ is a good estimate of $E_{out}$
2. $\uparrow N \Rightarrow$ $\downarrow \text{RHS} \Rightarrow$ $\downarrow$ probable that the difference $|E_{in}(g) - E_{out}(g)|$ was too high
   
   $\Rightarrow$ it's more probable that those erros are close. Then, $E_{in}$ is a good estimate of $E_{out}$
3. The third option is concluded by two previous ones.
4. There exists a Trade-off between $M$, $E_{in}$, and $E_{out}$

We will start to handle this trade-off later by changing our notion of model complexity using VC dimension.