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:

  1. $H$ has the uniform convergence property.
  2. Any ERM rule is a successful agnostic PAC learner for $H$.
  3. $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. If the ERM rule exists, and it is a successful agnostic PAC learner, then $H$ is agnostic PAC learnable, of course. But it is based on an assumption that ERM rule exists. ERM rule is the rule which, given a sample $S$, finds hypothesis with minimal empiric risk among all functions in $H$. Whole proof of the theorem depends on the 2 $\rightarrow$ 3 inference. Is there a proof that ERM rule exists always, or is there a way to see that the theorem is true regardless?

  • $\begingroup$ What do you mean by "...assumption that ERM rule exists"? Are you saying that sometimes it is not possible to find a hypothesis that minimizes the empirical risk? Since the loss function can be chosen, then it should be chosen such that a minimum empirical risk exists. In theorem 6.7, they choose the 0 - 1 loss, which can indeed be used to find a minimum empirical risk. $\endgroup$
    – mhdadk
    Aug 24, 2021 at 18:23
  • $\begingroup$ @mhdadk How do you find a function with the minimal empiric risk in an infinite class? For a finite class, the authors suggest that you take one by one every function from the class, evaluate its empiric risk on a given training set, then select the function with the minimal empiric risk. How would you do it for an infinite class? $\endgroup$
    – Marina
    Aug 24, 2021 at 18:26
  • $\begingroup$ Lemma 6.1 in section 6.1 provides an example of how to do this. I have not yet investigated how to do this more generally, however. $\endgroup$
    – mhdadk
    Aug 24, 2021 at 18:29
  • $\begingroup$ @mhdadk They give an example of the class of functions, when it is possible. It does not prove that it is possible always. Yet, the FTSL shall be true for any class of functions, not only for this one. $\endgroup$
    – Marina
    Aug 24, 2021 at 18:31
  • $\begingroup$ May be, the theorem should be updated to say: if class of functions $H$ has an ERM rule, then the next properties are equivalent... $\endgroup$
    – Marina
    Aug 24, 2021 at 18:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.