This is part 2 of a three part series on the fundamentals of Machine Learning as presented by this book. It builds heavily onto part I.

Uniform Convergence

Uniform convergence is a property which a hypothesis class may satisfy that will end up being equivalent to PAC learning, and the ability to use either definition whenever needed will be quite useful. "Uniform convergence" means convergence with respect to the difference between the empirical error and the real error, which is uniform with respect to all hypotheses in the class – i.e. we can bound the difference between real and empirical error across all hypotheses simultaneously. We have the following formal definition:

A hypothesis class $H$ has the uniform convergence property iff there is a function $u^{*} : (0, 1)^{2} \to N$ such that, for every probability distribution $D$ over $X \times Y$ , every gap $ϵ \in (0, 1)$ and every confidence level $δ \in (0, 1)$ , if $| S | > u^{*} (ϵ, δ)$ , then with probability at least $1 - δ$ over the choice of $S$ , the inequality $| ℓ_{S} (h) - ℓ (h) | \leq ϵ$ holds for all $h \in H$ .

Recall that PAC learnability demands that the true error of the hypothesis output by $A_{ERM}$ is low. On the other hand, uniform convergence demands that the gap between the empirical and the true error is low. Unsurprisingly, both properties are equivalent. We will prove one direction now, namely that uniform convergence implies PAC learnability.

Suppose the uniform convergence property holds for values $ϵ, δ$ . We apply $A_{ERM}$ to our task, feed it our training sequence $S$ which fulfills the property that $| S | > u^{*} (ϵ, δ)$ , and now want to argue that the true error of $A_{ERM} (S)$ is not much higher than the true error of some $h^{*} \in {argmin}_{h \in H} [ℓ (h)]$ . The uniform convergence property does not allow us to compare both errors directly, rather, we can argue that $ℓ (A_{ERM} (S)) - ℓ_{S} (A_{ERM} (S)) \leq ϵ$ because of uniform convergence, that $ℓ_{S} (A_{ERM} (S)) - ℓ_{S} (h^{*}) \leq 0$ because of what $A_{ERM}$ does, and finally that $ℓ_{S} (h^{*}) - ℓ (h^{*}) \leq ϵ$ because of uniform convergence. Putting these three inequalities together, we do indeed obtain a bound on $ℓ (A_{ERM} (S)) - ℓ (h^{*})$ , but it is $2 ϵ$ not $ϵ$ . The c... ,,

Understanding Machine Learning