← All setups

Finite-Sum Convex Strong Growth

Descriptions may be stale. Consult the linked Lean sources.

Finite-Sum Convex Strong Growth

We minimize F(x)=n−1∑i=1nfi(x) on a finite-dimensional real inner product space E, where n≥1 is an integer. Each fi:E→R is differentiable and convex with L-Lipschitz gradient, L>0. Strong growth requires n−1∑i=1n∥∇fi(x)∥2≤ρ∥∇F(x)∥2 for every x∈E, with ρ≥1. A given x0∈E satisfies ∥x0−x⋆∥≤R, where R≥0 and x⋆ minimizes F. The oracle returns ∇fi(x) at a queried pair (i,x). For ε>0, the goal is a measurable output x¯∈E with integrable 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 and smoothness). Each fi is Fréchet differentiable everywhere on E. For every i∈{1,…,n}, x,y∈E, and t∈[0,1], fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y),∥∇fi(x)−∇fi(y)∥≤L∥x−y∥.

Assumption 2 (Strong growth). For every x∈E, 1n∑i=1n∥∇fi(x)∥2≤ρ∥∇F(x)∥2,∇F(x)=1n∑i=1n∇fi(x).

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

The algorithm may query any component index i∈{1,…,n} at any point x∈E; each query returns the exact component gradient. After the allotted component-gradient calls, its output x¯ must be measurable and satisfy EP[F(x¯)−F(x⋆)]≤ε. The gap must be integrable under P. Here x⋆ is a fixed global minimizer; all global minimizers have the same objective value.

Results

On a finite-dimensional real inner-product space, f=n−1∑i=1nfi, n≥1, with convex differentiable L-smooth components and n−1∑i∥∇fi(x)∥2≤ρ∥∇f(x)∥2 globally. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R; L,ε>0, ρ≥1, R≥0. Exact indexed component gradients are available. The target is ∫[f(X(ω))−f(x⋆)]dP(ω)≤ε, with measurable output and integrable gap, where P is the algorithm’s probability law. Costs count all component-gradient evaluations, including reuse and inner solves.

Sufficient upper-bound budgets for FiniteSumStrongGrowthConvex.
Result Oracle complexity Novelty Limitations
(1) StrongGrowthConvexFiniteSumAcceleration (Ours) (⋆⋆⋆) (review) O((min{n,ρ}+min{n,ρ}T)ℓρ)
(2) SNAG (Hermant et al. 2026), Thm. 3, (8) O(1+ρLfR2/ε) (1): rate gain ≍ρLf/L/ℓρ when ρ≤n, ρLf/L≫ℓρ2, LfR2/ε≫ℓρ2. At ρ=q, n=T=q3, Lf=L: O(q2log⁡q) versus O(q5/2). (1) needs convex smooth components and finite-sum reuse; adds ℓρ. Can lose when Lf≲Lℓρ2/ρ.
(3) Katyusha + AdaptReg (Allen-Zhu 2018), Cor. 3.5 O(nℓT+nT) (1): rate gain at least ≍n/ρ/ℓρ when ρℓρ2≪n≲T. At ρ=q, n=T=q3: O(q2log⁡q) versus O(q3log⁡q). (1) needs strong growth; adds ℓρ to the accelerated term, losing that factor when ρ≥n and T≫nℓT2.
(4) Proximal STORM (LongTails 2026) O((ρ+ρ3/4L¯R2/ε)ℓρ); same-index pairs cost two component calls. (1): ρ1/2 instead of ρ3/4 in the accuracy term for ρ≤n, L¯=L. At ρ=q, n=T=q3: O(q2log⁡q) versus O(q9/4log⁡q). (1) needs convex components and finite sums. Its accuracy term is worse when L¯<L/ρ and ρ≤n.
(5) Derived bound (Novoselov et al. 2026), Thm. 5.1 O(1+TℓT); serial sample-reuse specialization, one worker, one query per round, unlimited IID sample pool. (1): for ρ≤n and T≫ρ, replaces linear T dependence with ρT, retaining ρℓρ. At ρ=q, n=T=q3: O(q2log⁡q) versus O(q3log⁡q). (1) needs strong growth and a finite sum; (5) covers general interpolating populations without a strong-growth constant.

Abbr: T=LR2/ε; ℓρ=1+log⁡ρ; ℓT=1+log⁡(1+T). Lf≤L is the mean’s gradient Lipschitz constant; L¯≤L satisfies n−1∑i∥∇fi(x)−∇fi(y)∥2≤L¯2∥x−y∥2. In (4), Γ2=ρ−1. In the examples q→∞. ≍ denotes equality up to universal factors.

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.
Hermant, Julien, Marien Renaud, Jean-François Aujol, Charles Dossal, and Aude Rondepierre. 2026. Gradient Correlation Is a Key Ingredient to Accelerate SGD with Momentum. https://doi.org/10.48550/arXiv.2410.07870.
LongTails: ProximalStormStrongGrowth. 2026. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/ProximalStormStrongGrowth.lean.
Novoselov, Kirill, Yuriy Dorn, Darina Dvinskikh, and Alexander Gasnikov. 2026. The Minimax Complexity of Federated Optimization Under Interpolation: The Role of Oracle Models. https://doi.org/10.48550/arXiv.2610.38354.

Lean setup