极小极大最优相关 AI 资讯 · AI 热点

7月14日

11:01

11:01

官方账号arXiv cs.LG@Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa Saha

精选

该论文研究在线PCA的bandit反馈版本（Bandit PCA），每一轮t=1,...,T中，对手选择秩至多为r的d×d对称增益矩阵G_t，学习者选择单位向量w_t并接收奖励w_t^T G_t w_t。Kotlowski和Neu(2019)给出遗憾上界O(d√(rT log T))和下界Ω(r√(T/log T))。本文将上界改进至O(r√(dT))（忽略d和T的对数因子），下界提升至Ω(r√(dT))，从而确定了该问题的极小极大最优遗憾。上界算法结合了在密度矩阵谱面上的在线镜像下降与多尺度探索方案。

AI模型 Bandit PCA 在线PCA 遗憾分析

推荐理由：这篇论文把Bandit PCA的遗憾上界从O(d√(rT log T))降到O(r√(dT))，下界也提到Ω(r√(dT))，彻底解决了这个优化问题的理论最优性。