← All setups

Recursive Gradient Nonconvex — Finite-Sum Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Finite-Sum Nonconvex Optimization · Lean proof

Finite-Sum Nonconvex Optimization

We consider minimizing F(x)=n−1∑i=1nfi(x) on a real Hilbert space E, where n≥1 and the differentiable components fi:E→R may be nonconvex. Their gradients satisfy a mean-square Lipschitz bound with constant L>0. At a given starting point x0∈E, the objective lies within Δ≥0 of a global lower bound. The oracle returns ∇fi(x) at a queried index i and point x. For ε>0, the goal is a measurable output x¯∈E with EP[∥∇F(x¯)∥2]≤ε2, where P is the law of the algorithm’s randomness.

The optimization problem is infx∈EF(x). The norm ∥⋅∥ is induced by the inner product on E, which is equipped with a measurable structure. The algorithm receives E, n, L, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Mean-square smoothness). Each component fi is Fréchet differentiable everywhere on E, and 1n∑i=1n∥∇fi(x)−∇fi(y)∥2≤L2∥x−y∥2,x,y∈E. Consequently, the objective gradient is ∇F(x)=1n∑i=1n∇fi(x).

Assumption 2 (Lower bound and initial gap). There exists ℓ∈R such that F(x)≥ℓfor every x∈E,F(x0)−ℓ≤Δ.

Queries may use any index i∈{1,…,n} and any point x∈E; each query returns one exact component gradient. After the allotted oracle calls, the output x¯ must be measurable, its squared gradient norm must be integrable under P, and it must satisfy EP[∥∇F(x¯)∥2]≤ε2.

Proved result

5⋅n+⌈20⋅n⋅L⋅Δε2⌉+

OracleTemplate.Convergence LongTails.Setups.FiniteSumSmoothNonconvex.spec OracleTemplate.NonconvexFiniteSum.budget

Relevant previous results