mlsanityData to 7 Oct 2026

Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks

arXiv 2410.09640 ↗First posted 12 Oct 2024cs.LG math.OC stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

We study the convergence rate of first-order methods for rectangular matrix factorization, which is a canonical nonconvex optimization problem. Specifically, given a rank-r matrix A∈ℝm× n, we prove that gradient descent (GD) can find a pair of ε-optimal solutions XT∈ℝm× d and YT∈ℝn× d, where d≥ r, satisfying lVertXTYT^top-ArVertF≤εlVertArVertF in T=O(kappa2logfrac1ε) iterations with high probability, where kappa denotes the condition number of A. Furthermore, we prove that Nesterov's accelerated gradient (NAG) attains an iteration complexity of O(kappalogfrac1ε), which is the best-known bound of first-order methods for rectangular matrix factorization. Different from small balanced random initialization in the existing literature, we adopt an unbalanced initialization, where X0 is large and Y0 is 0. Moreover, our initialization and analysis can be further extended to linear neural networks, where we prove that NAG can also attain an accelerated linear convergence rate. In particular, we only require the width of the network to be greater than or equal to the rank of the output label matrix. In contrast, previous results achieving the same rate require excessive widths that additionally depend on the condition number and the rank of the input data matrix.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 20 of its 36 references that are in the map. First posted on arXiv 12 Oct 2024.

Builds on

20 of 36 references.

References · 20

  1. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
  2. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  3. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  4. 2020Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networkscited by 73
  5. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  6. 2019Width Provably Matters in Optimization for Deep Linear Neural Networkscited by 52
  7. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 48
  8. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  9. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
  10. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
  11. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  12. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
8 more
  1. 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 27
  2. 2023Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapultcited by 23
  3. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  4. 2020A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Networkcited by 18
  5. 2021General Low-rank Matrix Optimization: Geometric Analysis and Sharper Boundscited by 12
  6. 2023Convergence of Alternating Gradient Descent for Matrix Factorizationcited by 12
  7. 2021Local and Global Linear Convergence of General Low-rank Matrix Recovery Problemscited by 8
  8. 2022A Convergence Analysis of Nesterov's Accelerated Gradient Method in Training Deep Linear Neural Networkscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2026Preconditioning Benefits of Spectral Orthogonalization in Muoncited by 28
  2. 2025PoLAR: Polar-Decomposed Low-Rank Adapter Representationcited by 19
  3. 2026Low-Rank Adaptation Redux for Large Modelscited by 2