← All setups

Heavy Tailed PLLast Iterate — Heavy-Tailed SGD under the PL Condition

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed SGD under the PL Condition · Lean proof

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⋆>ε)≤δ.

Proved result

⌈44⋅Lμ⋅Δε+1024⋅σ2⋅(Lμ+log⁡(3δ))μ⋅ε+((64⋅(Lμ)2⋅(νσ)2⋅log⁡(3δ))q⋅(3δ)2)1q−2⌉+

OracleTemplate.Convergence LongTails.Setups.HeavyTailedPL.spec OracleTemplate.HeavyTailedPL.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.