带对抗响应的不可知平滑在线回归
Agnostic Smoothed Online Regression with Adversarial Responses
Xuanyu Chen · Yue Yu
中文摘要
研究有界对抗响应下的平滑在线预测。该框架通过平滑参数 C_cov 连接独立同分布采样与对抗协变量选择,C_cov 约束条件协变量密度相对于固定未知基测度的上界。提出 Hedge-Cover,一种信息论算法,对具有有界伪维度的函数类达到次线性遗憾 O~(√(Pdim(F)·C_cov·T))。算法用 Hedge 聚合精心构造的专家族,其先验将遗憾与一致选择器和目标函数之间的不一致数联系起来,并利用协变量平滑性对该数量给出界。这回答了 Blanchard 2025 关于平滑在线回归问题极小极大最优自适应遗憾的开放问题。对线性预测器类建立匹配下界,其核心在于显式构造支撑在相互正交超平面上的困难序列协变量分布,该构造可能具有独立技术价值。最后重新审视良设定情形并量化响应噪声影响:对条件 ν²-次高斯响应,扩展可实现响应下的已有下界,证明 VC 维为 d 的函数类其极小极大期望遗憾为 Ω((1∨ν)√((C_cov−1)dT)),ERM 的对应上界匹配该 ν 依赖。
关键要点
- 01问题:平滑在线回归在对抗响应下的极小极大最优自适应遗憾此前未解决。
- 02方法:Hedge-Cover 用 Hedge 聚合专家族,借协变量平滑性约束不一致数。
- 03结果:达到 O~(√(Pdim(F)·C_cov·T)) 遗憾,并对线性预测器给出匹配下界。
- 04下界构造:显式构造支撑于相互正交超平面的序列协变量分布。
- 05噪声影响:条件 ν²-次高斯响应下遗憾为 Ω((1∨ν)√((C_cov−1)dT)),ERM 上界匹配。
解读
尚无解读。
原始英文摘要
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$.