Minimization with Minimizer-Anchored Hessian Regularity
Descriptions may be stale. Consult the linked Lean sources.
Minimization with Minimizer-Anchored Hessian Regularity
We consider minimizing a differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Strong convexity). For every
Assumption 2 (Differentiability and smoothness).
Both
Assumption 3 (Initial distance and Hessian
regularity). There exists
Queries may be made at any point of
Results
On a real Hilbert space of finite dimension
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) SpectralGradientQuadraticConvergence (Ours) (review) | |||
| (2) Derived bound: AGD warmup (Bubeck 2015, Thm. 3.18) + forward-difference Newton | Same anchored Hessian condition; |
(1): matches the quadratic-phase order using scalar gradient steps and quadratic windows; no established problem-class improvement. | (1): warmup bound at
least a |
| (3) AGD (Bubeck 2015, Thm. 3.18) | (1): for fixed |
(1) needs anchored
Hessian regularity, finite dimension, and known |
|
| (4) Silver stepsizes (Altschuler and Parrilo 2023, Thm. 1.1) | (1): for fixed |
(1) needs anchored
Hessian regularity, finite dimension, and known |
Abbr: