# Agnostic Smoothed Online Regression with Adversarial Responses

arXiv: https://arxiv.org/abs/2609.32478 · HTML: https://mlsanity.com/paper/2609.32478/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 37 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Builds on (most cited first, 18 of 18)

- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Uniform regret bounds over Rd for the sequential linear regression problem with the square loss](https://mlsanity.com/paper/1805.11386/) (2018)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions](https://mlsanity.com/paper/2205.13056/) (2022)
- [Online Learning in Dynamically Changing Environments](https://mlsanity.com/paper/2302.00103/) (2023)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Oracle-Efficient Hybrid Online Learning with Unknown Distribution](https://mlsanity.com/paper/2401.15520/) (2024)
- [Oracle-efficient Hybrid Learning with Constrained Adversaries](https://mlsanity.com/paper/2603.04546/) (2026)
- [Universal coding, intrinsic volumes, and metric complexity](https://mlsanity.com/paper/2303.07279/) (2023)
- [Smoothed Online Classification can be Harder than Batch Classification](https://mlsanity.com/paper/2405.15424/) (2024)
- [An Optimal Agnostic PAC Algorithm](https://mlsanity.com/paper/2608.06363/) (2026)
- [Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression](https://mlsanity.com/paper/2605.01628/) (2026)

## Abstract (arXiv)

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 textscHedge-Cover, an information-theoretic algorithm that achieves sublinear regret widetildeO(√Pdim(F) textsfC_textsfcov T) for function classes with bounded pseudo-dimension. The algorithm aggregates a carefully constructed family of experts using textscHedge, 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 citeblanchard2025agnostic 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 nu2-subGaussian responses, we extend the existing lower bound under realizable responses by showing that the minimax expected regret is Omega((1vee nu)√(textsfC_textsfcov-1)dT) for a function class of VC dimension d. A corresponding upper bound for ERM matches this dependence on nu.