{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T19:47:19Z","timestamp":1649015239065},"reference-count":27,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3521,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2004,1]]},"DOI":"10.1016\/s0890-5401(03)00164-0","type":"journal-article","created":{"date-parts":[[2003,7,31]],"date-time":"2003-07-31T23:44:52Z","timestamp":1059695092000},"page":"99-115","source":"Crossref","is-referenced-by-count":0,"title":["Efficient algorithms for learning functions with bounded variation"],"prefix":"10.1016","volume":"188","author":[{"given":"Philip M.","family":"Long","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"4","key":"10.1016\/S0890-5401(03)00164-0_BIB1","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1145\/263867.263927","article-title":"Scale-sensitive dimensions, uniform convergence, and learnability","volume":"44","author":"Alon","year":"1997","journal-title":"Journal of the Association for Computing Machinery"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB2","series-title":"Neural Network Learning: Theoretical Foundations","author":"Anthony","year":"1999"},{"issue":"5","key":"10.1016\/S0890-5401(03)00164-0_BIB3","doi-asserted-by":"crossref","first-page":"1721","DOI":"10.1109\/18.623181","article-title":"Covering numbers for real-valued function classes","volume":"43","author":"Bartlett","year":"1997","journal-title":"IEEE Transactions on Information Theory"},{"issue":"2","key":"10.1016\/S0890-5401(03)00164-0_BIB4","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1006\/jcss.1997.1557","article-title":"Prediction, learning, uniform convergence, and scale-sensitive dimensions","volume":"56","author":"Bartlett","year":"1998","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"10.1016\/S0890-5401(03)00164-0_BIB5","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1006\/inco.1997.2656","article-title":"On the complexity of learning from drifting distributions","volume":"138","author":"Barve","year":"1997","journal-title":"Information and Computation"},{"issue":"4","key":"10.1016\/S0890-5401(03)00164-0_BIB6","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","article-title":"Learnability and the Vapnik\u2013Chervonenkis dimension","volume":"36","author":"Blumer","year":"1989","journal-title":"JACM"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB7","series-title":"Pattern Classification and Scene Analysis","author":"Duda","year":"1973"},{"issue":"1","key":"10.1016\/S0890-5401(03)00164-0_BIB8","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","article-title":"Decision theoretic generalizations of the PAC model for neural net and other learning applications","volume":"100","author":"Haussler","year":"1992","journal-title":"Information and Computation"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB9","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0890-5401(91)90042-Z","article-title":"Equivalence of models for polynomial learnability","volume":"95","author":"Haussler","year":"1991","journal-title":"Information and Computation"},{"issue":"2","key":"10.1016\/S0890-5401(03)00164-0_BIB10","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/inco.1994.1097","article-title":"Predicting {0,1}-functions on randomly drawn points","volume":"115","author":"Haussler","year":"1994","journal-title":"Information and Computation"},{"issue":"2","key":"10.1016\/S0890-5401(03)00164-0_BIB11","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0097-3165(95)90001-2","article-title":"A generalization of Sauer\u2019s Lemma","volume":"71","author":"Haussler","year":"1995","journal-title":"Journal of Combinatorial Theory, Series A"},{"issue":"3","key":"10.1016\/S0890-5401(03)00164-0_BIB12","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1016\/S0022-0000(05)80062-5","article-title":"Efficient distribution-free learning of probabilistic concepts","volume":"48","author":"Kearns","year":"1994","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB13","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF00993468","article-title":"Toward efficient agnostic learning","volume":"17","author":"Kearns","year":"1994","journal-title":"Machine Learning"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB14","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1090\/trans2\/017\/10","article-title":"\u03f5-Entropy and \u03f5-capacity of sets in functional spaces","volume":"17","author":"Kolmogorov","year":"1961","journal-title":"American Mathematical Society Translations (Ser. 2)"},{"issue":"5","key":"10.1016\/S0890-5401(03)00164-0_BIB15","first-page":"1977","article-title":"The importance of convexity in learning with squared loss","volume":"44","author":"Lee","year":"1998","journal-title":"IEEE Transactions on Information Theory"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB16","doi-asserted-by":"crossref","unstructured":"P.M. Long, The complexity of learning according to two models of a drifting environment, in: Proceedings of the 1998 Conference on Computational Learning Theory, 1998","DOI":"10.1145\/279943.279968"},{"issue":"3","key":"10.1016\/S0890-5401(03)00164-0_BIB17","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1023\/A:1007666507971","article-title":"The complexity of learning according to two models of a drifting environment","volume":"37","author":"Long","year":"1999","journal-title":"Machine Learning"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB18","series-title":"Proceedings of the 1993 ACM Conference on Computational Learning Theory","first-page":"370","article-title":"Occam\u2019s razor for functions","author":"Natarajan","year":"1993"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB19","series-title":"Convergence of Stochastic Processes","author":"Pollard","year":"1984"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB20","doi-asserted-by":"crossref","unstructured":"D. Pollard, Empirical Processes: Theory and Applications, volume 2 of NSF-CBMS Regional Conference Series in Probability and Statistics, Institute of Mathematical Statistics and American Statistics Association, 1990","DOI":"10.1214\/cbms\/1462061091"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB21","doi-asserted-by":"crossref","unstructured":"S.E. Posner, S.R. Kulkarni, On-line learning of functions of bounded variation under various sampling schemes, in: Proceedings of the 1993 Conference on Computational Learning Theory, 1993, pp. 439\u2013445","DOI":"10.1145\/168304.168392"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB22","series-title":"Real Analysis","author":"Royden","year":"1963"},{"issue":"2","key":"10.1016\/S0890-5401(03)00164-0_BIB23","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1006\/jcss.1996.0019","article-title":"General lower bounds on the number of examples needed for learning probabilistic concepts","volume":"52","author":"Simon","year":"1996","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"10.1016\/S0890-5401(03)00164-0_BIB24","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1137\/S0097539793259185","article-title":"Bounds on the number of examples needed for learning functions","volume":"26","author":"Simon","year":"1997","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB25","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1214\/aop\/1176995801","article-title":"Distribution inequalities for the binomial law","volume":"5","author":"Slud","year":"1977","journal-title":"Annals of Probability"},{"key":"10.1016\/S0890-5401(03)00164-0_BIB26","doi-asserted-by":"crossref","unstructured":"P. Vaidya, A new algorithm for minimizing convex functions over convex sets, in: Proceedings of the 30th Annual Symposium on the Foundations of Computer Science, 1989, pp. 338\u2013343","DOI":"10.1109\/SFCS.1989.63500"},{"issue":"11","key":"10.1016\/S0890-5401(03)00164-0_BIB27","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1984","journal-title":"Communications of the ACM"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540103001640?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540103001640?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:44:02Z","timestamp":1623199442000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540103001640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["S0890540103001640"],"URL":"https:\/\/doi.org\/10.1016\/s0890-5401(03)00164-0","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}