How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
arXiv:2006.06915
Abstract
Given a sufficiently large amount of labeled data, the non-convex low-rank matrix recovery problem contains no spurious local minima, so a local optimization algorithm is guaranteed to converge to a global minimum starting from any initial guess. However, the actual amount of data needed by this theoretical guarantee is very pessimistic, as it must prevent spurious local minima from existing anywhere, including at adversarial locations. In contrast, prior work based on good initial guesses have more realistic data requirements, because they allow spurious local minima to exist outside of a neighborhood of the solution. In this paper, we quantify the relationship between the quality of the initial guess and the corresponding reduction in data requirements. Using the restricted isometry constant as a surrogate for sample complexity, we compute a sharp threshold number of samples needed to prevent each specific point on the optimization landscape from becoming a spurious local minimum. Optimizing the threshold over regions of the landscape, we see that for initial points around the ground truth, a linear improvement in the quality of the initial guess amounts to a constant factor improvement in the sample complexity.
16 pages, 2 figures
References in corpus (9)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Guaranteed Matrix Completion via Non-convex Factorization
- Global Optimality of Local Search for Low Rank Matrix Recovery
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
- Non-convex Robust PCA
- The Non-convex Geometry of Low-rank Matrix Optimization