Davis, Drusvyatskiy, and Jiang showed that gradient descent with an adaptive stepsize converges locally at a nearly-linear rate for smooth functions that grow at least quartically away from their minimizers. The argument is intricate, relying on monitoring the performance of the algorithm relative to a certain manifold of slow growth -- called the ravine. In this work, we provide a direct Lyapunov-based argument that bypasses these difficulties when the objective is in addition convex and a has a unique minimizer. As a byproduct of the argument, we obtain a more adaptive variant than the original algorithm with encouraging numerical performance.
Figures & tables
Figure 1: The function f(v,u)=21(v+u4)2+u4 near the origin. Left: surface plot. Right: level sets. The solid black curve is the ravine v=−u4 ; the dashed green line is the null space Q={v=0} ; the dashed red line is the range P={u=0} .
Figure 2: The function g(v,u)=21(v+u2)2+u4 near the origin. Left: surface plot. Right: level sets. The solid black curve is the ravine v=−u2 ; the dashed green line is Q={v=0} ; the dashed red line is P={u=0} . Compare with Figure 1 : the ravine here has O(∥u∥2) curvature, matching the nonvanishing cubic coupling P∇3g(0)[eu,eu]=2ev .
Figure 3: Algorithm 1 on the two quartics from Figures 1 and 2 . Top: convex f with (η,τ)=(1,0.15) ; 66 iterations. Bottom: nonconvex g with (η,τ)=(1,0.12) ; 80 iterations. GDPolyak (stepsize 1 , block length 1 , i.e., alternating GD/Polyak every iteration): 84 iterations on both. GD stepsize 1 . Distance threshold 10−6 .
Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of O(T−1) (where T denotes the number of iterations) to O(T−log2(1+2)) using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical Ω(T−2) benchmark for general first-order methods. In this work, we present a new lower bound of Ω(T−1.9319) for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal O(T−2) convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.
Jianhao Ma, Yuxin Chen
Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania
We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing psil=log2(1+2), we prove an Ω(n−psil−O(loglogn/logn)) non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error Ω(n−1+psil2psil−O(loglogn/logn)). Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.
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.
Sharan Vaswani, Yifan Sun, Reza Babanezhad
1Simon Fraser University · 2Stony Brook University · 3Samsung AI, Montreal.