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 on a finite-dimensional
real inner-product space . The
gradient and Hessian are Lipschitz with constants and , respectively. A given starting
point satisfies , where
. The oracle returns
at . Adaptive gradient descent must return
a queried point satisfying
, for , almost surely under
, the law of the algorithm’s
randomness; with no queries it returns .
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm. The Hessian acts on . The
algorithm receives , , , , , and .
Our assumptions:
Assumption 1 (Smoothness and Hessian regularity).
The function is twice
continuously Fréchet differentiable on . For every ,
Assumption 2 (Initial objective gap). The given
starting point satisfies
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
. At iteration , the method queries , receives , and updates 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 be the stored point and its stored squared
gradient norm. Initialize ;
the initial value is
unrestricted. After each reply, set After an allotted number of oracle calls, the output is
. For , this is the most recently queried
point attaining the smallest gradient norm among . The required accuracy
is
Proved result
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.