← All setups

Strong-Growth Second-Order Finite-Sum Optimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a finite-dimensional real inner-product space, F=n−1∑i=1nfi, n≥1, fi∈C2, κ≥1, ρ,ε>0, and F(x0)−F(x)≤Δ for every x. Assume n−1∑i∥∇fi(x)∥2≤κ∥∇F(x)∥2 and n−1∑i∥∇2fi(x)−∇2fi(y)∥2≤ρ2∥x−y∥2. One paired call returns a component gradient and full Hessian. Target: Pr(∥∇F(X)∥≤ε, ∇2F(X)⪰−ρεI)≥2/3.

Comparison for StrongGrowthFiniteSumSecondOrder.
Result Oracle complexity Novelty Limitations
(1) CoupledCubicStrongGrowth (Ours) (⋆⋆⋆) (review) O(κ(d+1)T(1+log⁡T)) paired calls
(2) Full-batch cubic regularization, (Shen et al. 2019), Table 1 O(nT) paired calls; deterministic (1): removes n; asymptotic factor n/[κ(d+1)(1+log⁡T)] when this ratio diverges. (1): adds strong growth and RMS Hessian regularity; probability 2/3 instead of certainty. Worse outside the gain regime; very large leading constant.
(3) STR2 (Shen et al. 2019), Cor. 5.1, Estimator 6 O(n+T[n3/4(1+log⁡T)+nlog⁡(e(d+1)T)]) paired calls, confidence 2/3. Special case: component L1-smoothness and uniform ρ-Hessian Lipschitzness. (1): removes L1; uniform Hessian regularity becomes RMS. On overlap, fixed κ,ρ,Δ, n=ε−1, d=ε−1/4: O(ε−7/4log⁡(1/ε)) versus O(ε−9/4log⁡(1/ε)). (1): adds strong growth; linear dimension cost can lose when κd≳n3/4. Fixed confidence instead of adjustable 1−δ.
(4) PSGD (Roy et al. 2020), Thm. 3.1(a) Gradient-only oracle; half the iterates satisfy second-order accuracy with probability 1−δ. Special case: population gradient smoothness and relative sub-Gaussian gradient tails. (1): selected certified output instead of an unselected collection; drops population gradient smoothness and relative sub-Gaussian tails. (1): requires component Hessians and RMS Hessian regularity; fixed confidence instead of adjustable 1−δ.

Abbr: d=dim⁡E; T=1+ρΔ/ε3/2; Δ≥0 is an initial objective-gap bound. Hessian norms are operator norms. L1 is the component gradient-Lipschitz constant; δ is failure probability. Paired-call bounds count all component evaluations, including refreshes and sampled batches.

Roy, Abhishek, Krishnakumar Balasubramanian, Saeed Ghadimi, and Prasant Mohapatra. 2020. “Escaping Saddle-Point Faster Under Interpolation-Like Conditions.” Advances in Neural Information Processing Systems 33. https://proceedings.neurips.cc/paper/2020/hash/92a08bf918f44ccd961477be30023da1-Abstract.html.
Shen, Zebang, Pan Zhou, Cong Fang, and Alejandro Ribeiro. 2019. A Stochastic Trust Region Method for Non-Convex Minimization. https://arxiv.org/abs/1903.01540v1.

Lean setup