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
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness and Hessian regularity).
The function
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
To specify the output exactly, let
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AdaptiveSilverHessianLipschitz (Ours) (review) | |||
| (2) GD, step |
(1): Cost reduction by
|
(1) needs Lipschitz
Hessian and |
|
| (3) Restarted AGD (Li and Lin 2023, Thm. 1, v4); derived bound | For |
(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 |
| (4) RecoveryFractalGdStationarity (Ours) (review) | |||
| (5) Restarted AGD (Li and Lin 2023, Thm. 1, v4); derived bound | (4): No established improvement in problem-class complexity; provides a momentum-free GD guarantee outside (5)’s method family. | (4): Leading term worse
by |
|
| (6) Fractal Chebyshev GD
(LongTails
2026); |
(4): Method-specific
exponent |
(4) needs |
|
| (7) GD, step |
(4): For |
(4) needs Lipschitz
Hessian and |
Abbr: