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.
Code (0)
등록된 구현이 없습니다.
Tasks
FormSimilar Papers 제목 키워드 기반
Learning nonnegative matrix factorizations from compressed data
We propose a flexible and theoretically supported framework for scalable nonnegative matrix factorization. The goal is to find nonnegative low-rank components directly from compressed measurements, accessing the original…
Sequential Low-Rank Change Detection
Detecting emergence of a low-rank signal from high-dimensional data is an important problem arising from many applications such as camera surveillance and swarm monitoring using sensors. We consider a procedure based on …
Change DetectionDimensionality ReductionSketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a low-rank approximation of a solution. In particular, when …
Multiplicative weights, equalizers, and P=PPAD
We show that, by using multiplicative weights in a game-theoretic thought experiment (and an important convexity result on the composition of multiplicative weights with the relative entropy function), a symmetric bimatr…
Localized sketching for matrix multiplication and ridge regression
We consider sketched approximate matrix multiplication and ridge regression in the novel setting of localized sketching, where at any given point, only part of the data matrix is available. This corresponds to a block di…
regression