← All setups

Heavy-Tailed Strong-Growth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Strong-Growth Convex Minimization

We minimize a differentiable convex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and a given point x0∈E lies within distance R≥0 of a global minimizer x⋆. At x, the oracle returns an unbiased stochastic gradient g(x,ξ) using independent samples ξ from a probability measure μ on a measurable space Ω. Its noise has pth moment at most ρ∥∇f(x)∥p, where 1<p≤2 and ρ≥0. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, averaging over sampling and algorithm randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which is equipped with its Borel sigma-algebra. The algorithm receives E, Ω, L, R, ρ, p, ε, and x0; access to f is through the stochastic gradient oracle.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is Fréchet differentiable everywhere on E. For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥.

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

Assumption 3 (Relative moment and independent sampling). The map g:E×Ω→E is jointly measurable. For each x∈E, the map g(x,⋅) is Bochner integrable under μ, and ∥g(x,⋅)−∇f(x)∥p is integrable under μ. They satisfy Eξ∼μ[g(x,ξ)]=∇f(x),Eξ∼μ[∥g(x,ξ)−∇f(x)∥p]≤ρ∥∇f(x)∥p. The oracle uses a sequence (ξk)k≥0 of measurable, mutually independent random variables, each with distribution μ. At call k, a query x∈E receives g(x,ξk). The algorithm’s randomness is independent of this sample sequence.

Queries may be made at any point of E. Let P denote the joint law of the sample sequence and the algorithm’s randomness. After the allotted oracle calls, the output x¯ must be measurable, its gap f(x¯)−f(x⋆) must be integrable under P, and EP[f(x¯)−f(x⋆)]≤ε.

Results

Convex differentiable f on a separable real Hilbert space, with L-Lipschitz gradient, a minimizer x⋆, and ∥x0−x⋆∥≤R. Here L,ε>0, R,ρ≥0, and 1<p≤2. The jointly measurable oracle has integrable samples and integrable central pth moments, with ∫g(x,ω)dμ=∇f(x) and ∫∥g(x,ω)−∇f(x)∥pdμ≤ρ∥∇f(x)∥p. Samples are IID with marginal μ under probability law P. Target: measurable output with integrable gap and ∫[f(output)−f(x⋆)]dP≤ε. Result (1) constructs SplitRobustAcceleration, tuned using L,R,ρ,p,ε; the setup imposes no algorithm restriction.

Heavy-tailed relative-moment convex optimization: HeavyTailedStrongGrowthConvex.
Result Oracle complexity Novelty Limitations
(1) SplitRobustHeavyTailedAcceleration (Ours) (⋆⋆⋆) (review) O(H+1{ρ>0}[1+(234ρ)1/(p−1)]⋅(1+log⁡H)Hp/(3p−2))
(2) Clip-SSTM (Nekrasova et al. 2026, Theorem 5.2); finite-dimensional restriction, moment model with σ0=0, σ1p=ρ Op(A[1+log⁡(A/β)]) calls; Pr{f(y)−f(x⋆)≤ε}≥1−β. (1): For fixed 1<p<2, ρ>0, and β, smaller accuracy exponent at large T, with expectation rather than high probability. At p=3/2: O(T3/5log⁡T) versus O(T3/2log⁡T). (1): Expectation only; excludes additive noise and weak-Lp tails. Large p-dependent factor; batching floor loses for 0<ρ≲T−p2/[2(3p−2)], up to logarithms, at fixed p and confidence.
(3) AGNES (Gupta et al. 2024, Theorem 3); p=2, finite-dimensional restriction O((1+ρ)H) calls; expected objective gap at most ε. (1): Scope extends to 1<p<2, allowing infinite variance. Matches the deterministic accelerated rate at ρ=0. (1): At p=2 and fixed ρ>0, loses a factor 1+log⁡H; uses batched median-of-means pilots.

Abbr: T=LR2/ε, H=max{1,T}, A=H+ρ1/(p−1)Hp/[2(p−1)]; β∈(0,1) is the failure probability. Op allows constants depending on p; 1{ρ>0} is an indicator. Costs count individual stochastic-gradient samples, including all batches.

Gupta, Kanan, Jonathan W. Siegel, and Stephan Wojtowytsch. 2024. Nesterov Acceleration Despite Very Noisy Gradients. https://doi.org/10.48550/arXiv.2302.05515.
Nekrasova, Alyona, Makar Sidorov, Savelii Chezhegov, et al. 2026. Weak-Lα Noise, Strong Guarantees: Gradient Clipping Under Affine Heavy Tails. https://doi.org/10.48550/arXiv.2610.28107.

Lean setup