mlsanityData to 7 Oct 2026

Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization

arXiv 2212.09396 ↗First posted 19 Dec 2022stat.ML cs.IT cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

The nonconvex formulation of the matrix completion problem has received significant attention in recent years due to its affordable complexity compared to the convex formulation. Gradient Descent (GD) is a simple yet efficient baseline algorithm for solving nonconvex optimization problems. The success of GD has been witnessed in many different problems in both theory and practice when it is combined with random initialization. However, previous works on matrix completion require either careful initialization or regularizers to prove the convergence of GD. In this paper, we study the rank-1 symmetric matrix completion and prove that GD converges to the ground truth when small random initialization is used. We show that in a logarithmic number of iterations, the trajectory enters the region where local convergence occurs. We provide an upper bound on the initialization size that is sufficient to guarantee the convergence, and show that a larger initialization can be used as more samples are available. We observe that the implicit regularization effect of GD plays a critical role in the analysis, and for the entire trajectory, it prevents each entry from becoming much larger than the others.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 19 of its 28 references that are in the map. First posted on arXiv 19 Dec 2022.

Builds on

19 of 28 references.

References · 19

  1. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  2. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  3. 2017Implicit Regularization in Matrix Factorizationcited by 318
  4. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  5. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 148
  6. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  7. 2020Implicit Regularization in Deep Learning May Not Be Explainable by Normscited by 118
  8. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  9. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 81
  10. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  11. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  12. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
7 more
  1. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  2. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 68
  3. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  4. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  5. 2020Adversarial Crowdsourcing Through Robust Rank-One Matrix Completioncited by 21
  6. 2019Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workerscited by 11
  7. 2018A Generalized Structured Low-Rank Matrix Completion Algorithm for MR Image Recoverycited by 3

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1; 2025: 1.

4 papers.

  1. 2023Transformers learn through gradual rank increasecited by 52
  2. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  3. 2025Principled Multimodal Representation Learningcited by 19
  4. 2024Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completioncited by 6