← All setups

Local Finite Sum Acceleration — Generalized Smooth Finite-Sum Minimization

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smooth Finite-Sum Minimization · Lean proof

Generalized Smooth Finite-Sum Minimization

We consider minimizing F(x)=n−1∑i=1nfi(x) on a real Hilbert space E, where n≥1 is an integer. Each component fi:E→R is convex, continuously differentiable, and (L0,L1)-smooth, with L0>0 and L1≥0. A global minimizer x⋆ satisfies bounds on its distance from a given starting point x0∈E, the initial objective gap, and the average component-gradient norm at x⋆. At a query (i,x), the oracle returns (fi(x),∇fi(x)). For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying EP[F(x¯)−F(x⋆)]≤ε, 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, which is equipped with a measurable structure. The algorithm receives E, n, L0, L1, G≥0, R>0, Δ>0, ε>0, and x0.

Our assumptions:

Assumption 1 (Component convexity). For every i∈{1,…,n}, x,y∈E, and t∈[0,1], fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y).

Assumption 2 (Generalized smoothness). Each fi is Fréchet differentiable everywhere, and ∇fi:E→E is continuous. For every i∈{1,…,n}, x,y∈E, and M∈R satisfying ∥∇fi(x+θ(y−x))∥≤Mfor all θ∈[0,1], we have ∥∇fi(x)−∇fi(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Minimizer and initial bounds). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ,1n∑i=1n∥∇fi(x⋆)∥≤G.

The algorithm may query any component at any point in E; each query returns the exact component value and gradient together. After the allotted oracle calls, its output x¯ must be measurable, its objective gap must be integrable under P, and it must satisfy EP[F(x¯)−F(x⋆)]≤ε.

Proved result

⌈16777216⋅(n⋅(1+L1⋅R)⋅(log⁡(2+Δε))2+n⋅(L0+L1⋅G)⋅R2ε⋅log⁡(2+Δε))⌉+

OracleTemplate.Convergence LongTails.Setups.GeneralizedSmoothFiniteSum.spec
  OracleTemplate.GeneralizedFiniteSum.LocalFiniteSumAcceleration.budget

Relevant previous results

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