{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T15:59:20Z","timestamp":1783439960006,"version":"3.54.6"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DMS-1855464"],"award-info":[{"award-number":["DMS-1855464"]}]},{"name":"Azrieli Foundation"},{"name":"Simons Foundation"},{"name":"BSF","award":["2018267, 2018385"],"award-info":[{"award-number":["2018267, 2018385"]}]},{"name":"ISF","award":["1225\/20"],"award-info":[{"award-number":["1225\/20"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451030","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"481-489","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Boosting simple learners"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1332-4883","authenticated-orcid":false,"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Princeton University, USA \/ Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alon","family":"Gonen","sequence":"additional","affiliation":[{"name":"OrCam, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elad","family":"Hazan","sequence":"additional","affiliation":[{"name":"Princeton University, USA \/ Google AI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8662-2737","authenticated-orcid":false,"given":"Shay","family":"Moran","sequence":"additional","affiliation":[{"name":"Technion, Israel \/ Google Research, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02123006"},{"key":"e_1_3_2_1_2_1","volume-title":"Boosting Simple Learners. CoRR, abs\/2001.11704","author":"Alon Noga","year":"2020","unstructured":"Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran. 2020. Boosting Simple Learners. CoRR, abs\/2001.11704, 2020. arxiv:2001.11704"},{"key":"e_1_3_2_1_3_1","first-page":"1983","article-title":"Densite et dimension","volume":"3","author":"Assouad P.","year":"1983","unstructured":"P. Assouad. 1983. Densite et dimension. Ann. Institut Fourier, 3, 1983. Pages 232\u2013282.","journal-title":"Ann. Institut Fourier"},{"key":"e_1_3_2_1_4_1","first-page":"2007","article-title":"AdaBoost is Consistent","volume":"8","author":"Bartlett Peter L.","year":"2007","unstructured":"Peter L. Bartlett and Mikhail Traskin. 2007. AdaBoost is Consistent. J. Mach. Learn. Res., 8, 2007. Pages 2347\u20132368. http:\/\/dl.acm.org\/citation.cfm?id=1314574","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_5_1","first-page":"2003","article-title":"On the Rate of Convergence of Regularized Boosting Classifiers","volume":"4","author":"Blanchard Gilles","year":"2003","unstructured":"Gilles Blanchard, G\u00e1bor Lugosi, and Nicolas Vayatis. 2003. On the Rate of Convergence of Regularized Boosting Classifiers. J. Mach. Learn. Res., 4, 2003. Pages 861\u2013894. http:\/\/jmlr.org\/papers\/v4\/blanchard03a.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_1_7_1","unstructured":"Leo Breiman. 1997. Arcing the edge."},{"key":"e_1_3_2_1_8_1","volume-title":"Some Infinite Theory for Predictor Ensembles. 09","author":"Breiman Leo","year":"2000","unstructured":"Leo Breiman. 2000. Some Infinite Theory for Predictor Ensembles. 09, 2000."},{"key":"e_1_3_2_1_9_1","first-page":"2","article-title":"Boosting With the L2 Loss","volume":"98","author":"B\u00fchlmann Peter","year":"2003","unstructured":"Peter B\u00fchlmann and B. Yu. 2003. Boosting With the L2 Loss: Regression and Classification. J. Amer. Statist. Assoc., 98, 2, 2003. Pages 324\u2013339.","journal-title":"Regression and Classification. J. Amer. Statist. Assoc."},{"key":"e_1_3_2_1_10_1","first-page":"2019","article-title":"Tight Lower Bounds on the VC-dimension of Geometric Set Systems","volume":"20","author":"Csik\u00f3s M\u00f3nika","year":"2019","unstructured":"M\u00f3nika Csik\u00f3s, Nabil H. Mustafa, and Andrey Kupavskii. 2019. Tight Lower Bounds on the VC-dimension of Geometric Set Systems. J. Mach. Learn. Res., 20, 2019. Pages 81:1\u201381:8. http:\/\/jmlr.org\/papers\/v20\/18-719.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.10.004"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-146-8.50019-9"},{"key":"e_1_3_2_1_13_1","first-page":"2000","article-title":"Greedy Function Approximation: A Gradient Boosting Machine","volume":"29","author":"Friedman Jerome H.","year":"2000","unstructured":"Jerome H. Friedman. 2000. Greedy Function Approximation: A Gradient Boosting Machine. Annals of Statistics, 29, 2000. Pages 1189\u20131232.","journal-title":"Annals of Statistics"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9473(01)00065-2"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90052-7"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos"},{"key":"e_1_3_2_1_17_1","volume-title":"Dec., 1988.","author":"Kearns M.","year":"1988","unstructured":"M. Kearns. 1988. Thoughts on Hypothesis Boosting. Dec., 1988."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos"},{"key":"e_1_3_2_1_19_1","volume-title":"Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS)","author":"Mannor Shie","year":"2000","unstructured":"Shie Mannor, Ron Meir, Todd K. Leen, Thomas G. Dietterich, and Volker Tresp. 2000. Weak Learners and Improved Rates of Convergence in Boosting. In Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS) 2000, Denver, CO, USA. MIT Press. Pages 280\u2013286. http:\/\/papers.nips.cc\/paper\/1906-weak-learners-and-improved-rates-of-convergence-in-boosting"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45435-7_22"},{"key":"e_1_3_2_1_21_1","volume-title":"Advances in Neural Information Processing Systems 12","author":"Mason Llew","unstructured":"Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. 2000. Boosting Algorithms as Gradient Descent. In In Advances in Neural Information Processing Systems 12. MIT Press. Pages 512\u2013518."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Ji\\v r\u00ed Matou\\v sek. 2009. Geometric Discrepancy. isbn:3540204563 https:\/\/doi.org\/10.1017\/cbo9780511526633 10.1017\/cbo9780511526633","DOI":"10.1017\/cbo9780511526633"},{"key":"e_1_3_2_1_23_1","first-page":"1","article-title":"A theory of multiclass boosting","volume":"14","author":"Mukherjee Indraneel","year":"2013","unstructured":"Indraneel Mukherjee and Robert E. Schapire. 2013. A theory of multiclass boosting. J. Mach. Learn. Res., 14, 1, 2013. Pages 437\u2013497. http:\/\/dl.acm.org\/citation.cfm?id=2502596","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116037"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107415324.004"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Paul Viola and Michael Jones. 2001. Rapid object detection using a boosted cascade of simple features. Pages 511\u2013518.","DOI":"10.1109\/CVPR.2001.990517"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1079120130"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451030","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451030","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451030","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451030"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":29,"alternative-id":["10.1145\/3406325.3451030","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451030","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}