← All setups

Heavy-Tailed SGD under the PL Condition

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed SGD under the PL Condition

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, and it satisfies the Polyak–Łojasiewicz condition with constant μ, where 0<μ≤L. Write f⋆=infx∈Ef(x)>−∞. A given starting point x0∈E satisfies f(x0)−f⋆≤Δ, where Δ≥0. The oracle returns unbiased stochastic gradients from independent, identically distributed samples, with uniformly bounded second and qth noise moments for q>2, allowing heavy tails. For ε>0 and δ∈(0,1), scheduled SGD must return a measurable last iterate x¯ satisfying P(f(x¯)−f⋆>ε)≤δ, where P is the sample law.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives only E, L, μ, and x0; the noise parameters σ,ν>0, moment order q, initial gap bound Δ, tolerance ε, and failure probability δ may enter the oracle-call budget but not the step-size schedule.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, with ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Polyak–Łojasiewicz condition and initialization). The function f is bounded below, and 2μ(f(x)−f⋆)≤∥∇f(x)∥2,x∈E,f(x0)−f⋆≤Δ.

Assumption 3 (Independent sampling and noise moments). Let Ω be a measurable space and P0 a probability measure on Ω. The measurable sample variables (ξt)t≥0 are mutually independent under P, each with distribution P0. The oracle is a jointly measurable map g:E×Ω→E and returns g(x,ξt) at the tth query x∈E. For every fixed x∈E, the map g(x,⋅) is Bochner integrable, and the scalar maps ∥g(x,⋅)−∇f(x)∥2 and ∥g(x,⋅)−∇f(x)∥q are integrable under P0. They satisfy Eξ∼P0[g(x,ξ)]=∇f(x),Eξ∼P0[∥g(x,ξ)−∇f(x)∥2]≤σ2,Eξ∼P0[∥g(x,ξ)−∇f(x)∥q]≤νq.

Our result is algorithm-specific: we analyze scheduled stochastic gradient descent (SGD). Starting from the given x0, the method uses a deterministic schedule (ηt)t≥0 with ηt>0 and performs xt+1=xt−ηtg(xt,ξt),t=0,1,2,…. The schedule depends only on the algorithm inputs specified above. After K∈{0,1,2,…} oracle calls, the output is the last iterate x¯=xK. It must be measurable and satisfy P(f(x¯)−f⋆>ε)≤δ.

Results

A differentiable, bounded-below f on a separable real Hilbert space with its Borel structure has globally L-Lipschitz gradient and satisfies 2μ(f(x)−inff)≤∥∇f(x)∥2, 0<μ≤L, and f(x0)−inff≤Δ. The jointly measurable oracle is unbiased, with uniformly bounded central moments E∥g(x,ξ)−∇f(x)∥2≤σ2 and E∥g(x,ξ)−∇f(x)∥q≤νq, where σ,ν>0 and q>2; samples are IID. The setup restricts algorithms to plain SGD with positive deterministic steps and last-iterate output. Target: P{f(xT)−inff>ε}≤δ, for ε>0, 0<δ<1. Costs count individual stochastic-gradient calls.

High-probability PL optimization under finite-moment noise: HeavyTailedPL.
Result Oracle complexity Novelty Limitations
(1) HeavyTailedPLLastIterate (Ours) (⋆⋆) (review) O(1+κΔ/ε+σ2(κ+ℓ)με+H)

(2) Clipped-SGD (Sadiev et al. 2023, Thm. E.4, α=2)

Finite-dimensional competitor; finite variance suffices locally.

O(1+κℓΔlogeκℓΔδ

+κσ2μεℓN

⋅[1+log+ΔεℓN]2)

(1): for fixed positive Δ,σ,κ,δ,q,ν/σ and ε→0, O(ε−1) versus O(ε−1log3⁡(1/ε)); noise regime ε≲σ4/(μ2Δ), H≲κσ2/(με).

Adaptivity: steps need only L,μ; (2) tunes with Δ,σ,T,δ. Stopping still needs σ,ν,q,Δ,ε,δ.

(1) needs global assumptions and q>2 moments; excludes infinite variance. Polynomial initialization and confidence burn-in can outweigh savings at moderate accuracy or small δ.

(3) SGD (Madden et al. 2024, Thm. 8)

Special case: conditionally norm-sub-Gaussian noise in Rd.

O(1+κΔℓε+κσ2ℓμε)

Derived bound retaining initialization; here σ also bounds the norm-sub-Gaussian scale.

(1): scope extends plain SGD to one finite q>2 moment.

Noise term: κℓ→κ+ℓ, factor min{κ,ℓ} on the overlap with q=2+2ℓ, ν≲σq; total gain requires κΔ/ε+H≲σ2(κ+ℓ)/(με).

(1) requires IID sampling and uniform-in-x moments; (3) allows adapted martingale noise. (1) adds burn-in H.

(4) SGD (Tong et al. 2026, Thm. 3.7)

Finite-data empirical risk in Rd; conditional β-Orlicz noise, β>1.

T=O(1+e2log1/β⁡(T/δ)εlog⁡Tℓ), implicitly in T≥2.

Requires smooth component losses, bounded initial component gradients, and ηt∥∇f(xt)∥≤G. Constants depend on smoothness, PL, initialization, G, and Orlicz parameters; full parameter rates are not comparable.

(1): removes finite-data and trajectory-cap restrictions; needs one moment instead of all moments. On the overlap, fixed δ and other parameters, ε→0: O(ε−1) removes the super-polylogarithmic overhead. (1) requires uniform-in-x moments, excluding heterogeneous-curvature finite sums allowed by (4); scopes are incomparable. Its burn-in is polynomial in 1/δ.

Abbr: κ=L/μ, ℓ=log⁡(3/δ), log+⁡u=max{0,log⁡u} (with log+⁡0=0), ℓΔ=1+log+⁡(Δ/ε), ℓN=1+log+⁡(κσ2/(μεδ)); H=[(64κ2(ν/σ)2ℓ)q(3/δ)2]1/(q−2) is the burn-in. T is the number of oracle calls. The β-Orlicz function is Ψβ(u)=exp⁡(logβ⁡(1+u))−1; G is the trajectory cap.

Madden, Liam, Emiliano Dall’Anese, and Stephen Becker. 2024. “High Probability Convergence Bounds for Non-Convex Stochastic Gradient Descent with Sub-Weibull Noise.” Journal of Machine Learning Research 25 (241): 1–36. https://www.jmlr.org/papers/v25/23-0466.html.
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://doi.org/10.48550/arXiv.2302.00999.
Tong, Qijun, Masahiro Ikeda, and Ryota Kawasumi. 2026. High-Probability Guarantees for SGD Under β-Heavy-Tailed Gradient Noise. https://doi.org/10.48550/arXiv.2609.32195.

Lean setup