← All setups

Accelerated Interpolated Generalized Finite Sum — Interpolated Generalized Smooth Finite Sums

Descriptions may be stale. Consult the linked Lean sources.

Interpolated Generalized Smooth Finite Sums · Lean proof

Interpolated Generalized Smooth Finite Sums

We consider minimizing f(x)=n−1∑i=1nfi(x) on a finite-dimensional real inner product 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. The components share a global minimizer x⋆, with ∥x0−x⋆∥≤R for a given x0∈E and R>0. The oracle returns ∇fi(x) at a queried pair (i,x). Given ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε with probability at least 2/3 over the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, n, L0, L1, R, ε, and x0.

Our assumptions:

Assumption 1 (Component convexity and differentiability). Each fi is differentiable everywhere on E with continuous gradient ∇fi:E→E. 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). For every i∈{1,…,n}, x,y∈E, and M∈R, the segment bound ∥∇fi(x+θ(y−x))∥≤Mfor every θ∈[0,1] implies ∥∇fi(x)−∇fi(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Interpolation and initial distance). There exists x⋆∈E such that fi(x⋆)≤fi(x)for every i∈{1,…,n}, x∈E,∥x0−x⋆∥≤R.

Queries may select any component i∈{1,…,n} and any point x∈E, with each call returning its exact component gradient. After the allotted oracle calls, the output must satisfy P(f(x¯)−f(x⋆)≤ε)≥23, where P is the law of the algorithm’s randomness and x⋆ is a fixed common global minimizer.

Proved result

⌈1073741824⋅(n⋅(1+L12⋅R2)+n⋅L0⋅R2ε)⋅log⁡(2+n+L0⋅R2ε+L12⋅R2)⌉+

OracleTemplate.Convergence LongTails.Setups.InterpolatedGeneralizedFiniteSum.spec
  OracleTemplate.AcceleratedInterpolatedGeneralizedFiniteSum.budget

Relevant previous results

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