← All setups

Accelerated Finite Sum Convex — Smooth Convex Finite-Sum Minimization

Descriptions may be stale. Consult the linked Lean sources.

Smooth Convex Finite-Sum Minimization · Lean proof

Smooth Convex 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 and each fi:E→R is differentiable and convex with an L-Lipschitz gradient, for L>0. A given starting point x0∈E lies within distance R≥0 of a global minimizer x⋆ of F. The oracle returns ∇fi(x) at a queried pair (i,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, L, R, ε, 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 (Component smoothness). Each fi is Fréchet differentiable everywhere on E, and ∥∇fi(x)−∇fi(y)∥≤L∥x−y∥,x,y∈E,i∈{1,…,n}.

Assumption 3 (Initial distance). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,∥x0−x⋆∥≤R.

Queries may select any component i∈{1,…,n} and any point x∈E, and each call returns its exact component gradient. After the allotted oracle calls, the output x¯ must be measurable with respect to the given measurable structure on E, its objective gap must be integrable under P, and it must satisfy EP[F(x¯)−F(x⋆)]≤ε.

Proved result

3⋅n⋅(clog2(clog2(n))+⌈32⋅L⋅R2n⋅ε⌉+)

OracleTemplate.Convergence LongTails.Setups.FiniteSumSmoothAndConvex.spec
  OracleTemplate.FiniteSum.AcceleratedFiniteSumConvex.budget

Relevant previous results