# Smoothed Analysis with Adaptive Adversaries

arXiv: https://arxiv.org/abs/2102.08446 · HTML: https://mlsanity.com/paper/2102.08446/

## Key facts

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

## Builds on (most cited first, 29 of 29)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Active Learning for Cost-Sensitive Classification](https://mlsanity.com/paper/1703.01014/) (2017)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Discrepancy Minimization via a Self-Balancing Walk](https://mlsanity.com/paper/2006.14009/) (2020)
- [The Externalities of Exploration and How Data Diversity Helps Exploitation](https://mlsanity.com/paper/1806.00543/) (2018)
- [Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates](https://mlsanity.com/paper/1506.04838/) (2015)
- [The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues](https://mlsanity.com/paper/1708.01079/) (2017)
- [Smoothed Analysis in Unsupervised Learning via Decoupling](https://mlsanity.com/paper/1811.12361/) (2018)
- [On-Line Balancing of Random Inputs](https://mlsanity.com/paper/1903.06898/) (2019)
- [Online Vector Balancing and Geometric Discrepancy](https://mlsanity.com/paper/1912.03350/) (2019)
- [Efficient PAC Learning from the Crowd](https://mlsanity.com/paper/1703.07432/) (2017)
- [Boosting for Control of Dynamical Systems](https://mlsanity.com/paper/1906.08720/) (2019)
- [Constructive discrepancy minimization for convex sets](https://mlsanity.com/paper/1404.0339/) (2014)
- [k-center Clustering under Perturbation Resilience](https://mlsanity.com/paper/1505.03924/) (2015)
- [Online Optimization of Smoothed Piecewise Constant Functions](https://mlsanity.com/paper/1604.01999/) (2016)
- [Online Discrepancy Minimization for Stochastic Arrivals](https://mlsanity.com/paper/2007.10622/) (2020)
- [Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut](https://mlsanity.com/paper/1305.1681/) (2013)
- [Algorithmic Discrepancy Beyond Partial Coloring](https://mlsanity.com/paper/1611.01805/) (2016)
- [Clustering Stable Instances of Euclidean k-means](https://mlsanity.com/paper/1712.01241/) (2017)
- [A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem](https://mlsanity.com/paper/1801.03423/) (2018)
- [Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization](https://mlsanity.com/paper/1910.01073/) (2019)

## Built on by (most cited first, 30 of 57)

- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2302.04658/) (2023)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [On the power of adaptivity in statistical adversaries](https://mlsanity.com/paper/2111.10352/) (2021)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions](https://mlsanity.com/paper/2205.13056/) (2022)
- [Beyond IID: data-driven decision-making in heterogeneous environments](https://mlsanity.com/paper/2206.09642/) (2022)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [Group-wise oracle-efficient algorithms for online multi-group learning](https://mlsanity.com/paper/2406.05287/) (2024)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [Online Learning in Dynamically Changing Environments](https://mlsanity.com/paper/2302.00103/) (2023)
- [Adaptive Oracle-Efficient Online Learning](https://mlsanity.com/paper/2210.09385/) (2022)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [Market Making without Regret](https://mlsanity.com/paper/2411.13993/) (2024)
- [Oracle-Efficient Hybrid Online Learning with Unknown Distribution](https://mlsanity.com/paper/2401.15520/) (2024)
- [Avoiding Catastrophe in Online Learning by Asking for Help](https://mlsanity.com/paper/2402.08062/) (2024)
- [Prospective Learning: Learning for a Dynamic Future](https://mlsanity.com/paper/2411.00109/) (2024)
- [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026)

## 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.