← All setups

Pointwise Hessian Stationarity Lower Bound — Stationarity with Exact Hessian Access

Descriptions may be stale. Consult the linked Lean sources.

Stationarity with Exact Hessian Access · Lean proof

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¯)∥]≤ε.

Proved result

⌊Δ⋅L0+L1⋅ε239⋅ε⋅ε⌋+

OracleTemplate.NonConvergence LongTails.Setups.PointwiseHessianStationarity.spec
  LongTails.Theorems.PointwiseHessianStationarityLowerBound.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.