A Local Polyak-Łojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Models

Ziqing Xu [email protected], Hancheng Min [email protected], Salma Tarmoun [email protected], Enrique Mallada [email protected], René Vidal [email protected] · 2025

Read A Local Polyak-Łojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Models by Ziqing Xu [email protected], Hancheng Min [email protected], Salma Tarmoun [email protected], Enrique Mallada [email protected], René Vidal [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11664.txt.

Introduction

Ziqing Xu and four co-authors prove fast training convergence for two-layer linear networks without extreme assumptions, in a paper from 2025. Prior proofs needed tiny steps, huge width, or special starting points. Real training uses none of those crutches, so theory lagged practice.

Classic tools for convergence rates fail globally on such overparameterized models. The team shows both tools hold locally, with constants that depend on current weights. They bound those constants from the starting point, current loss, and traits of the simpler model. The result is a linear convergence rate and a better step size rule, backed by numeric tests.

Catalog record

CREATORZiqing Xu [email protected], Hancheng Min [email protected], Salma Tarmoun [email protected], Enrique Mallada [email protected], René Vidal [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE120 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-11664

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Local Polyak-Łojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Models Ziqing Xu [email protected], Hancheng Min [email protected], Salma Tarmoun [email protected], Enrique Mallada [email protected], René Vidal [email protected] Abstract 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-Łojasiewicz (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. 1 Introduction Neural networks have shown great empirical success in many real-world applications, such as computer vision He et al. 2016 and natural language processing ( Vaswani et al. 2018 ) . However, our theoretical understanding of why neural networks work so well is still scarce. One unsolved question is why neural networks trained via vanilla gradient descent (GD) enjoy fast convergence although their loss landscape is non-convex. This question has motivated recent work which focuses on deriving convergence rates for overparameterized neural networks. However, most prior work on the linear convergence of GD for overparametrized neural networks requires strong assumptions on the step size (infinitesimal), width (infinitely large), initialization (large, spectral), or restrictive choices of the loss function (squared loss) (See Table 1 for details). Derivation of convergence of nonlinear networks requires restrictive assumptions. The work of ( Du et al. 2018b ; Lee et al. 2019 ; Liu et al. 2022 ) studies the convergence of GD for neural networks in the neural tangent kernel (NTK) regime, which requires the network to have large or infinite width and large initialization. However, Chizat et al. 2019 ; Chen et al. 2022 show that the NTK regime limits feature learning, and the generalization performance of neural networks in this regime degrades substantially. To go beyond the NTK regime, Mei et al. 2018 ; Chizat & Bach 2018 ; Sirignano & Spiliopoulos 2020 ; Ding et al. 2022 study convergence of neural networks in the mean-field regime under the assumption of infinite width and infinitesimal step sizes. However, while such analysis can guarantee convergence to a global optimum for a wider range of initializations, it still imposes strong assumptions on the network width (infinite) and step size (infinitesimal). Suboptimal convergence rates of overparametrized linear networks. To relax the assumptions on the width, step size, or initialization, some recent work focused on deriving convergence rates of GD for neural networks with a linear activation function in the context of matrix factorization ( Arora et al. 2018 ; Du et al. 2018b ) and linear regression ( Du & Hu 2019 ; Xu et al. 2023 ) . In these settings, instead of learning a matrix W directly, one learns an overparametrized version of W defined as the product of L matrices W_{1}\cdots W_{L} . For example, in the case L=2 , which is the one we will analyze in this paper, this leads to the following non-overparametrized and overparametrized problems defined, respectively, by \min_{W}\ell_{\mathrm{LS}}(W):=\frac{1}{2}\lVert Y\!-\!XW\rVert_{F}^{2}, (non-overparametrized) and \min_{W_{1},W_{2}}L_{\mathrm{LS}}(W_{1},W_{2}):=\frac{1}{2}\lVert Y\!-\!XW_{1}W_{2}\rVert_{F}^{2}\,, (overparametrized) where X,Y are data matrices, W,W_{1},W_{2} are weight matrices, and \mathrm{LS} stands for least-square objective. Here, overparametrized indicates that, although the function classes represented by XW and XW_{1}W_{2} coincide when the sizes of W_{1} and W_{2} are large enough, XW_{1}W_{2} introduces additional matrices to represent the same function. Therefore, while the non-overparametrized loss above defines a standard linear regression problem, the overparametrized loss can be seen as using a two-layer linear network to solve the regression problem. A classical approach to derive a linear convergence rate for non-convex problems relies on the PL condition 1 1 1 PL condition has been widely used to derive convergence for non-convex problems ( Karimi et al. 2020 ; Arora et al. 2018 ; Min et al. 2021 ; Fridovich-Keil et al. 2023 ; Xu et al. 2023 ) . and the smoothness inequality (see § 2.1 for details). While these two conditions hold globally for non-overparametrized models, they do not hold globally for overparametrized linear networks (see § 2.2 for details). This is because overparametrization skews the gradient through a weight-dependent linear operator \mathcal{T} that acts on \nabla\ell_{\text{LS}} (derived based on chain rule) \displaystyle\nabla L_{\text{LS}}(W_{1},W_{2})=\nabla_{W_{1},W_{2}}W\circ\nabla\ell_{\text{LS}}:=\mathcal{T}(\nabla\ell_{\text{LS}})\,,\quad W=W_{1}W_{2}\,. (1) To circumvent this challenge, existing studies ( Arora et al. 2018 ; Du & Hu 2019 ; Xu et al. 2023 ) use the smoothness inequality of the non-overparametrized model, which holds globally, as a substitute for the one of the overparametrized model. In addition, prior works use different methods and assumptions to derive (local) PL conditions (See Appendix C for details). For example, Arora et al. 2018 impose unrealistic assumptions on the initialization (large margin 2 2 2 The margin is a quantity that measure how close the initialization is to the global minimum. and small imbalance 3 3 3 The imbalance is a quantity that measures the difference between the weights of two adjacent layers. ), while Du & Hu 2019 assume large initialization and large width. Xu et al. 2023 show the overparametrized models satisfy local PL conditions and control these constants using the weights at initialization through careful choices of the step sizes. However, how the initialization scale and width of the network affect these constants is missing. While the aforementioned analyses successfully derive linear convergence rates for overparametrized linear networks, all of them only consider squared loss and do not generalize to other types of loss functions. Moreover, the analysis techniques rely on the smoothness inequality of the non-overparametrized model. Therefore, they lack insight into the optimization geometry of overparameterized problems. Numerically, the actual convergence rate of the loss under the step sizes proposed in all the above work is slow (See § 4.2 for details). Hence, an analysis is needed that establishes the convergence of neural networks trained using GD with a general loss under more relaxed assumptions. Furthermore, this analysis should offer more accurate predictions of the actual rates of convergence. This paper aims to bridge some of these gaps. Table 1: Comparison with prior work Work Loss Step Size Width Initialization Nonlinear networks ( Du et al. 2018b ; Lee et al. 2019 ; Jacot et al. 2018 ; Liu et al. 2022 ; Nguyen & Mondelli 2020 ) Squared loss Finite Large Large ( Mei et al. 2018 ; Chizat & Bach 2018 ; Sirignano & Spiliopoulos 2020 ; Ding et

Read the complete text