Convergence of Steepest Descent and Adam under Non-Uniform Smoothness

Sharan Vaswani, Yifan Sun, Reza Babanezhad · 2026

Read Convergence of Steepest Descent and Adam under Non-Uniform Smoothness by Sharan Vaswani, Yifan Sun, Reza Babanezhad (2026) 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-2605-30648.txt.

Introduction

Vaswani, Sun, and Babanezhad study steepest descent and Adam under uneven smoothness, where curvature tracks the loss value. The class covers logistic regression, softmax policy gradients, and some neural nets. Under this rule plus gradient dominance, they prove convergence rates for steepest descent, RMSProp, and Adam. Sign descent runs linearly and beats plain descent on separable logistic data and softmax gradients. RMSProp and Adam run linearly on a two-layer net class, and a lower bound shows both beat AdaGrad, AMSGrad, plain descent, and heavy-ball momentum.

Catalog record

CREATORSharan Vaswani, Yifan Sun, Reza Babanezhad
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE198405
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30648

Browse the full library · About the Tower of Babel

Full text

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

Convergence of Steepest Descent and Adam under Non-Uniform Smoothness Sharan Vaswani, Yifan Sun, Reza Babanezhad Abstract Recent work has analyzed the convergence of first-order methods under non-uniform smoothness assumptions that better model the loss landscape in machine learning tasks. We generalize this assumption to objectives whose curvature is an affine function of the objective value. This property is satisfied by a broad class of problems, including logistic regression, generalized linear models with a logistic link function, softmax policy gradient in reinforcement learning, and a class of neural networks. Under this assumption and gradient domination conditions, we establish a general convergence rate for the steepest descent method, and deterministic, diagonal variants of RMSProp and Adam. Our results imply that for logistic regression on separable data and the softmax policy gradient objective, sign GD converges linearly and is provably faster than GD. Furthermore, we show that for a class of two-layer neural networks on separable data, RMSProp and Adam can converge at a linear rate with a constant step-size and momentum parameter. Finally, we present a lower bound demonstrating that, under our assumption, RMSProp and Adam are provably faster than AdaGrad, AMSGrad, gradient descent, and heavy-ball momentum. 1 Introduction Recent works ( 40 ; 38 ; 7 ; 31 ; 11 ; 32 ; 1 ) have studied the convergence of first-order methods under non-uniform smoothness . Unlike the standard smoothness assumption, which imposes a global uniform upper-bound on the Hessian norm, non-uniform smoothness ( NS ) upper-bounds the Hessian locally as a function of the parameter value. For example, 40 proposed that the Hessian norm at any point can be bounded as an affine function of the gradient norm at that point. They empirically showed that this property holds during neural network training under standard loss functions, and leveraged this assumption to justify the role of gradient clipping. Following this, there have been numerous works ( 7 ; 16 ; 32 ; 1 ) relaxing this NS assumption, with the goal of better modeling the loss landscapes arising in machine learning problems. Under such NS assumptions, recent works have revisited the theoretical convergence rates of common first-order methods including gradient descent (GD) with adaptive step-sizes, heavy-ball momentum ( 31 ; 11 ; 32 ; 12 ) , and adaptive gradient methods such as Adam and RMSProp ( 17 ; 33 ; 34 ) (see Appendix A for a detailed review). We focus on a particular form of NS where the spectral norm of the Hessian is upper-bounded by an affine function of the objective value ( 32 ; 1 ) . For twice-differentiable functions, this property strictly generalizes the NS assumption in 40 . Furthermore, this property is satisfied by a broad class of problems, including logistic regression, generalized linear models with a logistic link ( 23 ) , softmax policy gradient in reinforcement learning ( 24 ) , and certain two-layer neural networks ( 29 ; 1 ) . Moreover, unlike the assumption in 40 , the class of functions satisfying this alternative NS assumption is closed under finite-sums and affine transformations ( 1 ) . This enables an easier analysis of finite-sum losses prevalent in machine learning. We note that under this assumption, 32 analyzed GD and demonstrated the advantage of using an Armijo line-search over constant step-sizes. On the other hand, 1 have used this assumption to theoretically characterize the importance of learning rate warm-up. In this paper, we generalize this assumption to handle induced (p,q) operator norms of the Hessian, and refer to the resulting property as (H_{0},H_{1}) - NS . In addition to this assumption, we consider objectives that satisfy a (possibly non-uniform) Łojasiewicz ( NL ) assumption. The NL condition is a gradient domination property implying that the gradient norm is lower-bounded in terms of the function sub-optimality. Hence, minimizing the gradient norm results in minimizing the function value. Consequently, the NL condition is widely used to analyze the global convergence of algorithms ( 14 ) . It is satisfied for convex objectives such as quadratics, the exponential loss on separable data, and structured non-convex losses including the softmax policy gradient objective ( 24 ) , matrix factorization ( 35 ) and sufficiently over-parameterized neural networks ( 19 ; 27 ; 42 ; 18 ) . Working under the (H_{0},H_{1}) - NS and NL assumptions, we derive convergence guarantees for steepest descent, and deterministic, diagonal variants of RMSProp and Adam . To our knowledge, these are the first such results. Our contributions are summarized as follows. Contribution 1: In Section 3 , we derive structural properties of functions satisfying (H_{0},H_{1}) - NS . In particular, we first generalize the results in 32 ; 1 beyond Euclidean norms. This subsequently allows us to derive convergence rates for steepest descent algorithms without any dimension dependence. Furthermore, we prove that (H_{0},H_{1}) - NS implies multiplicative Lipschitz bounds for both the function and the gradient norm. This property enables a new framework for analyzing RMSProp ( 30 ) and Adam ( 15 ) . Contribution 2: In Section 4 , under our NS and NL assumptions, we analyze the convergence of normalized steepest descent ( NSD ) methods including Sign GD and Normalized GD . Our general theorem implies that for logistic regression on separable data and the softmax policy gradient objective, using Sign GD with a constant step-size results in a dimension-free linear convergence rate matching GD with line-search ( 32 ) . For these applications, Sign GD is provably faster than constant step-size GD ( 24 ; 36 ) . Furthermore, our results demonstrate the effectiveness of Sign CD-GS , a specific coordinate descent instantiation of NSD . Sign CD-GS uses the Gauss–Southwell rule ( 25 ) to select the coordinate, and updates it using the sign of its gradient. When minimizing the exponential or logistic loss on separable data, Sign CD-GS converges linearly, matching the rate for a normalized variant of coordinate descent ( 3 ) . Contribution 3 : In Section 5 , we derive convergence rates for the deterministic, diagonal variants of RMSProp and Adam . Our results imply that for a class of two-layer neural networks on separable data, RMSProp and Adam can converge with a constant step-size, and do so at a dimension-free linear rate. Importantly, our analysis does not require any convexity or bounded gradient assumption. In contrast to our setting, previous works ( 17 ; 33 ; 34 ) consider non-convex functions satisfying the NS assumption in 40 , and analyze both deterministic and stochastic variants of Adam . For this class of functions, we show that our proof techniques can also be used to attain faster rates in the deterministic setting. Contribution 4 : In Section 6 , we consider the one-dimensional logistic loss which satisfies our NL and NS assumptions, and for which RMSProp and Adam achieve a linear convergence rate. For this example, we prove a sub-linear lower-bound for GD, heavy-ball momentum and deterministic variants of AdaGrad ( 10 ) and AMSGrad ( 26 ) . Consequently, our results show that these methods are provably slower on this class of functions. This is the first such separation for adaptive gradient methods, and provides theoretical justification for the

Read the complete text