Backend
Agnostic Smoothed Online Regression with Adversarial Responses
arXiv stat.ML0 views
arXiv:2609.32478v2 Announce Type: replace 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 $\nu^2$-subGaussian responses, we extend the existing lower bound under realizable responses by showing that the minimax expected regret is $\Omega((1\vee \nu)\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 $\nu$.
Source:https://arxiv.org/abs/2609.32478PreviousAdaptive Inference for Resource-Constrained Dynamic PricingNextPrediction with Foundation Models under Deployment Budgets
Related posts
Splunk's Empty Cluster Secret Turns a Standalone Default into an Authentication Bypass
0dev.to
Pragmatic zero-trust: what to ship in the first 90 days
0dev.to
The EKS cost playbook: 7 levers we pull on every audit
0dev.to
Building a hearing test in the browser with the Web Audio API (and why we refuse to call it an audiogram)
0dev.to
How we score French speaking with AI: an honest look at limits
0dev.to
What a Four-Letter Word Ladder Taught Me About Planning Under Constraints
0dev.to