Agnostic Smoothed Online Regression with Adversarial Responses

Xuanyu Chen; Yue Yu

stat.MLSep 26, 2026

Agnostic Smoothed Online Regression with Adversarial Responses

Authors: Xuanyu Chen, Yue Yu

Organizations: Department of Statistics, University of Michigan

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 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 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 $ν$ .

Figures & tables

	Adversarial responses	Well-specified responses
Upper bound	Unknown $\mu$ , oblivious. R-Cover : $O\big(\log^{3}T\sqrt{{\textsf{C}}_{\textsf{cov}}dT}\big)$ , for $\textsf{fat}_{\mathcal{F}}(r)\leq d\log(1/r)$ . ( Blanchard, 2025 , Theorem 4) Unknown $\mu$ , adaptive. Hedge-Cover : $\widetilde{O}\big(\sqrt{\operatorname{Pdim}(\mathcal{F}){\textsf{C}}_{\textsf{cov}}T}\big)$ . Theorem 2.1 Known $\mu$ , adaptive. $O\big(\log^{3/2}T\log({\textsf{C}}_{\textsf{cov}}T)\sqrt{dT}\big)$ . ( Block et al., 2022 , Theorem 3)	Unknown $\mu$ , estimation error. ERM : $\widetilde{O}\big(\sqrt{{\textsf{C}}_{\textsf{cov}}dT}\big)$ . ( Block et al., 2024 , Theorem 8)
Lower bound	Unknown $\mu$ , adaptive. $\Omega\Big(\sqrt{({\textsf{C}}_{\textsf{cov}}-1)dT}\wedge T\Big)$ for all algorithms. Theorem 3.1	Unknown $\mu$ , adaptive. $\Omega\Big(\sqrt{({\textsf{C}}_{\textsf{cov}}-1)dT}\wedge T\Big)$ for all algorithms. Realizable responses: ( Blanchard, 2025 , Theorem 2) Noise-dependent extension: Theorem 3.3

Table 1: Upper and lower regret bounds for regression under

{\textsf{C}}_{\textsf{cov}}

-smooth covariates.

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 579 papers

Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
Oct 7, 2026Sasha Voitovych, Adam Block, Alexander Rakhlin +1Follow-the-Perturbed-Leader
MIT · Columbia University · Georgia Tech
Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
May 2, 2026Fan Chen, Jian Qian, Alexander Rakhlin +1Linear Regression
MIT · University of Hong Kong · UC Berkeley
Optimal Multiclass Online Regret with Arbitrary Label Spaces
Oct 23, 2026Sajad Ashkezari, Shai Ben-DavidMulticlass Classification Statistical Learning Theory
University of Waterloo

Oct 7, 2026J/K move · Enter open · S save

Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning

Sasha Voitovych, Adam Block, Alexander Rakhlin, Abhishek Shetty

MIT · Columbia University · Georgia Tech

Follow-the-Perturbed-Leader

Open paper AskPDF arXiv

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 that are perfectly predicted by a fixed hypothesis. Both assumptions limit the applicability of these algorithms, in contrast to statistical learning, where empirical risk minimization (ERM) learns efficiently in the agnostic setting without any knowledge of the data distribution. We show that neither assumption is necessary, giving the first oracle-efficient algorithm that achieves sublinear regret in the agnostic setting without knowledge of

μ

. Our algorithm, based on Gaussian Follow-The-Perturbed-Leader, is parameter-free: it requires no knowledge of

μ

, the smoothing parameter

σ

, or the horizon

T

, and it achieves regret

\widetilde O(d\sqrt{T/σ})

for binary classes of VC dimension

d

with a single call to an ERM oracle per round, which is optimal up to a

\sqrt{d}

factor. En route to establishing the regret bound, we introduce several new techniques that may be of independent interest.

Abstract

Statistical Learning Theory

Explore similar work

Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression

Optimal Multiclass Online Regret with Arbitrary Label Spaces