Abstract
Standard Matrix Multiplicative Weight Update (MMWU) algorithms are minimax optimal but often pessimistic, failing to adapt to the inherent simplicity of specific problem instances. We present an "instance-optimal" MMWU that achieves tighter regret bounds for "easy" target states by leveraging a novel one-sided Jensen’s trace inequality and an imaginary error function (erfi) potential. This approach maintains the computational efficiency of standard MMWU while providing significant speedups in quantum learning tasks, such as predicting properties of noisy circuits and Gibbs states.
Introduction
The Matrix Multiplicative Weight Update (MMWU) algorithm is a fundamental tool in online optimization and quantum information theory. In the Learning from Expert Advice (LEA) framework, a learner aims to predict a matrix—often representing a quantum state—while an adversary reveals loss matrices. The objective is to minimize regret: the cumulative difference between the learner's loss and the loss of the best fixed comparator matrix $X$ chosen in hindsight.
While standard MMWU achieves a regret bound of $O(\sqrt{T \log d})$, where $T$ is time and $d$ is the dimension, this bound is "minimax optimal" for the absolute worst-case scenario. However, it does not account for the complexity of the target matrix $X$. Intuitively, if $X$ is "simple" (e.g., a high-entropy, highly mixed state), it should be easier to learn. The primary obstacle to achieving such instance-optimality in the matrix setting is non-commutativity, which prevents the direct application of standard vector-based optimization tools like Jensen’s inequality.
Methodology: Overcoming Non-Commutativity
The researchers overcome the challenges of non-commutativity through a potential-based framework centered on three key innovations:
1. The "One-Sided" Jensen’s Trace Inequality
The authors identified a specific class of convex functions—those whose second derivatives are Laplace transforms of non-negative functions—that satisfy a "one-sided" version of Jensen’s trace inequality. This mathematical breakthrough allows for tighter analysis in the matrix setting that was previously only possible for vectors.
2. The Erfi Potential
Moving beyond the standard exponential potential, the algorithm utilizes a potential based on the imaginary error function (erfi). This choice allows the algorithm to effectively perform automatic learning-rate tuning, adapting its performance based on the observed losses without requiring manual parameter adjustment.
3. Unconstrained Reduction and Projection
To simplify the optimization, the problem is first solved on the unconstrained space of all Hermitian matrices. The results are then projected back onto the "spectraplex" (the space of valid quantum states) using a rate-preserving reduction. This ensures that the algorithm remains computationally efficient, requiring only one eigen-decomposition per step—identical to the standard MMWU.
Key Results and Quantum Applications
The instance-optimal MMWU achieves a regret bound of $O(\sqrt{T \cdot S(X || d^{-1}I_d)})$, where $S(X || d^{-1}I_d)$ is the quantum relative entropy. This means that for target states close to the maximally mixed state (high entropy), the regret is significantly lower than the traditional $\sqrt{\log d}$ bound.
As shown in the table above, this theoretical improvement translates into concrete gains across several quantum learning benchmarks:
- Noisy Quantum Circuits: For circuits of depth $D$ with noise rate $\gamma$, the regret improves by a factor of $(1-\gamma)^D$.
- Gibbs States: At constant temperatures, the algorithm achieves $O(\sqrt{T})$ regret, outperforming the standard $O(\sqrt{T \log d})$ bound.
- Haar Random and Product States: The algorithm demonstrates superior average-case performance for these common state classes.
Furthermore, the authors established a memory lower bound of $\Omega(d^2)$, confirming that their algorithm is memory-optimal as it stores only a single $d \times d$ matrix.
Conclusion and Future Directions
This work demonstrates that instance-optimality in matrix optimization can be achieved without increasing computational complexity. By identifying the mathematical conditions under which matrix inequalities mirror their vector counterparts, the authors have opened new avenues for applying advanced optimization techniques to quantum information.
Future research may focus on addressing the $O(d^3)$ computational bottleneck through low-rank sketching techniques. Additionally, extending these bounds to non-convex loss functions—common in metrics like quantum fidelity—remains a significant open challenge. Finally, the "Monomial Conjecture" regarding the generality of the one-sided Jensen's inequality presents an intriguing mathematical problem that could further generalize these results.
Summary updated