← All setups

Convex Minimization with Affine Moments

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Affine Moments

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 minimizer x⋆. The oracle returns unbiased stochastic gradients from independent, identically distributed samples, with error α-moment bounded by σ0α+σα∥∇f(x)∥α at x, where 1<α≤2 and σ0,σ≥0. For ε>0 and δ∈(0,1), the goal is a measurable output x¯∈E satisfying P{f(x¯)−f(x⋆)>ε}≤δ, where P is the joint law of sampling and independent 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. Let Ω be a measurable sample space. The algorithm receives E, Ω, L, R, σ, σ0, α, ε, δ, and x0; the objective is accessed through the 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 (Sampling and affine moment bound). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. At the kth query x∈E, the oracle returns g(x,ξk), where the measurable random variables (ξk)k≥0 are mutually independent with common law ν, and are independent of the algorithm’s randomness. For every x∈E, the map g(x,⋅) is Bochner integrable and ∥g(x,⋅)−∇f(x)∥α is integrable with respect to ν. They satisfy Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥α]≤σ0α+σα∥∇f(x)∥α.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable and satisfy the high-probability objective-gap requirement P{f(x¯)−f(x⋆)>ε}≤δ.

Results

Convex differentiable f on a separable real Hilbert space with its Borel measurable structure; globally L-Lipschitz gradient and a minimizer x⋆ with ∥x0−x⋆∥≤R. IID samples have law ν; the jointly measurable oracle is integrable and satisfies ∫g(x,ω)dν=∇f(x) and ∫∥g(x,ω)−∇f(x)∥pdν≤σ0p+σp∥∇f(x)∥p, with integrable moments. Here L,R,ε>0, σ0,σ≥0, 1<p≤2, and 0<δ<1 are supplied parameters. Target: measurable output with P{f(out)−f(x⋆)>ε}≤δ under the IID execution law P. Costs count all individual stochastic-gradient replies. Literature comparisons are on the common finite-dimensional restriction.

Affine-moment convex optimization: AffineMomentConvex.
Result Oracle complexity Novelty Limitations
(1) RecursiveAffineMomentAcceleration (Ours) (⋆⋆⋆) (review) O(Hδ[(1+σ)qT+1+V])
(2) AffineMomentAcceleration (Ours) (⋆⋆⋆) (review)

O(2256qℓq+1[(1+σ)q(4+T)qq+2

+(σ0(4LR+Rε))q])

(3) Clip-SSTM (Nekrasova et al. 2026), Thm. 5.2, Cor. I.2; finite-moment specialization Op(B[1+log⁡(B/δ)])

(1): for fixed p<2,δ,σ≥1 and V=O(T), Tq/2→T1/2+o(1); crossover requires roughly log⁡T≳1026 (parameter-dependent).

(2): relative term σqTq/2→(1+σ)qTq/(q+2); total gain for large T, σ≥1, σ0≪σLε, up to logs.

(1), (2) require global smoothness and finite moments; (3) permits local smoothness and weak tails. (1) pays H/δ; (2) has larger constants/log powers. For p<2, (2) loses when σ≲T1/(q+2)−1/2 and initialization dominates.
(4) RCSAG (Lobanov et al. 2026), Thm. 9; H1=σ2=0, Q=BR(x0) Op(B[1+log(1+log⁡(1+T)δ)])

(1): same relative-term exponent gain as against (3), under the stated regime.

(2): p=3/2, L=R=σ=1, σ0=η→0, ε=η3/2: Op(η−9/4log⁡log⁡(1/η)) versus O(η−3/2log4⁡(1/η)) at fixed δ.

(1), (2) exclude generalized smoothness and gap-dependent noise. (1) loses logarithmic confidence dependence; at σ=0, its overhead is H/δ. (2) loses T scaling when p<2 and noise is small.
(5) AGNES (Gupta et al. 2024), Thm. 3 + Markov; p=2, σ0=0 O(1+(1+σ2)T/δ) (2): confidence cost δ−1/2→ℓ3, with matching polynomial T,σ dependence for T≥1. Scope: (1), (2) admit p<2 and σ0>0. (2) adds three logarithmic factors to the expected-accuracy rate. (1) pays H/δ. (5) also supplies an expectation guarantee.
(6) Clipped-SSTM (Sadiev et al. 2023), Thm. 3.2; σ=0

Op((1+T+V)

⋅[1+log⁡((1+T+V)/δ)])

(1), (2): no established improvement on σ=0. (2): Tq/(q+2) instead of T when p<2 and initialization dominates. (1) adds H/δ overhead.

Abbr: p=α in the setup; q=p/(p−1); T=LR2/ε; V=(σ0R/ε)q; B=1+T+V+σqTq/2; ℓ=log⁡(20+q+T+1/δ); M=4+T+V+1/δ; H=(2+q+log⁡M)232q4(1+log⁡M)=Mo(1) for fixed p. Op permits constants depending on p. In (4), H1 and σ2 denote the additional curvature and gap-noise parameters; Δ0=LR2/2 and the ball projection is closed form.

Gupta, Kanan, Jonathan W. Siegel, and Stephan Wojtowytsch. 2024. Nesterov Acceleration Despite Very Noisy Gradients. https://doi.org/10.48550/arXiv.2302.05515.
Lobanov, Aleksandr, Darina Dvinskikh, and Alexander Gasnikov. 2026. Accelerated Stochastic Method Under (H0,H1)-Smoothness and Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2609.33415.
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.
Sadiev, Abdurakhmon, Marina Danilova, Eduard Gorbunov, et al. 2023. “High-Probability Bounds for Stochastic Optimization and Variational Inequalities: The Case of Unbounded Variance.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 29563–648. https://proceedings.mlr.press/v202/sadiev23a.html.

Lean setup