mlsanityData to 7 Oct 2026

Smoothed Analysis with Adaptive Adversaries

arXiv 2102.08446 ↗First posted 16 Feb 2021cs.LG cs.DS stat.MLcited by 57

Not on the map. Why?

Abstract (arXiv)

We prove novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time an adversary chooses an input distribution with density function bounded above by tfrac1σ times that of the uniform distribution; nature then samples an input from this distribution. Crucially, our results hold for em adaptive adversaries that can choose an input distribution based on the decisions of the algorithm and the realizations of the inputs in the previous time steps. This paper presents a general technique for proving smoothed algorithmic guarantees against adaptive adversaries, in effect reducing the setting of adaptive adversaries to the simpler case of oblivious adversaries. We apply this technique to prove strong smoothed guarantees for three problems: -Online learning: We consider the online prediction problem, where instances are generated from an adaptive sequence of σ-smooth distributions and the hypothesis class has VC dimension d. We bound the regret by tildeObig(√T dln(1/σ) + d√ln(T/σ)big). This answers open questions of [RST11,Hag18]. -Online discrepancy minimization: We consider the online Koml'os problem, where the input is generated from an adaptive sequence of σ-smooth and isotropic distributions on the ℓ2 unit ball. We bound the ℓ_∞ norm of the discrepancy vector by tildeObig(ln2!big( fracnTσbig) big). -Dispersion in online optimization: We consider online optimization of piecewise Lipschitz functions where functions with ℓ discontinuities are chosen by a smoothed adaptive adversary and show that the resulting sequence is big( σ/√Tℓ, tilde Obig(√Tℓ big)big)-dispersed. This matches the parameters of [BDV18] for oblivious adversaries, up to log factors.

Key facts. Cited by 57 papers in the map (data through 7 Oct 2026). Builds on 29 of its 73 references that are in the map. First posted on arXiv 16 Feb 2021.

Builds on

29 of 73 references.

References · 29

  1. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  2. 2020An Equivalence Between Private Classification and Online Predictioncited by 63
  3. 2015A PAC Approach to Application-Specific Algorithm Selectioncited by 57
  4. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  5. 2020Smoothed Analysis of Online and Differentially Private Learningcited by 47
  6. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  7. 2017Active Learning for Cost-Sensitive Classificationcited by 40
  8. 2021Adversarial Laws of Large Numbers and Optimal Regret in Online Classificationcited by 39
  9. 2015The Computational Power of Optimization in Online Learningcited by 38
  10. 2017Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimizationcited by 37
  11. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  12. 2020Discrepancy Minimization via a Self-Balancing Walkcited by 22
17 more
  1. 2018The Externalities of Exploration and How Data Diversity Helps Exploitationcited by 19
  2. 2015Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updatescited by 14
  3. 2017The Gram-Schmidt Walk: A Cure for the Banaszczyk Bluescited by 9
  4. 2018Smoothed Analysis in Unsupervised Learning via Decouplingcited by 9
  5. 2019On-Line Balancing of Random Inputscited by 9
  6. 2019Online Vector Balancing and Geometric Discrepancycited by 9
  7. 2017Efficient PAC Learning from the Crowdcited by 7
  8. 2019Boosting for Control of Dynamical Systemscited by 7
  9. 2014Constructive discrepancy minimization for convex setscited by 6
  10. 2015k-center Clustering under Perturbation Resiliencecited by 6
  11. 2016Online Optimization of Smoothed Piecewise Constant Functionscited by 6
  12. 2020Online Discrepancy Minimization for Stochastic Arrivalscited by 5
  13. 2013Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cutcited by 4
  14. 2016Algorithmic Discrepancy Beyond Partial Coloringcited by 4
  15. 2017Clustering Stable Instances of Euclidean k-meanscited by 2
  16. 2018A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problemcited by 2
  17. 2019Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimizationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 9; 2023: 15; 2024: 12; 2025: 8; 2026: 12.

57 papers.

Sort:

By area:

  1. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  2. 2022Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothnesscited by 21
  3. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 19
  4. 2022Online Prediction in Sub-linear Spacecited by 16
  5. 2023Repeated Bilateral Trade Against a Smoothed Adversarycited by 15
  6. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  7. 2023The Role of Transparency in Repeated First-Price Auctions with Unknown Valuationscited by 15
  8. 2023The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learningcited by 13
  9. 2024On the Performance of Empirical Risk Minimization with Smoothed Datacited by 13
  10. 2021On the power of adaptivity in statistical adversariescited by 12
  11. 2022Expected Worst Case Regret via Stochastic Sequential Coveringcited by 12
  12. 2023Adversarial Resilience in Sequential Prediction via Abstentioncited by 11
38 more
  1. 2022Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functionscited by 10
  2. 2022Beyond IID: data-driven decision-making in heterogeneous environmentscited by 9
  3. 2023Smoothed Online Learning for Prediction in Piecewise Affine Systemscited by 9
  4. 2022Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classescited by 8
  5. 2023Online Learning in Dynamically Changing Environmentscited by 8
  6. 2024Group-wise oracle-efficient algorithms for online multi-group learningcited by 8
  7. 2022Adaptive Oracle-Efficient Online Learningcited by 7
  8. 2023Accelerated Rates between Stochastic and Adversarial Online Convex Optimizationcited by 7
  9. 2023Smoothed Analysis of Sequential Probability Assignmentcited by 7
  10. 2025Nearly Tight Regret Bounds for Profit Maximization in Bilateral Tradecited by 7
  11. 2023Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Makingcited by 5
  12. 2024Oracle-Efficient Differentially Private Learning with Public Datacited by 5
  13. 2024Selling Joint Ads: A Regret Minimization Perspectivecited by 5
  14. 2024Avoiding Catastrophe in Online Learning by Asking for Helpcited by 4
  15. 2024Prospective Learning: Learning for a Dynamic Futurecited by 4
  16. 2024Market Making without Regretcited by 4
  17. 2026Learning with Monotone Adversarial Corruptionscited by 4
  18. 2023Smooth Nash Equilibria: Algorithms and Complexitycited by 3
  19. 2023Learning Thresholds with Latent Values and Censored Feedbackcited by 3
  20. 2024Oracle-Efficient Hybrid Online Learning with Unknown Distributioncited by 3
  21. 2023Time-uniform confidence bands for the CDF under nonstationaritycited by 2
  22. 2024MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximationcited by 2
  23. 2024No Free Lunch: Fundamental Limits of Learning Non-Hallucinating Generative Modelscited by 2
  24. 2025Learning in Structured Stackelberg Gamescited by 2
  25. 2025Smoothed Analysis of Learning from Positive Samplescited by 2
  26. 2025Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarkscited by 2
  27. 2025Learning Juntas under Markov Random Fieldscited by 2
  28. 2026Oracle-efficient Hybrid Learning with Constrained Adversariescited by 2
  29. 2025Online Learning of Pure States is as Hard as Mixed Statescited by 1
  30. 2025Safe Learning Under Irreversible Dynamics via Asking for Helpcited by 1
  31. 2025Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learningcited by 1
  32. 2026Distribution-Free Sequential Prediction with Abstentionscited by 1
  33. 2026Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothnesscited by 1
  34. 2026Self-Normalized Martingales and Uniform Regret Bounds for Linear Regressioncited by 1
  35. 2026Profit Maximization in Bilateral Trade against a Smooth Adversarycited by 1
  36. 2026Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputscited by 1
  37. 2023Online nearest neighbor classificationcited by 0
  38. 2023Agnostic Interactive Imitation Learning: New Theory and Practical Algorithmscited by 0

50 most cited of 57 All 57 (JSON)