# A Rank-1 Sketch for Matrix Multiplicative Weights

arXiv: https://arxiv.org/abs/1903.02675 · HTML: https://mlsanity.com/paper/1903.02675/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2019.

## Built on by (most cited first, 2 of 2)

- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [Optimistic Online Learning in Symmetric Cone Games](https://mlsanity.com/paper/2504.03592/) (2025)

## Abstract (arXiv)

We show that a simple randomized sketch of the matrix multiplicative weight (MMW) update enjoys (in expectation) the same regret bounds as MMW, up to a small constant factor. Unlike MMW, where every step requires full matrix exponentiation, our steps require only a single product of the form eA b, which the Lanczos method approximates efficiently. Our key technique is to view the sketch as a textitrandomized mirror projection, and perform mirror descent analysis on the textitexpected projection. Our sketch solves the online eigenvector problem, improving the best known complexity bounds by Omega(log5 n). We also apply this sketch to semidefinite programming in saddle-point form, yielding a simple primal-dual scheme with guarantees matching the best in the literature.