{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T16:07:02Z","timestamp":1774627622825,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Army Research Office","award":["W911NF-17-1-0304"],"award-info":[{"award-number":["W911NF-17-1-0304"]}]},{"name":"National Science Foundation","award":["CCF-2145898"],"award-info":[{"award-number":["CCF-2145898"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,9]]},"DOI":"10.1145\/3580507.3597787","type":"proceedings-article","created":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T14:19:22Z","timestamp":1688739562000},"page":"540-560","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Smoothed Analysis of Online Non-parametric Auctions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-3253-5335","authenticated-orcid":false,"given":"Naveen","family":"Durvasula","sequence":"first","affiliation":[{"name":"UC Berkeley, Berkeley, CA, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8612-2089","authenticated-orcid":false,"given":"Nika","family":"Haghtalab","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-4967-5927","authenticated-orcid":false,"given":"Manolis","family":"Zampetakis","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,7]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263927"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Martin Anthony Peter L Bartlett Peter L Bartlett etal 1999. Neural network learning: Theoretical foundations. Vol. 9. Cambridge University Press Cambridge.  Martin Anthony Peter L Bartlett Peter L Bartlett et al. 1999. Neural network learning: Theoretical foundations. Vol. 9. Cambridge University Press Cambridge.","DOI":"10.1017\/CBO9780511624216"},{"key":"e_1_3_2_2_3_1","volume-title":"Proceedings of the 7th ACM Conference on Economics and Computation (EC). 29--35","author":"Balcan Maria-Florina","year":"2006","unstructured":"Maria-Florina Balcan and Avrim Blum . 2006 . Approximation algorithms and online mechanisms for item pricing . In Proceedings of the 7th ACM Conference on Economics and Computation (EC). 29--35 . Maria-Florina Balcan and Avrim Blum. 2006. Approximation algorithms and online mechanisms for item pricing. In Proceedings of the 7th ACM Conference on Economics and Computation (EC). 29--35."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00064"},{"key":"e_1_3_2_2_5_1","volume-title":"Proceedings of the 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 Conference on Learning Theory (COLT). Shai Ben-David, D\u00e1vid P\u00e1l, and Shai Shalev-Shwartz. 2009. Agnostic Online Learning.. In Proceedings of the Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"crossref","first-page":"1399","DOI":"10.3982\/TE3797","article-title":"Countering the winner's curse: Optimal auction design in a common value model","volume":"15","author":"Bergemann Dirk","year":"2020","unstructured":"Dirk Bergemann , Benjamin Brooks , and Stephen Morris . 2020 . Countering the winner's curse: Optimal auction design in a common value model . Theoretical Economics 15 , 4 (2020), 1399 -- 1434 . Dirk Bergemann, Benjamin Brooks, and Stephen Morris. 2020. Countering the winner's curse: Optimal auction design in a common value model. Theoretical Economics 15, 4 (2020), 1399--1434.","journal-title":"Theoretical Economics"},{"key":"e_1_3_2_2_7_1","volume-title":"Proceedings of the Conference on Learning Theory (COLT). PMLR, 1716--1786","author":"Block Adam","year":"2022","unstructured":"Adam Block , Yuval Dagan , Noah Golowich , and Alexander Rakhlin . 2022 . Smoothed online learning is as easy as statistical learning . In Proceedings of the Conference on Learning Theory (COLT). PMLR, 1716--1786 . Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. 2022. Smoothed online learning is as easy as statistical learning. In Proceedings of the Conference on Learning Theory (COLT). PMLR, 1716--1786."},{"key":"e_1_3_2_2_8_1","volume-title":"Hartline","author":"Blum Avrim","year":"2005","unstructured":"Avrim Blum and Jason D . Hartline . 2005 . Near-Optimal Online Auctions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, USA, 1156--1163. Avrim Blum and Jason D. Hartline. 2005. Near-Optimal Online Auctions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, USA, 1156--1163."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085145"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2365772"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1017939242"},{"key":"e_1_3_2_2_13_1","volume-title":"Proceedings of the 47th annual ACM Symposium on Theory of computing (STOC). 243--252","author":"Cole Richard","year":"2014","unstructured":"Richard Cole and Tim Roughgarden . 2014 . The sample complexity of revenue maximization . In Proceedings of the 47th annual ACM Symposium on Theory of computing (STOC). 243--252 . Richard Cole and Tim Roughgarden. 2014. The sample complexity of revenue maximization. In Proceedings of the 47th annual ACM Symposium on Theory of computing (STOC). 243--252."},{"key":"e_1_3_2_2_14_1","volume-title":"Full extraction of the surplus in Bayesian and dominant strategy auctions. Econometrica: Journal of the Econometric Society","author":"Cr\u00e9mer Jacques","year":"1988","unstructured":"Jacques Cr\u00e9mer and Richard P McLean . 1988. Full extraction of the surplus in Bayesian and dominant strategy auctions. Econometrica: Journal of the Econometric Society ( 1988 ), 1247--1257. Jacques Cr\u00e9mer and Richard P McLean. 1988. Full extraction of the surplus in Bayesian and dominant strategy auctions. Econometrica: Journal of the Econometric Society (1988), 1247--1257."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2022.03.001"},{"key":"e_1_3_2_2_16_1","volume-title":"Proceedings of the 48th annual ACM Symposium on Theory of Computing (STOC). 426--439","author":"Devanur Nikhil R","year":"2016","unstructured":"Nikhil R Devanur , Zhiyi Huang , and Christos-Alexandros Psomas . 2016 . The sample complexity of auctions with side information . In Proceedings of the 48th annual ACM Symposium on Theory of Computing (STOC). 426--439 . Nikhil R Devanur, Zhiyi Huang, and Christos-Alexandros Psomas. 2016. The sample complexity of auctions with side information. In Proceedings of the 48th annual ACM Symposium on Theory of Computing (STOC). 426--439."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402203"},{"key":"e_1_3_2_2_18_1","volume-title":"Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics","author":"Dvoretzky Aryeh","year":"1956","unstructured":"Aryeh Dvoretzky , Jack Kiefer , and Jacob Wolfowitz . 1956. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics ( 1956 ), 642--669. Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. 1956. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics (1956), 642--669."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_3_2_2_20_1","volume-title":"Proceedings of the 2014 ACM conference on Economics and computation (EC). 23--36","author":"Fu Hu","year":"2014","unstructured":"Hu Fu , Nima Haghpanah , Jason Hartline , and Robert Kleinberg . 2014 . Optimal auctions for correlated buyers with sampling . In Proceedings of the 2014 ACM conference on Economics and computation (EC). 23--36 . Hu Fu, Nima Haghpanah, Jason Hartline, and Robert Kleinberg. 2014. Optimal auctions for correlated buyers with sampling. In Proceedings of the 2014 ACM conference on Economics and computation (EC). 23--36."},{"key":"e_1_3_2_2_21_1","volume-title":"A comparison of signalling alphabets. The Bell system technical journal 31, 3","author":"Gilbert Edgar N","year":"1952","unstructured":"Edgar N Gilbert . 1952. A comparison of signalling alphabets. The Bell system technical journal 31, 3 ( 1952 ), 504--522. Edgar N Gilbert. 1952. A comparison of signalling alphabets. The Bell system technical journal 31, 3 (1952), 504--522."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316325"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840766"},{"key":"e_1_3_2_2_25_1","first-page":"4072","article-title":"Oracle-efficient online learning for smoothed adversaries","volume":"35","author":"Haghtalab Nika","year":"2022","unstructured":"Nika Haghtalab , Yanjun Han , Abhishek Shetty , and Kunhe Yang . 2022 . Oracle-efficient online learning for smoothed adversaries . Advances in Neural Information Processing Systems 35 (2022), 4072 -- 4084 . Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. 2022. Oracle-efficient online learning for smoothed adversaries. Advances in Neural Information Processing Systems 35 (2022), 4072--4084.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_2_26_1","first-page":"9203","article-title":"Smoothed Analysis of Online and Differentially Private Learning","volume":"33","author":"Haghtalab Nika","year":"2020","unstructured":"Nika Haghtalab , Tim Roughgarden , and Abhishek Shetty . 2020 . Smoothed Analysis of Online and Differentially Private Learning . Advances in Neural Information Processing Systems 33 (2020), 9203 -- 9215 . Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. 2020. Smoothed Analysis of Online and Differentially Private Learning. Advances in Neural Information Processing Systems 33 (2020), 9203--9215.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_2_27_1","volume-title":"2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 942--953","author":"Haghtalab Nika","year":"2021","unstructured":"Nika Haghtalab , Tim Roughgarden , and Abhishek Shetty . 2021 . Smoothed analysis with adaptive adversaries . In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 942--953 . Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. 2021. Smoothed analysis with adaptive adversaries. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 942--953."},{"key":"e_1_3_2_2_28_1","volume-title":"Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning 2, 4","author":"Littlestone Nick","year":"1988","unstructured":"Nick Littlestone . 1988. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning 2, 4 ( 1988 ), 285--318. Nick Littlestone. 1988. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning 2, 4 (1988), 285--318."},{"key":"e_1_3_2_2_29_1","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"Manthey Bodo","unstructured":"Bodo Manthey . 2020. Smoothed Analysis of Local Search . In Beyond the Worst-Case Analysis of Algorithms , Tim Roughgarden (Ed.). Cambridge University Press , Chapter 13, 285--308. Bodo Manthey. 2020. Smoothed Analysis of Local Search. In Beyond the Worst-Case Analysis of Algorithms, Tim Roughgarden (Ed.). Cambridge University Press, Chapter 13, 285--308."},{"key":"e_1_3_2_2_30_1","volume-title":"A theory of auctions and competitive bidding. Econometrica: Journal of the Econometric Society","author":"Milgrom Paul R","year":"1982","unstructured":"Paul R Milgrom and Robert J Weber . 1982. A theory of auctions and competitive bidding. Econometrica: Journal of the Econometric Society ( 1982 ), 1089--1122. Paul R Milgrom and Robert J Weber. 1982. A theory of auctions and competitive bidding. Econometrica: Journal of the Econometric Society (1982), 1089--1122."},{"key":"e_1_3_2_2_31_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 ). 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_2_32_1","volume-title":"Optimal auction design. Mathematics of operations research 6, 1","author":"Myerson Roger B","year":"1981","unstructured":"Roger B Myerson . 1981. Optimal auction design. Mathematics of operations research 6, 1 ( 1981 ), 58--73. Roger B Myerson. 1981. Optimal auction design. Mathematics of operations research 6, 1 (1981), 58--73."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329563"},{"key":"e_1_3_2_2_34_1","volume-title":"Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems 24","author":"Rakhlin Alexander","year":"2011","unstructured":"Alexander Rakhlin , Karthik Sridharan , and Ambuj Tewari . 2011. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems 24 ( 2011 ). Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. 2011. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems 24 (2011)."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355900"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_2_37_1","first-page":"781","article-title":"On the uniform convergence of relative frequencies of events to their probabilities","volume":"181","author":"Vapnik Vladimir","year":"1968","unstructured":"Vladimir Vapnik and A Ya Chervonenkis . 1968 . On the uniform convergence of relative frequencies of events to their probabilities . In Doklady Akademii Nauk USSR , Vol. 181. 781 -- 787 . Vladimir Vapnik and A Ya Chervonenkis. 1968. On the uniform convergence of relative frequencies of events to their probabilities. In Doklady Akademii Nauk USSR, Vol. 181. 781--787.","journal-title":"Doklady Akademii Nauk USSR"},{"key":"e_1_3_2_2_38_1","first-page":"739","article-title":"Estimate of the number of signals in error correcting codes","volume":"117","author":"Varshamov Rom Rubenovich","year":"1957","unstructured":"Rom Rubenovich Varshamov . 1957 . Estimate of the number of signals in error correcting codes . Docklady Akad. Nauk, SSSR 117 (1957), 739 -- 741 . Rom Rubenovich Varshamov. 1957. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR 117 (1957), 739--741.","journal-title":"Docklady Akad. Nauk, SSSR"},{"key":"e_1_3_2_2_39_1","volume-title":"International Conference on Machine Learning (ICML). PMLR, 11716--11726","author":"Yang Chunxue","year":"2021","unstructured":"Chunxue Yang and Xiaohui Bei . 2021 . Learning Optimal Auctions with Correlated Valuations from Samples . In International Conference on Machine Learning (ICML). PMLR, 11716--11726 . Chunxue Yang and Xiaohui Bei. 2021. Learning Optimal Auctions with Correlated Valuations from Samples. In International Conference on Machine Learning (ICML). PMLR, 11716--11726."},{"key":"e_1_3_2_2_40_1","volume-title":"Festschrift for Lucien Le Cam","author":"Assouad Bin Yu.","unstructured":"Bin Yu. 1997. Assouad , fano, and le cam . In Festschrift for Lucien Le Cam . Springer , 423--435. Bin Yu. 1997. Assouad, fano, and le cam. In Festschrift for Lucien Le Cam. Springer, 423--435."}],"event":{"name":"EC '23: 24th ACM Conference on Economics and Computation","location":"London United Kingdom","acronym":"EC '23","sponsor":["SIGecom Special Interest Group on Economics and Computation"]},"container-title":["Proceedings of the 24th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597787","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580507.3597787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:57Z","timestamp":1750182537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,7]]},"references-count":39,"alternative-id":["10.1145\/3580507.3597787","10.1145\/3580507"],"URL":"https:\/\/doi.org\/10.1145\/3580507.3597787","relation":{},"subject":[],"published":{"date-parts":[[2023,7,7]]},"assertion":[{"value":"2023-07-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}