# Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 55 references that are in the map.
- First posted on arXiv 25 May 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (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)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [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 for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [Majorizing Measures, Sequential Complexities, and Online Learning](https://mlsanity.com/paper/2102.01729/) (2021)

## Built on by (most cited first, 10 of 10)

- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregression](https://mlsanity.com/paper/2310.11428/) (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)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023)
- [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)
- [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)

Due to the drastic gap in complexity between sequential and batch statistical learning, recent work has studied a smoothed sequential learning setting, where Nature is constrained to select contexts with density bounded by 1/σ with respect to a known measure μ. Unfortunately, for some function classes, there is an exponential gap between the statistically optimal regret and that which can be achieved efficiently. In this paper, we give a computationally efficient algorithm that is the first to enjoy the statistically optimal log(T/σ) regret for realizable K-wise linear classification. We extend our results to settings where the true classifier is linear in an over-parameterized polynomial featurization of the contexts, as well as to a realizable piecewise-regression setting assuming access to an appropriate ERM oracle. Somewhat surprisingly, standard disagreement-based analyses are insufficient to achieve regret logarithmic in 1/σ. Instead, we develop a novel characterization of the geometry of the disagreement region induced by generalized linear classifiers. Along the way, we develop numerous technical tools of independent interest, including a general anti-concentration bound for the determinant of certain matrix averages.