← All setups

Gradient Only Third Order Acceleration — Gradient-Only Third-Order Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Gradient-Only Third-Order Nonconvex Optimization · Lean proof

Gradient-Only Third-Order Nonconvex Optimization

We consider minimizing a possibly nonconvex function f:E→R on a finite-dimensional real inner product space E. The function is three times continuously differentiable, with L1-Lipschitz gradient and L3-Lipschitz third derivative in the induced operator norm, where L1,L3>0. A given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ>0. The oracle returns ∇f(x) at x. For ε>0, the goal is an output x¯∈E satisfying ∥∇f(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm, including for multilinear forms. In particular, ∇3f(x) is a trilinear form on E. The algorithm receives E, x0, L1, L3, Δ, and ε.

Our assumptions:

Assumption 1 (Smoothness). The function f belongs to C3(E;R), and its gradient satisfies ∥∇f(x)−∇f(y)∥≤L1∥x−y∥,x,y∈E.

Assumption 2 (Third-derivative regularity). The third derivative satisfies ∥∇3f(x)−∇3f(y)∥op≤L3∥x−y∥,x,y∈E.

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

Queries may be made at any point of E. After the allotted gradient calls, the output must satisfy the first-order stationarity criterion ∥∇f(x¯)∥≤εP-a.s.

Proved result

(⌊2048⋅Δ⋅L313ε43⌋++1)⋅(97⋅⌈L1L313⋅ε23+4⋅log⁡(1+200⋅(L1+4⋅L313⋅ε23)⋅Δε2)⌉++290)

OracleTemplate.Convergence LongTails.Setups.GradientOnlyThirdOrderNonconvex.spec
  OracleTemplate.GradientOnlyThirdOrderAcceleration.budget

Relevant previous results

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