A Rank-1 Sketch for Matrix Multiplicative Weights

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.