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

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

## Key facts

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

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

- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [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)
- [Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networks](https://mlsanity.com/paper/2001.05992/) (2020)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Width Provably Matters in Optimization for Deep Linear Neural Networks](https://mlsanity.com/paper/1901.08572/) (2019)
- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [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)
- [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020)
- [Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult](https://mlsanity.com/paper/2310.17087/) (2023)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network](https://mlsanity.com/paper/2010.01618/) (2020)
- [General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds](https://mlsanity.com/paper/2104.10356/) (2021)
- [Convergence of Alternating Gradient Descent for Matrix Factorization](https://mlsanity.com/paper/2305.06927/) (2023)
- [Local and Global Linear Convergence of General Low-rank Matrix Recovery Problems](https://mlsanity.com/paper/2104.13348/) (2021)
- [A Convergence Analysis of Nesterov's Accelerated Gradient Method in Training Deep Linear Neural Networks](https://mlsanity.com/paper/2204.08306/) (2022)

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

- [Preconditioning Benefits of Spectral Orthogonalization in Muon](https://mlsanity.com/paper/2601.13474/) (2026)
- [PoLAR: Polar-Decomposed Low-Rank Adapter Representation](https://mlsanity.com/paper/2506.03133/) (2025)
- [Low-Rank Adaptation Redux for Large Models](https://mlsanity.com/paper/2604.21905/) (2026)

## 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.