← All setups

Finite Sum Nondual Convex — Finite-Sum Minimization on an \(\ell_1\) Ball

Descriptions may be stale. Consult the linked Lean sources.

Finite-Sum Minimization on an \(\ell_1\) Ball · Lean proof

Finite-Sum Minimization on an ℓ1 Ball

We consider minimizing F(x)=n−1∑i=1nfi(x) over C={x∈Rd:∥x∥1≤R}, where d,n are positive integers and R>0. Each component fi:Rd→R is convex and differentiable, with an L-Lipschitz gradient in the Euclidean norm, where L>0. The oracle returns ∇fi(x) at a queried component i and feasible point x∈C. For ε>0, the goal is a measurable output x¯∈C with integrable objective gap satisfying EP[F(x¯)−F(x⋆)]≤ε, where x⋆ minimizes F on C and P is the law of the algorithm’s randomness.

The constraint uses ∥x∥1=∑j=1d|xj|, while ∥⋅∥2 denotes the Euclidean norm. The optimization problem is minx∈CF(x). The algorithm receives d,n,L,R, and ε.

Our assumptions:

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

Assumption 2 (Component smoothness). Each fi is differentiable everywhere on Rd, and ∥∇fi(x)−∇fi(y)∥2≤L∥x−y∥2,x,y∈Rd.

Oracle queries consist of a chosen index i∈{1,…,n} and a point x∈C. The smoothness and convexity conditions hold on the entire ambient space, although queries are restricted to C.

Continuity of F and compactness of C ensure that a constrained minimizer exists. Fix x⋆∈C satisfying F(x⋆)≤F(x)for every x∈C. After the allotted oracle calls, the output must be a measurable C-valued random variable. Its objective gap must satisfy EP[|F(x¯)−F(x⋆)|]<∞,EP[F(x¯)−F(x⋆)]≤ε.

Proved result

1099511627776⋅n⋅(1+⌈(L⋅R2n⋅ε)13⌉+)⋅(1+Nat.log2(2+d+n+⌈L⋅R2ε⌉+))4

OracleTemplate.Convergence LongTails.Setups.FiniteSumNondualSmoothConvex.spec
  LongTails.Theorems.FiniteSumNondualConvex.budget

Relevant previous results

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