Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster

Sharan Vaswani, Reza Babanezhad · 2025

Read Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster by Sharan Vaswani, Reza Babanezhad (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-2503-00229.txt.

Introduction

Sharan Vaswani and Reza Babanezhad published a research paper in 2025 on a classic step-size rule that can make gradient descent, the workhorse of machine learning, provably faster. The rule, named for Armijo, picks each step by testing the local slope rather than trusting one global constant. Earlier theory showed only modest, fixed-factor gains from the rule.

The pair prove stronger results under a looser, local form of smoothness. For logistic-style problems, descent with the rule now converges at a fast linear rate where the fixed-step version crawls. For some non-convex problems it matches tailor-made fast methods. They also extend the analysis to the noisy, stochastic version used in practice.

Catalog record

CREATORSharan Vaswani, Reza Babanezhad
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE129 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00229

Browse the full library · About the Tower of Babel

Full text

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

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster Sharan Vaswani, Reza Babanezhad Abstract Armijo line-search ( Armijo-LS ) is a standard method to set the step-size for gradient descent (GD). For smooth functions, Armijo-LS alleviates the need to know the global smoothness constant L L and adapts to the “local” smoothness, enabling GD to converge faster. Existing theoretical analyses show that GD with Armijo-LS ( GD-LS ) can result in constant factor improvements over GD with a 1 / L 1/L step-size (denoted as GD(1/L) ). We strengthen these results and show that if the objective function satisfies a certain non-uniform smoothness condition, GD-LS can result in a faster convergence rate than GD(1/L) . In particular, we prove that for convex objectives corresponding to logistic regression and multi-class classification, GD-LS can converge to the optimum at a linear rate, and hence improves over the sublinear convergence of GD(1/L) . Furthermore, for non-convex objectives satisfying gradient domination (e.g. those corresponding to the softmax policy gradient in RL or generalized linear models with a logistic link function), GD-LS can match the fast convergence of algorithms tailored for these specific settings. Finally, we analyze the convergence of stochastic GD with a stochastic line-search on convex losses under the interpolation assumption. 1 Introduction Gradient descent (GD) ( Cauchy and others, 1847 ) and its stochastic variants are the preferred optimization methods in machine learning. The practical effectiveness of gradient methods heavily relies on the choice of the step-size (“learning rate”) parameter. Backtracking Armijo line-search ( Armijo, 1966 ; Nocedal and Wright, 2006 ) (referred to as Armijo-LS ) is a standard method to set the step-size for gradient descent. Given an initial step-size, the simplest form of Armijo-LS “searches” for the largest step-size that guarantees a sufficient decrease in the function value. When minimizing L -smooth functions using GD, Armijo-LS alleviates the need to know L , the global smoothness constant and enables setting the GD step-size in an adaptive manner. For both L -smooth convex and non-convex functions, GD with Armijo-LS (henceforth GD-LS ) has been shown to match the favorable theoretical guarantees of GD with a constant \nicefrac{{1}}{{L}} step-size (henceforth GD(1/L) ). However, empirically, GD-LS typically results in faster convergence and is consequently, the default choice in practice. One often-cited reason to explain the faster convergence of GD-LS is that it adapts to the “local” smoothness constant L(\theta) near the point \theta , and results in an effective step-size of \nicefrac{{1}}{{L(\theta)}} . In some regions, L(\theta) might be much smaller than the global smoothness L , thus allowing GD-LS to use much bigger step-sizes and consequently lead to faster convergence. Existing works that define notions of local smoothness ( Scheinberg et al., 2014 ; Lu and Mei, 2023 ; Mishkin et al., 2024 ; Fox and Schmidt, , and references there in) can be used to formalize this intuition and show that GD-LS can result in constant factor improvements over GD(1/L) , while having the same rate of convergence. In contrast, we consider a special class of objective functions and show that GD-LS (with a large initial step-size) can result in a provably faster rate of convergence compared to GD(1/L) . In particular, we make the following contributions. Contribution 1. In Section 2 , we introduce a class of functions that satisfy an (L_{0},L_{1}) non-uniform smoothness condition. In particular, we consider functions where the local smoothness constant around a point \theta is given by L(\theta)=L_{0}+L_{1}\,f(\theta) where L_{0} and L_{1} are non-negative constants (and L_{1}=0 corresponds to the standard uniform smoothness). We show that the proposed condition is satisfied by common objectives; for example, both the logistic and exponential losses used for linear classification satisfy the condition with L_{0}=0 and L_{1}\neq 0 . Furthermore, we prove that this condition is also satisfied by non-convex functions corresponding to generalized linear models with a logistic link function, and the softmax policy gradient objective in reinforcement learning. This condition is similar to that proposed in Zhang et al. (2019) to explain the success of normalization and gradient clipping when training neural networks. The difference is that we consider problems where the smoothness is proportional to f(\theta) rather than \left\|\nabla f(\theta)\right\| ( Zhang et al., 2019 ; Zhang et al., 2020 ; Chen et al., 2023 ) . Furthermore, in Section 2 , we show that non-negative, twice-differentiable functions satisfying the non-uniform smoothness condition in Zhang et al. (2019) satisfy the proposed condition. Contribution 2. In Section 3 , we analyze the convergence of GD-LS on functions satisfying the proposed conditions. We first prove that the step-size selected by GD-LS around \theta is lower-bounded by 1/L(\theta) , and hence, GD-LS provably adapts to the local smoothness. We use this to prove Theorem 1 , a meta-theorem that quantifies the convergence rate of GD-LS for both convex and non-convex objectives. Contribution 3. In Section 4 , we instantiate Theorem 1 for non-uniform smooth, convex losses that include logistic regression and multi-class classification with the cross-entropy loss as examples. Specifically, in Corollary 1 , we show that GD-LS (with a sufficiently large initial step-size) converges at an O\left(\left(\nicefrac{{f^{*}}}{{\epsilon}}\right)\,\ln\left(\nicefrac{{1}}{{\epsilon}}\right)\right) rate where f^{*}:=\inf f(\theta) . Hence, when f^{*} is \Theta(\epsilon) , GD-LS converges at an O\left(\ln\left(\nicefrac{{1}}{{\epsilon}}\right)\right) rate, compared to the sublinear O\left(\nicefrac{{1}}{{\epsilon}}\right) convergence of GD(1/L) . We further instantiate this result for logistic regression on linearly separable data, and prove the linear convergence of GD-LS ( Corollary 2 ), thus matching the rate for normalized GD ( Axiotis and Sviridenko, 2023 ) . In Appendix C , we show that GD with the Polyak step-size ( Polyak, 1987 ) can inherit this fast convergence for logistic regression. In comparison to our results, most work exploiting non-uniform smoothness ( Zhang et al., 2019 ; Zhang et al., 2020 ; Koloskova et al., 2023 ; Chen et al., 2023 ; Li et al., 2023 ) requires the knowledge of the corresponding problem-dependent constants. Notable exceptions include Hübler et al. (2024) and ( Vankov et al., 2024 ; Takezawa et al., 2024 ; Gorbunov et al., 2024 ) that consider GD-LS and the Polyak step-size respectively, and aim to minimize the class of non-uniform smooth functions in ( Zhang et al., 2019 ) . In particular, the work in Hübler et al. (2024) considers general non-convex functions and does not demonstrate the algorithm’s adaptivity to the smoothness, nor does it result in a faster rate than GD(1/L) . Moreover, their resulting algorithm requires the knowledge of the non-uniform smoothness constant, making it impractical. On the other hand, ( Vankov et al., 2024 ; Takezawa et al., 2024 ; Gorbunov et al., 2024 ) consider minimizing convex, non-uniform smooth functions using GD with the Polyak step-size. In Section 4 , we show that GD-LS (without any modification) can achieve a similar convergence guarantee as these works. Contribution 4. In Section 5 , we instantiate Theorem 1 for non-convex functions satisfying non-uniform smoothness and gradient domination conditions that guarantee global optimality. Specifically, in Section 5.1 , we analyze the convergence of GD-LS for the softmax policy gradient objective in reinforcement learning ( Mei et al., 2020 ) . In this setting, the linear convergence rate attained by GD-LS is provably better than the \Omega(\nicefrac{{1}}{{\epsilon}}) convergence

Read the complete text