提出最优带通量主成分分析算法，实现理论极限的误差控制。
Bandit PCA with Minimax Optimal Regret
- 结合镜像下降与多尺度探索，动态调整不同特征空间更新速率。
- 上界达到 $ r\sqrt{dT} $ 阶，下界为 $ \Omega(r\sqrt{T/\log T}) $，逼近理论最优。
- 适用于在线学习、量子态探测等需低反馈场景，尤其适合高维稀疏数据。
研究带通量反馈下的在线主成分分析（Bandit PCA）：每轮中，对手选择一个 $ d \times d $ 对称增益矩阵 $ G_t $，其谱在 $[0,1]$ 内且秩不超过 $ r $；学习者同时选择单位向量 $ w_t \in S^{d-1} $，仅获得奖励 $ w_t^\top G_t w_t $，无其他反馈，目标是最小化对最优历史单位向量的后悔值。该问题由 Kotlowski 与 Neu (2019) 提出，给出 $ O(d\sqrt{rT \log T}) $ 的后悔上界，并证明下界为 $ \Omega(r\sqrt{T/\log T}) $。本文改进两者，基本填补差距，确立最小最大后悔值为 $ r\sqrt{dT} $ 阶（含对数因子）。上界由新算法达成，融合了在密度矩阵谱体上的在线镜像下降与多尺度探索机制，不同谱幅特征空间以不同速率更新。下界通过构造自适应对手，基于学习者行为逐步精炼隐藏高收益子空间，迫使必须估计子空间才能低悔，从而将后悔下界转化为子空间估计问题。最后讨论其与自适应测量量子态层析的联系。
原文摘要 · Abstract (English)
We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round $t = 1,\dots,T$, the adversary selects a $d \times d$ symmetric gain matrix $G_t$ with spectrum in $[0,1]$ and rank at most $r$; the learner simultaneously selects a unit vector $w_t \in S^{d-1}$ and receives the reward $w_t^\top G_t w_t$. The learner receives no other feedback, and aims to minimize the regret against the best unit vector in hindsight. This problem was introduced by Kotlowski and Neu (2019), who gave an algorithm with regret $O(d\sqrt{rT \log T})$ and showed the lower bound of $Ω(r\sqrt{T/\log T})$. We improve upon both of these bounds and essentially bridge the gap between them, establishing the minimax regret of order $r\sqrt{dT}$ up to polylogarithmic factors in $d$ and $T$. The upper bound is attained by a novel algorithm, which combines online mirror descent on the spectrahedron of (real) density matrices with a multiscale exploration scheme in which the eigenspaces with different spectral magnitudes are updated at different rates. For the lower bound, we construct an adaptive adversary that refines a hidden large-reward subspace based on the learner's actions, in such a way that low regret is impossible without estimating the subspace; as a result, lower-bounding the regret reduces to studying the arising subspace estimation problem. Finally, we discuss connections of Bandit PCA with adaptive-measurement quantum tomography.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。