← All setups

Strong Growth Finite-Sum Minimization

Descriptions may be stale. Consult the linked Lean sources.

Strong Growth Finite-Sum Minimization

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 component fi:E→R is convex with L-Lipschitz gradient, and F is μ-strongly convex, with L,μ>0. Strong growth requires n−1∑i=1n∥∇fi(x)∥2≤ρ∥∇F(x)∥2 for all x∈E, where ρ≥1. A given point x0∈E is within distance R≥0 of a minimizer x⋆. 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 and smoothness). Each fi is Fréchet differentiable everywhere. 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 convexity). For every x,y∈E and t∈[0,1], F((1−t)x+ty)≤(1−t)F(x)+tF(y)≤−μ2t(1−t)∥x−y∥2.

Assumption 3 (Strong growth). The component gradients satisfy 1n∑i=1n∥∇fi(x)∥2≤ρ∥∇F(x)∥2,x∈E, where ∇F(x)=n−1∑i=1n∇fi(x).

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

Queries may select any component index i∈{1,…,n} and any point x∈E; each reply is the exact component gradient. After the allotted oracle calls, the output x¯ must be measurable and satisfy EP[|F(x¯)−F(x⋆)|]<∞,EP[F(x¯)−F(x⋆)]≤ε.

Results

On a finite-dimensional real inner-product space, f=n−1∑i=1nfi, n≥1, each fi is convex and L-smooth, and f is μ-strongly convex. Globally, n−1∑i∥∇fi(x)∥2≤ρ∥∇f(x)∥2, with L,μ,ε>0, ρ≥1. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R, R≥0. Exact component-gradient access; target E[f(X)−f(x⋆)]≤ε.

Strong-growth finite sums: FiniteSumStrongGrowthStronglyConvex.
Result Oracle complexity Novelty Limitations
(1) StrongGrowthFiniteSumAcceleration (Ours) (⋆⋆⋆) (review) O((m+mκ)log⁡(2+κ)ℓ)
(2) Restarted Katyusha, derived bound (Allen-Zhu 2018, Thm. 4.1) O((n+nκ)ℓ) (1): replaces n by min{n,ρ}, paying log⁡(2+κ). For ρ≤n≤κ, gain ≍n/ρ/log⁡(2+κ) when n≫ρlog2⁡(2+κ). (1) requires global strong growth; loses log⁡(2+κ) when ρ≥n.
(3) SNAG (Hermant et al. 2026, Thm. 3) O(ρLf/μℓ) (1): for ρ≤min{n,κ}, gain ≍ρLf/L/log⁡(2+κ) if ρLf/L≫log2⁡(2+κ). At n=κ=q3, ρ=q, Lf≍L: O(q2log⁡qℓ) versus O(q5/2ℓ). (1) needs convex, smooth components and a finite sum; loses when Lf≲Llog2⁡(2+κ)/ρ in that regime.

Abbr: κ=L/μ, m=min{n,ρ}, ℓ=log⁡(2+LR2/ε); Lf≤L is mean smoothness. Costs count all component-gradient calls, including batches and inner solves; expectation is over algorithmic sampling. ≍ 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.

Lean setup