Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent

Abstract

Matrix completion, where we wish to recover a low rank matrix by observing a few entries from it, is a widely studied problem in both theory and practice with wide applications. Most of the provable algorithms so far on this problem have been restricted to the offline setting where they provide an estimate of the unknown matrix using all observations simultaneously. However, in many applications, the online version, where we observe one entry at a time and dynamically update our estimate, is more appealing. While existing algorithms are efficient for the offline setting, they could be highly inefficient for the online setting. In this paper, we propose the first provable, efficient online algorithm for matrix completion. Our algorithm starts from an initial estimate of the matrix and then performs non-convex stochastic gradient descent (SGD). After every observation, it performs a fast update involving only one row of two tall matrices, giving near linear total runtime. Our algorithm can be naturally used in the offline setting as well, where it gives competitive sample complexity and runtime to state of the art algorithms. Our proofs introduce a general framework to show that SGD updates tend to stay away from saddle surfaces and could be of broader interests for other non-convex problems to prove tight rates.

References in corpus (5)

• A Simpler Approach to Matrix Completion
• Gradient Descent Converges to Minimizers
• Simple, Efficient, and Neural Algorithms for Sparse Coding
• Computational Limits for Matrix Completion
• Streaming, Memory Limited Matrix Completion with Noise

Cited by in corpus (17)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Understanding the Downstream Instability of Word Embeddings
• Online linear optimization with the log-determinant regularizer
• On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• Implicit Regularization in Matrix Sensing via Mirror Descent
• Compositional Stochastic Average Gradient for Machine Learning and Related Applications
• Online high rank matrix completion