# Smoothed Online Learning is as Easy as Statistical Learning

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

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 77 references that are in the map.
- First posted on arXiv 9 Feb 2022.

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

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Online Linear Optimization via Smoothing](https://mlsanity.com/paper/1405.6076/) (2014)
- [Learning in Non-convex Games with an Optimization Oracle](https://mlsanity.com/paper/1810.07362/) (2018)
- [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013)
- [Majorizing Measures, Sequential Complexities, and Online Learning](https://mlsanity.com/paper/2102.01729/) (2021)
- [A Chaining Algorithm for Online Nonparametric Regression](https://mlsanity.com/paper/1502.07697/) (2015)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Online Nonparametric Regression with General Loss Functions](https://mlsanity.com/paper/1501.06598/) (2015)
- [Prediction by Random-Walk Perturbation](https://mlsanity.com/paper/1302.5797/) (2013)

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

- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback](https://mlsanity.com/paper/2205.13451/) (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)
- [Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits](https://mlsanity.com/paper/2306.07923/) (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)
- [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)
- [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)
- [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)
- [On Efficient Online Imitation Learning via Classification](https://mlsanity.com/paper/2209.12868/) (2022)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (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)
- [Quantum Learning Theory Beyond Batch Binary Classification](https://mlsanity.com/paper/2302.07409/) (2023)
- [Smooth Nash Equilibria: Algorithms and Complexity](https://mlsanity.com/paper/2309.12226/) (2023)
- [Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?](https://mlsanity.com/paper/2406.11667/) (2024)

## Abstract (arXiv)

Much of modern learning theory has been split between two regimes: the classical offline setting, where data arrive independently, and the online setting, where data arrive adversarially. While the former model is often both computationally and statistically tractable, the latter requires no distributional assumptions. In an attempt to achieve the best of both worlds, previous work proposed the smooth online setting where each sample is drawn from an adversarially chosen distribution, which is smooth, i.e., it has a bounded density with respect to a fixed dominating measure. We provide tight bounds on the minimax regret of learning a nonparametric function class, with nearly optimal dependence on both the horizon and smoothness parameters. Furthermore, we provide the first oracle-efficient, no-regret algorithms in this setting. In particular, we propose an oracle-efficient improper algorithm whose regret achieves optimal dependence on the horizon and a proper algorithm requiring only a single oracle call per round whose regret has the optimal horizon dependence in the classification setting and is sublinear in general. Both algorithms have exponentially worse dependence on the smoothness parameter of the adversary than the minimax rate. We then prove a lower bound on the oracle complexity of any proper learning algorithm, which matches the oracle-efficient upper bounds up to a polynomial factor, thus demonstrating the existence of a statistical-computational gap in smooth online learning. Finally, we apply our results to the contextual bandit setting to show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits in the case that contexts arrive in a smooth manner.