← All setups

Energy Hessian Reuse — Stationarity with Gradient-Dependent Third Derivatives

Descriptions may be stale. Consult the linked Lean sources.

Stationarity with Gradient-Dependent Third Derivatives · Lean proof

Stationarity with Gradient-Dependent Third Derivatives

We consider a possibly nonconvex objective f:E→R on a finite-dimensional real inner product space E. The function is three times continuously differentiable, with its third derivative bounded by L0+L1∥∇f(x)∥ at each x∈E, where L0>0 and L1≥0. A given starting point x0∈E has objective gap at most Δ>0 above the infimum and gradient norm at most G0≥0. Two exact oracles return the gradient and Hessian. For ε>0, the goal is an output x¯∈E satisfying ∥∇f(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The underlying optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and derivative norms ∥⋅∥op are the induced operator norms. The algorithm receives E, x0, L0, L1, Δ, G0, ε, and an integer m≥1.

Our assumptions:

Assumption 1 (Third-derivative bound). The function f belongs to C3(E;R) and satisfies ∥∇3f(x)∥op≤L0+L1∥∇f(x)∥,x∈E. Here ∇3f(x) denotes the trilinear third derivative of f, equivalently the second derivative of its gradient under the inner product identification.

Assumption 2 (Initial bounds). The given point x0 satisfies f(x0)−f(x)≤Δfor every x∈E,∥∇f(x0)∥≤G0.

Queries to either oracle may be made at any point of E. The gradient oracle returns ∇f(x) at x. The Hessian oracle returns ∇2f(x) at x, as a linear operator from E to E. Gradient and Hessian calls are counted separately.

After the allotted calls to each oracle, the output must satisfy ∥∇f(x¯)∥≤εP-a.s.

Proved result

Oracle 0:⌈log⁡(1+L1⋅G0m⋅L0)log⁡(43)⌉++(⌈27000⋅Δ⋅(m⋅L0)ε⋅ε+15000⋅Δ⋅(m⋅L1)ε⌉++m+74) Oracle 1:⌈log⁡(1+L1⋅G0m⋅L0)log⁡(43)⌉++(⌈54000⋅Δ⋅L0mε⋅ε+30000⋅Δ⋅L1mε⌉++146)

OracleTemplate.Convergence LongTails.Setups.GradientDependentHessian.spec LongTails.Theorems.EnergyHessianReuse.budget

Relevant previous results

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