Paper Overview
Field: ML Authors: Sasha Voitovych, Adam Block, Alexander Rakhlin, Abhishek Shetty Published: 2026-10-07 arXiv: 2610.10499
Abstract
Online learning is an attractive framework in many domains because it permits well-defined learning even when data are dependent or chosen adversarially. This generality, however, comes at a steep price, introducing significant statistical and computational barriers. Recently, smoothed online learning has emerged as a promising framework that interpolates between the fully adversarial and fully stochastic settings by assuming that the conditional law of each covariate has density at most \(1/σ\) with respect to some fixed base measure \(μ\), and it is known to match the statistical and computational guarantees of classical learning while still allowing for much of the flexibility of online learning.
However, existing oracle-efficient algorithms require either (i) sampling access to the base measure μ or (ii) labels perfectly predicted by a fixed hypothesis. Both assumptions limit applicability—in contrast, empirical risk minimization (ERM) in statistical learning learns efficiently in the agnostic setting without any knowledge of the data distribution. This paper shows that neither assumption is necessary, giving the first oracle-efficient algorithm achieving sublinear regret in the agnostic setting with no knowledge of μ.
Key Results
- The algorithm is based on Gaussian Follow-The-Perturbed-Leader and is parameter-free: it requires no knowledge of the base measure μ, the smoothing parameter σ, or the time horizon T.
- For a binary hypothesis class of VC dimension d, it achieves regret Õ(d√(T/σ)) using a single ERM oracle call per round.
- This regret bound is optimal up to a √d factor.
- Along the way, the authors introduce several new techniques that may be of independent interest.
Original Abstract
Online learning is an attractive framework in many domains because it permits well-defined learning even when data are dependent or chosen adversarially. This generality, however, comes at a steep price, introducing significant statistical and computational barriers. Recently, smoothed online learning has emerged as a promising framework that interpolates between the fully adversarial and fully stochastic settings by assuming that the conditional law of each covariate has density at most \(1/σ\) with respect to some fixed base measure \(μ\), and it is known to match the statistical and computational guarantees of classical learning while still allowing for much of the flexibility of online learning. However, existing oracle-efficient algorithms require either (i) sampling access to the base me... *(truncated)*