← All setups

Strong Growth Convex Finite Sum Acceleration — Finite-Sum Convex Strong Growth

Descriptions may be stale. Consult the linked Lean sources.

Finite-Sum Convex Strong Growth · Lean proof

Finite-Sum Convex Strong Growth

We minimize F(x)=n−1∑i=1nfi(x) on a finite-dimensional real inner product space E, where n≥1 is an integer. Each fi:E→R is differentiable and convex with L-Lipschitz gradient, L>0. Strong growth requires n−1∑i=1n∥∇fi(x)∥2≤ρ∥∇F(x)∥2 for every x∈E, with ρ≥1. A given x0∈E satisfies ∥x0−x⋆∥≤R, where R≥0 and x⋆ minimizes F. The oracle returns ∇fi(x) at a queried pair (i,x). For ε>0, the goal is a measurable output x¯∈E with integrable 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 and smoothness). Each fi is Fréchet differentiable everywhere on E. For every i∈{1,…,n}, x,y∈E, and t∈[0,1], fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y),∥∇fi(x)−∇fi(y)∥≤L∥x−y∥.

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

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

The algorithm may query any component index i∈{1,…,n} at any point x∈E; each query returns the exact component gradient. After the allotted component-gradient calls, its output x¯ must be measurable and satisfy EP[F(x¯)−F(x⋆)]≤ε. The gap must be integrable under P. Here x⋆ is a fixed global minimizer; all global minimizers have the same objective value.

Proved result

7000⋅(min{n,⌈1024⋅ρ⌉+}+⌈min{n,⌈1024⋅ρ⌉+}⋅L⋅R2ε⌉+)⋅clog2(⌈232⋅ρ5⌉+)

OracleTemplate.Convergence LongTails.Setups.FiniteSumStrongGrowthConvex.spec
  LongTails.Theorems.StrongGrowthConvexFiniteSumAcceleration.budget

Relevant previous results

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