Algorithm achieves optimal regret for smooth online regression problems
Agnostic Smoothed Online Regression with Adversarial Responses
Machine Learning
Summary
This paper studies how to make predictions online when data can be chosen by an adversary but follow some smoothness rules. The authors develop an algorithm, Hedge-Cover, that learns efficiently and closely matches the best possible performance, measured by regret, for a broad class of prediction functions. They also prove that no algorithm can do significantly better, showing their method is optimal in theory. Additionally, they analyze how noise in responses affects learning in well-behaved scenarios.
What this means in practice
- •For machine learning engineers: Design online prediction systems that tolerate adversarial changes but assume some smooth structure in data distribution for better performance guarantees.
- •For financial analysts: Develop robust forecasting tools for trading that handle smoothly changing market conditions adversarially influenced but statistically constrained.
A theory result. No direct application yet.
Authors
Xuanyu Chen, Yue Yu
Abstract
We study smoothed online prediction with bounded adversarial responses. This widely studied framework bridges i.i.d. sampling and adversarial covariate selection through a smoothness parameter $\textsf{C}_{\textsf{cov}}$, which bounds conditional covariate densities relative to a fixed, unknown base measure. We propose \textsc{Hedge-Cover}, an information-theoretic algorithm that achieves sublinear regret $\widetilde{O}(\sqrt{\text{Pdim}(\mathcal{F}) \textsf{C}_{\textsf{cov}} T})$ for function classes with bounded pseudo-dimension. The algorithm aggregates a carefully constructed family of experts using \textsc{Hedge}, with a prior that links regret to the number of disagreements between a consistent selector and a target function. We bound this number by exploiting covariate smoothness. This answers an open problem posed in \cite{blanchard2025agnostic} on the minimax optimal adaptive regret of the smoothed online regression problem. We establish a matching lower bound for the class of linear predictors. The main intricacy of the lower bound lies in explicitly constructing a challenging sequential covariate distribution supported on mutually orthogonal hyperplanes. This construction may be of independent technical interest. Finally, we revisit the well-specified setting and quantify the effect of response noise. For conditionally $ν^2$-subGaussian responses, we extend the existing lower bound under realizable responses by showing that the minimax expected regret is $Ω((1\vee ν)\sqrt{(\textsf{C}_{\textsf{cov}}-1)dT})$ for a function class of VC dimension $d$. A corresponding upper bound for ERM matches this dependence on $ν$.