Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
Abstract
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.
Cite
Text
Yurtsever et al. "Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage." International Conference on Artificial Intelligence and Statistics, 2017.Markdown
[Yurtsever et al. "Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage." International Conference on Artificial Intelligence and Statistics, 2017.](https://mlanthology.org/aistats/2017/yurtsever2017aistats-sketchy/)BibTeX
@inproceedings{yurtsever2017aistats-sketchy,
title = {{Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage}},
author = {Yurtsever, Alp and Udell, Madeleine and Tropp, Joel A. and Cevher, Volkan},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2017},
pages = {1188-1196},
url = {https://mlanthology.org/aistats/2017/yurtsever2017aistats-sketchy/}
}