Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications

Weiyuan Gong, Tongyang Li, Xinzhao Wang, Zhiyu ZhangarXiv 2025 · DOI · arXiv

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.

Summary of regret and mistake bounds for various classes of quantum states using the instance-optimal MMWU algorithm.

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

Abstract

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.
BibTeX
@misc{gong2025instance,
  author = {Weiyuan Gong and Tongyang Li and Xinzhao Wang and Zhiyu Zhang},
  title = {{Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications}},
  year = {2025},
  eprint = {2509.08911},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.08911},
}
Figure