← All setups

Log Free Second Order Third Smooth — Nonconvex Optimization with Lipschitz Third Derivatives

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Lipschitz Third Derivatives · Lean proof

Nonconvex Optimization with Lipschitz Third Derivatives

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 L3-Lipschitz third derivative, where L3>0. A given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ and ∥∇2f(x0)∥op≤H0, where Δ>0 and H0≥0; derivative norms are induced operator norms. Two exact oracles return (f(x),∇f(x)) and ∇2f(x), respectively. 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. The Hessian ∇2f(x) is a linear operator from E to E, and ∇3f(x) is the third derivative viewed as a trilinear form on E. The algorithm receives E, x0, L3, Δ, H0, and ε.

Our assumptions:

Assumption 1 (Third-derivative regularity). The function f belongs to C3(E;R), and ∥∇3f(x)−∇3f(y)∥op≤L3∥x−y∥,x,y∈E.

Assumption 2 (Initial gap and curvature). The given point x0 satisfies f(x0)−f(x)≤Δfor every x∈E,∥∇2f(x0)∥op≤H0.

Both oracles accept queries at any point of E, and their calls are counted separately. After the allotted calls, the output must satisfy ∥∇f(x¯)∥≤εP-a.s.

Proved result

Oracle 0:⌈230⋅(1+Δ⋅L313ε43+log⁡(2+H0⋅Δε2+L3⋅Δ3ε4))⌉+ Oracle 1:⌈230⋅(1+Δ⋅L313ε43+log⁡(2+H0⋅Δε2+L3⋅Δ3ε4))⌉+

OracleTemplate.Convergence LongTails.Setups.ThirdDerivativeSmoothNonconvex.spec
  LongTails.Theorems.LogFreeSecondOrderThirdSmooth.budget

Relevant previous results

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