math.OCApr 15, 2026

A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity

Authors: Damek Davis, Dmitriy Drusvyatskiy

Organizations: Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA 19104

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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)=12(v+u4)2+u4f(v,u)=\frac{1}{2}(v+u^{4})^{2}+u^{4} near the origin. Left: surface plot. Right: level sets. The solid black curve is the ravine v=−u4v=-u^{4} ; the dashed green line is the null space Q={v=0}\mathsf{Q}=\{v=0\} ; the dashed red line is the range P={u=0}\mathsf{P}=\{u=0\} .
Figure 2: The function g(v,u)=12(v+u2)2+u4g(v,u)=\frac{1}{2}(v+u^{2})^{2}+u^{4} near the origin. Left: surface plot. Right: level sets. The solid black curve is the ravine v=−u2v=-u^{2} ; the dashed green line is Q={v=0}\mathsf{Q}=\{v=0\} ; the dashed red line is P={u=0}\mathsf{P}=\{u=0\} . Compare with Figure 1 : the ravine here has O(∥u∥2)O(\lVert u\rVert^{2}) curvature, matching the nonvanishing cubic coupling P∇3g(0)[eu,eu]=2evP\nabla^{3}g(0)[e_{u},e_{u}]=2e_{v} .
Figure 3: Algorithm 1 on the two quartics from Figures 1 and 2 . Top: convex ff with (η,τ)=(1,0.15)(\eta,\tau)=(1,0.15) ; 6666 iterations. Bottom: nonconvex gg with (η,τ)=(1,0.12)(\eta,\tau)=(1,0.12) ; 8080 iterations. GDPolyak (stepsize 11 , block length 11 , i.e., alternating GD/Polyak every iteration): 8484 iterations on both. GD stepsize 11 . Distance threshold 10−610^{-6} .
Figure 4: DDJ fourth-order benchmarks. Rows: Rosenbrock (distance 10−710^{-7} ), quadratic sensing (Procrustes 10−510^{-5} ), single neuron (surrogate 10−1210^{-12} ). Left: f(xk)−f⋆f(x_{k})-f_{\star} . Right: stop diagnostic. Algorithm 1 : (η,τ)=(0.05,0.01)(\eta,\tau)=(0.05,0.01) , (0.075,0.15)(0.075,0.15) , (1,0.0125)(1,0.0125) . GDPolyak : (stepsize, block) =(0.03,50){}=(0.03,50) , (0.075,200)(0.075,200) , (1,10)(1,10) . GD stepsize: 0.030.03 , 0.0750.075 , 1.51.5 .
More in this topic

Gradient Descent

Gradient descent iteratively updates model parameters to reduce a loss using its slope, with variants for speed, scale, and constraints.

See all 118 papers

Explore similar work

CardsList

  1. A lower bound for stepsize-based acceleration of gradient descent

    Aug 11, 2026Jianhao Ma, Yuxin ChenLearning Rate SchedulingLast-Iterate Convergence

    Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania

  2. Silver Rate Is (Almost) Optimal for Gradient Descent

    Sep 8, 2026Yuhan Ye, Kaizhao LiuLearning Rate SchedulingOptimization Convergence Analysis

    MIT

  3. Convergence of Steepest Descent and Adam under Non-Uniform Smoothness

    May 28, 2026Sharan Vaswani, Yifan Sun, Reza BabanezhadOptimization Convergence AnalysisGradient Descent

    1Simon Fraser University · 2Stony Brook University · 3Samsung AI, Montreal.