# Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion

arXiv: https://arxiv.org/abs/2402.06756 · HTML: https://mlsanity.com/paper/2402.06756/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 9 Feb 2024.

## Builds on (most cited first, 15 of 15)

- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [Understanding Deflation Process in Over-parametrized Tensor Decomposition](https://mlsanity.com/paper/2106.06573/) (2021)
- [Beyond Lazy Training for Over-parameterized Tensor Decomposition](https://mlsanity.com/paper/2010.11356/) (2020)
- [Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA](https://mlsanity.com/paper/1711.01742/) (2017)
- [Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations](https://mlsanity.com/paper/1712.09203/) (2017)
- [Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition](https://mlsanity.com/paper/2210.00346/) (2022)
- [Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization](https://mlsanity.com/paper/2212.09396/) (2022)
- [Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?](https://mlsanity.com/paper/2302.10963/) (2023)

## Built on by (most cited first, 6 of 6)

- [Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity](https://mlsanity.com/paper/2408.13276/) (2024)
- [On the Benefits of Weight Normalization for Overparameterized Matrix Sensing](https://mlsanity.com/paper/2510.01175/) (2025)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)
- [KITINet: KInetic Theory Inspired Inter-Channel Information Exchange for Residual Networks](https://mlsanity.com/paper/2505.17919/) (2025)
- [Global Convergence Analysis of Vanilla Gradient Descent for Asymmetric Matrix Completion](https://mlsanity.com/paper/2508.09685/) (2025)
- [One-Sided Matrix Completion from Ultra-Sparse Samples](https://mlsanity.com/paper/2601.12213/) (2026)

## Abstract (arXiv)

We study the problem of symmetric matrix completion, where the goal is to reconstruct a positive semidefinite matrix rmX^star ∈ ℝd× d of rank-r, parameterized by rmUrmUtop, from only a subset of its observed entries. We show that the vanilla gradient descent (GD) with small initialization provably converges to the ground truth rmX^star without requiring any explicit regularization. This convergence result holds true even in the over-parameterized scenario, where the true rank r is unknown and conservatively over-estimated by a search rank r'gg r. The existing results for this problem either require explicit regularization, a sufficiently accurate initial point, or exact knowledge of the true rank r. In the over-parameterized regime where r'≥ r, we show that, with widetildeOmega(dr9) observations, GD with an initial point |rmU0| ≤ ε converges near-linearly to an ε-neighborhood of rmX^star. Consequently, smaller initial points result in increasingly accurate solutions. Surprisingly, neither the convergence rate nor the final accuracy depends on the over-parameterized search rank r', and they are only governed by the true rank r. In the exactly-parameterized regime where r'=r, we further enhance this result by proving that GD converges at a faster rate to achieve an arbitrarily small accuracy ε>0, provided the initial point satisfies |rmU0| = O(1/d). At the crux of our method lies a novel weakly-coupled leave-one-out analysis, which allows us to establish the global convergence of GD, extending beyond what was previously possible using the classical leave-one-out analysis.