Some issues with proof of Fundamental Theorem of Statistical learning - Theoretical Computer Science Stack Exchange most recent 30 from cstheory.stackexchange.com 2022-01-20T10:55:04Z https://cstheory.stackexchange.com/feeds/question/50428 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cstheory.stackexchange.com/q/50428 2 Some issues with proof of Fundamental Theorem of Statistical learning Marina https://cstheory.stackexchange.com/users/63308 2021-08-28T04:38:03Z 2021-10-06T13:17:51Z <p>I am reading the book &quot;Understanding Machine Learning&quot; by Shai Shalev-Shwartz and Shai Ben-David. The theorem 6.7 has several equivalent statements for a class of functions <span class="math-container">$H$</span>. The first three are:</p> <ol> <li><span class="math-container">$H$</span> has the uniform convergence property.</li> <li>Any ERM rule is a successful agnostic PAC learner for <span class="math-container">$H$</span>.</li> <li><span class="math-container">$H$</span> is agnostic PAC learnable.</li> </ol> <p>For the proof of inference 1 <span class="math-container">$\rightarrow$</span> 2 the book refers to the chapter 4, where the results are proven only for finite classes. It says, inference 2 <span class="math-container">$\rightarrow$</span> 3 is trivial. Is it?</p> <p>ERM rule is the algorithm which, given a sample <span class="math-container">$S$</span>, finds hypothesis with minimal empirical risk among all functions in <span class="math-container">$H$</span>. If the ERM rule for a given class of functions exists, and it is a successful agnostic PAC learner, then <span class="math-container">$H$</span> is agnostic PAC learnable, of course.</p> <p>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?</p> https://cstheory.stackexchange.com/questions/50428/-/50432#50432 4 Answer by Aryeh for Some issues with proof of Fundamental Theorem of Statistical learning Aryeh https://cstheory.stackexchange.com/users/1746 2021-08-29T07:44:56Z 2021-10-06T13:17:51Z <p>There has been a recent line of work on <em>computable learnability</em>:</p> <p><a href="http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf" rel="nofollow noreferrer">http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf</a></p> <p><a href="http://www.learningtheory.org/colt2021/virtual/static/images/agarwal21b.pdf" rel="nofollow noreferrer">http://www.learningtheory.org/colt2021/virtual/static/images/agarwal21b.pdf</a></p> <p>This seems to be exactly the sort of thing you're asking about. You also ask about the implications <span class="math-container">$1\implies 2$</span> and <span class="math-container">$2\implies 3$</span>. The latter is indeed trivial: if <em>a particular</em> learning rule (ERM) succeeds, then certainly <em>some</em> rule does.</p> <p><span class="math-container">$1\implies 2$</span> holds for all classes, not just finite ones. Again, it's pretty straightforward: uniform convergence means that the behavior of any <span class="math-container">$f\in F$</span> 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.</p> <p>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 <span class="math-container">$\epsilon$</span> precision in finite time. If <span class="math-container">$\epsilon$</span> is sufficinetly smaller than the margin, I can still guarantee generalization.</p> https://cstheory.stackexchange.com/questions/50428/-/50436#50436 1 Answer by Aryeh for Some issues with proof of Fundamental Theorem of Statistical learning Aryeh https://cstheory.stackexchange.com/users/1746 2021-08-29T15:20:19Z 2021-08-29T20:38:33Z <p>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.</p> <p>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 <a href="https://arxiv.org/pdf/1906.09855.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1906.09855.pdf</a> ). However, the mapping need not be effectively computable by a Turing machine. For example, the learning &quot;algorithm&quot; described in the Benedek-Itai paper &quot;Learnability with respect to fixed distributions&quot; (<a href="https://dl.acm.org/doi/10.5555/117115.117118" rel="nofollow noreferrer">https://dl.acm.org/doi/10.5555/117115.117118</a>) has the form <a href="https://i.stack.imgur.com/N3pCd.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/N3pCd.png" alt="enter image description here" /></a>, where <span class="math-container">$n_D$</span> is an <span class="math-container">$\ell_1$</span> covering number of the concept class <span class="math-container">$C$</span> w.r.t. the distribution <span class="math-container">$D$</span>. 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 <em>representation</em>. Section 1.2.2 of the Kearns-Vazirani book (<a href="https://mitpress.mit.edu/books/introduction-computational-learning-theory" rel="nofollow noreferrer">https://mitpress.mit.edu/books/introduction-computational-learning-theory</a>) addresses the topic of representation in detail. Once a representation has been specified, one can talk about effective algorithms and even exact runtimes.</p>