# Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 28 references that are in the map.
- First posted on arXiv 27 Jun 2021.

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

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions](https://mlsanity.com/paper/1605.00405/) (2016)
- [Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot](https://mlsanity.com/paper/1507.05854/) (2015)
- [Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2102.12430/) (2021)
- [Polynomial time guarantees for the Burer-Monteiro method](https://mlsanity.com/paper/1912.01745/) (2019)

## Built on by (most cited first, 30 of 45)

- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Flat minima generalize for low-rank matrix recovery](https://mlsanity.com/paper/2203.03756/) (2022)
- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult](https://mlsanity.com/paper/2310.17087/) (2023)
- [PoLAR: Polar-Decomposed Low-Rank Adapter Representation](https://mlsanity.com/paper/2506.03133/) (2025)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [On the Crucial Role of Initialization for Matrix Factorization](https://mlsanity.com/paper/2410.18965/) (2024)
- [Convergence of Alternating Gradient Descent for Matrix Factorization](https://mlsanity.com/paper/2305.06927/) (2023)
- [Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions](https://mlsanity.com/paper/2203.14383/) (2022)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [Active Self-Supervised Learning: A Few Low-Cost Relationships Are All You Need](https://mlsanity.com/paper/2303.15256/) (2023)
- [Maestro: Uncovering Low-Rank Structures via Trainable Decomposition](https://mlsanity.com/paper/2308.14929/) (2023)
- [A Novel Stochastic Gradient Descent Algorithm for Learning Principal Subspaces](https://mlsanity.com/paper/2212.04025/) (2022)
- [Federated Representation Learning in the Under-Parameterized Regime](https://mlsanity.com/paper/2406.04596/) (2024)
- [Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Region](https://mlsanity.com/paper/2509.25351/) (2025)
- [How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization](https://mlsanity.com/paper/2111.08706/) (2021)
- [Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition](https://mlsanity.com/paper/2204.14067/) (2022)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [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)
- [Characterizing the Training Dynamics of Private Fine-tuning with Langevin diffusion](https://mlsanity.com/paper/2402.18905/) (2024)
- [Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks](https://mlsanity.com/paper/2410.09640/) (2024)
- [BLAST: Block-Level Adaptive Structured Matrices for Efficient Deep Neural Network Inference](https://mlsanity.com/paper/2410.21262/) (2024)
- [On the Benefits of Weight Normalization for Overparameterized Matrix Sensing](https://mlsanity.com/paper/2510.01175/) (2025)
- [Low-Rank Adaptation Redux for Large Models](https://mlsanity.com/paper/2604.21905/) (2026)
- [Balanced LoRA: Removing Parameter Invariance to Accelerate Convergence](https://mlsanity.com/paper/2605.31484/) (2026)

## Abstract (arXiv)

We study the asymmetric low-rank factorization problem: [min_U ∈ ℝm × d, V ∈ ℝn × d frac12|UV^top -Sigma|F2] where Sigma is a given matrix of size m × n and rank d. This is a canonical problem that admits two difficulties in optimization: 1) non-convexity and 2) non-smoothness (due to unbalancedness of U and V). This is also a prototype for more complex problems such as asymmetric matrix sensing and matrix completion. Despite being non-convex and non-smooth, it has been observed empirically that the randomly initialized gradient descent algorithm can solve this problem in polynomial time. Existing theories to explain this phenomenon all require artificial modifications of the algorithm, such as adding noise in each iteration and adding a balancing regularizer to balance the U and V. This paper presents the first proof that shows randomly initialized gradient descent converges to a global minimum of the asymmetric low-rank factorization problem with a polynomial rate. For the proof, we develop 1) a new symmetrization technique to capture the magnitudes of the symmetry and asymmetry, and 2) a quantitative perturbation analysis to approximate matrix derivatives. We believe both are useful for other related non-convex problems.