{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:55Z","timestamp":1781031415034,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101078075"],"award-info":[{"award-number":["101078075"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101039692"],"award-info":[{"award-number":["101039692"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["882396"],"award-info":[{"award-number":["882396"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["993\/17"],"award-info":[{"award-number":["993\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["3174\/23"],"award-info":[{"award-number":["3174\/23"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2250\/22"],"award-info":[{"award-number":["2250\/22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1225\/20"],"award-info":[{"award-number":["1225\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018385"],"award-info":[{"award-number":["2018385"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800787","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"722-733","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4757-5763","authenticated-orcid":false,"given":"Alon","family":"Cohen","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"},{"name":"Google Research, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5374-4129","authenticated-orcid":false,"given":"Liad","family":"Erez","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5511-1467","authenticated-orcid":false,"given":"Steve","family":"Hanneke","sequence":"additional","affiliation":[{"name":"Purdue University, Indiana, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9061-0448","authenticated-orcid":false,"given":"Tomer","family":"Koren","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"},{"name":"Google Research, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6891-2645","authenticated-orcid":false,"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"},{"name":"Google Research, Tel Aviv, Israel"}],"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, Haifa, Israel"},{"name":"Google Research, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2735-5133","authenticated-orcid":false,"given":"Qian","family":"Zhang","sequence":"additional","affiliation":[{"name":"Purdue University, Indiana, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00071"},{"key":"e_1_3_2_1_2_1","volume-title":"Closure Properties for Private Classification and Online Prediction. CoRR, abs\/2003.04509","author":"Alon Noga","year":"2020","unstructured":"Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. 2020. Closure Properties for Private Classification and Online Prediction. CoRR, abs\/2003.04509 (2020), arxiv:2003.04509. arxiv:2003.04509"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3526074"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00070"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316312"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 37^ th Conference on Learning Theory.","author":"Alon Noga","year":"2024","unstructured":"Noga Alon, Shay Moran, Hilla Schefler, and Amir Yehudayoff. 2024. A Unified Characterization of Private Learnability via Graph Theory. In Proceedings of the 37^ th Conference on Learning Theory."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"I. Attias S. Hanneke A. Kalavasis A. Karbasi and G. Velegkas. 2023. Optimal Learners for Realizable Regression: PAC Learning and Online Learning. In Advances in Neural Information Processing Systems 36.","DOI":"10.52202\/075280-1936"},{"key":"e_1_3_2_1_8_1","first-page":"1","article-title":"Characterizing the Sample Complexity of Pure Private Learners","volume":"20","author":"Beimel Amos","year":"2019","unstructured":"Amos Beimel, Kobbi Nissim, and Uri Stemmer. 2019. Characterizing the Sample Complexity of Pure Private Learners. Journal of Machine Learning Research, 20, 146 (2019), 1\u2013\u201333.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1008"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00093"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00044"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 27^ th International Conference on Artificial Intelligence and Statistics.","author":"Carmon D.","unstructured":"D. Carmon, R. Livni, and A. Yehudayoff. 2024. The Sample Complexity of ERMs in Stochastic Convex Optimization. In Proceedings of the 27^ th International Conference on Artificial Intelligence and Statistics."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.833339"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","unstructured":"N. Cesa-Bianchi and G. Lugosi. 2006. Prediction Learning and Games. Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511546921 10.1017\/CBO9780511546921","DOI":"10.1017\/CBO9780511546921"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585190"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2912074"},{"key":"e_1_3_2_1_17_1","unstructured":"Amit Daniely Sivan Sabato and Shai Shalev-Shwartz. 2012. Multiclass Learning Approaches: A Theoretical Comparison with Implications. In NIPS. 494\u2013502."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Amit Daniely Michael Schapira and Gal Shahaf. 2015. STOC. 401\u2013408. https:\/\/doi.org\/10.1145\/2746539.2746597 10.1145\/2746539.2746597","DOI":"10.1145\/2746539.2746597"},{"key":"e_1_3_2_1_19_1","volume-title":"Conference on Learning Theory. 287\u2013316","author":"Daniely Amit","year":"2014","unstructured":"Amit Daniely and Shai Shalev-Shwartz. 2014. Optimal learners for multiclass problems. In Conference on Learning Theory. 287\u2013316."},{"key":"e_1_3_2_1_20_1","unstructured":"Ofir David Shay Moran and Amir Yehudayoff. 2016. Supervised learning through the lens of compression. In Advances in Neural Information Processing Systems 29 D. Lee M. Sugiyama U. Luxburg I. Guyon and R. Garnett (Eds.)."},{"key":"e_1_3_2_1_21_1","unstructured":"L. Erez A. Peled-Cohen T. Koren Y. Mansour and S. Moran. 2024. Fast Rates for Bandit PAC Multiclass Classification. In Advances in Neural Information Processing Systems 37."},{"key":"e_1_3_2_1_22_1","unstructured":"V. Feldman. 2016. Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back. In Advances in Neural Information Processing Systems 29."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022660318680"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1136"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_3_2_1_26_1","unstructured":"S. Hanneke. 2025. Agnostic Active Learning Is Always Better Than Passive Learning. In Advances in Neural Information Processing Systems 38."},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 42^ nd International Conference on Machine Learning.","author":"Hanneke S.","unstructured":"S. Hanneke, Q. Meng, and A. Shaeiri. 2025. Representation Preserving Multiclass Agnostic to Realizable Reduction. In Proceedings of the 42^ nd International Conference on Machine Learning."},{"key":"e_1_3_2_1_28_1","volume-title":"Improved Sample Complexity for Multiclass PAC Learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. https:\/\/openreview.net\/forum?id=l2yvtrz3On","author":"Hanneke Steve","year":"2024","unstructured":"Steve Hanneke, Shay Moran, and Qian Zhang. 2024. Improved Sample Complexity for Multiclass PAC Learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. https:\/\/openreview.net\/forum?id=l2yvtrz3On"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2912111"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90001-2"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.46298\/THEORETICS.24.2"},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the 41^ st International Conference on Machine Learning.","author":"Li Bo","year":"2024","unstructured":"Bo Li, Wei Wang, and Peng Ye. 2024. Improved Bounds for Pure Private Agnostic Learning: Item-level and User-level Privacy. In Proceedings of the 41^ st International Conference on Machine Learning."},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the 38^ th Conference on Learning Theory.","author":"Li Bo","year":"2025","unstructured":"Bo Li, Wei Wang, and Peng Ye. 2025. Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity. In Proceedings of the 38^ th Conference on Learning Theory."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44581-1_19"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022605311895"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-64-4.50046-3"},{"key":"e_1_3_2_1_38_1","unstructured":"Benjamin Rubinstein Peter Bartlett and J. Rubinstein. 2006. Shifting One-Inclusion Mistake Bounds and Tight Multiclass Expected Risk Bounds. In Advances in Neural Information Processing Systems B. Sch\u00f6lkopf J. Platt and T. Hoffman (Eds.). 19 MIT Press. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2006\/file\/a11ce019e96a4c60832eadd755a17a58-Paper.pdf"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:56:47Z","timestamp":1781027807000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":39,"alternative-id":["10.1145\/3798129.3800787","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800787","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}