Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage

This paper considers a fundamental class of convex matrix optimization problems with low-rank solutions. We show it is possible to solve these problem using far less memory than the natural size of the decision variable when the problem data has a concise representation. Our proposed method, SketchyCGM, is the first algorithm to offer provable convergence to an optimal point with an optimal memory footprint. SketchyCGM modifies a standard convex optimization method - the conditional gradient method - to work on a sketched version of the decision variable, and can recover the solution from this sketch. In contrast to recent work on non-convex methods for this problem class, SketchyCGM is a convex method; and our convergence guarantees do not rely on statistical assumptions.

Presented at:
20th International Conference on Artificial Intelligence and Statistics (AISTATS2017), Fort Lauderdale, Florida, USA, April 20-22, 2017

 Record created 2017-02-16, last modified 2019-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)