← All setups

Cyclic Gradient Interpolation — Cyclic Gradient Under Interpolation

Descriptions may be stale. Consult the linked Lean sources.

Cyclic Gradient Under Interpolation · Lean proof

Cyclic Gradient Under Interpolation

We consider minimizing F(x)=m−1∑i=0m−1fi(x) on a real Hilbert space E, where m≥1 is an integer. Each component fi:E→R is convex and differentiable with an L-Lipschitz gradient, where L>0. The components share a global minimizer x⋆, and the given starting point x0∈E satisfies ∥x0−x⋆∥≤R for R≥0. The oracle returns ∇fi(x) at a queried pair (i,x). Cyclic gradient descent with step size 1/L must return its last iterate x¯ with F(x¯)−F(x⋆)≤ε almost surely under the output law P, for ε>0.

The optimization problem is minx∈EF(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives only E, m, L, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Component convexity and smoothness). Each fi is Fréchet differentiable everywhere on E. For every i∈{0,…,m−1}, 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 (Interpolation and initial distance). There exists x⋆∈E such that fi(x⋆)≤fi(x)for every i∈{0,…,m−1}, x∈E,∥x0−x⋆∥≤R.

The oracle accepts any component index and any point in E and returns the exact component gradient. Our formulation is algorithm-specific: we analyze cyclic gradient descent, initialized at the given point x0. Its updates are ik=kmodm,xk+1=xk−1L∇fik(xk),k=0,1,…. Each update uses one component-gradient call. After an allotted budget of K≥0 calls, with K an integer, the output is the last iterate x¯=xK. The required accuracy is F(x¯)−F(x⋆)=1m∑i=0m−1(fi(x¯)−fi(x⋆))≤εP-a.s. The common minimizer in this requirement is fixed independently of the output; all common minimizers have the same component objective values.

Proved result

m⋅⌈m3⋅L⋅R2ε⌉+

OracleTemplate.Convergence LongTails.Setups.InterpolatedFiniteSum.spec OracleTemplate.CyclicInterpolation.budget

Relevant previous results