{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:41Z","timestamp":1781077721557,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":49,"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":"ISF","award":["950\/15, 1225\/20, 2686\/20, 484\/18, 1789\/19"],"award-info":[{"award-number":["950\/15, 1225\/20, 2686\/20, 484\/18, 1789\/19"]}]},{"name":"Blavatnik Foundation"},{"name":"BSF","award":["2018267, 2018385"],"award-info":[{"award-number":["2018267, 2018385"]}]},{"name":"Simons Foundation"},{"name":"NSF","award":["DMS-1855464"],"award-info":[{"award-number":["DMS-1855464"]}]},{"name":"Azrieli Faculty Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451041","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"447-455","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Adversarial laws of large numbers and optimal regret in online classification"],"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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6366-5964","authenticated-orcid":false,"given":"Omri","family":"Ben-Eliezer","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7940-4002","authenticated-orcid":false,"given":"Yuval","family":"Dagan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, 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"}]},{"given":"Moni","family":"Naor","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8599-2472","authenticated-orcid":false,"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[{"name":"Boston University, USA \/ Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Adversarial Laws of Large Numbers and Optimal Regret in Online Classification. arXiv preprint arXiv:2101.09054","author":"Alon Noga","year":"2021","unstructured":"Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. 2021. Adversarial Laws of Large Numbers and Optimal Regret in Online Classification. arXiv preprint arXiv:2101.09054, 2021. arxiv:2101.09054"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 22nd Conference on Learning Theory (COLT).","author":"Ben-David Shai","year":"2009","unstructured":"Shai Ben-David, D\u00e1vid P\u00e1l, and Shai Shalev-Shwartz. 2009. Agnostic Online Learning. In Proceedings of the 22nd Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387658"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387643"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the International Congress of Mathematicians. 3, Pages 336\u2013338","author":"Blackwell David","year":"1954","unstructured":"David Blackwell. 1954. Controlled random walks. In Proceedings of the International Congress of Mathematicians. 3, Pages 336\u2013338."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1956.6.1"},{"key":"e_1_3_2_1_8_1","volume-title":"arXiv preprint arXiv:2102.01729","author":"Block Adam","year":"2021","unstructured":"Adam Block, Yuval Dagan, and Sasha Rakhlin. 2021. Majorizing Measures, Sequential Complexities, and Online Learning. arXiv preprint arXiv:2102.01729, 2021."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28650-9_8"},{"key":"e_1_3_2_1_11_1","unstructured":"Yeshwanth Cherapanamjeri and Jelani Nelson. 2020. On Adaptive Distance Estimation. In Advances in Neural Information Processing Systems 33 (NeurIPS)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00042"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Richard M. Dudley and P. L. Hennequin. 1984. A course on empirical processes. In \\'Ecole d'\\'Et\u00e9 de Probabilit\u00e9s de Saint-Flour XII - 1982. Springer Berlin Heidelberg. Pages 1\u2013142. https:\/\/doi.org\/10.1007\/BFb0099432 10.1007\/BFb0099432","DOI":"10.1007\/BFb0099432"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aaa9375"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITA.2012.6181772"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSP.2012.6319752"},{"key":"e_1_3_2_1_20_1","unstructured":"Nika Haghtalab Tim Roughgarden and Abhishek Shetty. 2020. Smoothed Analysis of Online and Differentially Private Learning. In Advances in Neural Information Processing Systems 33 (NeurIPS)."},{"key":"e_1_3_2_1_21_1","volume-title":"Approximation to Bayes risk in repeated play. Contributions to the Theory of Games, 3","author":"Hannan James","year":"1957","unstructured":"James Hannan. 1957. Approximation to Bayes risk in repeated play. Contributions to the Theory of Games, 3, 1957. Pages 97\u2013139."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488624"},{"key":"e_1_3_2_1_23_1","unstructured":"Avinatan Hassidim Haim Kaplan Yishay Mansour Yossi Matias and Uri Stemmer. 2020. Adversarially Robust Streaming Algorithms via Differential Privacy. In Advances in Neural Information Processing Systems 33 (NeurIPS)."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"e_1_3_2_1_25_1","volume-title":"Separating Adaptive Streaming from Oblivious Streaming. arXiv preprint arXiv:2101.10836","author":"Kaplan Haim","year":"2021","unstructured":"Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. 2021. Separating Adaptive Streaming from Oblivious Streaming. arXiv preprint arXiv:2101.10836, 2021."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1090\/mbk"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022869011914"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03942-3"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303517"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733772"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306193"},{"key":"e_1_3_2_1_33_1","volume-title":"Book Draft","author":"Rakhlin Alexander","year":"2014","unstructured":"Alexander Rakhlin and Karthik Sridharan. 2014. Statistical learning and sequential prediction. Book Draft, 2014."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21852-6_15"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Alexander Rakhlin Karthik Sridharan and Ambuj Tewari. 2010. Online learning: Random averages combinatorial parameters and learnability. In Advances in Neural Information Processing Systems. Pages 1984\u20131992. https:\/\/doi.org\/10.5555\/2997046.2997117","DOI":"10.5555\/2997046.2997117"},{"key":"e_1_3_2_1_36_1","first-page":"1","article-title":"Online learning via sequential complexities","volume":"16","author":"Rakhlin Alexander","year":"2015","unstructured":"Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. 2015. Online learning via sequential complexities.. J. Mach. Learn. Res., 16, 1, 2015. Pages 155\u2013186.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-013-0545-5"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1525\/9780520411586-011"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1953019"},{"key":"e_1_3_2_1_42_1","volume-title":"Arsalan Mosenia, Mung Chiang, and Prateek Mittal.","author":"Sitawarin Chawin","year":"2018","unstructured":"Chawin Sitawarin, Arjun Nitin Bhagoji, Arsalan Mosenia, Mung Chiang, and Prateek Mittal. 2018. DARTS: Deceiving Autonomous Cars with Toxic Signs. CoRR, abs\/1802.06430, 2018."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3264-1"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_3_2_1_46_1","volume-title":"Chervonenkis","author":"Vapnik Vladimir N.","year":"1974","unstructured":"Vladimir N. Vapnik and Alexey Y. Chervonenkis. 1974. Theory of Pattern Recognition. Nauka, Moscow."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_3_2_1_48_1","volume-title":"Woodruff and Samson Zhou","author":"David","year":"2020","unstructured":"David P. Woodruff and Samson Zhou. 2020. Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. arXiv preprint arXiv:2011.07471, 2020."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","unstructured":"Blake E. Woodworth Vitaly Feldman Saharon Rosset and Nati Srebro. 2018. The Everlasting Database: Statistical Validity at a Fair Price. In Advances in Neural Information Processing Systems 31 (NeurIPS). Pages 6532\u20136541. https:\/\/doi.org\/10.5555\/3327757.3327760","DOI":"10.5555\/3327757.3327760"}],"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.3451041","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451041","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451041","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.3451041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":49,"alternative-id":["10.1145\/3406325.3451041","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451041","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"}}]}}