{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:11Z","timestamp":1781078291024,"version":"3.54.1"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T00:00:00Z","timestamp":1718064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            We prove novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time step an adversary chooses an input distribution with density function bounded above pointwise by\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tfrac{1}{\\sigma }\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            times that of the uniform distribution; nature then samples an input from this distribution. Here, \u03c3 is a parameter that interpolates between the extremes of worst-case and average case analysis. Crucially, our results hold for\n            <jats:italic>adaptive<\/jats:italic>\n            adversaries that can base their choice of input distribution on the decisions of the algorithm and the realizations of the inputs in the previous time steps. An adaptive adversary can nontrivially correlate inputs at different time steps with each other and with the algorithm\u2019s current state; this appears to rule out the standard proof approaches in smoothed analysis.\n          <\/jats:p>\n          <jats:p>\n            This paper presents a general technique for proving smoothed algorithmic guarantees against adaptive adversaries, in effect reducing the setting of an adaptive adversary to the much simpler case of an oblivious adversary (i.e., an adversary that commits in advance to the entire sequence of input distributions). We apply this technique to prove strong smoothed guarantees for three different problems:\n            <jats:list list-type=\"ordered\">\n              <jats:list-item>\n                <jats:label>(1)<\/jats:label>\n                <jats:p>\n                  Online learning: We consider the online prediction problem, where instances are generated from an adaptive sequence of \u03c3-smooth distributions and the hypothesis class has VC dimension\n                  <jats:italic>d<\/jats:italic>\n                  . We bound the regret by\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(\\sqrt {T d\\ln (1\/\\sigma)} + d\\ln (T\/\\sigma))\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  and provide a near-matching lower bound. Our result shows that under smoothed analysis, learnability against adaptive adversaries is characterized by the finiteness of the VC dimension. This is as opposed to the worst-case analysis, where online learnability is characterized by Littlestone dimension (which is infinite even in the extremely restricted case of one-dimensional threshold functions). Our results fully answer an open question of\u00a0Rakhlin et\u00a0al. [\n                  <jats:xref ref-type=\"bibr\">64<\/jats:xref>\n                  ].\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(2)<\/jats:label>\n                <jats:p>\n                  Online discrepancy minimization: We consider the setting of the online Koml\u00f3s problem, where the input is generated from an adaptive sequence of \u03c3-smooth and isotropic distributions on the \u2113\n                  <jats:sub>2<\/jats:sub>\n                  unit ball. We bound the \u2113\n                  <jats:sub>\u221e<\/jats:sub>\n                  norm of the discrepancy vector by\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(\\ln ^2(\\frac{nT}{\\sigma }))\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  . This is as opposed to the worst-case analysis, where the tight discrepancy bound is\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Theta (\\sqrt {T\/n})\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  . We show such\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathrm{polylog}(nT\/\\sigma)\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  discrepancy guarantees are not achievable for non-isotropic \u03c3-smooth distributions.\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(3)<\/jats:label>\n                <jats:p>\n                  Dispersion in online optimization: We consider online optimization with piecewise Lipschitz functions where functions with \u2113 discontinuities are chosen by a smoothed adaptive adversary and show that the resulting sequence is\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(({\\sigma }\/{\\sqrt {T\\ell }}, \\tilde{O}(\\sqrt {T\\ell }))\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  -dispersed. That is, every ball of radius\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\({\\sigma }\/{\\sqrt {T\\ell }}\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  is split by\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(\\sqrt {T\\ell })\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  of the partitions made by these functions. This result matches the dispersion parameters of Balcan et\u00a0al. [\n                  <jats:xref ref-type=\"bibr\">13<\/jats:xref>\n                  ] for oblivious smooth adversaries, up to logarithmic factors. On the other hand, worst-case sequences are trivially (0,\n                  <jats:italic>T<\/jats:italic>\n                  )-dispersed.\n                  <jats:xref ref-type=\"fn\">\n                    <jats:sup>1<\/jats:sup>\n                  <\/jats:xref>\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>","DOI":"10.1145\/3656638","type":"journal-article","created":{"date-parts":[[2024,4,13]],"date-time":"2024-04-13T07:32:57Z","timestamp":1712993577000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Smoothed Analysis with Adaptive Adversaries"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8612-2089","authenticated-orcid":false,"given":"Nika","family":"Haghtalab","sequence":"first","affiliation":[{"name":"University of California Berkeley, Berkeley, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7163-8306","authenticated-orcid":false,"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[{"name":"Columbia University, New York, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7127-5961","authenticated-orcid":false,"given":"Abhishek","family":"Shetty","sequence":"additional","affiliation":[{"name":"University of California Berkeley, Berkeley, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"96","volume-title":"Proceedings of the 37th International Conference on Machine Learning, (ICML\u201920)","volume":"119","author":"Agarwal Naman","year":"2020","unstructured":"Naman Agarwal, Nataly Brukhim, Elad Hazan, and Zhou Lu. 2020. Boosting for control of dynamical systems. In Proceedings of the 37th International Conference on Machine Learning, (ICML\u201920), Vol. 119. PMLR, 96\u2013103."},{"key":"e_1_3_3_3_2","first-page":"100","volume-title":"Proceedings of the 38th International Conference on Machine Learning (ICML\u201921)","volume":"139","author":"Agarwal Naman","year":"2021","unstructured":"Naman Agarwal, Elad Hazan, Anirudha Majumdar, and Karan Singh. 2021. A regret minimization approach to iterative learning control. In Proceedings of the 38th International Conference on Machine Learning (ICML\u201921), Vol. 139. PMLR, 100\u2013109."},{"key":"e_1_3_3_4_2","first-page":"237","volume-title":"Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC\u201915)","author":"Allen-Zhu Zeyuan","year":"2015","unstructured":"Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. 2015. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC\u201915). 237\u2013245."},{"key":"e_1_3_3_5_2","first-page":"447","volume-title":"Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC\u201921)","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. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC\u201921). 447\u2013455."},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/3406325.3450994","volume-title":"53rd Annual ACM Symposium on Theory of Computing (STOC\u201921)","author":"Alweiss Ryan","year":"2021","unstructured":"Ryan Alweiss, Yang P. Liu, and Mehtaab Sawhney. 2021. Discrepancy minimization via a self-balancing walk. In 53rd Annual ACM Symposium on Theory of Computing (STOC\u201921). 14\u201320."},{"key":"e_1_3_3_7_2","first-page":"1","volume-title":"Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS\u201912)","author":"Arora Sanjeev","year":"2012","unstructured":"Sanjeev Arora, Rong Ge, and Ankur Moitra. 2012. Learning topic models \u2013 going beyond SVD. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS\u201912). 1\u201310."},{"issue":"6","key":"e_1_3_3_8_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","article-title":"The multiplicative weights update method: A meta-algorithm and applications","volume":"8","author":"Arora Sanjeev","year":"2012","unstructured":"Sanjeev Arora, Elad Hazan, and Satyen Kale. 2012. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing 8, 6 (2012), 121\u2013164.","journal-title":"Theory of Computing"},{"key":"e_1_3_3_9_2","first-page":"144","volume-title":"Proceedings of the 22nd Symposium on Computational Geometry (SoCG\u201906)","author":"Arthur David","year":"2006","unstructured":"David Arthur and Sergei Vassilvitskii. 2006. How slow is the k-means method?. In Proceedings of the 22nd Symposium on Computational Geometry (SoCG\u201906). 144\u2013153."},{"key":"e_1_3_3_10_2","first-page":"167","volume-title":"Conference on Learning Theory (COLT\u201915)","author":"Awasthi Pranjal","year":"2015","unstructured":"Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. 2015. Efficient learning of linear separators under bounded noise. In Conference on Learning Theory (COLT\u201915). 167\u2013190."},{"key":"e_1_3_3_11_2","first-page":"152","volume-title":"Conference on Learning Theory (COLT\u201916)","author":"Awasthi Pranjal","year":"2016","unstructured":"Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. 2016. Learning and 1-bit compressed sensing under asymmetric noise. In Conference on Learning Theory (COLT\u201916). 152\u2013192."},{"key":"e_1_3_3_12_2","first-page":"127","volume-title":"Conference on Learning Theory (COLT\u201917)","author":"Awasthi Pranjal","year":"2017","unstructured":"Pranjal Awasthi, Avrim Blum, Nika Haghtalab, and Yishay Mansour. 2017. Efficient PAC learning from the crowd. In Conference on Learning Theory (COLT\u201917). 127\u2013150."},{"issue":"2","key":"e_1_3_3_13_2","first-page":"8","article-title":"Clustering under approximation stability","volume":"60","author":"Balcan Maria-Florina","year":"2013","unstructured":"Maria-Florina Balcan, Avrim Blum, and Anupam Gupta. 2013. Clustering under approximation stability. J. ACM 60, 2, Article 8 (May 2013), 34 pages.","journal-title":"J. ACM"},{"key":"e_1_3_3_14_2","first-page":"603","volume-title":"Proceedings of the 59th Annual Symposium on Foundations of Computer Science (FOCS\u201918)","author":"Balcan Maria-Florina","year":"2018","unstructured":"Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. 2018. Dispersion for data-driven algorithm design, online learning, and private optimization. In Proceedings of the 59th Annual Symposium on Foundations of Computer Science (FOCS\u201918). 603\u2013614."},{"issue":"2","key":"e_1_3_3_15_2","first-page":"22","article-title":"K-center clustering under perturbation resilience","volume":"16","author":"Balcan Maria-Florina","year":"2020","unstructured":"Maria-Florina Balcan, Nika Haghtalab, and Colin White. 2020. K-center clustering under perturbation resilience. ACM Trans. Algorithms 16, 2, Article 22 (March 2020), 39 pages.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_3_16_2","first-page":"3","volume-title":"Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS\u201910)","author":"Bansal Nikhil","year":"2010","unstructured":"Nikhil Bansal. 2010. Constructive algorithms for discrepancy minimization. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS\u201910). 3\u201310."},{"key":"e_1_3_3_17_2","first-page":"587","volume-title":"Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC\u201918)","author":"Bansal Nikhil","year":"2018","unstructured":"Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett. 2018. The Gram-Schmidt walk: A cure for the Banaszczyk blues. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC\u201918). 587\u2013597."},{"key":"e_1_3_3_18_2","first-page":"914","volume-title":"Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC\u201917)","author":"Bansal Nikhil","year":"2017","unstructured":"Nikhil Bansal and Shashwat Garg. 2017. Algorithmic discrepancy beyond partial coloring. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC\u201917). 914\u2013926."},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","first-page":"2842","DOI":"10.1137\/1.9781611976465.169","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921)","author":"Bansal Nikhil","year":"2021","unstructured":"Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. 2021. Online discrepancy minimization for stochastic arrivals. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921). 2842\u20132861."},{"key":"e_1_3_3_20_2","series-title":"LIPIcs","first-page":"13:1\u201313:22","volume-title":"13th Innovations in Theoretical Computer Science Conference (ITCS\u201922)","volume":"215","author":"Bansal Nikhil","year":"2022","unstructured":"Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. 2022. Prefix discrepancy, smoothed analysis, and combinatorial vector balancing. In 13th Innovations in Theoretical Computer Science Conference (ITCS\u201922)(LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 13:1\u201313:22."},{"key":"e_1_3_3_21_2","series-title":"LIPIcs","first-page":"14:1\u201314:12","volume-title":"49th International Colloquium on Automata, Languages, and Programming (ICALP\u201922)","author":"Bansal Nikhil","year":"2022","unstructured":"Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. 2022. Smoothed analysis of the Koml\u00f3s conjecture. In 49th International Colloquium on Automata, Languages, and Programming (ICALP\u201922)(LIPIcs, Vol. 229). 14:1\u201314:12."},{"key":"e_1_3_3_22_2","first-page":"1139","volume-title":"Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC\u201920)","author":"Bansal Nikhil","year":"2020","unstructured":"Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha. 2020. Online vector balancing and geometric discrepancy. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC\u201920). 1139\u20131152."},{"issue":"4","key":"e_1_3_3_23_2","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1002\/rsa.20955","article-title":"On-line balancing of random inputs","volume":"57","author":"Bansal Nikhil","year":"2020","unstructured":"Nikhil Bansal and Joel H. Spencer. 2020. On-line balancing of random inputs. Random Struct. Algorithms 57, 4 (2020), 879\u2013891.","journal-title":"Random Struct. Algorithms"},{"key":"e_1_3_3_24_2","volume-title":"Proceedings of the 22nd Annual Conference on Learning Theory (COLT\u201909)","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 Annual Conference on Learning Theory (COLT\u201909)."},{"key":"e_1_3_3_25_2","first-page":"582","volume-title":"Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS\u201919)","author":"Bhaskara Aditya","year":"2019","unstructured":"Aditya Bhaskara, Aidao Chen, Aidan Perreault, and Aravindan Vijayaraghavan. 2019. Smoothed analysis in unsupervised learning via decoupling. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS\u201919). 582\u2013610."},{"issue":"5","key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1017\/S0963548312000193","article-title":"Are stable instances easy?","volume":"21","author":"Bilu Yonatan","year":"2012","unstructured":"Yonatan Bilu and Nathan Linial. 2012. Are stable instances easy? Combinatorics, Probability and Computing 21, 5 (2012), 643\u2013660.","journal-title":"Combinatorics, Probability and Computing"},{"key":"e_1_3_3_27_2","first-page":"1716","volume-title":"Conference on Learning Theory (COLT\u201922)","volume":"178","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 Conference on Learning Theory (COLT\u201922), Vol. 178. PMLR, 1716\u20131786."},{"key":"e_1_3_3_28_2","first-page":"228","volume-title":"Conference on Learning Theory (COLT\u201923)","volume":"195","author":"Block Adam","year":"2023","unstructured":"Adam Block and Yury Polyanskiy. 2023. The sample complexity of approximate rejection sampling with applications to smoothed online learning. In Conference on Learning Theory (COLT\u201923), Vol. 195. PMLR, 228\u2013273."},{"key":"e_1_3_3_29_2","first-page":"7477","volume-title":"Advances in Neural Information Processing Systems (NeurIPS\u201922)","author":"Block Adam","year":"2022","unstructured":"Adam Block and Max Simchowitz. 2022. Efficient and near-optimal smoothed online learning for generalized linear functions. In Advances in Neural Information Processing Systems (NeurIPS\u201922). 36, 7477\u20137489."},{"key":"e_1_3_3_30_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1017\/CBO9780511800481.006","volume-title":"Algorithmic Game Theory","author":"Blum Avrim","year":"2007","unstructured":"Avrim Blum and Yishay Mansour. 2007. Learning, regret minimization, and equilibria. In Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Editors Vazirani (Eds.). Cambridge University Press, 79\u2013102."},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001","volume-title":"Concentration Inequalities: A Nonasymptotic Theory of Independence","author":"Boucheron St\u00e9phane","year":"2013","unstructured":"St\u00e9phane Boucheron, G\u00e1bor Lugosi, and Pascal Massart. 2013. Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford. 2012277339"},{"key":"e_1_3_3_32_2","first-page":"169","volume-title":"Summer School on Machine Learning","author":"Bousquet Olivier","year":"2003","unstructured":"Olivier Bousquet, St\u00e9phane Boucheron, and G\u00e1bor Lugosi. 2003. Introduction to statistical learning theory. In Summer School on Machine Learning. Springer, 169\u2013207."},{"key":"e_1_3_3_33_2","first-page":"389","volume-title":"Proceeding of the 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920)","author":"Bun Mark","year":"2020","unstructured":"Mark Bun, Roi Livni, and Shay Moran. 2020. An equivalence between private classification and online prediction. In Proceeding of the 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920). 389\u2013402."},{"key":"e_1_3_3_34_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546921","volume-title":"Prediction, Learning, and Games","author":"Cesa-Bianchi Nicol\u00f2","year":"2006","unstructured":"Nicol\u00f2 Cesa-Bianchi and G\u00e1bor Lugosi. 2006. Prediction, Learning, and Games. Cambridge University Press."},{"key":"e_1_3_3_35_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"Chazelle Bernard","year":"2000","unstructured":"Bernard Chazelle. 2000. The Discrepancy Method: Randomness and Complexity. Cambridge University Press."},{"key":"e_1_3_3_36_2","first-page":"412","volume-title":"Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS\u201917)","author":"Cohen-Addad Vincent","year":"2017","unstructured":"Vincent Cohen-Addad and Varun Kanade. 2017. Online optimization of smoothed piecewise constant functions. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS\u201917). 412\u2013420."},{"key":"e_1_3_3_37_2","first-page":"5299","volume-title":"Advances in Neural Information Processing Systems (NeurIPS\u201917)","author":"Dekel Ofer","year":"2017","unstructured":"Ofer Dekel, Arthur Flajolet, Nika Haghtalab, and Patrick Jaillet. 2017. Online learning with a hint. In Advances in Neural Information Processing Systems (NeurIPS\u201917). 30, 5299\u20135308."},{"key":"e_1_3_3_38_2","first-page":"4749","volume-title":"Advances in Neural Information Processing Systems (NeurIPS\u201919)","author":"Diakonikolas Ilias","year":"2019","unstructured":"Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. 2019. Distribution-independent PAC learning of halfspaces with Massart noise. In Advances in Neural Information Processing Systems (NeurIPS\u201919). 32, 4749\u20134760."},{"issue":"3","key":"e_1_3_3_39_2","doi-asserted-by":"crossref","first-page":"992","DOI":"10.1137\/15M1050276","article-title":"A PAC approach to application-specific algorithm selection","volume":"46","author":"Gupta Rishi","year":"2017","unstructured":"Rishi Gupta and Tim Roughgarden. 2017. A PAC approach to application-specific algorithm selection. SIAM J. Comput. 46, 3 (2017), 992\u20131017.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_3_40_2","volume-title":"Foundation of Machine Learning, by the People, for the People","author":"Haghtalab Nika","year":"2018","unstructured":"Nika Haghtalab. 2018. Foundation of Machine Learning, by the People, for the People. Ph. D. Dissertation. Carnegie Mellon University."},{"key":"e_1_3_3_41_2","first-page":"4072","volume-title":"Advances in Neural Information Processing Systems (NeurIPS\u201922)","author":"Haghtalab Nika","year":"2022","unstructured":"Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. 2022. Oracle-efficient online learning for beyond worst-case adversaries. In Advances in Neural Information Processing Systems (NeurIPS\u201922). 36, 4072\u20134084."},{"key":"e_1_3_3_42_2","first-page":"9203","volume-title":"Advances in Neural Information Processing Systems (NeurIPS\u201920)","author":"Haghtalab Nika","year":"2020","unstructured":"Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. 2020. Smoothed analysis of online and differentially private learning. In Advances in Neural Information Processing Systems (NeurIPS\u201920). 34, 9203\u20139215."},{"key":"e_1_3_3_43_2","first-page":"942","volume-title":"Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS\u201921)","author":"Haghtalab Nika","year":"2021","unstructured":"Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. 2021. Smoothed analysis with adaptive adversaries. In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS\u201921). 942\u2013953."},{"key":"e_1_3_3_44_2","article-title":"Smoothed analysis with adaptive adversaries","volume":"2102","author":"Haghtalab Nika","year":"2021","unstructured":"Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. 2021. Smoothed analysis with adaptive adversaries. CoRR abs\/2102.08446 (2021).","journal-title":"CoRR"},{"key":"e_1_3_3_45_2","first-page":"2348","volume-title":"Advances in Neural Information Processing Systems (NeuRIPS\u201912)","author":"Hardt Moritz","year":"2012","unstructured":"Moritz Hardt, Katrina Ligett, and Frank McSherry. 2012. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems (NeuRIPS\u201912). 25, 2348\u20132356."},{"key":"e_1_3_3_46_2","first-page":"331","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC\u201913)","author":"Hardt Moritz","year":"2013","unstructured":"Moritz Hardt and Aaron Roth. 2013. Beyond worst-case analysis in private singular vector computation. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC\u201913). 331\u2013340."},{"key":"e_1_3_3_47_2","first-page":"61","volume-title":"Proceeding of the 51st Annual Symposium on Foundations of Computer Science (FOCS\u201910)","author":"Hardt Moritz","year":"2010","unstructured":"Moritz Hardt and Guy N. Rothblum. 2010. A multiplicative weights mechanism for privacy-preserving data analysis. In Proceeding of the 51st Annual Symposium on Foundations of Computer Science (FOCS\u201910). 61\u201370."},{"key":"e_1_3_3_48_2","article-title":"Balancing covariates in randomized experiments using the Gram-Schmidt walk","volume":"1911","author":"Harshaw Christopher","year":"2019","unstructured":"Christopher Harshaw, Fredrik S\u00e4vje, Daniel A. Spielman, and Peng Zhang. 2019. Balancing covariates in randomized experiments using the Gram-Schmidt walk. CoRR abs\/1911.03071 (2019). arxiv:1911.03071","journal-title":"CoRR"},{"issue":"2","key":"e_1_3_3_49_2","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0097-3165(95)90052-7","article-title":"Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension","volume":"69","author":"Haussler David","year":"1995","unstructured":"David Haussler. 1995. Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension. Journal of Combinatorial Theory, Series A 69, 2 (1995), 217\u2013232.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"e_1_3_3_50_2","first-page":"128","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC\u201916)","author":"Hazan Elad","year":"2016","unstructured":"Elad Hazan and Tomer Koren. 2016. The computational power of optimization in online learning. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC\u201916). 128\u2013141."},{"key":"e_1_3_3_51_2","first-page":"11902","volume-title":"Advances in Neural Information Processing Systems (NeuRIPS\u201920)","author":"Hopkins Samuel B.","year":"2020","unstructured":"Samuel B. Hopkins, Jerry Li, and Fred Zhang. 2020. Robust and heavy-tailed mean estimation made simple, via regret minimization. In Advances in Neural Information Processing Systems (NeuRIPS\u201920). 30, 11902\u201311912."},{"key":"e_1_3_3_52_2","volume-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC\u201924)","author":"Kulkarni Victor Reis Janardhan","year":"2024","unstructured":"Victor Reis Janardhan Kulkarni and Thomas Rothvoss. 2024. Optimal online discrepancy minimization. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC\u201924)."},{"key":"e_1_3_3_53_2","article-title":"Online geometric discrepancy for stochastic arrivals with applications to envy minimization","volume":"1910","author":"Jiang Haotian","year":"2019","unstructured":"Haotian Jiang, Janardhan Kulkarni, and Sahil Singla. 2019. Online geometric discrepancy for stochastic arrivals with applications to envy minimization. CoRR abs\/1910.01073 (2019). arxiv:1910.01073","journal-title":"CoRR"},{"key":"e_1_3_3_54_2","first-page":"395","volume-title":"Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS\u201909)","author":"Kalai Adam Tauman","year":"2009","unstructured":"Adam Tauman Kalai, Alex Samorodnitsky, and Shang-Hua Teng. 2009. Learning and smoothed analysis. In Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS\u201909). 395\u2013404."},{"key":"e_1_3_3_55_2","article-title":"Decision trees are PAC-learnable from most product distributions: A smoothed analysis","volume":"0812","author":"Kalai Adam Tauman","year":"2008","unstructured":"Adam Tauman Kalai and Shang-Hua Teng. 2008. Decision trees are PAC-learnable from most product distributions: A smoothed analysis. CoRR abs\/0812.0933 (2008). arxiv:0812.0933","journal-title":"CoRR"},{"key":"e_1_3_3_56_2","first-page":"2227","volume-title":"Advances in Neural Information Processing Systems (NeurIPS\u201918)","author":"Kannan Sampath","year":"2018","unstructured":"Sampath Kannan, Jamie H. Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. 2018. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Advances in Neural Information Processing Systems (NeurIPS\u201918). 31, 2227\u20132236."},{"issue":"3","key":"e_1_3_3_57_2","first-page":"159","article-title":"How good is the simplex algorithm","volume":"3","author":"Klee Victor","year":"1972","unstructured":"Victor Klee and George J. Minty. 1972. How good is the simplex algorithm. Inequalities 3, 3 (1972), 159\u2013175.","journal-title":"Inequalities"},{"key":"e_1_3_3_58_2","first-page":"65:1\u201365:50","article-title":"Active learning for cost-sensitive classification","volume":"20","author":"Krishnamurthy Akshay","year":"2019","unstructured":"Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daum\u00e9 III, and John Langford. 2019. Active learning for cost-sensitive classification. J. Mach. Learn. Res. 20 (2019), 65:1\u201365:50.","journal-title":"J. Mach. Learn. Res."},{"issue":"5","key":"e_1_3_3_59_2","doi-asserted-by":"crossref","first-page":"1573","DOI":"10.1137\/130929400","article-title":"Constructive discrepancy minimization by walking on the edges","volume":"44","author":"Lovett Shachar","year":"2015","unstructured":"Shachar Lovett and Raghu Meka. 2015. Constructive discrepancy minimization by walking on the edges. SIAM J. Comput. 44, 5 (2015), 1573\u20131582.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_3_60_2","first-page":"890","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Makarychev Konstantin","year":"2014","unstructured":"Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. 2014. Bilu\u2013Linial stable instances of max cut and minimum multiway cut. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914). 890\u2013906."},{"key":"e_1_3_3_61_2","first-page":"285","volume-title":"Smoothed Analysis of Local Search","author":"Manthey Bodo","year":"2021","unstructured":"Bodo Manthey. 2021. Smoothed Analysis of Local Search. Cambridge University Press, 285\u2013308."},{"issue":"6","key":"e_1_3_3_62_2","first-page":"28","article-title":"The effectiveness of Lloyd-type methods for the k-means problem","volume":"59","author":"Ostrovsky Rafail","year":"2013","unstructured":"Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy. 2013. The effectiveness of Lloyd-type methods for the k-means problem. J. ACM 59, 6, Article 28 (2013).","journal-title":"J. ACM"},{"key":"e_1_3_3_63_2","first-page":"1724","volume-title":"Proceedings of the 31st Conference On Learning Theory (COLT\u201918)","author":"Raghavan Manish","year":"2018","unstructured":"Manish Raghavan, Aleksandrs Slivkins, Jennifer Vaughan Wortman, and Zhiwei Steven Wu. 2018. The externalities of exploration and how data diversity helps exploitation. In Proceedings of the 31st Conference On Learning Theory (COLT\u201918). 1724\u20131738."},{"key":"e_1_3_3_64_2","first-page":"3066","volume-title":"Advances in Neural Information Processing Systems (NeurIPS\u201913)","author":"Rakhlin Alexander","year":"2013","unstructured":"Alexander Rakhlin and Karthik Sridharan. 2013. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems (NeurIPS\u201913). 26, 3066\u20133074."},{"key":"e_1_3_3_65_2","first-page":"1764","volume-title":"Advances in Neural Information Processing Systems (NeurIPS\u201911)","author":"Rakhlin Alexander","year":"2011","unstructured":"Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. 2011. Online learning: Stochastic, constrained, and smoothed adversaries. In Advances in Neural Information Processing Systems (NeurIPS\u201911). 24, 1764\u20131772."},{"issue":"1","key":"e_1_3_3_66_2","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/141000282","article-title":"Constructive discrepancy minimization for convex sets","volume":"46","author":"Rothvoss Thomas","year":"2017","unstructured":"Thomas Rothvoss. 2017. Constructive discrepancy minimization for convex sets. SIAM J. Comput. 46, 1 (2017), 224\u2013234.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_3_67_2","doi-asserted-by":"crossref","DOI":"10.1017\/9781108637435","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"Roughgarden Tim","year":"2020","unstructured":"Tim Roughgarden. 2020. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press."},{"issue":"1","key":"e_1_3_3_68_2","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/0220004","article-title":"Simple local search problems that are hard to solve","volume":"20","author":"Sch\u00e4ffer Alejandro A.","year":"1991","unstructured":"Alejandro A. Sch\u00e4ffer. 1991. Simple local search problems that are hard to solve. SIAM Journal on Computing 20, 1 (1991), 56\u201387.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_69_2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970074","volume-title":"Ten Lectures on the Probabilistic Method (2nd edition)","author":"Spencer Joel","year":"1994","unstructured":"Joel Spencer. 1994. Ten Lectures on the Probabilistic Method (2nd edition). Society for Industrial and Applied Mathematics."},{"issue":"3","key":"e_1_3_3_70_2","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","article-title":"Smoothed analysis: Why the simplex algorithm usually takes polynomial time","volume":"51","author":"Spielman Daniel A.","year":"2004","unstructured":"Daniel A. Spielman and Shang-Hua Teng. 2004. Smoothed analysis: Why the simplex algorithm usually takes polynomial time. J. ACM 51, 3 (2004), 385\u2013463.","journal-title":"J. ACM"},{"key":"e_1_3_3_71_2","first-page":"6500","volume-title":"Advances in Neural Information Processing Systems (NeurIPS\u201917)","author":"Vijayaraghavan Aravindan","year":"2017","unstructured":"Aravindan Vijayaraghavan, Abhratanu Dutta, and Alex Wang. 2017. Clustering stable instances of Euclidean k-means. In Advances in Neural Information Processing Systems (NeurIPS\u201917). 30, 6500\u20136509."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656638","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:57:31Z","timestamp":1750291051000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,11]]},"references-count":70,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3656638"],"URL":"https:\/\/doi.org\/10.1145\/3656638","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,11]]},"assertion":[{"value":"2022-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}