← All setups

Coupled Cubic Strong Growth — Strong-Growth Second-Order Finite-Sum Optimization

Descriptions may be stale. Consult the linked Lean sources.

Strong-Growth Second-Order Finite-Sum Optimization · Lean proof

Strong-Growth Second-Order Finite-Sum Optimization

We consider minimizing F=n−1∑i=1nfi on a finite-dimensional real inner product space E, with n≥1 components fi:E→R. The twice continuously differentiable components satisfy strong growth and a mean-square Hessian Lipschitz bound with constant ρ>0. The objective may be nonconvex, and a given point x0∈E has bounded objective gap. The oracle returns (∇fi(x),∇2fi(x)) at a queried index i and point x. For ε>0, the goal is an output x¯∈E satisfying both ∥∇F(x¯)∥≤ε and ⟨v,∇2F(x¯)v⟩≥−ρε∥v∥2 for every v∈E, with probability at least 2/3 under P, the law of the algorithm’s randomness.

The optimization problem is infx∈EF(x),F(x)=1n∑i=1nfi(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. Hessians are linear operators from E to E. The algorithm receives E, n, x0, and the parameters κ≥1,ρ>0,Δ≥0,ε>0.

Our assumptions:

Assumption 1 (Second-order regularity). Each component fi is twice continuously differentiable. For every x,y∈E, 1n∑i=1n∥∇2fi(x)−∇2fi(y)∥op2≤ρ2∥x−y∥2.

Assumption 2 (Strong growth). For every x∈E, 1n∑i=1n∥∇fi(x)∥2≤κ∥∇F(x)∥2.

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

Queries may use any index i∈{1,…,n} and any point x∈E. Each oracle call returns the exact component gradient and Hessian together; this pair counts as one call.

After the allotted oracle calls, the required simultaneous accuracy criterion is P({∥∇F(x¯)∥≤ε,⟨v,∇2F(x¯)v⟩≥−ρε∥v∥2for every v∈E})≥23. The event displayed here must be measurable under P.

Proved result

⌈1020⋅κ⋅(dimR⁡(E)+1)⌉+⋅(Nat.log2(3⋅(⌈16000⋅ρ⋅Δε⋅ε⌉++1))+1)⋅(⌈16000⋅ρ⋅Δε⋅ε⌉++1)

OracleTemplate.Convergence LongTails.Setups.StrongGrowthFiniteSumSecondOrder.spec
  LongTails.Theorems.CoupledCubicStrongGrowth.budget

Relevant previous results

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