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

Jun 1, 2017, 3:30pm
Location TBA
Madeleine Udell, Department of Operations Research and Information Engineering, Cornell University

Abstract: In this talk, we consider 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.