← All setups

Kappa Free Heavy Tailed PLHessian — Heavy-Tailed Polyak–Łojasiewicz Minimization

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Polyak–Łojasiewicz Minimization · Lean proof

Heavy-Tailed Polyak–Łojasiewicz Minimization

We consider minimizing a possibly nonconvex function f:E→R on a finite-dimensional real inner product space E. The objective has Lipschitz gradient and Hessian, satisfies a Polyak–Łojasiewicz inequality, and admits a global minimizer x⋆. A given starting point x0∈E has bounded objective gap. The oracle returns an unbiased stochastic gradient at each query, using independent, identically distributed samples with bounded noise moments of order p∈(1,2], allowing heavy tails. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, where expectation includes sampling and independent algorithm randomness.

The optimization problem is minx∈Ef(x). Write ∥⋅∥ for the norm induced by the inner product and ∥⋅∥op for the induced operator norm. Fix parameters 0<μ≤L,ρ,σ,Δ≥0,1<p≤2,ε>0. The algorithm receives E, the measurable sample space Ω, L, μ, ρ, σ, p, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Gradient and Hessian regularity). The function f is Fréchet differentiable everywhere, and its gradient is Fréchet differentiable. The Hessian ∇2f(x) is a linear operator from E to E. For all x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥.

Assumption 2 (Polyak–Łojasiewicz inequality and initialization). There exists x⋆∈E such that, for every x∈E, f(x⋆)≤f(x),2μ(f(x)−f(x⋆))≤∥∇f(x)∥2, and the given starting point satisfies f(x0)−f(x⋆)≤Δ.

Assumption 3 (Unbiased oracle with heavy-tailed noise). There is a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For each x∈E, the map g(x,⋅) is Bochner integrable and ∥g(x,⋅)−∇f(x)∥p is integrable under ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥p]≤σp. The samples (ξk)k≥0 are measurable, mutually independent, and each has law ν under their joint probability law on ΩN. At the kth query x∈E, the oracle returns g(x,ξk). 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 and have integrable objective gap, with EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the samples and the algorithm’s randomness.

Proved result

65⋅(⌈512⋅((Lμ)54+(2128p+27⋅σ2⋅(1ε⋅1μ+(Lμ)52⋅ρ2μ4))p2⋅(p−1))⋅(log⁡(1+48⋅Lμ⋅Δε)+1)⌉++1)

OracleTemplate.Convergence LongTails.Setups.HeavyTailedPLHessian.spec
  LongTails.Theorems.KappaFreeHeavyTailedPLHessian.budget

Relevant previous results

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