← All setups

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 f:E→R on a finite-dimensional real inner product space E, with induced norm ∥⋅∥. Its Hessian is H-Lipschitz for H>0, and a given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ for Δ≥0. Two exact oracles return (f(x),∇f(x)) and ∇2f(x), respectively. For ε>0 and ρ∈(0,1), the goal is an output x¯∈E satisfying both ∥∇f(x¯)∥≤ε and ⟨v,∇2f(x¯)v⟩≥−Hε∥v∥2 for every v∈E, with probability at least 1−ρ over the algorithm’s randomness.

The optimization problem is infx∈Ef(x). The Hessian ∇2f(x):E→E is a linear operator, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, x0, H, Δ, ε, ρ, and an additional real parameter m≥1; the setup imposes no further condition involving m.

Our assumptions:

Assumption 1 (Hessian regularity). The function f is twice continuously Fréchet differentiable on E, and ∥∇2f(x)−∇2f(y)∥op≤H∥x−y∥,x,y∈E.

Assumption 2 (Initial objective gap). The given point x0 satisfies f(x0)−f(x)≤Δ,x∈E.

Queries to either oracle may be made at any point of E. 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 P({∥∇f(x¯)∥≤ε,⟨v,∇2f(x¯)v⟩≥−Hε∥v∥2for every v∈E})≥1−ρ, where P is the law of the algorithm’s randomness.

Proved result

Oracle 0:⌈2120⋅m13⋅(1+Δ⋅Hε⋅ε)⋅(log⁡(2+(dimR⁡(E)+1)⋅m⋅(1+Δ⋅Hε⋅ε)ρ))2⌉+ Oracle 1:⌈244⋅(1+Δ⋅Hm23⋅ε⋅ε)⌉+

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: O(b+b1/3ΔH/ε3/2) exact-gradient oracle calls and O(1+ΔH/(b2/3ε3/2)) full-Hessian oracle calls, including initialization and output selection, deterministically achieving ∥∇f(x)∥≤ε with NALEN. Here b≥1 is the integer Hessian-refresh period; choose b=max{1,⌊min{m,(1+ΔH/ε3/2)3/2}⌋}.