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

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.

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