← All setups

Smooth Convex Finite-Sum Minimization

Descriptions may be stale. Consult the linked Lean sources.

Smooth Convex 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 and each fi:E→R is differentiable and convex with an L-Lipschitz gradient, for L>0. A given starting point x0∈E lies within distance R≥0 of a global minimizer x⋆ of F. The oracle returns ∇fi(x) at a queried pair (i,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, L, R, ε, 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 (Component smoothness). Each fi is Fréchet differentiable everywhere on E, and ∥∇fi(x)−∇fi(y)∥≤L∥x−y∥,x,y∈E,i∈{1,…,n}.

Assumption 3 (Initial distance). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,∥x0−x⋆∥≤R.

Queries may select any component i∈{1,…,n} and any point x∈E, and each call returns its exact component gradient. After the allotted oracle calls, the output x¯ must be measurable with respect to the given measurable structure on E, its objective gap must be integrable under P, and it must satisfy EP[F(x¯)−F(x⋆)]≤ε.

Results

F=n−1∑i=1nfi on a real Hilbert space E equipped with a measurable structure; n≥1, each fi is convex with L-Lipschitz gradient, L>0. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R, R≥0. One oracle call returns an exact component gradient. Target: measurable output x^ with integrable gap and ∫[F(x^(ω))−F(x⋆)]dP(ω)≤ε, ε>0, where P is the algorithm’s sampling law. The setup imposes no algorithm restriction.

Finite-sum smooth convex optimization: FiniteSumSmoothAndConvex.
Result Oracle complexity Novelty Limitations
(1) AcceleratedFiniteSumConvex (Ours) (review) O(n[1+log⁡log⁡(n+2)]+nLR2/ε)
(2) SvrgConvex (Ours) (review) O(1+nlog⁡(1+LR2/ε)+LR2/ε)
(3) VRADA (Song et al. 2021, Thm. 1, (9)–(11)). E=Rd; l=0, σ=0, m=n. O(n[1+log⁡log⁡(n+2)]+nLR2/ε) (1): Matches known rate; Lean formalization on Hilbert spaces. (2): Smaller startup when 1≪T≪log⁡n. (2): T instead of nT for high accuracy. (1), (2) do not cover the additional composite objective supported by (3).
(4) ANITA (Li 2022, Thm. 1, Cor. 1). E=Rd.

O(n[1+min{log+LR2εn,log⁡n}]+nLR2/ε)

Expected call count.

(1): Intermediate-accuracy savings for nlog⁡n≲T≲nlog2⁡n; at T=n, O(nlog⁡log⁡n) versus (4)’s O(nlog⁡n) for the shared expected-gap target. (1): At T≤n, O(nlog⁡log⁡n) versus (4)’s O(n). Epoch average instead of last iterate; ε needed for stopping, while (4)’s updates are accuracy-independent.
(5) SVRG++ (Allen-Zhu and Yuan 2016, Thm. 4.1). E=Rd, Ψ=0, m0=1. O(n[1+log⁡(1+LR2/ε)]+LR2/ε) (1): At T=n, O(nlog⁡log⁡n) versus (5)’s O(nlog⁡n); accuracy term nT instead of T when T>n. (2): Matches known rate; dimension-free Lean formalization. (1), (2) omit the composite term supported by (5).
(6) SVRG++ (Allen-Zhu and Yuan 2016, Thm. 4.1). E=Rd, Ψ=0; m0=⌈LR2/Δ⌉, 0<ε<Δ. O(n[1+log⁡(Δ/ε)]+LR2/ε) (2): Matches known rate when Δ≍LR2. (2): Uses log⁡(1+LR2/ε) instead of 1+log⁡(Δ/ε); can lose when Δ≪LR2. No composite term.
(7) Katyusha + AdaptReg (Allen-Zhu 2018, Cor. 3.5). E=Rd, ψ=0; 0<ε<Δ. O(n[1+log⁡(Δ/ε)]+nLR2/ε) (2): No established improvement. (2): T instead of nT; up to T/n higher total cost for T≫n. (1), (2) omit the composite term supported by (7).

Abbr: n: component count; L: component smoothness; R: initial-distance bound; ε: expected-gap tolerance; T=LR2/ε; Δ=F(x0)−F(x⋆)≤LR2/2; log+⁡u=max{0,log⁡u} (zero at u=0). Costs count component gradients, including full-gradient refreshes; (4) counts calls in expectation. l,Ψ,ψ: optional convex composite terms; σ: strong-convexity parameter; m,m0: epoch-length parameters.

Allen-Zhu, Zeyuan. 2018. “Katyusha: The First Direct Acceleration of Stochastic Gradient Methods.” Journal of Machine Learning Research 18 (221): 1–51. https://jmlr.org/papers/v18/16-410.html.
Allen-Zhu, Zeyuan, and Yang Yuan. 2016. “Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives.” In Proceedings of the 33rd International Conference on Machine Learning, edited by Maria Florina Balcan and Kilian Q. Weinberger, vol. 48. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v48/allen-zhub16.html.
Li, Zhize. 2022. ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method. https://doi.org/10.48550/arXiv.2103.11333.
Song, Chaobing, Yong Jiang, and Yi Ma. 2021. Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization. https://doi.org/10.48550/arXiv.2006.10281.

Lean setup