A Rank-1 Sketch for Matrix Multiplicative Weights

Abstract

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 $\text{randomized mirror projection}$, and perform mirror descent analysis on the $\text{expected projection}$. Our sketch solves the online eigenvector problem, improving the best known complexity bounds by $\Omega ({\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.

References in corpus (5)

• Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming
• Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
• Subsampling Algorithms for Semidefinite Programming
• Geometric Median in Nearly Linear Time
• Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$-Matrices

Cited by in corpus (3)

• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
• Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent