提出更优的矩阵乘法权重更新算法，可自适应最优性能且计算开销不变。
Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications
- 基于新势函数框架设计算法，突破传统指数势函数限制。
- 实现实例最优后悔界 $O(\ oot\of{T\cdot S(X||d^{-1}I_d)})$，优于经典 $O(\ oot\of{T\log d})$。
- 适用于量子态学习与非线性量子性质预测，适合量子机器学习研究者。
矩阵乘法权重更新（MMWU）是在线学习中的经典算法，应用于 $d$ 维谱单纯形上的专家建议学习问题时，可达到最小最大后悔界 $O(\ oot\of{T\log d})$。本文提出一种改进算法，实现实例最优后悔界 $O(\ oot\of{T\cdot S(X||d^{-1}I_d)})$，其中 $X$ 为比较器，$I_d$ 为单位矩阵，$S(\ullet||\bullet)$ 为量子相对熵。该算法计算复杂度与原版相同，即“免费提升”。技术上，构建了通用势函数框架，将 MMWU 作为指数势的特例；核心是基于拉普拉斯变换的新“单边”Jensen 迹不等式，使一般势函数可用于矩阵专家学习。最终算法由向量问题中虚误差函数导出的最优势函数诱导。此外，我们给出矩阵专家学习的记忆下界，并在量子学习理论中展示应用：对去极化噪声、随机量子态和吉布斯态的学习均优于现有方法。还可用于线性化凸损失，预测非线性量子性质如纯度、量子虚拟冷却和瑞尼-2 关联。
原文摘要 · Abstract (English)
The Matrix Multiplicative Weight Update (MMWU) is a seminal online learning algorithm with numerous applications. Applied to the matrix version of the Learning from Expert Advice (LEA) problem on the $d$-dimensional spectraplex, it is well known that MMWU achieves the minimax-optimal regret bound of $O(\sqrt{T\log d})$, where $T$ is the time horizon. In this paper, we present an improved algorithm achieving the instance-optimal regret bound of $O(\sqrt{T\cdot S(X||d^{-1}I_d)})$, where $X$ is the comparator in the regret, $I_d$ is the identity matrix, and $S(\cdot||\cdot)$ denotes the quantum relative entropy. Furthermore, our algorithm has the same computational complexity as MMWU, indicating that the improvement in the regret bound is ``free''. Technically, we first develop a general potential-based framework for matrix LEA, with MMWU being its special case induced by the standard exponential potential. Then, the crux of our analysis is a new ``one-sided'' Jensen's trace inequality built on a Laplace transform technique, which allows the application of general potential functions beyond exponential to matrix LEA. Our algorithm is finally induced by an optimal potential function from the vector LEA problem, based on the imaginary error function. Complementing the above, we provide a memory lower bound for matrix LEA, and explore the applications of our algorithm in quantum learning theory. We show that it outperforms the state of the art for learning quantum states corrupted by depolarization noise, random quantum states, and Gibbs states. In addition, applying our algorithm to linearized convex losses enables predicting nonlinear quantum properties, such as purity, quantum virtual cooling, and Rényi-$2$ correlation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。