← All setups

Heavy-Tailed Polyak–Łojasiewicz Minimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Finite-dimensional real inner-product space; f has an L-Lipschitz, differentiable gradient and ρ-Lipschitz Hessian, an attained minimum f⋆, and 2μ(f−f⋆)≤∥∇f∥2, where 0<μ≤L. Initially f(x0)−f⋆≤Δ. IID samples feed a jointly measurable unbiased gradient oracle with integrable centered pth moment at most σp, 1<p≤2; ρ,σ,Δ≥0. Target: ∫(f(xout)−f⋆)dPout≤ε, ε>0, where Pout includes the IID samples and independent uniform final-window selection.

Heavy-tailed PL optimization with a Lipschitz Hessian (HeavyTailedPLHessian).
Result Oracle complexity Novelty Limitations
(1) KappaFreeHeavyTailedPLHessian (Ours) (⋆⋆⋆) (review) O([κ5/4+Cp(σ2με+κ5/2σ2ρ2μ4)q]ℓ); includes all pilot/clipping calls.
(2) (Ou and Wang 2026), Thm. 4.3 Op(κ(S+Q)log⁡(1+κS/δ)); last-iterate gap ≤ε with probability 1−δ; 0<ε<Δ. (1): statistical κQ→Qℓ for fixed p, Q≫κ1/4ℓ, ε≪μ3κ1/q−5/2/ρ2. At p=2, μ=σ=ρ=Δ=1, ε=κ−3: O(κ4log⁡κ)→O(κ3log⁡κ) at fixed confidence. (1) needs Hessian regularity and ρ; adds a ρ-term and κ5/4 initialization. Expected random output replaces high-probability last iterate; excludes constrained mirror-PL and conditional non-IID oracles.
(3) (Ou and Wang 2026), Thm. D.1(i); d=1 Op((1+Q)ℓlog⁡(1+ℓ/δ)); probability 1−δ, 0<ε<Δ. (1): dimension-independent scope; matches the κ-free statistical power. (1) adds Hessian regularity, a ρ-term and polynomial initialization; loses high-probability accuracy.
(4) (Ou and Wang 2026), Thm. D.1(ii); fixed d≥2 Od,p(Λ[SDd−1(κJ)+Hd−1,2qQ]); probability 1−δ, 0<ε<Δ. (1): dimension-independent constants; removes statistical κ(d−1−2q)/2 when d−1>2q, up to logarithms. For d−1≤2q, statistical power matches. (1) needs Hessian regularity; adds a ρ-term, loses high-probability accuracy, and has worse initialization for d≤3.
(5) R-clipped-SSTM (Sadiev et al. 2023), Thm. 3.3; strongly convex restriction Op(κSlog⁡(1+κS/δ)+Qlog⁡(1+QS/δ)); probability 1−δ. Use R2=2Δ/μ. (1): scope extends from strong convexity to PL with non-isolated minimizers. (1) loses accelerated initialization and high-probability accuracy; adds Hessian regularity, ρ-cost and a logarithm on Q. (5) requires regularity only on B3R(x⋆).
(6) (LongTails, n.d.); p=2, bounded kurtosis O([κ5/4+Kκ3/2σ2ρ2/μ4+σ2/(με)]ℓ); expected window-iterate gap. (1) removes fourth-moment requirement, permits p<2 and infinite variance; at p=2, improves the Hessian term when K≫κ. (1) worsens the Hessian term when K≲κ; large p-dependent constants grow as p↓1.

Abbr: Costs count stochastic-gradient calls. κ=L/μ, q=p/[2(p−1)], Q=(σ2/(με))q, Cp=2(128/p+27)q, ℓ=1+log⁡(1+κΔ/ε), S=1+log+⁡(Δ/ε), log+⁡t=max{0,log⁡t}, 0<δ<1/2, d=dim⁡E. Subscripts on O allow dependence on those parameters. In (4), J=1+log⁡(1+κ), Λ=1+log⁡((S+1)(J+1)(1+κJ)(d−1)/2/δ); D1(z)=z2/3, Dk(z)=zk/2 for k≥2; Hk,r=Jr+1 if k<r, Jr+1[1+log⁡(1+κJ)]r+1 if k=r, and Jr(κJ)(k−r)/2 if k>r. In (6), K bounds ∫∥g−∇f∥4≤Kσ4.

LongTails: KappaFreeSgdPLHessian. n.d. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/KappaFreeSgdPLHessian.lean.
Ou, Weiming, and Xiao Wang. 2026. Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak–Łojasiewicz Objectives. https://doi.org/10.48550/arXiv.2609.03990.
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://proceedings.mlr.press/v202/sadiev23a.html.

Lean setup