← All setups

Recovery Fractal Gd Stationarity — Adaptive Gradient Descent with Lipschitz Hessian

Descriptions may be stale. Consult the linked Lean sources.

Adaptive Gradient Descent with Lipschitz Hessian · Lean proof

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.

Proved result

⌈262144⋅(8+log2⁡(2+L⋅Δε2))43⋅(Δ⋅L23⋅ρ16ε116+L⋅Δε+L1117⋅Δ1517⋅ρ217ε2817+1)⌉+

OracleTemplate.Convergence LongTails.Setups.SmoothHessianLipschitzGd.spec
  LongTails.Theorems.RecoveryFractalGdStationarity.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.