Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
arXiv:2008.13777
Abstract
Existing results for low-rank matrix recovery largely focus on quadratic loss, which enjoys favorable properties such as restricted strong convexity/smoothness (RSC/RSM) and well conditioning over all low rank matrices. However, many interesting problems involve more general, non-quadratic losses, which do not satisfy such properties. For these problems, standard nonconvex approaches such as rank-constrained projected gradient descent (a.k.a. iterative hard thresholding) and Burer-Monteiro factorization could have poor empirical performance, and there is no satisfactory theory guaranteeing global and fast convergence for these algorithms. In this paper, we show that a critical component in provable low-rank recovery with non-quadratic loss is a regularity projection oracle. This oracle restricts iterates to low-rank matrices within an appropriate bounded set, over which the loss function is well behaved and satisfies a set of approximate RSC/RSM conditions. Accordingly, we analyze an (averaged) projected gradient method equipped with such an oracle, and prove that it converges globally and linearly. Our results apply to a wide range of non-quadratic low-rank estimation problems including one bit matrix sensing/completion, individualized rank aggregation, and more broadly generalized linear models with rank constraints.
arXiv comment30 pages and 3 figures
References in corpus (11)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Global Optimality in Low-rank Matrix Optimization
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
- Exponential Family Matrix Completion under Structural Constraints
- Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
- Between hard and soft thresholding: optimal iterative thresholding algorithms