{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:55Z","timestamp":1781031475348,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":42,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800729","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"84-92","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Learning Curves of Revenue Maximization"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5511-1467","authenticated-orcid":false,"given":"Steve","family":"Hanneke","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1479-5268","authenticated-orcid":false,"given":"Alkis","family":"Kalavasis","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, 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, Haifa, Israel"},{"name":"Google Research, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7148-0548","authenticated-orcid":false,"given":"Grigoris","family":"Velegkas","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Submultiplicative Glivenko-Cantelli and uniform convergence of revenues. Advances in Neural Information Processing Systems, 30","author":"Alon Noga","year":"2017","unstructured":"Noga Alon, Moshe Babaioff, Yannai A Gonczarowski, Yishay Mansour, Shay Moran, and Amir Yehudayoff. 2017. Submultiplicative Glivenko-Cantelli and uniform convergence of revenues. Advances in Neural Information Processing Systems, 30 (2017)."},{"key":"e_1_3_2_1_2_1","volume-title":"Performance limits of nonparametric estimators. Ph. D. Dissertation","author":"Antos Andr\u00e1s","unstructured":"Andr\u00e1s Antos. 1999. Performance limits of nonparametric estimators. Ph. D. Dissertation. Budapest University of Technology and Economics (Hungary)."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0378-3758(99)00084-1","article-title":"Lower bounds on the rate of convergence of nonparametric regression estimates","volume":"83","author":"Antos Andr\u00e1s","year":"2000","unstructured":"Andr\u00e1s Antos, L\u00e1szl\u00f3 Gy\u00f6rfi, and Michael Kohler. 2000. Lower bounds on the rate of convergence of nonparametric regression estimates. Journal of statistical planning and inference, 83, 1 (2000), 91\u2013100.","journal-title":"Journal of statistical planning and inference"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10019"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/238061.238160"},{"key":"e_1_3_2_1_6_1","volume-title":"The Thirty Seventh Annual Conference on Learning Theory. 359\u2013405","author":"Attias Idan","year":"2024","unstructured":"Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, and Grigoris Velegkas. 2024. Universal Rates for Regression: Separations between Cut-Off and Absolute Loss. In The Thirty Seventh Annual Conference on Learning Theory. 359\u2013405."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.08.002"},{"key":"e_1_3_2_1_8_1","volume-title":"Market research and market design. Advances in theoretical Economics, 3, 1","author":"Baliga Sandeep","year":"2003","unstructured":"Sandeep Baliga and Rakesh Vohra. 2003. Market research and market design. Advances in theoretical Economics, 3, 1 (2003)."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626514"},{"key":"e_1_3_2_1_10_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 5890\u20135924","author":"Bousquet Olivier","year":"2023","unstructured":"Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, and Ilya Tolstikhin. 2023. Fine-grained distribution-dependent learning curves. In The Thirty Sixth Annual Conference on Learning Theory. 5890\u20135924."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451087"},{"key":"e_1_3_2_1_12_1","first-page":"932","article-title":"Lower bounds for nonparametric density estimation rates","author":"Boyd David W","year":"1978","unstructured":"David W Boyd and J Michael Steele. 1978. Lower bounds for nonparametric density estimation rates. The Annals of Statistics, 932\u2013934.","journal-title":"The Annals of Statistics"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399541"},{"key":"e_1_3_2_1_14_1","volume-title":"2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 516\u2013527","author":"Cai Yang","year":"2017","unstructured":"Yang Cai and Constantinos Daskalakis. 2017. Learning multi-item auctions with (or without) samples. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 516\u2013527."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591867"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897553"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00534199"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"L Devroye and L\u00e1szl\u00f3 Gy\u00f6rfi. 2002. Distribution and density estimation. Principles of nonparametric learning 211\u2013270.","DOI":"10.1007\/978-3-7091-2568-7_5"},{"key":"e_1_3_2_1_19_1","volume-title":"A probabilistic theory of pattern recognition. 31","author":"Devroye Luc","unstructured":"Luc Devroye, L\u00e1szl\u00f3 Gy\u00f6rfi, and G\u00e1bor Lugosi. 2013. A probabilistic theory of pattern recognition. 31, Springer Science & Business Media."},{"key":"e_1_3_2_1_20_1","first-page":"1250","article-title":"Distribution-free lower bounds in density estimation","author":"Devroye Luc","year":"1984","unstructured":"Luc Devroye and Clark S Penrod. 1984. Distribution-free lower bounds in density estimation. The Annals of Statistics, 1250\u20131262.","journal-title":"The Annals of Statistics"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807364"},{"key":"e_1_3_2_1_22_1","unstructured":"Edith Elkind. 2007. Designing and learning optimal finite support auctions."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055427"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3439722"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316325"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","first-page":"28657","DOI":"10.52202\/068431-2077","article-title":"Universal rates for interactive learning","volume":"35","author":"Hanneke Steve","year":"2022","unstructured":"Steve Hanneke, Amin Karbasi, Shay Moran, and Grigoris Velegkas. 2022. Universal rates for interactive learning. Advances in Neural Information Processing Systems, 35 (2022), 28657\u201328669.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_27_1","volume-title":"Universal Rates for Active Learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems.","author":"Hanneke Steve","year":"2024","unstructured":"Steve Hanneke, Amin Karbasi, Shay Moran, and Grigoris Velegkas. 2024. Universal Rates for Active Learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems."},{"key":"e_1_3_2_1_28_1","volume-title":"Universal Rates for Multiclass Learning. In The Thirty Sixth Annual Conference on Learning Theory. 5615\u20135681","author":"Hanneke Steve","year":"2023","unstructured":"Steve Hanneke, Shay Moran, and Qian Zhang. 2023. Universal Rates for Multiclass Learning. In The Thirty Sixth Annual Conference on Learning Theory. 5615\u20135681."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Steve Hanneke and Mingyue Xu. 2024. Universal Rates of Empirical Risk Minimization. arXiv preprint arXiv:2412.02810.","DOI":"10.52202\/079017-3693"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1065719"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Alkis Kalavasis Anay Mehrotra and Grigoris Velegkas. 2024. On the limits of language generation: Trade-offs between hallucination and mode collapse. arXiv preprint arXiv:2411.09642.","DOI":"10.1145\/3717823.3718108"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","first-page":"20809","DOI":"10.52202\/068431-1513","article-title":"Multiclass learnability beyond the pac framework: Universal rates and partial concept classes","volume":"35","author":"Kalavasis Alkis","year":"2022","unstructured":"Alkis Kalavasis, Grigoris Velegkas, and Amin Karbasi. 2022. Multiclass learnability beyond the pac framework: Universal rates and partial concept classes. Advances in Neural Information Processing Systems, 35 (2022), 20809\u201320822.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_33_1","volume-title":"Conference on Learning Theory. 1298\u20131318","author":"Morgenstern Jamie","year":"2016","unstructured":"Jamie Morgenstern and Tim Roughgarden. 2016. Learning simple auctions. In Conference on Learning Theory. 1298\u20131318."},{"key":"e_1_3_2_1_34_1","volume-title":"On the pseudo-dimension of nearly optimal auctions. Advances in Neural Information Processing Systems, 28","author":"Morgenstern Jamie H","year":"2015","unstructured":"Jamie H Morgenstern and Tim Roughgarden. 2015. On the pseudo-dimension of nearly optimal auctions. Advances in Neural Information Processing Systems, 28 (2015)."},{"key":"e_1_3_2_1_35_1","volume-title":"The effectiveness of English auctions. Games and economic Behavior, 43, 2","author":"Neeman Zvika","year":"2003","unstructured":"Zvika Neeman. 2003. The effectiveness of English auctions. Games and economic Behavior, 43, 2 (2003), 214\u2013238."},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the 2016 ACM Conference on Economics and Computation. 1\u201318","author":"Roughgarden Tim","year":"2016","unstructured":"Tim Roughgarden and Okke Schrijvers. 2016. Ironing in the dark. In Proceedings of the 2016 ACM Conference on Economics and Computation. 1\u201318."},{"key":"e_1_3_2_1_37_1","volume-title":"Characterizing rational versus exponential learning curves. journal of computer and system sciences, 55, 1","author":"Schuurmans Dale","year":"1997","unstructured":"Dale Schuurmans. 1997. Characterizing rational versus exponential learning curves. journal of computer and system sciences, 55, 1 (1997), 140\u2013160."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1257\/000282803322156963"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Charles J Stone. 1977. Consistent nonparametric regression. The annals of statistics 595\u2013620.","DOI":"10.1214\/aos\/1176343886"},{"key":"e_1_3_2_1_40_1","volume-title":"A sample complexity measure with applications to learning optimal auctions. Advances in Neural Information Processing Systems, 30","author":"Syrgkanis Vasilis","year":"2017","unstructured":"Vasilis Syrgkanis. 2017. A sample complexity measure with applications to learning optimal auctions. Advances in Neural Information Processing Systems, 30 (2017)."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_42_1","volume-title":"The nature of statistical learning theory","author":"Vapnik Vladimir","unstructured":"Vladimir Vapnik. 2013. The nature of statistical learning theory. Springer science & business media."}],"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.3800729","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:41Z","timestamp":1781028341000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":42,"alternative-id":["10.1145\/3798129.3800729","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800729","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"}}]}}