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 $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
$\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.
