← All setups

Expected Interpolated Generalized Finite Sum Lower Bound — 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 Euclidean space Rd, where n≥2 is the number of components and d is the dimension. Each fi:Rd→R is convex and (L0,L1)-smooth, with L0>0 and L1≥0, and has a differentiable gradient. The components share a minimizer x⋆ satisfying ∥x⋆∥≤R and F(0)−F(x⋆)≤Δ, where R>0 and Δ>0. At a queried pair (i,x), the oracle returns (fi(x),∇fi(x)). For ε>0, the goal is an output x¯ 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∈RdF(x). We use the Euclidean norm and its induced operator norms, denoted by ∥⋅∥ and ∥⋅∥op, respectively. The algorithm receives all parameters d,n,L0,L1,R,Δ,ε; the component functions are accessed through the oracle. The parameter regime is n,d∈N,n≥2,L0>0,L1≥0,R>0,ε>0,2ε≤Δ,4nε≤L0R2,d≥⌈280(1+n+L1R+L0R2ε)24⌉.

Our assumptions:

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

Assumption 2 (Generalized smoothness). Each fi is differentiable everywhere, and ∇fi:Rd→Rd is Fréchet differentiable everywhere. Its Hessian satisfies ∥∇2fi(x)∥op≤L0+L1∥∇fi(x)∥,i∈{1,…,n},x∈Rd.

Assumption 3 (Interpolation and reference bounds). There exists x⋆∈Rd such that fi(x⋆)≤fi(x)for every i∈{1,…,n}, x∈Rd,∥x⋆∥≤R,F(0)−F(x⋆)≤Δ. The origin is a reference point for these bounds, rather than a prescribed algorithm initialization.

Each oracle call selects any component i∈{1,…,n} and any point x∈Rd and returns the exact pair (fi(x),∇fi(x)). After the allotted calls, the output x¯∈Rd must satisfy EP[|F(x¯)−F(x⋆)|]<∞,EP[F(x¯)−F(x⋆)]≤ε. Here x⋆ is a fixed common minimizer of the components; all such minimizers have the same value of F.

Proved result

⌊n+n⋅L0⋅R2ε+n⋅L1⋅R+n⋅(L1⋅R)231000000000⋅(1+log⁡(2+n+L1⋅R+L0⋅R2ε))2⌋+

OracleTemplate.NonConvergence LongTails.Setups.ExpectedInterpolatedGeneralizedFiniteSum.spec
  LongTails.Theorems.ExpectedInterpolatedGeneralizedFiniteSumLowerBound.budget

Relevant previous results

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