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

Abstract

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 all solutions have low rank, the algorithm converges to a solution. This algorithm, SketchyCGM, modifies a standard convex optimization scheme, the conditional gradient method, to store only a small randomized sketch of the matrix variable. After the optimization terminates, the algorithm extracts a low-rank approximation of the solution from the sketch. In contrast to nonconvex heuristics, the guarantees for SketchyCGM do not rely on statistical models for the problem data. Numerical work demonstrates the benefits of SketchyCGM over heuristics.

Cited by in corpus (30)

• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• Phase retrieval from noisy data based on sparse approximation of object phase and amplitude
• Single-frame far-field diffractive imaging with randomized illumination
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• Basis Pursuit Denoise with Nonsmooth Constraints
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
• Large Scale Private Learning via Low-rank Reparametrization
• An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity
• Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• A Conditional Gradient-Based Augmented Lagrangian Framework
• Dimensionality reduction of SDPs through sketching
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Rapid characterisation of linear-optical networks via PhaseLift
• Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence
• Don't take it lightly: Phasing optical random projections with unknown operators
• Total Least Squares Phase Retrieval
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
• Accelerated and Inexact Soft-Impute for Large-Scale Matrix and Tensor Completion
• Random mesh projectors for inverse problems
• Polar Alignment and Atomic Decomposition
• On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization
• Smoothed analysis of the low-rank approach for smooth semidefinite programs
• On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
• Training Quantized Neural Networks to Global Optimality via Semidefinite Programming
• Sketching semidefinite programs for faster clustering
• Memory-Efficient Approximation Algorithms for Max-k-Cut and Correlation Clustering
• $k$FW: A Frank-Wolfe style algorithm with stronger subproblem oracles
• Which Factorization Machine Modeling is Better: A Theoretical Answer with Optimal Guarantee
• Scalable Incremental Nonconvex Optimization Approach for Phase Retrieval