mlsanityData to 7 Oct 2026

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

arXiv 2106.14289 ↗First posted 27 Jun 2021math.OC cs.LG stat.MLcited by 44

Not on the map. Why?

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.

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

Builds on

17 of 28 references.

References · 17

  1. 2017How to Escape Saddle Points Efficientlycited by 284
  2. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  3. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
  4. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  5. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  6. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  7. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 81
  8. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  9. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  10. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  11. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
  12. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
5 more
  1. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 37
  2. 2016Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regionscited by 33
  3. 2015Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squarerootcited by 15
  4. 2021Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorizationcited by 15
  5. 2019Polynomial time guarantees for the Burer-Monteiro methodcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 9; 2023: 11; 2024: 10; 2025: 8; 2026: 3.

44 papers.

Sort:

  1. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 48
  2. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  3. 2023The Ideal Continual Learner: An Agent That Never Forgetscited by 34
  4. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  5. 2022Flat minima generalize for low-rank matrix recoverycited by 28
  6. 2023Matrix Compression via Randomized Low Rank and Low Precision Factorizationcited by 25
  7. 2023Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapultcited by 23
  8. 2025PoLAR: Polar-Decomposed Low-Rank Adapter Representationcited by 19
  9. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  10. 2024On the Crucial Role of Initialization for Matrix Factorizationcited by 15
  11. 2023Convergence of Alternating Gradient Descent for Matrix Factorizationcited by 12
  12. 2022Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructionscited by 11
32 more
  1. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  2. 2023Active Self-Supervised Learning: A Few Low-Cost Relationships Are All You Needcited by 9
  3. 2023Maestro: Uncovering Low-Rank Structures via Trainable Decompositioncited by 8
  4. 2022A Novel Stochastic Gradient Descent Algorithm for Learning Principal Subspacescited by 7
  5. 2024Federated Representation Learning in the Under-Parameterized Regimecited by 7
  6. 2021How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorizationcited by 5
  7. 2022Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decompositioncited by 5
  8. 2025Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Regioncited by 5
  9. 2022Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decompositioncited by 4
  10. 2022Rank-1 Matrix Completion with Gradient Descent and Small Random Initializationcited by 4
  11. 2024Characterizing the Training Dynamics of Private Fine-tuning with Langevin diffusioncited by 4
  12. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 3
  13. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
  14. 2024Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networkscited by 3
  15. 2025On the Benefits of Weight Normalization for Overparameterized Matrix Sensingcited by 3
  16. 2023Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbationscited by 2
  17. 2024In-depth Analysis of Low-rank Matrix Factorisation in a Federated Settingcited by 2
  18. 2024BLAST: Block-Level Adaptive Structured Matrices for Efficient Deep Neural Network Inferencecited by 2
  19. 2026Low-Rank Adaptation Redux for Large Modelscited by 2
  20. 2026Balanced LoRA: Removing Parameter Invariance to Accelerate Convergencecited by 2
  21. 2023Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensingcited by 1
  22. 2024Reweighted Solutions for Weighted Low Rank Approximationcited by 1
  23. 2025HRP: High-Rank Preheating for Superior LoRA Initializationcited by 1
  24. 2025Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descentcited by 1
  25. 2023Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensingcited by 0
  26. 2024On subdifferential chain rule of matrix factorization and beyondcited by 0
  27. 2024On Multi-Stage Loss Dynamics in Neural Networks: Mechanisms of Plateau and Descent Stagescited by 0
  28. 2024Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problemcited by 0
  29. 2025Global Convergence Analysis of Vanilla Gradient Descent for Asymmetric Matrix Completioncited by 0
  30. 2025Towards Reliable and Generalizable Differentially Private Machine Learning (Extended Version)cited by 0
  31. 2025Block Coordinate Descent for Neural Networks Provably Finds Global Minimacited by 0
  32. 2026Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamicscited by 0