Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning

Classical online learning deals with scenarios where data arrive sequentially and decisions must be made in an online fashion, often under adversarial conditions, and is attractive due to its robustness relative to more classical learning that relies on assuming independence. Unfortunately, due to the minimal assumptions it makes about the data-generating process, it often suffers from poor statistical and computational efficiency. Recently, smoothed online learning has emerged as a promising framework that interpolates between the fully adversarial and fully stochastic settings, making the assumption that the conditional law of each covariate has a density at most $1/\sigma$ with respect to some fixed base measure $\mu$. Prior work has investigated this setting either under the assumption that $\mu$ is known to the learner or under the assumption that the labels are perfectly predicted by a fixed hypothesis; in both cases, smoothed online learning admits statistically and computationally efficient algorithms. Recent work has demonstrated that even absent these conditions, smoothed online learning with unknown $\mu$ can be statistically efficient, but the algorithm studied was computationally intractable, leaving open the key question of whether it is possible to achieve both statistical and computational efficiency simultaneously when $\mu$ is unknown. In this work we resolve this question by giving the first oracle-efficient algorithm that achieves sublinear regret in the agnostic setting without knowledge of $\mu$. We introduce a new, parameter-free algorithm based on Gaussian Follow-The-Perturbed-Leader that does not require prior knowledge of the smoothing parameter $\sigma$ and is capable of achieving regret $\tilde{O}(d\sqrt{T/\sigma })$ for binary classes of VC dimension $d$ with a single call to an optimization oracle per round. En route to establishing the regret bound, we introduce several new techniques that may be of independent interest.