专家问题交替遗憾率突破：常数级Θ(log d)颠覆认知，远超T^(1/3)旧界！
Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
📖 AI 总结
本文研究了在线凸优化（OCO）中的交替遗憾问题，该问题源于两人博弈中交替学习动态的成功。此前研究虽在多种损失函数和可行域假设下证明了次线性交替遗憾可实现，但极小极大遗憾率一直悬而未决。作者解决了这一开放问题，为专家问题和一般OCO均给出了匹配的上下界。令人意外的是，对于d专家问题，极小极大交替遗憾为Θ(log d)，与时间T无关，显著优于Hait等人2025年得出的O(T^{1/3}log^{2/3}d)上界。研究进一步将结果推广至d维紧凸集上的一般OCO，证明最坏情形极小极大交替遗憾为Θ(d log(1+T/d))，同样大幅改进了此前最优的O((d log T)^{2/3}T^{1/3})上界，解决了Cevher等人2023年及Hait等人2025年提出的开放问题。技术上，上界通过修正的Hedge算法实现，其中精心设计的修正项抵消了交替遗憾分析中的不利曲率；下界构造则分别采用反复淘汰半数候选专家和单位圆盘上的多尺度构造。
🔑 关键词速览
| 交替遗憾 (Alternating Regret) | 一种衡量在线学习算法性能的指标，考虑算法与对手交替更新时的累积损失差异。 |
| 在线凸优化 (Online Convex Optimization, OCO) | 一种在线学习框架，每次迭代中算法选择凸集中的点，随后遭受凸损失函数。 |
| 极小极大遗憾率 (Minimax Regret Rate) | 在最坏情况下，算法相对于最优固定决策的最小可能遗憾的渐近增长率。 |
| Hedge 算法 | 一种用于专家问题的经典在线学习算法，通过加权投票和指数权重更新来最小化遗憾。 |
| 多尺度构造 (Multiscale Construction) | 一种用于构造下界实例的技术，通过在不同尺度上设计损失函数来迫使算法产生高遗憾。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅