← All setups

Stationarity with Exact Hessian Access

Descriptions may be stale. Consult the linked Lean sources.

Stationarity with Exact Hessian Access

We seek approximate stationarity of a possibly nonconvex function f:Rd→R, where d is a nonnegative integer. The function is three times continuously differentiable, with third-derivative norm bounded by L0+L1∥∇f(x)∥ at each point x, where L0,L1≥0 and L0+L1>0. At the reference point x0=0, the objective gap above the infimum is at most Δ>0 and the gradient norm is at most G≥0. The oracle returns the exact value, gradient, and Hessian. For ε>0, the goal is a measurable output x¯ with EP∥∇f(x¯)∥≤ε, where P is the law of the algorithm’s randomness.

The underlying optimization problem is infx∈Rdf(x). We use the Euclidean norm on Rd. Derivative norms ∥⋅∥op are the induced operator norms; in particular, ∇2f(x) is a linear operator on Rd, and ∇3f(x) is a trilinear form. The algorithm receives d,L0,L1,Δ,G, and ε.

The parameter regime is restricted by 16ε≤G,ρ:=ΔL0+L1εε3/2≥239,d≥2140(1+⌈ρ⌉)4. Here ⌈ρ⌉ is the least integer greater than or equal to ρ.

Our assumptions:

Assumption 1 (Third-derivative bound). The function f belongs to C3(Rd;R) and satisfies ∥∇3f(x)∥op≤L0+L1∥∇f(x)∥,x∈Rd.

Assumption 2 (Initial objective and gradient control). At the reference point x0=0, f(x0)−f(x)≤Δfor every x∈Rd,∥∇f(x0)∥≤G.

Queries may be made at any x∈Rd. Each oracle call returns (f(x),∇f(x),∇2f(x)). After the allotted oracle calls, the output x¯∈Rd must be measurable under P, its gradient norm must be integrable, and it must satisfy EP[∥∇f(x¯)∥]≤ε.

Results

f:Rd→R is C3, with ∥D3f(x)∥≤L0+L1∥∇f(x)∥, f(0)−inff≤Δ, and ∥∇f(0)∥≤G. Here L0,L1≥0, L0+L1>0, Δ,ε>0, G≥16ε, S≥239, and d≥2140(1+⌈S⌉)4; S is defined below. Each query returns exact (f,∇f,∇2f); the setup imposes no algorithm restriction. The target is measurable X with integrable gradient norm and ∫∥∇f(X(ω))∥dP(ω)≤ε, for the algorithm’s seed law P. The paired bounds match in their polynomial terms; the additive logarithm in (2) is not matched by (1).

Stationarity under pointwise Hessian growth: PointwiseHessianStationarity.
Result Oracle complexity Novelty Limitations

(1) PointwiseHessianStationarityLowerBound (Ours) (⋆⋆⋆) (review)

Lower bound

Necessary: Ω(S) joint calls. Failure for every randomized adaptive algorithm at every integer budget b≤⌊S/239⌋; instance independent of the realized seed.

(2) PointwiseHessianStationarity (Ours) (review)

Upper bound

Sufficient joint calls:

O(S+log(2+L1GL0+L1ε)).

(3) (Carmon et al. 2020), Theorem 2, p=2

Lower bound; Lipschitz-Hessian subclass

Necessary: Ω(ΔL0ε−3/2), L0>0. Randomized algorithms, even with all derivatives; d≳1+T2log⁡(2+T). (1): Necessary budget increases by 1+L1ε/L0; polynomial gain when L1ε≫L0. Scope: also covers L0=0. (1): Requires dimension of order S4, rather than T2log⁡(2+T); also needs G≥16ε and S≥239.

(4) Cubic Newton (Fang et al. 2026), Corollary 1

Upper bound; pointwise condition

Sufficient joint calls, including backtracking:

O(S+log(2+L1GL0+L13/2Δ)). Use σinit=L0+L1ε, δ=L0ε+L1ε; for L0=0, substitute L0′=L1ε.

(2): Matches known polynomial rate, with a different additive logarithm; formalizes the transfer to a joint oracle. (2): Needs L0,L1,Δ,G,ε; larger leading constant. Loses the ∇2f⪰−δI guarantee and parameter-free updates; restricted to the stated G,S,d regime.

Abbr: S=ΔL0+L1εε−3/2≍ΔL0ε−3/2+ΔL1ε−1; T=ΔL0ε−3/2. D3f denotes the third derivative with operator norm; ∇2f is the Hessian; δ is curvature tolerance; σinit is the initial cubic regularization parameter. O and Ω suppress universal constants; ≳ and ≍ are comparisons up to universal constants.

Carmon, Yair, John C. Duchi, Oliver Hinder, and Aaron Sidford. 2020. “Lower Bounds for Finding Stationary Points I.” Mathematical Programming 184: 71–120. https://doi.org/10.1007/s10107-019-01406-y.
Fang, Shaoying, Naoki Marumo, and Akiko Takeda. 2026. Parameter-Free Cubic-Regularized Newton Method: Sharp Complexity and Generalized Smoothness. https://doi.org/10.48550/arXiv.2607.10741.

Lean setup