mlsanityData to 14 Oct 2026

Convergence of Alternating Gradient Descent for Matrix Factorization

arXiv 2305.06927 ↗First posted 11 May 2023cs.LG math.OC stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

We consider alternating gradient descent (AGD) with fixed step size applied to the asymmetric matrix factorization objective. We show that, for a rank-r matrix A ∈ ℝm × n, T = C (fracσ1(A)σr(A))2 log(1/ε) iterations of alternating gradient descent suffice to reach an ε-optimal factorization | A - X YT |2 ≤ ε | A|2 with high probability starting from an atypical random initialization. The factors have rank d ≥ r so that XT∈ℝm × d and YT ∈ℝn × d, and mild overparameterization suffices for the constant C in the iteration complexity T to be an absolute constant. Experiments suggest that our proposed initialization is not merely of theoretical benefit, but rather significantly improves the convergence rate of gradient descent in practice. Our proof is conceptually simple: a uniform Polyak-Lojasiewicz (PL) inequality and uniform Lipschitz smoothness constant are guaranteed for a sufficient number of iterations, starting from our random initialization. Our proof method should be useful for extending and simplifying convergence analyses for a broader class of nonconvex low-rank factorization problems.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 19 of its 28 references that are in the map. First posted on arXiv 11 May 2023.

Builds on

19 of 28 references.

References · 19

  1. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  2. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  3. 2017Implicit Regularization in Matrix Factorizationcited by 322
  4. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  5. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 177
  6. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  7. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  8. 2022Learning threshold neurons via the "edge of stability"cited by 51
  9. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 50
  10. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 45
  11. 2020Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rankcited by 42
  12. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
7 more
  1. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 39
  2. 2018Generalized Canonical Polyadic Tensor Decompositioncited by 34
  3. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  4. 2016First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Ratecited by 32
  5. 2019Stochastic Gradients for Large-Scale Tensor Decompositioncited by 16
  6. 2015Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squarerootcited by 15
  7. 2015The local convexity of solving systems of quadratic equationscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 5; 2026: 2.

12 papers.

  1. 2025PoLAR: Polar-Decomposed Low-Rank Adapter Representationcited by 20
  2. 2024On the Crucial Role of Initialization for Matrix Factorizationcited by 15
  3. 2024Loss Landscape Characterization of Neural Networks without Over-Parametrizationcited by 8
  4. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  5. 2024Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networkscited by 3
  6. 2025Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Fastercited by 3
  7. 2025On the Benefits of Weight Normalization for Overparameterized Matrix Sensingcited by 3
  8. 2025Learning Multi-Index Models with Hyper-Kernel Ridge Regressioncited by 3
  9. 2026Low-Rank Adaptation Redux for Large Modelscited by 3
  10. 2026Balanced LoRA: Removing Parameter Invariance to Accelerate Convergencecited by 3
  11. 2024In-depth Analysis of Low-rank Matrix Factorisation in a Federated Settingcited by 2
  12. 2024Efficient Federated Low Rank Matrix Completioncited by 0