← All setups

Generalized Smooth Finite-Sum Minimization

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smooth Finite-Sum Minimization

We consider minimizing F(x)=n−1∑i=1nfi(x) on a real Hilbert 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. A global minimizer x⋆ satisfies bounds on its distance from a given starting point x0∈E, the initial objective gap, and the average component-gradient norm at x⋆. At a query (i,x), the oracle returns (fi(x),∇fi(x)). For ε>0, the goal is a measurable output x¯∈E 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∈EF(x). The norm ∥⋅∥ is induced by the inner product on E, which is equipped with a measurable structure. The algorithm receives E, n, L0, L1, G≥0, R>0, Δ>0, ε>0, and x0.

Our assumptions:

Assumption 1 (Component convexity). 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). Each fi is Fréchet differentiable everywhere, and ∇fi:E→E is continuous. For every i∈{1,…,n}, x,y∈E, and M∈R satisfying ∥∇fi(x+θ(y−x))∥≤Mfor all θ∈[0,1], we have ∥∇fi(x)−∇fi(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Minimizer and initial bounds). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ,1n∑i=1n∥∇fi(x⋆)∥≤G.

The algorithm may query any component at any point in E; each query returns the exact component value and gradient together. After the allotted oracle calls, its output x¯ must be measurable, its objective gap must be integrable under P, and it must satisfy EP[F(x¯)−F(x⋆)]≤ε.

Results

On a real Hilbert space, F=n−1∑i=1nfi, n≥1, with convex fi and continuous gradients satisfying ∥∇fi(x)−∇fi(y)∥≤(L0+L1supz∈[x,y]∥∇fi(z)∥)∥x−y∥. Here L0,R,Δ,ε>0 and L1,G≥0; some minimizer x⋆ satisfies ∥x0−x⋆∥≤R, F(x0)−F(x⋆)≤Δ, and n−1∑i∥∇fi(x⋆)∥≤G. Exact component value–gradient queries are available. The target is a measurable returned point with integrable gap and ∫(F(out(ω))−F(x⋆))dP(ω)≤ε, where P is the algorithm’s probability law.

Generalized-smooth finite sums: GeneralizedSmoothFiniteSum.
Result Oracle complexity Novelty Limitations
(1) LocalFiniteSumAcceleration (Ours) (⋆⋆⋆) (review) O(n(1+L1R)ℓ2+n(L0+L1G)R2/εℓ) component value–gradient calls, including trials and selection.
(2) Varag (Lan et al. 2019, Thm. 1). Derived bound on B(x0,R); finite-dimensional overlap. O(nlog⁡(1+n)+eL1Rn(L0+L1G)R2/ε) component gradients; includes n initialization queries. Ball projection is closed-form. (1): eL1R becomes ℓ in the accuracy term. Total gain when eL1R≫ℓ and eL1RT/n≫(1+L1R)ℓ2. For T=n(L1R)2, L1R≥1: O(nlog⁡(1+n)+nL1ReL1R) becomes O(nL1Rℓ2). (1): for L1R=O(1), pays ℓ on the accuracy term and ℓ2 versus log⁡(1+n) on the n term; additionally needs values, G,Δ.
(3) (L0,L1)-SGD (Gorbunov et al. 2024, Thm. 7.2). Special case: G=0 on Rd. O(1+L0R2/ε) component gradients for mink≤NE[min{τ,F(xk)−F(x⋆)}]≤ε; informative only for ε<τ. (1): untruncated expected returned gap; permits G>0. At G=0, cheaper even for this weaker criterion when L0R2/ε≫n(1+L1R)2ℓ4, with gain at least of order L0R2/(nε)/ℓ2. (1): needs component values and Δ in addition on G=0.

Abbr: ℓ=1+log⁡(1+Δ/ε); T=(L0+L1G)R2/ε; [x,y] is the line segment; τ=νL0/(4nL12), where ν=e−ν>0, with τ=+∞ when L1=0; N is the number of SGD iterations. E denotes expectation over the sampled component indices; ≫ denotes asymptotic domination.

Gorbunov, Eduard, Nazarii Tupitsa, Sayantan Choudhury, et al. 2024. Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity. https://doi.org/10.48550/arXiv.2409.14989.
Lan, Guanghui, Zhize Li, and Yi Zhou. 2019. “A Unified Variance-Reduced Accelerated Gradient Method for Convex Optimization.” Advances in Neural Information Processing Systems 32. https://proceedings.neurips.cc/paper_files/paper/2019/hash/add5aebfcb33a2206b6497d53bc4f309-Abstract.html.

Lean setup