Generalization
2.1 No Free Lunch Theorem
Theorem 2.1 (No Free Lunch) Let \(A\) be any learning algorithm for the task of binary classification with respect to the \(0\)–\(1\) loss over a domain \(X\). Let \(m\) be any number smaller than \(|X|/2\), representing a training set size. Then, there exists a distribution \(D\) over \(X \times \{0,1\}\) such that:
There exists a function \(f : X \to \{0,1\}\) with \(L_D(f) = 0\).
With probability of at least \(\frac{1}{7}\) over the choice of \(S \sim D^m\), we have
\[ L_D(A(S)) \ge \frac{1}{8} \]
(that is, the training algorithm fails).
2.2 Finite Hypothesis Classes
Hypothesis class (\(H\)): The class of functions can be finite or infinite.
Empirical Risk Minimization (ERM): Pick the hypothesis with the smallest training loss.
\[ \mathrm{ERM}_H(S)\in\arg\min_{h\in H}L_S(h). \]
Realizability assumption: There exists \(h^*\in H\) such that \(L_{D,f}(h^*)=0\). Therefore, for every training set \(S\), we have \(L_S(h^*)=0\).
Theorem 2.2 (ERM for Finite Hypothesis Classes) Let \(H\) be a finite hypothesis class. Let \(\delta\in(0,1)\) and \(\epsilon>0\), and let \(m\) be an integer that satisfies
\[ m\ge\frac{\log(|H|/\delta)}{\epsilon}. \]
Then, for any labeling function \(f\) and any distribution \(D\) for which the realizability assumption holds (that is, for some \(h\in H\), \(L_{D,f}(h)=0\)), with probability at least \(1-\delta\) over the choice of an i.i.d. sample \(S\) of size \(m\), every ERM hypothesis \(h_S\) satisfies
\[ L_{D,f}(h_S)\le\epsilon. \]
2.3 PAC Learning
2.3.1 Realizable PAC Learning
PAC learning: A hypothesis class \(H\) is PAC learnable if there exist a function \(m_H:(0,1)^2\to\mathbb N\) and a learning algorithm with the following property:
For every \(\epsilon,\delta\in(0,1)\), every distribution \(D\) over \(X\), and every labeling function \(f:X\to\{0,1\}\), if the realizability assumption holds with respect to \(H,D,f\), then, when running the learning algorithm on
\[ m\ge m_H(\epsilon,\delta) \]
i.i.d. examples generated by \(D\) and labeled by \(f\), the algorithm returns a hypothesis \(h\) such that, with probability at least \(1-\delta\) over the choice of the examples,
\[ L_{D,f}(h)\le\epsilon. \]
2.3.2 Agnostic PAC Learning
Agnostic PAC learnable: A hypothesis class \(H\) is agnostic PAC learnable if there exist a function \(m_H:(0,1)^2\to\mathbb N\) and a learning algorithm with the following property:
For every \(\epsilon,\delta\in(0,1)\) and every distribution \(D\) over \(X\times Y\), when running the learning algorithm on \(m\ge m_H(\epsilon,\delta)\) i.i.d. examples generated by \(D\), the algorithm returns a hypothesis \(h\) such that, with probability at least \(1-\delta\) over the choice of the \(m\) training examples,
\[ L_D(h)\le\min_{h'\in H}L_D(h')+\epsilon. \]
2.3.3 Error Decomposition
\[ L_D(h_S)=\epsilon_{\mathrm{app}}+\epsilon_{\mathrm{est}}. \]
\[ \begin{aligned} \epsilon_{\mathrm{app}} &=\min_{h\in H}L_D(h),\\ \epsilon_{\mathrm{est}} &=L_D(h_S)-\epsilon_{\mathrm{app}}. \end{aligned} \]
Bayes decomposition:
\[ \epsilon_{\mathrm{app}} =L_D(\mathrm{BO})+\min_{h\in H}L_D(h)-L_D(\mathrm{BO}). \]
2.3.4 Infinite Hypothesis Classes
Threshold functions: Let \(H\) be the class of threshold functions (\(h_a(x) = \mathbf{1}_{\{x<a\}}\)). Then \(H\) is PAC learnable using the ERM rule, with sample complexity
\[ m_H(\epsilon,\delta) \le \frac{\left\lceil\log(2/\delta)\right\rceil}{\epsilon}. \]
2.4 VC Dimension
2.4.1 Restriction and Shattering
Restriction of \(H\) to \(C\): Let \(H\) be a class of functions from \(X\) to \(\{0,1\}\), and let \(C=\{c_1,\ldots,c_m\}\subset X\). The restriction of \(H\) to \(C\) is the set of functions from \(C\) to \(\{0,1\}\) that can be derived from \(H\). That is,
\[ H_C=\left\{\bigl(h(c_1),\ldots,h(c_m)\bigr):h\in H\right\}. \]
Here we represent each function from \(C\) to \(\{0,1\}\) as a vector in \(\{0,1\}^{|C|}\).
Shattering: A hypothesis class \(H\) shatters a finite set \(C\subset X\) if the restriction of \(H\) to \(C\) is the set of all functions from \(C\) to \(\{0,1\}\). That is,
\[ |H_C|=2^{|C|}. \]
Theorem 2.3 (Sample Lower Bound from Shattering) Let \(H\) be a hypothesis class of functions from \(X\) to \(\{0,1\}\). Let \(m\) be a training set size. Assume that there exists a set \(C\subset X\) of size \(2m\) that is shattered by \(H\). Then, for any learning algorithm \(A\), there exist a distribution \(D\) over \(X\times\{0,1\}\) and a predictor \(h\in H\) such that \(L_D(h)=0\), but with probability at least \(\frac17\) over the choice of \(S\sim D^m\), we have
\[ L_D(A(S))\ge\frac18. \]
2.4.2 VC Dimension and Learnability
VC-dimension: The VC dimension of a hypothesis class \(H\), denoted \(\mathrm{VCdim}(H)\), is the maximal size of a set \(C\subset X\) that can be shattered by \(H\). If \(H\) can shatter sets of arbitrarily large size, we say that \(H\) has infinite VC dimension.
Theorem 2.4 (Infinite VC Dimension) Let \(H\) be a class of infinite VC dimension. Then \(H\) is not PAC learnable.
2.4.3 Sample Complexity
Theorem 2.5 (Fundamental Theorem of Statistical Learning — Quantitative Version) Let \(H\) be a hypothesis class of functions from a domain \(X\) to \(\{0,1\}\), and let the loss function be the \(0\)–\(1\) loss. Assume that \(\mathrm{VCdim}(H)=d<\infty\). Then there are absolute constants \(C_1,C_2\) such that:
\(H\) is agnostic PAC learnable with sample complexity
\[ C_1\frac{d+\log(1/\delta)}{\epsilon^2} \le m_H(\epsilon,\delta) \le C_2\frac{d+\log(1/\delta)}{\epsilon^2}. \]
\(H\) is PAC learnable with sample complexity
\[ C_1\frac{d+\log(1/\delta)}{\epsilon} \le m_H(\epsilon,\delta) \le C_2\frac{d\log(1/\epsilon)+\log(1/\delta)}{\epsilon}. \]
These assumptions limit the tasks covered or the benchmark promised, making learning guarantees possible without providing a universal learner. Real-world tasks share patterns and structure. The key is to find a balance between model complexity and population loss.