# On the Performance of Empirical Risk Minimization with Smoothed Data arXiv: https://arxiv.org/abs/2402.14987 · HTML: https://mlsanity.com/paper/2402.14987/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 25 of its 58 references that are in the map. - First posted on arXiv 22 Feb 2024. ## Builds on (most cited first, 25 of 25) - [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) - [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018) - [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022) - [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) - [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021) - [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022) - [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014) - [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) - [Learning with Square Loss: Localization through Offset Rademacher Complexity](https://mlsanity.com/paper/1502.06134/) (2015) - [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022) - [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023) - [Learning from many trajectories](https://mlsanity.com/paper/2203.17193/) (2022) - [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013) - [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022) - [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023) - [The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2302.04658/) (2023) - [Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions](https://mlsanity.com/paper/2205.13056/) (2022) - [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023) - [Online Learning in Dynamically Changing Environments](https://mlsanity.com/paper/2302.00103/) (2023) - [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023) - [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023) - [Universal coding, intrinsic volumes, and metric complexity](https://mlsanity.com/paper/2303.07279/) (2023) ## Built on by (most cited first, 13 of 13) - [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) - [Smoothed Analysis of Learning from Positive Samples](https://mlsanity.com/paper/2504.10428/) (2025) - [Provably Learning from Modern Language Models via Low Logit Rank](https://mlsanity.com/paper/2512.09892/) (2025) - [Oracle-efficient Hybrid Learning with Constrained Adversaries](https://mlsanity.com/paper/2603.04546/) (2026) - [Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs](https://mlsanity.com/paper/2609.33760/) (2026) - [Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks](https://mlsanity.com/paper/2504.10598/) (2025) - [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025) - [Distribution-Free Sequential Prediction with Abstentions](https://mlsanity.com/paper/2602.17918/) (2026) - [Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness](https://mlsanity.com/paper/2602.20585/) (2026) - [Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning](https://mlsanity.com/paper/2605.07155/) (2026) - [Profit Maximization in Bilateral Trade against a Smooth Adversary](https://mlsanity.com/paper/2605.12664/) (2026) - [Agnostic Smoothed Online Regression with Adversarial Responses](https://mlsanity.com/paper/2609.32478/) (2026) ## Abstract (arXiv) In order to circumvent statistical and computational hardness results in sequential decision-making, recent work has considered smoothed online learning, where the distribution of data at each time is assumed to have bounded likeliehood ratio with respect to a base measure when conditioned on the history. While previous works have demonstrated the benefits of smoothness, they have either assumed that the base measure is known to the learner or have presented computationally inefficient algorithms applying only in special cases. This work investigates the more general setting where the base measure is unknown to the learner, focusing in particular on the performance of Empirical Risk Minimization (ERM) with square loss when the data are well-specified and smooth. We show that in this setting, ERM is able to achieve sublinear error whenever a class is learnable with iid data; in particular, ERM achieves error scaling as tilde O( √comp(mathcal F)· T ), where comp(mathcal F) is the statistical complexity of learning mathcal F with iid data. In so doing, we prove a novel norm comparison bound for smoothed data that comprises the first sharp norm comparison for dependent data applying to arbitrary, nonlinear function classes. We complement these results with a lower bound indicating that our analysis of ERM is essentially tight, establishing a separation in the performance of ERM between smoothed and iid data.