Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
By Yudong Chen, Martin J. Wainwright. 2015
336 citations recorded by the source corpus.
Optimization problems with rank constraints arise in many applications, including matrix regression, structured PCA, matrix completion and matrix decomposition problems. An attractive heuristic for solving such problems is to factorize the low-rank matrix, and to run projected gradient descent on the nonconvex factorized optimization problem. The goal of this problem is to provide a general theoretical framework for understanding when such methods work well, and to characterize the nature of the resulting fixed point. We provide a simple set of conditions under which projected gradient descent, when given a suitable initialization, converges geometrically to a statistically useful solution. Our results are applicable even when the initial solution is outside any region of local convexity, and even when the problem is globally concave. Working in a non-asymptotic framework, we show that our conditions are satisfied for a wide range of concrete models, including matrix regression, structured PCA, matrix completion with real and quantized observations, matrix decomposition, and graph clustering problems. Simulation results show excellent agreement with the theoretical predictions.
Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training, Statistical Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
In Computer Vision and Pattern Recognition
In Optimization & Training
In Statistical Learning Theory
Citations in the corpus
- Matrix Completion has No Spurious Local Minimum (2016, background): “More recently, there has been growing interest in analyzing non-convex algorithms for matrix completion [KMO10, JNS13, Har14, HW14, SL15, ZWL15, CW15].”
- Dropping Convexity for Faster Semi-definite Optimization (2015, methodology): “In many applications, an initial point U 0 with this type of guarantees is easy to obtain, often with just one eigenvalue decomposition; we refer the reader to the works [42, 64, 23, 82, 71] for specific initialization procedures for different problem settings.”
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, methodology): “For each p,we apply vanilla gradient descent, projected gradient descent [32] and gradient descent with additional regularization terms [107] with step size η = 0.”
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, methodology): “For matrix sensing or matrix completion, the works [Keshavan et al., 2010a,b, Hardt and Wootters, 2014, Hardt, 2014, Jain et al., 2013, Chen and Wainwright, 2015, Sun and Luo, 2015, Zhao et al., 2015, Zheng and Lafferty, 2016, Tu et al., 2015] showed that given a good enough initialization, many…”
- A Survey of Optimization Methods From a Machine Learning Perspective (2019, background): “include projection gradient descent [138], [139]; alternating minimization [140]–[142]; expectation maximization algorithm [143], [144]; and stochastic”
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “One notable example serving this purpose is projected GD for matrix completion [22], [62], [63], where in the positive semidefinite case (i.”
- GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projection (2024, neutral): “Projected Gradient Descent GaLore is closely related to the traditional topic of projected gradient descent (PGD) (Chen & Wainwright, 2015; Chen et al., 2019).”