← 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 Euclidean space Rd, where n≥2 is the number of components and d is the dimension. Each fi:Rd→R is convex and (L0,L1)-smooth, with L0>0 and L1≥0, and has a differentiable gradient. The components share a minimizer x⋆ satisfying ∥x⋆∥≤R and F(0)−F(x⋆)≤Δ, where R>0 and Δ>0. At a queried pair (i,x), the oracle returns (fi(x),∇fi(x)). For ε>0, the goal is an output x¯ 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∈RdF(x). We use the Euclidean norm and its induced operator norms, denoted by ∥⋅∥ and ∥⋅∥op, respectively. The algorithm receives all parameters d,n,L0,L1,R,Δ,ε; the component functions are accessed through the oracle. The parameter regime is n,d∈N,n≥2,L0>0,L1≥0,R>0,ε>0,2ε≤Δ,4nε≤L0R2,d≥⌈280(1+n+L1R+L0R2ε)24⌉.

Our assumptions:

Assumption 1 (Component convexity). For every i∈{1,…,n}, x,y∈Rd, and t∈[0,1], fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y).

Assumption 2 (Generalized smoothness). Each fi is differentiable everywhere, and ∇fi:Rd→Rd is Fréchet differentiable everywhere. Its Hessian satisfies ∥∇2fi(x)∥op≤L0+L1∥∇fi(x)∥,i∈{1,…,n},x∈Rd.

Assumption 3 (Interpolation and reference bounds). There exists x⋆∈Rd such that fi(x⋆)≤fi(x)for every i∈{1,…,n}, x∈Rd,∥x⋆∥≤R,F(0)−F(x⋆)≤Δ. The origin is a reference point for these bounds, rather than a prescribed algorithm initialization.

Each oracle call selects any component i∈{1,…,n} and any point x∈Rd and returns the exact pair (fi(x),∇fi(x)). After the allotted calls, the output x¯∈Rd must satisfy EP[|F(x¯)−F(x⋆)|]<∞,EP[F(x¯)−F(x⋆)]≤ε. Here x⋆ is a fixed common minimizer of the components; all such minimizers have the same value of F.

Results

F=n−1∑i=1nfi on Rd, with convex components having differentiable gradients and ∥∇2fi(x)∥≤L0+L1∥∇fi(x)∥. A common minimizer x⋆ satisfies ∥x⋆∥≤R and F(0)−F(x⋆)≤Δ. Parameters satisfy L0,R,ε>0, L1≥0, n≥2, Δ≥2ε, L0R2/ε≥4n, and d≥⌈280(1+n+L1R+L0R2/ε)24⌉. The target is an integrable gap with ∫[F(x^(ω))−F(x⋆)]dP(ω)≤ε, where P is the algorithm’s seed law. Hardness holds against every randomized adaptive algorithm using exact component value/gradient pairs, at every fixed budget through the stated threshold; the instance is independent of the realized seed.

Lower bounds (necessary budgets) for ExpectedInterpolatedGeneralizedFiniteSum.
Result Oracle complexity Novelty Limitations
(1) ExpectedInterpolatedGeneralizedFiniteSumLowerBound (Ours) (⋆⋆⋆) (review) Necessary: Ω(n(1+q2/3)+n(H+q)log2⁡(2+n+q+H)) component calls.
(2) (Rudomanov et al. 2026, Thm. 7.1, v2) Necessary: Ω(n(1+q2/3)+n[H+q2(1+δ/ε)]log2⁡(2+n+H+q2(1+δ/ε))) value/gradient calls. Requires q>0, δ≥3ε/q2; no interpolation guarantee. (1): Scope: all four terms persist at δ=0; matches (2) at δ=3ε/q2, and includes L1=0. (1) requires H≥4n and the explicit large polynomial dimension; fixed-budget hardness rather than expected-stopping-time hardness.
(3) (Woodworth and Srebro 2019, Thm. 7, v3). Smooth convex components on a radius-R ball; L1=0, without interpolation. Necessary: Ω(n+nH) component value/gradient/prox calls, in sufficiently large dimension. (1): Scope: hardness with a common minimizer; adds the L1>0 terms. At L1=0, (1) loses log2⁡(2+n+H), excludes prox queries, and requires H≥4n.

Abbr: n: component count; H=L0R2/ε; q=L1R; δ: upper bound on minF−n−1∑iinffi; Ω: necessary calls, up to universal factors. A component call returns the value and gradient together; (3) additionally permits a component proximal evaluation.

Rudomanov, Mikhail, Ivan Fomin, Alexander V. Gasnikov, and Fedor S. Stonyakin. 2026. Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)-Smooth Functions. https://doi.org/10.48550/arXiv.2611.04171.
Woodworth, Blake, and Nathan Srebro. 2019. Tight Complexity Bounds for Optimizing Composite Objectives. https://doi.org/10.48550/arXiv.1605.08003.

Lean setup