← All setups

Adaptive Gradient Descent with Lipschitz Hessian

Descriptions may be stale. Consult the linked Lean sources.

Adaptive Gradient Descent with Lipschitz Hessian

We consider minimizing a possibly nonconvex, twice continuously differentiable function f:E→R on a finite-dimensional real inner-product space E. The gradient and Hessian are Lipschitz with constants L>0 and ρ≥0, respectively. A given starting point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ≥0. The oracle returns ∇f(x) at x. Adaptive gradient descent must return a queried point x¯ satisfying ∥∇f(x¯)∥≤ε, for ε>0, almost surely under P, the law of the algorithm’s randomness; with no queries it returns x0.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The Hessian ∇2f(x) acts on E. The algorithm receives E, x0, L, ρ, Δ, and ε.

Our assumptions:

Assumption 1 (Smoothness and Hessian regularity). The function f is twice continuously Fréchet differentiable on E. For every x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥.

Assumption 2 (Initial objective gap). The given starting point satisfies f(x0)−f(x)≤Δ,x∈E.

Our formulation is algorithm-specific: we analyze adaptive gradient descent with strictly positive step sizes and an output selected by the smallest observed gradient norm. Queries may be made at any point of E. At iteration k, the method queries xk, receives gk=∇f(xk), and updates xk+1=xk−ηkgk,ηk>0. The step size may depend on the algorithm’s current information, its randomness, and the current reply. Its step-selection rule must return a strictly positive value for every possible reply.

To specify the output exactly, let bk∈E be the stored point and sk∈R its stored squared gradient norm. Initialize b0=x0; the initial value s0 is unrestricted. After each reply, set bk+1={xk,k=0 or ∥gk∥2≤sk,bk,otherwise,sk+1={∥gk∥2,k=0 or ∥gk∥2≤sk,sk,otherwise. After an allotted number K≥0 of oracle calls, the output is x¯=bK. For K≥1, this is the most recently queried point attaining the smallest gradient norm among x0,…,xK−1. The required accuracy is ∥∇f(x¯)∥≤εP-a.s.

Results

On a finite-dimensional real inner-product space, f∈C2 has L-Lipschitz gradient, ρ-Lipschitz Hessian, and f(x0)−f(x)≤Δ for every x, with L,ε>0 and ρ,Δ≥0. Exact gradient calls are counted. The setup requires positive, history-dependent GD steps and the best queried gradient-norm output; the target is ∥∇f(x^)∥≤ε (deterministically for our construction).

Comparison for SmoothHessianLipschitzGd.
Result Oracle complexity Novelty Limitations
(1) AdaptiveSilverHessianLipschitz (Ours) (review) O(1+Tq1/22+T4/5)
(2) GD, step 1/L (Nesterov 2018, sec. 1.2.3) O(1+LΔ/ε2) (1): Cost reduction by min{q−1/22,T1/5} when q≪1, T≫1. Fixed positive L,ρ,Δ: O(ε−21/11) versus O(ε−2) using momentum-free GD. (1) needs Lipschitz Hessian and ρ,Δ in updates; much larger constants. Explicit-budget gain requires q−1>4522, T>2005. No gain when q>1.
(3) Restarted AGD (Li and Lin 2023, Thm. 1, v4); derived bound

O(1+min{T,Tq1/4+T})

For Δ>0, retune with ρ′=max{ρ,ε3/Δ2}; rescale accuracy; AGD requires ρ′ε/82≤L2/16; otherwise use GD.

(1): No established improvement in problem-class complexity. Momentum-free GD analysis; (3) permits momentum and thus lies outside the prescribed GD family. (1): Slower leading term by q−9/44 for 0<q≤1; at ρ=0, T4/5 versus T1/2.
(4) RecoveryFractalGdStationarity (Ours) (review) O(ℓ4/3(1+Tq1/6+T+T15/17q2/17)) gradient calls, including aborted trials and recovery; ℓ=log⁡(2+T).
(5) Restarted AGD (Li and Lin 2023, Thm. 1, v4); derived bound O(1+min{T,Tq1/4+T}). For Δ>0, use ρ′=max{ρ,ε3/Δ2}, tolerance ε/82, and GD if ρ′ε/82>L2/16. (4): No established improvement in problem-class complexity; provides a momentum-free GD guarantee outside (5)’s method family. (4): Leading term worse by q−1/12ℓ4/3 for 0<q≤1; adds mixed term. For q>1, worse than GD.
(6) Fractal Chebyshev GD (LongTails 2026); ρ>0, different restart family O(1+Tq1/9log⁡(2+q−1)+q−1/9) gradient calls. (4): Method-specific exponent 17/9→11/6 at fixed positive L,ρ,Δ. Leading-term ratio q1/18ℓ4/3/log⁡(2+q−1); gain requires q≪1, T≥q−5/12 and sufficiently small ratio. (4) needs Δ in updates; adds T and mixed terms. Larger constants: explicit-budget gain only around q−1>2220.
(7) GD, step 1/L (Nesterov 2018, sec. 1.2.3) O(1+T) gradient calls. (4): For q≪1, T≥q−5/12, cost O(ℓ4/3Tq1/6) versus O(T); gain requires ℓ4/3q1/6≪1. Fixed positive L,ρ,Δ: ε−11/6 up to logs instead of ε−2. (4) needs Lipschitz Hessian and ρ,Δ in updates. Much larger constants: explicit-budget gain needs roughly q−1≳2170.

Abbr: T=LΔ/ε2, q=ρε/L2; L and ρ bound the Lipschitz constants of ∇f and ∇2f; Δ bounds the initial objective gap. GD: gradient descent; AGD: accelerated gradient descent.

Li, Huan, and Zhouchen Lin. 2023. Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ϵ−7/4) Complexity. https://doi.org/10.48550/arXiv.2201.11411.
LongTails: FractalChebyshevGdStationarity. 2026. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/4a914a3/LongTails/Theorems/FractalChebyshevGdStationarity.lean.
Nesterov, Yurii. 2018. Lectures on Convex Optimization. 2nd ed. Vol. 137. Springer Optimization and Its Applications. Springer. https://doi.org/10.1007/978-3-319-91578-4.

Lean setup