无需预知时间范围，遗憾界首次逼近固定时间最优常数！
Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
📖 AI 总结
本文研究在线学习中的专家建议预测问题。当时间范围T已知时，n个专家的最小化累积遗憾渐近为√(T ln n / 2)，由学习率针对T调优的乘法权重更新算法实现，且该界是紧的。若要求遗憾界在每个时刻t同时成立（即任意时间保证），此前已知最优结果为√(t ln n)，比固定时间常数差√2倍，而这一差距是否必要一直未知。本文证明该√2因子并非必要，提出一种无需预知时间范围的算法，其累积遗憾对所有t≥1同时满足R_t ≤ (1 + O(√(ln ln n / ln n)))√(t ln n / 2)。这一结果表明，在专家数量较多时，任意时间遗憾可以匹配固定时间的最优常数，缩小了在线学习理论中一个长期存在的差距。
🔑 关键词速览
| Prediction with Expert Advice | 在线学习中的经典框架，学习者每轮根据多个专家的建议进行预测，并累积遗憾。 |
| Multiplicative Weights Update | 一种经典的在线学习算法，通过乘法方式更新专家权重，常用于实现最优遗憾界。 |
| Cumulative Regret | 衡量在线算法性能的指标，定义为算法累积损失与事后最优专家累积损失之差。 |
| Anytime Regret | 要求遗憾界在所有时间点同时成立，而不依赖于预先知道的时间范围。 |
| Minimax Regret | 在最坏情况下，算法与最优专家之间的最小可能遗憾，用于衡量问题的固有难度。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅