Agnostic Smoothed Online Regression with Adversarial Responses

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.