학술

Agnostic Smoothed Online Regression with Adversarial Responses

arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.

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$.

관련 뉴스