Some issues with proof of Fundamental Theorem of Statistical learning

Question

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. 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?

Answer 1

There has been a recent line of work on computable learnability:

http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf

http://www.learningtheory.org/colt2021/virtual/static/images/agarwal21b.pdf

This seems to be exactly the sort of thing you're asking about. You also ask about the implications $1\implies 2$ and $2\implies 3$. The latter is indeed trivial: if a particular learning rule (ERM) succeeds, then certainly some rule does.

$1\implies 2$ holds for all classes, not just finite ones. Again, it's pretty straightforward: uniform convergence means that the behavior of any $f\in F$ on the sample will be, with high probability, representative of its behavior on the whole space -- and hence minimizing the sample error is a valid learning rule.

Your biggest issue seems to be with an effective procedure for performing ERM on given data. We CS people handle this difficulty as follows: Either you're in the real world of finite-precision measurements, in which case everything is finite, and no philosophical issues arise. Or, alternatively, if you insist on infinite-precision data, then you must allow me infinite-precision computation as well. For example, I can pose SVM as a quadratic program and guarantee convergence to within a specified $\epsilon$ precision in finite time. If $\epsilon$ is sufficinetly smaller than the margin, I can still guarantee generalization.

Answer 2

I know it's generally considered bad form to add another answer on top of an accepted one, but this one is by special request and it's a topic that deserves its own discussion.

The topic is: Effective learning algorithms vs. learning rules. A learning rule is simply a mathematically well-defined mapping from a labeled sample to some function class. (The mapping has to satisfy some minimal measurability properties, see Remark 4.10 here https://arxiv.org/pdf/1906.09855.pdf ). However, the mapping need not be effectively computable by a Turing machine. For example, the learning "algorithm" described in the Benedek-Itai paper "Learnability with respect to fixed distributions" (https://dl.acm.org/doi/10.5555/117115.117118) has the form , where $n_D$ is an $\ell_1$ covering number of the concept class $C$ w.r.t. the distribution $D$. This is a well-defined mapping from samples to classifiers, but not an effective algorithm. To obtain the latter, one needs to carefully specify a representation. Section 1.2.2 of the Kearns-Vazirani book (https://mitpress.mit.edu/books/introduction-computational-learning-theory) addresses the topic of representation in detail. Once a representation has been specified, one can talk about effective algorithms and even exact runtimes.