← All setups

Heavy-Tailed Second-Order Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Second-Order Stationarity

We consider minimizing a twice differentiable, possibly nonconvex function f:Rd→R, where d≥1. Its gradient and Hessian are Lipschitz with constants L>0 and ρ>0, respectively, and a given point x0 has objective gap at most Δ≥0 above a global lower bound. The oracle returns unbiased gradient or Hessian-vector estimates using independent samples, with bounded error moments of order p∈(1,2], allowing heavy-tailed noise. For ε>0, the goal is a measurable output x¯ satisfying both ∥∇f(x¯)∥≤ε and ⟨v,∇2f(x¯)v⟩≥−ρε∥v∥2 for every v∈Rd, with probability at least 2/3. Here the norm and inner product are Euclidean.

The optimization problem is infx∈Rdf(x). We use ∥⋅∥op for the induced operator norm on linear maps from Rd to itself. The algorithm receives d, the measurable sample space Ω, L, ρ, the noise bounds σg,σh≥0, p, Δ, ε, and x0∈Rd.

Our assumptions:

Assumption 1 (Gradient and Hessian regularity). The function f is differentiable everywhere, its gradient is differentiable everywhere, and, for every x,y∈Rd, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥.

Assumption 2 (Lower bound and initial gap). There exists m∈R such that f(x)≥mfor every x∈Rd,f(x0)−m≤Δ.

Assumption 3 (Unbiased oracles with bounded moments). There is a probability measure ν on Ω and jointly measurable maps g:Rd×Ω→Rd,H:Rd×Ω→L(Rd,Rd), where L(Rd,Rd) is the space of linear operators equipped with its operator norm. For every x,v∈Rd, the random vectors g(x,ξ) and H(x,ξ)v, with ξ∼ν, are Bochner integrable and satisfy Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[H(x,ξ)v]=∇2f(x)v. Their error moments are integrable and obey Eξ∼ν[∥g(x,ξ)−∇f(x)∥p]≤σgp,Eξ∼ν[∥H(x,ξ)v−∇2f(x)v∥p]≤σhp∥v∥p. The samples (ξk)k≥0 are measurable, mutually independent, and each has law ν. They are independent of the algorithm’s randomness.

At call k, the algorithm may query any x∈Rd for the vector g(x,ξk), or any pair x,v∈Rd for the vector H(x,ξk)v. Each call returns one of these two vectors and uses the next sample in the same sequence. Both query types count toward a single total oracle-call budget.

After the allotted calls, the output x¯∈Rd must be measurable and satisfy P(∥∇f(x¯)∥≤ε,⟨v,∇2f(x¯)v⟩≥−ρε∥v∥2for every v∈Rd)≥23, where P is the joint law of the algorithm’s randomness and the oracle samples.

Results

f:Rd→R, d≥1, has an L-Lipschitz gradient and a ρ-Lipschitz Hessian, with f(x0)−m≤Δ for a global lower bound m. Here L,ρ,ε>0, Δ,σg,σh≥0, and 1<p≤2. Jointly measurable, unbiased gradient and linear Hessian-vector estimators use fresh IID samples and satisfy E∥g(x)−∇f(x)∥p≤σgp and E∥(H(x)−∇2f(x))v∥p≤σhp∥v∥p for every x,v. The target is Pr{∥∇f(x^)∥≤ε, ∇2f(x^)⪰−ρεI}≥2/3, over the IID oracle samples and algorithm randomness. Each gradient or Hessian-vector query counts as one call.

Heavy-tailed second-order stationarity under the HeavyTailedHessianVector setup.
Result Oracle complexity Novelty Limitations
(1) DirectionalHeavyTailedSecondOrder (Ours) (⋆⋆⋆) (review) O(264r2[(1+σg/ε)r+(1+ΔM/ε2){1+(1+σg/ε)r−1a+ar+ℓℓdM/γ+ℓℓdr(σh/γ)r+ℓ2[1+(σh/γ)r]}])
(2) (Arjevani et al. 2020, arXiv v1, Theorem 4); bounded-noise special case

O(Δσgσ¯hε3+ΔLε2+Δ(σ¯h+L)2ρε5/2[1+log⁡dLγ]2)

p=2, ∥H−∇2f∥op≤σ¯h a.s.; ε≤min{σg,ΔL}, γ≤min{σ¯h,L}. SOSP probability ≥5/8.

(1): Scope extends to infinite variance (p<2); at p=2, directional variance replaces almost-sure operator-norm boundedness. Dimension dependence remains polylogarithmic. (1): At p=2, σh=σ¯h>0, the ε−3 coefficient worsens by order 1+Lσh/(ρσg), up to logarithms; extra logarithmic factors and a 2256 prefactor.
(3) (Sadiev et al. 2025, Theorem 2); first-order target

O(1+Δ(L+σh)ε2⋅[1+(σg/ε)r−1]+(σg/ε)r)

T−1∑t<TE∥∇f(xt)∥≤ε; operator-norm p-moment bound E∥H−∇2f∥opp≤σhp.

(1): Adds second-order stationarity with constant probability at the same polynomial ε−(r+1) dependence for fixed positive remaining parameters, up to logarithms. Directional moments replace operator-norm moments. (1): Needs a ρ-Lipschitz Hessian; adds curvature costs and dimension logarithms, with the large 264r2 prefactor.

Abbr: HVP: Hessian-vector product; SOSP: second-order stationary point. r=p/(p−1), γ=ρε, M=L+ρε, a=σh/(L+ρε)+ρε/(L+ρε)2, ℓ=log⁡(2+(L+ρε)2/(ρε)), ℓd=log⁡(2+d). σ¯h bounds Hessian noise almost surely in operator norm; T is the iteration count.

Arjevani, Yossi, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan. 2020. “Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations.” Proceedings of Thirty Third Conference on Learning Theory, Proceedings of machine learning research, vol. 125: 242–99. https://doi.org/10.48550/arXiv.2006.13476.
Sadiev, Abdurakhmon, Peter Richtárik, and Ilyas Fatkhullin. 2025. Second-Order Optimization Under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits. https://doi.org/10.48550/arXiv.2510.10690.

Lean setup