{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T11:32:39Z","timestamp":1780054359988,"version":"3.54.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T00:00:00Z","timestamp":1435622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"an Israel Science Foundation grant"},{"name":"Mathematical Sciences Institute -- The Australian National University"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,6,30]]},"abstract":"<jats:p>We obtain sharp bounds on the estimation error of the Empirical Risk Minimization procedure, performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have rapidly decaying tails.<\/jats:p>\n          <jats:p>Rather than resorting to a concentration-based argument, the method used here relies on a \u201csmall-ball\u201d assumption and thus holds for classes consisting of heavy-tailed functions and for heavy-tailed targets.<\/jats:p>\n          <jats:p>The resulting estimates scale correctly with the \u201cnoise level\u201d of the problem, and when applied to the classical, bounded scenario, always improve the known bounds.<\/jats:p>","DOI":"10.1145\/2699439","type":"journal-article","created":{"date-parts":[[2015,7,6]],"date-time":"2015-07-06T14:04:16Z","timestamp":1436191456000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":103,"title":["Learning without Concentration"],"prefix":"10.1145","volume":"62","author":[{"given":"Shahar","family":"Mendelson","sequence":"first","affiliation":[{"name":"Technion I.I.T"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,6,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053605000000282"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-011-0367-2"},{"key":"e_1_2_1_3_1","volume-title":"Concentration Inequalities","author":"Boucheron Stephane","unstructured":"Stephane Boucheron , Gabor Lugosi , and Pascal Massart . 2013. Concentration Inequalities . Oxford University Press , Oxford . x+481 pages. DOI:http:\/\/dx.doi.org\/10.1093\/acprof:oso\/9780199535255.001.0001 10.1093\/acprof:oso Stephane Boucheron, Gabor Lugosi, and Pascal Massart. 2013. Concentration Inequalities. Oxford University Press, Oxford. x+481 pages. DOI:http:\/\/dx.doi.org\/10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"e_1_2_1_4_1","volume-title":"Panoramas et Synth\u00e8ses","volume":"37","author":"Chafa\u00ef Djalil","year":"2012","unstructured":"Djalil Chafa\u00ef , Olivier Gu\u00e9don , Guillaume Lecu\u00e9 , and Alain Pajor . 2012 . Interactions between compressed sensing random matrices and high dimensional geometry . Panoramas et Synth\u00e8ses , Vol. 37 , Soci\u00e9t\u00e9 Math\u00e9matique de France, Paris. 181 pages. Djalil Chafa\u00ef, Olivier Gu\u00e9don, Guillaume Lecu\u00e9, and Alain Pajor. 2012. Interactions between compressed sensing random matrices and high dimensional geometry. Panoramas et Synth\u00e8ses, Vol. 37, Soci\u00e9t\u00e9 Math\u00e9matique de France, Paris. 181 pages."},{"key":"e_1_2_1_5_1","volume-title":"de la Pe\u00f1a and Evarist Gin\u00e9","author":"V\u00edctor","year":"1999","unstructured":"V\u00edctor H. de la Pe\u00f1a and Evarist Gin\u00e9 . 1999 . Decoupling. Springer-Verlag , New York. xvi+392 pages. DOI:http:\/\/dx.doi.org\/10.1007\/978-1-4612-0537-1 10.1007\/978-1-4612-0537-1 V\u00edctor H. de la Pe\u00f1a and Evarist Gin\u00e9. 1999. Decoupling. Springer-Verlag, New York. xvi+392 pages. DOI:http:\/\/dx.doi.org\/10.1007\/978-1-4612-0537-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993138"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053606000000768"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.3150\/bj\/1106314846"},{"key":"e_1_2_1_9_1","series-title":"Lecture Notes in Mathematics","volume-title":"Oracle inequalities in empirical risk minimization and sparse recovery problems","author":"Koltchinskii Vladimir","unstructured":"Vladimir Koltchinskii . 2011. Oracle inequalities in empirical risk minimization and sparse recovery problems . In Lecture Notes in Mathematics , vol. 2033 , Springer , Heidelberg . x+254 pages. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-22147-7 (Lectures from the 38th Probability Summer School held in Saint-Flour, 2008, \u00c9cole d'\u00c9t\u00e9 de Probabilit\u00e9s de Saint-Flour. {Saint-Flour Probability Summer School}). 10.1007\/978-3-642-22147-7 Vladimir Koltchinskii. 2011. Oracle inequalities in empirical risk minimization and sparse recovery problems. In Lecture Notes in Mathematics, vol. 2033, Springer, Heidelberg. x+254 pages. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-22147-7 (Lectures from the 38th Probability Summer School held in Saint-Flour, 2008, \u00c9cole d'\u00c9t\u00e9 de Probabilit\u00e9s de Saint-Flour. {Saint-Flour Probability Summer School})."},{"key":"e_1_2_1_10_1","first-page":"3580","article-title":"Bounding the smallest singular value of a random matrix without concentration","volume":"1312","author":"Koltchinskii Vladimir","year":"2013","unstructured":"Vladimir Koltchinskii and Shahar Mendelson . 2013 . Bounding the smallest singular value of a random matrix without concentration . Tech. Rep. Technion and Georgia Tech. arXiv : 1312 . 3580 . (Int. Math. Res. Notices, to appear). Vladimir Koltchinskii and Shahar Mendelson. 2013. Bounding the smallest singular value of a random matrix without concentration. Tech. Rep. Technion and Georgia Tech. arXiv:1312.3580. (Int. Math. Res. Notices, to appear).","journal-title":"Tech. Rep. Technion and Georgia Tech. arXiv"},{"key":"e_1_2_1_11_1","first-page":"4825","article-title":"Learning subgaussian classes: Upper and minimax bounds","volume":"1305","author":"Lecu\u00e9 Guillaume","year":"2013","unstructured":"Guillaume Lecu\u00e9 and Shahar Mendelson . 2013 a. Learning subgaussian classes: Upper and minimax bounds . Tech. Rep. CNRS, Ecole polytechnique and Technion. arXiv : 1305 . 4825 . Guillaume Lecu\u00e9 and Shahar Mendelson. 2013a. Learning subgaussian classes: Upper and minimax bounds. Tech. Rep. CNRS, Ecole polytechnique and Technion. arXiv: 1305.4825.","journal-title":"Tech. Rep. CNRS, Ecole polytechnique and Technion. arXiv"},{"key":"e_1_2_1_12_1","first-page":"5024","article-title":"Minimax rate of convergence and the performance of ERM in phase recovery","volume":"1311","author":"Lecu\u00e9 Guillaume","year":"2013","unstructured":"Guillaume Lecu\u00e9 and Shahar Mendelson . 2013 b. Minimax rate of convergence and the performance of ERM in phase recovery . Tech. Rep. CNRS, Ecole polytechnique and Technion. arXiv : 1311 . 5024 . Guillaume Lecu\u00e9 and Shahar Mendelson. 2013b. Minimax rate of convergence and the performance of ERM in phase recovery. Tech. Rep. CNRS, Ecole polytechnique and Technion. arXiv: 1311.5024.","journal-title":"Tech. Rep. CNRS, Ecole polytechnique and Technion. arXiv"},{"key":"e_1_2_1_13_1","first-page":"5763","article-title":"Sparse recovery under weak moment assumptions","volume":"1402","author":"Lecu\u00e9 Guillaume","year":"2014","unstructured":"Guillaume Lecu\u00e9 and Shahar Mendelson . 2014 . Sparse recovery under weak moment assumptions . Tech. Rep. CNRS, Ecole Polytechnique and Technion. arXiv : 1402 . 5763 . (J. Eur. Math. Soc., to appear). Guillaume Lecu\u00e9 and Shahar Mendelson. 2014. Sparse recovery under weak moment assumptions. Tech. Rep. CNRS, Ecole Polytechnique and Technion. arXiv:1402.5763. (J. Eur. Math. Soc., to appear).","journal-title":"Tech. Rep. CNRS, Ecole Polytechnique and Technion. arXiv"},{"key":"e_1_2_1_14_1","volume-title":"The Concnetration of Measure Phenomenon","author":"Ledoux Michel","unstructured":"Michel Ledoux . 2001. The Concnetration of Measure Phenomenon . American Mathematical Society , Providence, RI . Michel Ledoux. 2001. The Concnetration of Measure Phenomenon. American Mathematical Society, Providence, RI."},{"key":"e_1_2_1_15_1","volume-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete (3) {Results in Mathematics and Related Areas (3)}","author":"Ledoux Michel","unstructured":"Michel Ledoux and Michel Talagrand . 1991. Probability in Banach spaces . In Ergebnisse der Mathematik und ihrer Grenzgebiete (3) {Results in Mathematics and Related Areas (3)} , Vol. 23 , Springer-Verlag , Berlin . xii+480 pages. Isoperimetry and processes. Michel Ledoux and Michel Talagrand. 1991. Probability in Banach spaces. In Ergebnisse der Mathematik und ihrer Grenzgebiete (3) {Results in Mathematics and Related Areas (3)}, Vol. 23, Springer-Verlag, Berlin. xii+480 pages. Isoperimetry and processes."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0084-5"},{"key":"e_1_2_1_18_1","first-page":"3192","article-title":"Learning without concentration for gerenal loss functions","volume":"1410","author":"Mendelson Shahar","year":"2014","unstructured":"Shahar Mendelson . 2014 a. Learning without concentration for gerenal loss functions . Tech. Rep. Technion. arXiv : 1410 . 3192 . Shahar Mendelson. 2014a. Learning without concentration for gerenal loss functions. Tech. Rep. Technion. arXiv:1410.3192.","journal-title":"Tech. Rep. Technion. arXiv"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09477-9_25"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0618-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2012.01.027"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/448"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176988847"},{"key":"e_1_2_1_24_1","volume-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics {Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics}","author":"Talagrand Michel","unstructured":"Michel Talagrand . 2014. Upper and lower bounds for stochastic processes . In Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics {Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics} , Vol. 60 , Springer , Heidelberg . xvi+626 pages. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-54075-2 10.1007\/978-3-642-54075-2 Michel Talagrand. 2014. Upper and lower bounds for stochastic processes. In Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics {Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics}, Vol. 60, Springer, Heidelberg. xvi+626 pages. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-54075-2"},{"key":"e_1_2_1_25_1","volume-title":"Wellner","author":"van der Vaart Aad W.","year":"1996","unstructured":"Aad W. van der Vaart and Jom A . Wellner . 1996 . Weak Convergence and Empirical Processes. Springer-Verlag , New York. xvi+508 pages. Aad W. van der Vaart and Jom A. Wellner. 1996. Weak Convergence and Empirical Processes. Springer-Verlag, New York. xvi+508 pages."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699439","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:58Z","timestamp":1750227418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699439"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,30]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,6,30]]}},"alternative-id":["10.1145\/2699439"],"URL":"https:\/\/doi.org\/10.1145\/2699439","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,30]]},"assertion":[{"value":"2014-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}