Research map / Optimization / Nonconvex and smooth optimization
Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves GD and Nesterov's accelerated gradient converge linearly for rectangular matrix factorization and two-layer linear networks under an unbalanced initialization (large X0, zero Y0), with NAG achieving O(κ log 1/ε) iterations and width only needing to be at least the rank.
Problem
Global convergence rates of first-order methods (GD, NAG) for overparameterized rectangular matrix factorization and linear neural networks, where prior results needed balanced small random initialization and excessive widths or only covered GD/AltGD.
Approach
Use an unbalanced initialization X0 = cAΦ, Y0 = 0 so that the residual dynamics contract on the column space of A; the linear part of GD/NAG then contracts at rates governed by cond(X0), yielding GD O(κ²) and NAG O(κ) iteration complexity, extended to linear networks with width ≥ rank.
Key results
- Theorem 1: GD reaches ε-optimal residual in T = O(d²κ²/(τ²(d−r+1)²) log(C/ε)) iterations under unbalanced initialization, matching AltGD of Ward and Kolda (2023).
- Theorem 2: NAG attains O(dκ/(τ(d−r+1)) log(C/ε)) iterations, improving the κ dependence from quadratic to linear, the best known for first-order rectangular factorization.
- For linear networks with initialization (13) or (14), NAG converges at rate (1−1/(2√κ₂))^t with width only ≥ r or ≥ d_out + Ω(log 1/δ), removing the excessive width requirements of prior work.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use NAG instead of GD | Rectangular matrix factorization with unbalanced initialization · Rectangular matrix factorization | iteration complexity: O(d2(d − r + 1)−2κ2 log 1/ϵ) -> O(d(d − r + 1)−1κ log 1/ϵ) | Helped |
| use NAG instead of GD | Linear neural networks · Linear neural networks | convergence rate: O(κ) rather than O(κ) for NAG versus GD dependence is described as O(√κ) rather than O(κ) | Helped |
| orthonormalize LΦ to initialize X0 (ablation) | NAG for linear neural networks · Linear neural networks | iteration complexity: O(√(λmax(DD⊤)/λmin(DD⊤)) log 1/ϵ) | Helped |
| increase the initialization scale c beyond a sufficiently large value (ablation) | GD and NAG for matrix factorization and linear neural networks · Matrix factorization and linear neural networks | convergence rate | No clear effect |
| vary c2 in X0 = c1AΦ1, Y0 = c2Φ2 (ablation) | GD and NAG for matrix factorization and linear neural networks · Matrix factorization and linear neural networks | convergence rate | No clear effect |
| use GD instead of AltGD with the same initialization and step size | Matrix factorization and linear neural networks · Matrix factorization and linear neural networks | loss | No clear effect |
Surprising findings
- The authors note that their GD rate (quasi-strongly convex in Y with X fixed) matches that of QSC functions, and conjecture their rates are tight, but do not prove it.
Limitations
- Analysis assumes exact rank-r target matrix A and Y0 = 0 (exact unbalanced initialization).
- Linear neural network results rely on the interpolation assumption L = AD and two-layer linear networks only; nonlinear activations not covered.
- Requires sufficiently large constant c in the initialization, and the high-probability guarantee depends on overparameterization d ≥ r − 1 + Ω(log 1/δ).
Experimental setup
Metrics: Frobenius norm residual loss vs iteration iteration complexity
Baselines: GD AltGD GD with 1/L step NAG (Liu et al. 2022) HB (Wang et al. 2021) GD (Hu et al. 2020) GD (Du and Hu 2019)
Builds on: Ward and Kolda 2023 unbalanced initialization Nesterov accelerated gradient Du and Hu 2019 Liu et al. 2022 NAG for linear networks Wang et al. 2021 heavy ball for linear networks
Closest papers by meaning
- Convergence of Alternating Gradient Descent for Matrix Factorization (NeurIPS 2023 · similarity 0.93)
- On the Crucial Role of Initialization for Matrix Factorization (ICLR 2025 · similarity 0.91)
- Block Acceleration Without Momentum: On Optimal Stepsizes of Block Gradient Descent for Least-Squares (ICML 2024 · similarity 0.88)
- In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting (AAAI 2025 · similarity 0.88)
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.88)
- Nesterov acceleration despite very noisy gradients (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.