在线回归新突破：Hedge-Cover算法搞定对抗响应，遗憾直降次线性！
Agnostic Smoothed Online Regression with Adversarial Responses
📖 AI 总结
本文研究有界对抗响应下的平滑在线回归问题，该框架通过平滑参数Ccov在独立同分布采样与对抗性协变量选择之间建立联系。作者提出名为Hedge-Cover的信息论算法，对具有有界伪维度的函数类实现了次线性遗憾上界，其量级为伪维度、平滑参数与时间步长乘积的平方根。该算法通过Hedge方法聚合一组精心构造的专家，并利用协变量平滑性约束一致选择器与目标函数之间的不一致次数。这一结果回答了此前文献中关于平滑在线回归问题极小极大最优自适应遗憾的开放问题。作者进一步针对线性预测器类建立了匹配的下界，其核心在于显式构造支撑于相互正交超平面上的序列协变量分布。此外，文章重新审视了良好设定情形，量化了响应噪声的影响：对条件ν²次高斯响应，证明了极小极大期望遗憾的下界，并给出ERM的匹配上界。
🔑 关键词速览
| 平滑在线预测 (Smoothed Online Prediction) | 一种在线学习框架，通过平滑参数限制协变量分布与基准测度的偏差，介于独立同分布采样和完全对抗性选择之间。 |
| Hedge-Cover | 本文提出的信息论算法，通过 Hedge 聚合专家族，利用协变量平滑性实现次线性遗憾。 |
| 伪维度 (Pseudo-dimension) | 衡量函数类复杂度的组合维度，用于控制学习算法的泛化误差上界。 |
| 极小极大遗憾 (Minimax Regret) | 在最坏情况下，算法累积损失与最优固定策略累积损失之差的最小可能值，用于衡量在线学习算法的理论性能。 |
| VC 维 (VC Dimension) | Vapnik-Chervonenkis 维数，衡量二分类函数类复杂度的指标，表示能被函数类打散的最大点集大小。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅