I am reading the book "Understanding Machine Learning" by Shai Shalev-Shwartz and Shai Ben-David. The theorem 6.7 has several equivalent statements for a class of functions $H$. The first three are:
- $H$ has the uniform convergence property.
- Any ERM rule is a successful agnostic PAC learner for $H$.
- $H$ is agnostic PAC learnable.
For the proof of inference 1 $\rightarrow$ 2 the book refers to the chapter 4, where the results are proven only for finite classes. It says, inference 2 $\rightarrow$ 3 is trivial. Is it?
ERM rule is the algorithm which, given a sample $S$, finds hypothesis with minimal empirical risk among all functions in $H$. If the ERM rule for a given class of functions exists, and it is a successful agnostic PAC learner, then $H$ is agnostic PAC learnable, of course.
But is there a proof that ERM rule exists for every class of functions, or is there a way to see that the theorem is true even if the class of functions does not have a ERM rule?