Monotone Hessian Second Order — Hessian-Lipschitz Second-Order Stationarity
Descriptions may be stale. Consult the linked Lean sources.
Hessian-Lipschitz Second-Order Stationarity · Lean proof
Hessian-Lipschitz
Second-Order Stationarity
We consider minimizing a possibly nonconvex, twice continuously
differentiable function on a finite-dimensional
real inner product space , with
induced norm . Its Hessian
is -Lipschitz for , and a given point satisfies for
. Two exact oracles
return and , respectively. For and , the goal is an output satisfying both and
for every
, with probability at least
over the algorithm’s
randomness.
The optimization problem is The Hessian is a linear operator, and denotes the
induced operator norm. The algorithm receives , , , , , , and an additional real parameter
; the setup imposes no
further condition involving .
Our assumptions:
Assumption 1 (Hessian regularity). The function
is twice continuously Fréchet
differentiable on , and
Assumption 2 (Initial objective gap). The given
point satisfies
Queries to either oracle may be made at any point of . The first oracle returns the exact
function value and gradient together; the second returns the exact
Hessian. Calls to these two oracles are counted separately.
After the allotted calls, the output must satisfy where
is the law of the algorithm’s randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.HessianLipschitzSecondOrder.spec
LongTails.Theorems.MonotoneHessianSecondOrder.budget
Relevant previous results
- Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang. Faster Newton Methods for
Convex and Nonconvex Optimization in Gradient Complexity. 2026
(COLT; author version v3). Complexity: exact-gradient oracle calls and full-Hessian oracle calls,
including initialization and output selection, deterministically
achieving with NALEN. Here is the integer Hessian-refresh
period; choose .