# Some issues with proof of Fundamental Theorem of Statistical learning

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?

• why doesn't erm rule always exist? you get a finite sample, so just choose something with $0$ mistakes if it exists; otherwise choose something with $1$ mistake; etc.. If you're worried about the axiom of choice or something like that, then that's another story... Aug 28, 2021 at 8:54
• @mathworker21 How do you chose something that has no mistakes from an infinite class of functions? The class may not even have a function which has no mistakes. I am worried about existence of an algorithm which finds a minimum from an infinite set. Aug 28, 2021 at 11:22
• "How do you choose something that has no mistakes from an infinite class of functions?" Just choose one. Unless you're worried about axiom of choice (which you should say if you are). "The class may not even have a function which has no mistakes." I addressed this in my last comment. "I am worried about existence of an algorithm which finds a minimum from an infinite set." The relevant set is finite; you only get a finite number of samples. True there could be an infinite class of functions, but I don't see the relevance. Aug 28, 2021 at 14:16
• @mathworker21 "The relevant set is finite". No . The relevant set is infinite: this is the class of functions, from which we need to chose one function with the minimal number of errors. You know, like class of all polynomials of degree up to k. Aug 28, 2021 at 14:53
• An algorithm is just a function, at least for the first part of the book (which has as part of the title "from theory to algorithms"). Weirdly, I can't find the definition of "algorithm" given. I'm nearly certain it is just a function for the purposes of the first part of the book Aug 28, 2021 at 15:15

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.

• Thank you for the answer. I still do not see how it has anything to do with precision. If class of functions is infinite, ERM rule needs to find minimum from an infinite set. It doe not matter how long you try functions one by one, you can not guarantee that the solution is has some precision: unseen function may be much better that anything seen. Aug 29, 2021 at 10:52
• the other person said that in this section about PAC learning the word "leaning algorithm" means "function". Is this the case? So, the "algorithm" (function) may exist, but it is not "implementable". Is this how you understand it? The term "implementable" appears in chapter 6 of this book. Aug 29, 2021 at 10:57
• I noticed, in the articles you refer to there is the term "computable learners". It would imply that there may be un-computable learners. So, the ERM rule may be un-computable sometimes. And "PAC learnable" may not be "PAC computable learnable". Is this how you understand it? Aug 29, 2021 at 11:01
• They write: " We thus propose the notion of CPAC learnability, by adding some basic computability requirements into a PAC learning framework.". Exactly! Thank you very much for pointing it out. Aug 29, 2021 at 11:06
• From the same article. They write: " The common statistical learning theory, in which we have the fundamental characterization of PAC learnability by the finiteness of the VC-dimension, allows for the learners to be arbitrary functions". What the authors (including one of the authors of this artile) call "learning algorithm" in this part of the book is "arbitrary function". What they call "learning algorithm" in other parts of the book means "description of a computer program". They never let us know when they switched from one concept to another with the same name. Aug 29, 2021 at 11:25

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.

• Thank you. The book was published in 1994. Would you recommend this book for the study of statistical learning theory rather than "Understanding machine learning"? Aug 29, 2021 at 15:47
• I'd say K+V is quite a bit more dated -- certainly, the chapter on boosting is rather outdated. Also, learning automata, membership/equivalence queries have kind of fallen by the wayside (and I say this as someone who spent a good few years on automata learning). The first 3 chapters are still "modern". I'd say the Mohri et al. book (mitpress.mit.edu/books/foundations-machine-learning) is more modern and user-friendly. Aug 29, 2021 at 15:53
• In Mohri, there is practically the same definition of PAC learnable: "there exists an algorithm" without strict definition of algorithm. The newest article with Ben-David coauthor has very strict definitions. So, I will use it for my work. I need a mathematically-friendly text, and the latest articles you quoted are what I need. Thanks. Aug 29, 2021 at 16:02
• yes, ppl are a bit loose with "algorithm" vs. "learning rule". I reserve alg strictly for Turing-machine implementable rules. Aug 29, 2021 at 16:03