← All setups

Parameter Free Heavy Tailed Nsgdm — Parameter-Free Heavy-Tailed Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Parameter-Free Heavy-Tailed Stationarity · Lean proof

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.

Proved result

⌈80⋅(2+log2⁡(8000⋅L⋅Δε2+L⋅Δ⋅σpp−1⋅(80ε)3⋅p−2p−1+σ5⋅p−22⋅p−2⋅(L⋅Δ)−p2⋅p−2⋅(60ε)3⋅p−22⋅p−2+(σ2L⋅Δ)p2⋅p−2+3⋅LΔ+(Δ3⋅L)13+61p−1⋅(5⋅σε)pp−1+1+(64⋅(1+5⋅σε)p⋅(22+2⋅p⋅log2⁡(1+5⋅σε)p−1)4)1p−1))2⋅(8000⋅L⋅Δε2+L⋅Δ⋅σpp−1⋅(80ε)3⋅p−2p−1+σ5⋅p−22⋅p−2⋅(L⋅Δ)−p2⋅p−2⋅(60ε)3⋅p−22⋅p−2+(σ2L⋅Δ)p2⋅p−2+3⋅LΔ+(Δ3⋅L)13+61p−1⋅(5⋅σε)pp−1+1+(64⋅(1+5⋅σε)p⋅(22+2⋅p⋅log2⁡(1+5⋅σε)p−1)4)1p−1)⌉+

OracleTemplate.Convergence LongTails.Setups.ParameterFreeHeavyTailedSmooth.spec
  LongTails.Theorems.ParameterFreeHeavyTailedNsgdm.budget

Relevant previous results

  • Florian Hübler, Ilyas Fatkhullin, and Niao He. From Gradient Clipping to Normalization for Heavy Tailed SGD. 2025 (preprint 2024; analysis checked in arXiv v3). Complexity: O(1+LΔε−2[1+(σ/ε)p/(p−1)]) stochastic-gradient calls, including minibatches, for E∥∇f(X)∥≤ε using tuned minibatch normalized SGD.