← All setups

Nonconvex Optimization with Hölder Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Hölder Noise

We consider minimizing a differentiable, possibly nonconvex 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 satisfies f(x0)−infx∈Ef(x)≤Δ, with Δ≥0. Each oracle call returns unbiased gradients at two queried points using one shared sample, with independent samples across calls. The centered noise has variance at most σ2 and mean-square Hölder increments bounded by M∥x−y∥2ν, where σ,M≥0 and 0<ν≤1. The goal is a measurable output x¯∈E satisfying E∥∇f(x¯)∥≤ε, where ε>0 and expectation includes sampling and algorithm randomness.

The optimization problem is infx∈Ef(x), where ∥⋅∥ is the norm induced by the inner product on E. The algorithm receives E, the measurable sample space Ω, L, M, ν, σ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is Fréchet differentiable everywhere, and for every x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,f(x0)−f(x)≤Δ.

Assumption 2 (Unbiased stochastic gradients). There exist a probability measure p on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable under ξ∼p, with Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∥g(x,ξ)−∇f(x)∥2]≤σ2.

Assumption 3 (Hölder noise increments). Define the centered noise by ζ(x,ξ)=g(x,ξ)−∇f(x). For every x,y∈E, the squared increment ∥ζ(x,ξ)−ζ(y,ξ)∥2 is integrable under ξ∼p and satisfies Eξ∼p[∥ζ(x,ξ)−ζ(y,ξ)∥2]≤M∥x−y∥2ν.

At call k, a query (xk,yk)∈E×E receives (g(xk,ξk),g(yk,ξk)). The sample sequence (ξk)k≥0 consists of measurable, mutually independent random variables with common law p. Algorithm randomness is independent of the entire sample sequence. Queries may depend on earlier replies, and each paired reply counts as one oracle call.

After the allotted calls, the output x¯ must be measurable, its gradient norm must be integrable, and EP[∥∇f(x¯)∥]≤ε, where P is the joint law of the sample sequence and the algorithm’s randomness.

Results

On a separable real Hilbert space with its Borel measurable structure, f is differentiable with L-Lipschitz gradient and f(x0)−f(x)≤Δ for every x. Here L,ε>0, M,σ,Δ≥0, and 0<ν≤1. The jointly measurable oracle g uses IID samples with law p, satisfies ∫g(x,ω)dp(ω)=∇f(x), and, with e(x,ω)=g(x,ω)−∇f(x), satisfies ∫∥e(x,ω)∥2dp(ω)≤σ2 and ∫∥e(x,ω)−e(y,ω)∥2dp(ω)≤M∥x−y∥2ν, with the stated integrands integrable. One call returns gradients at two points using one shared sample. Target: a measurable output with integrable gradient norm and ∫∥∇f(xout(ω))∥dP(ω)≤ε, where P is the sampling law. The setup imposes no algorithm restriction.

Sufficient oracle budgets for HolderNoiseNonconvex.
Result Oracle complexity Novelty Limitations
(1) HolderNoiseMinimaxUpper (Ours) (⋆⋆⋆) (review) O(min{1+LΔ+σ2ε2+LΔσ2ε4,ℓ2[1+LΔ+σ2ε2+Δε3max{M(L/ε)1−2ν,M1/(2ν)σ2−1/ν}]})
(2) SGD/RSG (Ghadimi and Lan 2013), Cor. 2.2; finite-dimensional specialization O(1+LΔε2+LΔσ2ε4); single-point calls, squared-norm accuracy converted by Jensen (1): Noise term reduced by ρa/ℓ2; total gain requires ρa≫ℓ2 and LΔσ2/ε4≫ℓ2[1+(LΔ+σ2)/ε2]. At L=M=σ=Δ=1: O(ε−4) becomes O(ε−7/2ℓ2) for ν=1/4, or O(ε−3ℓ2) for ν≥1/2, as ε→0. (1) needs centered Hölder regularity and paired same-sample access; guarantees expected norm rather than the stronger squared-norm criterion.
(3) NSGD-MVR (Fradin et al. 2026), Thm. 4.2, p=q=2; ν=1, E=Rd O(1+σ2+(L+M)Δε2+MΔσε3); paired calls including initialization (1): Scope extends the distance exponent from ν=1 to 0<ν<1; at ν=1, polynomial orders match up to logarithms. (1) incurs an ℓ2 overhead at ν=1.
(4) (LongTails 2026); raw Hölder increments, 1/2≤ν≤1 O(ℓ2[1+LΔ+σ2ε2+ΔM1/(2ν)σ2−1/νε3]) (1): Scope extends to centered noise and 0<ν<1/2, admitting quadratic means. On the common class, no worse order; cheaper when the SGD cap wins.

Abbr: ℓ=1+log⁡(2+LΔ/ε2); ρ=σ2L2ν/(Mε2ν) for M,σ>0; a=min{1,1/(2ν)}. L: population smoothness; Δ: initial gap bound; σ2: noise variance bound; (M,ν): centered-noise regularity; ε: stationarity tolerance. For σ=0, use the first branch of (1). Raw increments in (4) mean ∫∥g(x,ω)−g(y,ω)∥2dp(ω)≤M∥x−y∥2ν. Paired and single-point call counts differ by at most a universal factor on their common oracle model; batches are included. All displayed costs are sufficient budgets.

Fradin, Adrien, Abdurakhmon Sadiev, Laurent Condat, and Peter Richtárik. 2026. Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2512.18713.
Ghadimi, Saeed, and Guanghui Lan. 2013. Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming. https://doi.org/10.48550/arXiv.1309.5549.
LongTails: DyadicVarianceReductionHolder. 2026. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/DyadicVarianceReductionHolder.lean.

Lean setup