跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2609.32478 · v2

Agnostic Smoothed Online Regression with Adversarial Responses

首次提交 2026-09-26 19:17
版本更新 2026-11-19 19:34
雷达观测 2026-11-20 16:53
arXiv ↗PDF ↗

摘要

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 Ccov\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 O~(Pdim(F)CcovT)\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 ν2ν^2-subGaussian responses, we extend the existing lower bound under realizable responses by showing that the minimax expected regret is Ω((1∨ν)(Ccov−1)dT)Ω((1\vee ν)\sqrt{(\textsf{C}_{\textsf{cov}}-1)dT}) for a function class of VC dimension dd. A corresponding upper bound for ERM matches this dependence on νν.

作者备注:32 pages, 1 table

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-19 19:34 · 最新观测版本

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 Ccov\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 O~(Pdim(F)CcovT)\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 ν2ν^2-subGaussian responses, we extend the existing lower bound under realizable responses by showing that the minimax expected regret is Ω((1∨ν)(Ccov−1)dT)Ω((1\vee ν)\sqrt{(\textsf{C}_{\textsf{cov}}-1)dT}) for a function class of VC dimension dd. A corresponding upper bound for ERM matches this dependence on νν.

查看此版本解读 →查看此版本原文 ↗