# A Local Polyak-Lojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Models

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 35 references that are in the map.
- First posted on arXiv 16 May 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks](https://mlsanity.com/paper/1904.13262/) (2019)
- [Tensor2Tensor for Neural Machine Translation](https://mlsanity.com/paper/1803.07416/) (2018)
- [Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology](https://mlsanity.com/paper/2002.07867/) (2020)
- [Width Provably Matters in Optimization for Deep Linear Neural Networks](https://mlsanity.com/paper/1901.08572/) (2019)
- [Overparameterization of deep ResNet: zero loss and mean-field analysis](https://mlsanity.com/paper/2105.14417/) (2021)
- [Convergence of gradient descent for learning linear neural networks](https://mlsanity.com/paper/2108.02040/) (2021)
- [On Feature Learning in Neural Networks with Global Convergence Guarantees](https://mlsanity.com/paper/2204.10782/) (2022)
- [Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth](https://mlsanity.com/paper/2409.19791/) (2024)
- [Spectral Compressed Sensing via Structured Matrix Completion](https://mlsanity.com/paper/1304.4610/) (2013)
- [Convergence and Implicit Bias of Gradient Flow on Overparametrized Linear Networks](https://mlsanity.com/paper/2105.06351/) (2021)
- [Gradient Descent Provably Solves Nonlinear Tomographic Reconstruction](https://mlsanity.com/paper/2310.03956/) (2023)

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

- [From Sublinear to Linear: Local Convergence in Finite-Width Networks via Locally Polyak-Lojasiewicz Regions](https://mlsanity.com/paper/2507.21429/) (2025)
- [SDS-LoRA: Overcoming Anisotropic Gradient Scaling in Low-Rank Adaptation](https://mlsanity.com/paper/2606.16454/) (2026)
- [Gradient Flow Convergence Guarantee for General Neural Network Architectures](https://mlsanity.com/paper/2509.23887/) (2025)
- [The Optimization Landscape of Carath'eodory Decomposition of Toeplitz Covariances](https://mlsanity.com/paper/2511.01605/) (2025)

## Abstract (arXiv)

Most prior work on the convergence of gradient descent (GD) for overparameterized neural networks relies on strong assumptions on the step size (infinitesimal), the hidden-layer width (infinite), or the initialization (large, spectral, balanced). Recent efforts to relax these assumptions focus on two-layer linear networks trained with the squared loss. In this work, we derive a linear convergence rate for training two-layer linear neural networks with GD for general losses and under relaxed assumptions on the step size, width, and initialization. A key challenge in deriving this result is that classical ingredients for deriving convergence rates for nonconvex problems, such as the Polyak-Lojasiewicz (PL) condition and Descent Lemma, do not hold globally for overparameterized neural networks. Here, we prove that these two conditions hold locally with local constants that depend on the weights. Then, we provide bounds on these local constants, which depend on the initialization of the weights, the current loss, and the global PL and smoothness constants of the non-overparameterized model. Based on these bounds, we derive a linear convergence rate for GD. Our convergence analysis not only improves upon prior results but also suggests a better choice for the step size, as verified through our numerical experiments.