← All setups

Finite-Sum Minimization on an \(\ell_1\) Ball

Descriptions may be stale. Consult the linked Lean sources.

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⋆)]≤ε.

Results

F=n−1∑i=1nfi on Q={x∈Rd:∥x∥1≤R}, with d,n≥1 and L,R,ε>0. Each fi is globally convex, differentiable, and has an L-Lipschitz Euclidean gradient. Queries return exact component gradients at feasible points. Target: measurable x^∈Q with integrable gap and ∫[F(x^(ω))−F(x⋆)]dP(ω)≤ε, where x⋆∈arg⁡minQF and P is the execution law.

Finite-sum optimization on an ℓ1 ball: FiniteSumNondualSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) FiniteSumNondualConvex (Ours) (⋆⋆) (review) O((n+n2/3T1/3)ℓ4)
(2) Varag (Lan et al. 2019), Thm. 1; projected full-gradient initialization O(nlog⁡(2n)+nT); includes n initialization calls (1): gain factor (T/n)1/6/ℓ4 when T≫nℓ24. At T=n4: O(n2ℓ4) versus O(n5/2). (1): extra logarithmic cost for T≲n; exact selectors and cut-emptiness tests have no efficient implementation guarantee, unlike (2).
(3) SP-Prox (Loginov et al. 2026), Prop. E.8, applied to F O(n[1+(Tlog⁡(2d))1/3log7/3⁡(2+Tlog⁡(2d))]) (1): leading n dependence improves by n1/3 up to logarithms; total-cost gain when T≥n and n≫ℓ12. (1) guarantees expectation only; (3) is deterministic. Extra logarithms can hurt when n is polylogarithmic.

Abbr: T=LR2/ε; ℓ=log⁡(2+d+n+T). Costs count component-gradient calls; one gradient of F costs n calls. P denotes the probability law of algorithmic and oracle seeds.

Lan, Guanghui, Zhize Li, and Yi Zhou. 2019. A Unified Variance-Reduced Accelerated Gradient Method for Convex Optimization. https://arxiv.org/abs/1905.12412v3.
Loginov, Timofei, Alexander Gasnikov, Yuriy Dorn, et al. 2026. The Complexity of Convex Optimization with Mismatched Geometry. https://arxiv.org/html/2609.32910v1.

Lean setup