Agnostic Smoothed Online Regression with Adversarial Responses

arXiv:2609.32478v1 Announce Type: cross 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 extsf{C}{extsf{cov}}, which bounds conditional covariate densities relative to a fixed, unknown base measure. We propose extsc{Hedge-Cover}, an information-theoretic algorithm that achieves sublinear regret widetilde{O}(sqrt{ext{Pdim}(F) extsf{C}{extsf{cov}} T}) for function classes with bounded pseudo-dimension. The algorithm aggregates a carefully constructed family of experts using extsc{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 ite{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 nu^2-subGaussian responses, we extend the existing lower bound under realizable responses by showing that the minimax expected regret is Omega((1ee nu)sqrt{(extsf{C}_{extsf{cov}}-1)dT}) for a function class of VC dimension d. A corresponding upper bound for ERM matches this dependence on nu.

Source: arXiv cs.LG | 2026-09-29