A Rank-1 Sketch for Matrix Multiplicative Weights
This work addresses computational efficiency issues in optimization algorithms for researchers and practitioners in machine learning and optimization, representing an incremental improvement over existing MMW methods.
The paper tackles the computational bottleneck of matrix exponentiation in matrix multiplicative weight (MMW) methods by proposing a randomized rank-1 sketch that approximates MMW updates efficiently using a single product e^A b via Lanczos. This approach achieves the same regret bounds as MMW up to a constant factor, improves complexity for the online eigenvector problem by Ω(log^5 n), and matches state-of-the-art guarantees for semidefinite programming.
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 $e^A b$, which the Lanczos method approximates efficiently. Our key technique is to view the sketch as a $\textit{randomized mirror projection}$, and perform mirror descent analysis on the $\textit{expected projection}$. Our sketch solves the online eigenvector problem, improving the best known complexity bounds by $Ω(\log^5 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.