← All setups

Hessian Only Finite Sum Third Smooth — Finite-Sum Convex Third-Order Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Finite-Sum Convex Third-Order Smoothness · Lean proof

Finite-Sum Convex Third-Order Smoothness

We consider minimizing f(x)=n−1∑i=1nfi(x) on a finite-dimensional real inner-product space E, where n≥1 is an integer. Each component fi:E→R is convex and three times continuously differentiable, with L-Lipschitz third derivative, where L≥0. A given point x0∈E lies within distance R>0 of a minimizer x⋆; its objective gradient and Hessian have norms bounded by G,H≥0, respectively. A query (i,x) returns (∇fi(x),∇2fi(x)). For ε>0, the goal is a measurable output x¯∈E satisfying P{f(x¯)−f(x⋆)≤ε}≥2/3, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. Derivative norms ∥⋅∥op are the induced operator norms: the Hessian acts from E to E, and the third derivative is a trilinear form on E. The algorithm receives E,n,L,R,ε,G,H, and x0.

Our assumptions:

Assumption 1 (Component convexity and regularity). For every i∈{1,…,n}, the function fi belongs to C3(E;R), and for all x,y∈E and t∈[0,1], fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y). Its third derivative satisfies ∥∇3fi(x)−∇3fi(y)∥op≤L∥x−y∥,x,y∈E.

Assumption 2 (Minimizer and initial bounds). The instance specifies a point x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,∥∇f(x0)∥≤G,∥∇2f(x0)∥op≤H.

The oracle accepts any component index i∈{1,…,n} and any point x∈E, returning the exact component gradient and Hessian together in one call. After the allotted calls, the output x¯ must be measurable with respect to the Borel sets of E and satisfy P{f(x¯)−f(x⋆)≤ε}≥23.

Proved result

274877906944⋅(n+⌈(n4⋅L⋅R4ε)15⌉+)⋅(1+⌈log⁡(2+n+G⋅Rε+H⋅R2ε+L⋅R4ε)⌉+)2

OracleTemplate.Convergence LongTails.Setups.FiniteSumThirdSmoothConvex.spec
  LongTails.Theorems.HessianOnlyFiniteSumThirdSmooth.budget

Relevant previous results

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