{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T00:48:08Z","timestamp":1663807688239},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1997,7]]},"abstract":"Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper, we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine\u00b4, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a Gine\u00b4, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to obtain the weakest combinatorial condition known to imply PAC learnability in the statistical regression (or \u201cagnostic\u201d) framework. Furthermore, we find a characterization of learnability in the probabilistic concept model, solving an open problem posed by Kearns and Schapire. These results show that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.<\/jats:p>","DOI":"10.1145\/263867.263927","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"615-631","source":"Crossref","is-referenced-by-count":139,"title":["Scale-sensitive dimensions, uniform convergence, and learnability"],"prefix":"10.1145","volume":"44","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel Aviv Univ., Tel Aviv, Israel"}]},{"given":"Shai","family":"Ben-David","sequence":"additional","affiliation":[{"name":"Technion\u2013Israel Institute of Technology, Haifa, Israel"}]},{"given":"Nicol\u00f2","family":"Cesa-Bianchi","sequence":"additional","affiliation":[{"name":"Univ. of Milan, Milan, Italy"}]},{"given":"David","family":"Haussler","sequence":"additional","affiliation":[{"name":"Univ. of California at Santa Cruz, Santa Cruz"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02804012","article-title":"Embedding of 1k in finite dimension Banach spaces","volume":"45","author":"ALON N.","year":"1983","journal-title":"Israel J. Math."},{"key":"e_1_2_1_2_1","unstructured":"ASSOUAD P. AND DUDLEY R. 1989. Minimax nonparametric estimation over classes of sets. Preprint. ASSOUAD P. AND DUDLEY R. 1989. Minimax nonparametric estimation over classes of sets. Preprint."},{"key":"e_1_2_1_3_1","first-page":"392","volume-title":"Proceedings of the 8th Annual Conference on Computational Learning Theory. ACM","author":"BARTLETT P.","year":"1995"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0033"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(87)90147-6"},{"key":"e_1_2_1_8_1","first-page":"2","volume-title":"Lecture Notes in Mathematics","author":"DUDLEY R."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BF01210321","article-title":"Uniform and universal Glivenko-Cantelli classes","volume":"4","author":"DUDLEY R.","year":"1991","journal-title":"J. Theoret. Prob."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1214\/aop\/1176993138","article-title":"Some limit theorems for empirical processes","volume":"12","author":"GINI","year":"1984","journal-title":"Ann. Prob."},{"key":"e_1_2_1_11_1","first-page":"471","volume-title":"Proceedings of the 1991 Conference on Advances in Neural Information Processing Systems.","author":"GUYON I.","year":"1991"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90001-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80062-5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF02761724","article-title":"Some remarks about embedding of 1k in finite dimensional spaces","volume":"43","author":"MILMAN","year":"1982","journal-title":"Israel J. Math."},{"key":"e_1_2_1_16_1","series-title":"NSF-CBMS Regional Conference Series in Probability and Statistics","doi-asserted-by":"crossref","volume-title":"Empirical Processes: Theory and Applications","author":"POLLARD D.","year":"1990","DOI":"10.1214\/cbms\/1462061091"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/0005-1098(78)90005-5","article-title":"Modeling by shortest data description","volume":"14","author":"RISSANEN J.","year":"1978","journal-title":"Automatica"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","article-title":"On the density of families of sets","volume":"13","author":"SAUER N.","year":"1972","journal-title":"J. Combin. Theory, Ser. A"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","article-title":"A combinatorial problem: Stability and order for models and theories in infinitary languages","volume":"41","author":"SHELAH S.","year":"1972","journal-title":"Pac. J. Math."},{"key":"e_1_2_1_20_1","first-page":"83","volume-title":"Proceedings of the 1st Euro-COLT Workshop. The Institute of Mathematics and Its Applications.","author":"SIMON H.","year":"1994"},{"key":"e_1_2_1_21_1","first-page":"113","volume-title":"Lecture Notes of London Mathematical Society","volume":"103","author":"VAN LINT J.","year":"1985"},{"key":"e_1_2_1_22_1","unstructured":"VAPNIK g. 1982. Estimation of Dependencies Based on Empirical Data. Springer Verlag New York. VAPNIK g. 1982. Estimation of Dependencies Based on Empirical Data. Springer Verlag New York."},{"key":"e_1_2_1_23_1","first-page":"1","volume-title":"Proceedings of the 2nd Annual Workshop on a Computational Learning Theory.","author":"VAPNIK V.","year":"1989"},{"issue":"2","key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","article-title":"On the uniform convergence of relative frequencies of events to their probabilities","volume":"16","author":"VAPNIK","year":"1971","journal-title":"Theory of Prob. Its Applic."},{"issue":"3","key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1137\/1126059","article-title":"Necessary and sufficient conditions for uniform convergence of means to mathematical expectations","volume":"26","author":"VAPNIK","year":"1981","journal-title":"Theory Prob. Applic."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/263867.263927","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T18:09:02Z","timestamp":1614622142000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/263867.263927"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,7]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,7]]}},"alternative-id":["10.1145\/263867.263927"],"URL":"http:\/\/dx.doi.org\/10.1145\/263867.263927","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1997,7]]}}}