agnostic PAC model: Learnability and Bias-Complexity Trade-off

Question

I am reading "Understanding Machine Learning: From Theory to Algorithms." In Chapter 5.2, it says that choosing the hypothesis class $\mathcal{H}$ to be a very rich class decreases the approximation error but at the same time

might increase the estimation error, as a rich $\mathcal{H}$ might lead to overfitting.

Based on this, it does not explain why overfitting is bad as we are talking about an upper bound. In this regard, I am even not sure in what sense Learning theory is necessary. As far as I know, the learning theory is concerned with the problem of generalization. To describe the problem in more detail, let me give some setup.

Let $\mathcal{D} \sim \mathcal{X}\times \mathcal{Y}$ be a data distribution and $\mathcal{T}_m = \{(x_i, y_i)\}_{i=1}^m$ be a set of $m$- iid data from $\mathcal{D}$. Let $\mathcal{H}$ be a hypothesis class. For each $h \in \mathcal{H}$, let us define $$L_{\mathcal{T}_m}(h) = \frac{1}{m}\sum_{i=1}^m (h(x_i) -y_i)^2, \qquad L_{\mathcal{D}}(h) = \mathbb{E}_{(x,y) \sim \mathcal{D}}[(h(x)-y)^2]. $$ By Glivenko–Cantelli theorem or Kolmogorov's theorem, we know that the empicical measure converges to the underlying distribution. Therefore, $$\lim_{m \to \infty} L_{\mathcal{T}_m}(h) = L_\mathcal{D}(h).$$ I couldn't find an analog of this result on a high-dimension. However, assuming $|L_{\mathcal{D}}(h) - L_{\mathcal{T}_m}(h)| \le \mathcal{O}(m^{-1/d})$ where $d$ is the input dimension, I believe that the generalization is now well explained. It shows that how the empirical error is close to the true error and the difference goes to 0 as the number of samples goes to $\infty$.

Then I think that the learnability is all about measuing difference between the empirical measure and the underlying measure. If then, why do we even care about statements like, with probability exceeding $1-\delta$ on the iid $m$-samples, $$ L_{\mathcal{D}}(h) \le L_{\mathcal{T}_m}(h) + \mathcal{O}\left(\frac{\log |\mathcal{H}|/\delta}{m}\right). $$ By the way, this is a PAC learnablitiy statement for a finite hypothesis class. Even this simple case, it does not explain that why overfitting is bad in generalization.

Any comments/suggestions/answers will be very appreciated.

Answer 1

You are correct in the connection between Learning theory and Glivenko-Cantelli theorem. Note that original Glivenko-Cantelli theorem was only for half-bounded intervals. Indeed, if we take $\mathcal{H}$ to be the set of half-bounded intervals, then Glivenko-Cantelli theorem is equivalent to $$ \lim_{m\to \infty} \sup_{h \in \mathcal{H}} | L_{\tau_m}(h) - L_{\mathcal{D}}(h) | \to 0 $$ This notion of uniform convergence over half-intervals was then generalized to $\mathcal{H}$ having finite VC-dimension. For example, one can obtain a similar convergence in multiple dimensions by choosing the hypothesis class $\mathcal{H}$ as all half-cuboids which has finite VC Dimension.

One may wonder what if you include a lot of functions in $\mathcal{H}$. If $\mathcal{H}$ is allowed to be large, then one can come up with an example where the uniform convergence doesn't hold. Following results give lower bounds on the estimation error, necessating the need of choosing $\mathcal{H}$ wisely.

(1) No Free Lunch theorem in the book, Theorem 5.1.

(2) Fundamental theorem of Learning, Theorem 6.8.

To quote the authors from Chapter 5 - "Learning theory studies how rich we can make $\mathcal{H}$ while still maintaining reasonable estimation error."

The book referenced is "Understanding Machine Learning" by Shai Ben-David and Shai Shalev-Shwartz.

Answer 2

Then I think that the learnability is all about measuring the difference between the empirical measure and the underlying measure. If then, why do we even care about statements like, with probability exceeding $1−\delta$ on the iid m-samples

That's a very good question BTW. And yes you're kind of right in saying that

learnability is all about measuring the difference between the empirical measure and the underlying measure

But in (asymptotics/statistics) literature the concept of convergence is based mostly on different approaches in which one can measure the distance between two random variables.

You can have convergence of a sequence of random variables

1. $\{X_{n}\}\rightarrow Z$ in probability
2. $\{X_{n}\}\rightarrow Z$ in distribution
3. $\{X_{n}\}\rightarrow Z$ almost surely

So why does PAC-learning still require the statement with probability $1-\delta$?

Mostly for 2 reasons:

a. To control randomness, that is each $x_{i}\in\mathcal{X}\sim\mathcal{D}$ being iid implies that they are random variables and hence $h\in\mathcal{H}$ and $L(\cdot)$ automatically become random functions since they depend on $x_{i}$.

Now in order to ensure that two random variables are close to each other, we need the notion of 1. defined above.

That notion states that two random variables are close to each other if there is a high probability (i.e. hence, $1-\delta$) that their difference is very small (i.e. hence, $\vert L(h) - L_{\mathcal{D}}(h)\vert< \epsilon$).

Hope that helps.