Agnostic Smoothed Online Regression with Adversarial Responses
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 textsfCtextsfcov, 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 Õ(√(Pdim(ℱ) textsfCtextsfcov 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∨ ν)√((textsfCtextsfcov−1)dT)) for a function class of VC dimension d. A corresponding upper bound for ERM matches this dependence on ν.
Related
- Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
- Sparse-group Convoluted Smoothed Quantile Regression in High Dimension
- Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
- Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs
- Distributionally robust linear regression through the lens of adversarial training
BibTeX
@misc{chen2026agnostic,
title = {{Agnostic Smoothed Online Regression with Adversarial Responses}},
author = {Xuanyu Chen and Yue Yu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32478},
eprint = {2609.32478},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32478},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Agnostic Smoothed Online Regression with Adversarial Responses
AU - Xuanyu Chen
AU - Yue Yu
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32478
UR - https://arxiv.org/abs/2609.32478
AB - 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 textsfC_textsfcov, 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 Õ(√(Pdim(ℱ) textsfC_textsfcov 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∨ ν)√((textsfC_textsfcov−1)dT)) for a function class of VC dimension d. A corresponding upper bound for ERM matches this dependence on ν.
ER -