← All setups

Parameter-Free Heavy-Tailed Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Parameter-Free Heavy-Tailed Stationarity

We consider a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E, with hidden gradient Lipschitz constant L>0. A given point x0∈E satisfies f(x0)−ℓ≤Δ for a global lower bound ℓ∈R and Δ>0. The oracle returns an unbiased stochastic gradient g(x,ξ) at x, using independent samples ξ with common law ν, with centered pth moment at most σp, where 1<p≤2 and σ≥0. For ε>0, the goal is E∥∇f(x¯)∥≤ε for an output x¯∈E, averaging over sampling and algorithm randomness.

The underlying optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and E carries its Borel sigma-algebra. The algorithm receives only E and x0; the parameters L, Δ, σ, p, and ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

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

Assumption 2 (Heavy-tailed stochastic gradients). Let Ω be a measurable sample space and ν a probability measure on Ω. The map g:E×Ω→E is jointly measurable. For every x∈E, g(x,⋅) is Bochner integrable, the random variable ∥g(x,ξ)−∇f(x)∥p is integrable for ξ∼ν, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥p]≤σp.

At call k, a query x∈E receives g(x,ξk). The sample variables (ξk)k≥0 are measurable and mutually independent with common law ν under their joint probability law. Any algorithm randomness is independent of this sample sequence. Queries may be made at any point of E.

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

Results

f is differentiable on a complete, second-countable real inner-product space with its Borel structure, ∇f is L-Lipschitz, and f(x0)−flower≤Δ for a global lower bound. IID samples give a jointly measurable, unbiased, integrable gradient oracle with integrable central pth moment at most σp, 1<p≤2. Here L,Δ,ε>0, σ≥0. Target: ∫∥∇f(xout)∥dP≤ε. Only the space and x0 are public; the setup imposes no algorithm restriction.

Parameter-free heavy-tailed smooth optimization: ParameterFreeHeavyTailedSmooth.
Result Oracle complexity Novelty Limitations
(1) ParameterFreeHeavyTailedNsgdm (Ours) (⋆⋆⋆) (review) O(B[1+log⁡(1+B)]2) stochastic gradients, including all restarted runs and validation samples.
(2) (Liu and Zhou 2025), Thm. 3.6 (L1=σ1=0); (Hübler et al. 2025), Prop. 1, (4) O(1+(Δ4+L4)/ε4+(σ/ε)2p/(p−1)) stochastic gradients. (1): Unknown-p gain; at p=3/2, L=Δ=σ=1, ε−6 becomes ε−5log2⁡(1/ε). Deterministic term becomes LΔ/ε2. No horizon input. (1): Squared logarithm, validation and scale costs; very large constants as p↓1. Horizon dependence in (2) is removable by doubling.
(3) (Liu and Zhou 2025), Thm. 3.2 (L1=σ1=0) O(1+LΔ/ε2+(σ/ε)(2p−1)/(p−1)+LΔσp/(p−1)ε−(3p−2)/(p−1)) stochastic gradients. (1): Needs no p,σ,L,Δ,T in updates. Matches leading parameter rates up to logarithms and additive costs when σε≤LΔ. (1): Extra logarithms, validation and scale terms; when σε>LΔ, deterioration can scale as (σε/(LΔ))p/(2p−2).
(4) (Khaled and Jin 2024), Thm. 6, bounded-noise restriction O(H[1+LΔ/ε2+LΔR2/ε4+R2/ε2]) stochastic gradients; ∥∇f(xout)∥≤ε with probability 1−δ. (1): Scope: finite central pth moments for all 1<p≤2, replacing bounded noise at p=2. Removes parameter hints. Rates not comparable across confidence criteria. (1): Expectation guarantee only; (4) supplies high probability.

Abbr: L: smoothness; Δ: initial gap bound; σ: central-moment scale; p: moment order; ε: accuracy. For a universal C>1, B=1+LΔ/ε2+C1/(p−1)[LΔσp/(p−1)ε−(3p−2)/(p−1)+σ(5p−2)/(2p−2)(LΔ)−p/(2p−2)ε−(3p−2)/(2p−2)+(σ2/(LΔ))p/(2p−2)+(1+σ/ε)p/(p−1)((1+log⁡(1+σ/ε))/(p−1))4/(p−1)]+L/Δ+(Δ/L)1/3. R: almost-sure noise bound; H: polylogarithmic factor in confidence 1/δ, budget and ratios of supplied positive upper/lower hints for L,Δ,R. All costs count individual stochastic-gradient calls; big-O constants are universal.

Hübler, Florian, Ilyas Fatkhullin, and Niao He. 2025. From Gradient Clipping to Normalization for Heavy Tailed SGD. arXiv:2410.13849v3. https://arxiv.org/abs/2410.13849v3.
Khaled, Ahmed, and Chi Jin. 2024. Tuning-Free Stochastic Optimization. arXiv:2402.07793v2. https://arxiv.org/abs/2402.07793v2.
Liu, Zijian, and Zhengyuan Zhou. 2025. Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping. arXiv:2412.19529v4. https://arxiv.org/abs/2412.19529v4.

Lean setup