Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization

Abstract

The analysis of nonconvex matrix completion has recently attracted much attention in the community of machine learning thanks to its computational convenience. Existing analysis on this problem, however, usually relies on ${\ell }_{2,\infty }$ projection or regularization that involves unknown model parameters, although they are observed to be unnecessary in numerical simulations, see, e.g., Zheng and Lafferty [2016]. In this paper, we extend the analysis of the vanilla gradient descent for positive semidefinite matrix completion proposed in Ma et al. [2017] to the rectangular case, and more significantly, improve the required sampling rate from $O(\mathrm{poly}(\kappa ){\mu }^3{r}^3{\log }^{3}n/n)$ to $O({\mu }^2{r}^2{\kappa }^{14}\log n/n)$. Our technical ideas and contributions are potentially useful in improving the leave-one-out analysis in other related problems.

References in corpus (10)

• A Simpler Approach to Matrix Completion
• Guaranteed Matrix Completion via Non-convex Factorization
• 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
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Incoherence-Optimal Matrix Completion
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA

Cited by in corpus (6)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees