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

Madeleine Udell (ORIE, Cornell)

Is it possible to solve an optimization problem using far less memory than the natural size of the decision variable? In this talk, we consider the special case of nuclear norm constrained matrix optimization problems, and propose an affirmative answer to this question when both the problem data and solution have a concise representation. We present an algorithm, Sketchy CGM, for provably solving these problems, whose natural size is $O(n^2)$, using no more than $O(n)$ memory. SketchyCGM modifies a standard convex optimization algorithm — the conditional gradient method — to work on a sketched version of the decision variable, and can recover the solution from this sketch. Importantly, and in contrast to recent work on non-convex methods for this problem class, SketchyCGM inherits all the benefits of convex optimization, including robustness, flexibility, and a well understood convergence theory.