常数次线性最小化无法突破T^{3/4}遗憾率，Weibel猜想被证明！
Lower Bounds for Linear-Oracle Online Learning
📖 AI 总结
本文研究线性预言机模型下的在线学习遗憾下界问题。作者证明并推广了Weibel等人关于固定系数方法无法突破在线Frank-Wolfe在一般凸集上T^{3/4}遗憾率的猜想，将下界扩展至预言机模型中所有确定性学习器。在该模型中，学习器仅获得初始可行点与直径界，且须在与其预言机回复一致的所有域上保持可行。对于T轮、每两次决策间至多b次调用、直径界D与梯度范数界L，作者构造了维度d=2b(T-1)+1的实例，遗憾至少为2^{-1/4}LDb^{-1/4}T^{3/4}。对手在博弈前固定域、初始点、确定性平局规则与线性损失。当b为常数时，该结果与已知的维度无关上界吻合。对于单次调用的固定调度，若最新梯度系数非零，第二个构造给出至少3LDT^{3/4}/4的遗憾，且每次查询处均有唯一极小值点。精确算术证书与Weibel等人调优调度的有限时域数值最坏情况高度吻合，且预言机回复唯一。
🔑 关键词速览
| 在线 Frank-Wolfe | 一种用于在线凸优化的投影自由算法，每轮通过线性最小化步骤更新决策。 |
| 遗憾率 | 衡量在线学习算法性能的指标，表示算法累积损失与事后最优固定决策累积损失之差。 |
| 线性预言机 | 一种计算模型，学习器只能通过查询线性函数的最小化来获取信息，而不直接访问梯度。 |
| 固定系数方法 | 指每轮更新时使用固定权重组合历史梯度的方法，如 Weibel 等人研究的调度。 |
| 直径界 | 凸集直径的上界，用于限制可行域的大小，影响遗憾界中的常数因子。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅