← All setups

Interpolated Generalized Smooth Finite Sums

Descriptions may be stale. Consult the linked Lean sources.

Interpolated Generalized Smooth Finite Sums

We consider minimizing 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, continuously differentiable, and (L0,L1)-smooth, with L0>0 and L1≥0. The components share a global minimizer x⋆, with ∥x0−x⋆∥≤R for a given x0∈E and R>0. The oracle returns ∇fi(x) at a queried pair (i,x). Given ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε with probability at least 2/3 over the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, n, L0, L1, R, ε, and x0.

Our assumptions:

Assumption 1 (Component convexity and differentiability). Each fi is differentiable everywhere on E with continuous gradient ∇fi:E→E. 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). For every i∈{1,…,n}, x,y∈E, and M∈R, the segment bound ∥∇fi(x+θ(y−x))∥≤Mfor every θ∈[0,1] implies ∥∇fi(x)−∇fi(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Interpolation and initial distance). There exists x⋆∈E such that fi(x⋆)≤fi(x)for every i∈{1,…,n}, x∈E,∥x0−x⋆∥≤R.

Queries may select any component i∈{1,…,n} and any point x∈E, with each call returning its exact component gradient. After the allotted oracle calls, the output must satisfy P(f(x¯)−f(x⋆)≤ε)≥23, where P is the law of the algorithm’s randomness and x⋆ is a fixed common global minimizer.

Results

Let F=n−1∑i=1nfi on a finite-dimensional real inner-product space, with n≥1, L0,R,ε>0 and L1≥0. Each fi is convex with continuous gradient and satisfies ∥∇fi(x)−∇fi(y)∥≤(L0+L1maxz∈[x,y]∥∇fi(z)∥)∥x−y∥. The components share a minimizer x⋆ with ∥x0−x⋆∥≤R. The oracle returns exact component gradients. The target is P{F(x^)−F(x⋆)≤ε}≥2/3; costs count all component-gradient calls.

Interpolated generalized-smooth finite sums: InterpolatedGeneralizedFiniteSum.
Result Oracle complexity Novelty Limitations
(1) AcceleratedInterpolatedGeneralizedFiniteSum (Ours) (⋆⋆⋆) (review) O([n(1+L12R2)+nκ]ℓ)
(2) (L0,L1)-SGD (Gorbunov et al. 2024, Thm. 7.2, App. H.1); Derived bound O(1+κ+nL12R2).
Uniform random iterate; telescoping and Markov conversion to probability 2/3.
(1): κ→nκℓ; total gain when κ≥Cmax{nℓ2,nL12R2ℓ}. Fixed n,L1R: O(ε−1)→O(ε−1/2log⁡(1/ε)). Final snapshot replaces random iterate. (1): extra ℓ when nL12R2 dominates; worse at κ≲n. Updates additionally need R,ε and ball projection; (2) uses them only for stopping.
(3) (Tyurin 2026, v2, Eq. (8)); full gradients O(n[1+κ+L12R2]).
Special-case overlap: d=1, twice-differentiable F; deterministic accuracy.
(1): up to n/ℓ cost saving for the shared target when n≥Cℓ2, κ≥Cℓ(1+L12R2). Scope: no mean-smoothness assumption in higher dimensions. (1): probability 2/3 replaces deterministic accuracy; extra ℓ on nL12R2. Rates not comparable in general dimensions without mean smoothness.
(4) (Tyurin 2026, v2, Thm. 4.3); full gradients O(n[1+κ+L1Rlog+⁡min{L12Δ/L0,Δ/ε}+log+⁡(Δ/(L0R2))])
Special-case overlap: d=1, twice-differentiable F; R=∥x0−x⋆∥>0, supplied gap bound Δ>0.
(1): scope extends to higher dimensions without mean smoothness; those rates are not comparable without that assumption. (1): loses deterministic accuracy; (4) sharpens the curvature term using an initial-gap bound.
(5) VARAG (Lan et al. 2019, Thm. 1) {O(n[1+log+⁡κ]),κ≤n,O(n[1+log⁡n]+nκ),κ>n.
Special case L1=0; expected gap converted to probability 2/3 by Markov.
(1): scope extends to L1>0 with component-gradient access. (1): at L1=0, extra ℓ on nκ; no rate improvement.

Abbr: κ=L0R2/ε; ℓ=log⁡(2+n+κ+L12R2); d is the dimension; Δ≥F(x0)−F(x⋆); log+⁡t=max{0,log⁡t}, with log+⁡0=0; C denotes a sufficiently large universal constant. A full gradient costs n component queries.

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.
Tyurin, Alexander. 2026. Near-Optimal Convergence of Accelerated Gradient Methods Under Generalized and (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2508.06884.

Lean setup