← All setups

Directional Heavy Tailed Second Order — Heavy-Tailed Second-Order Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Second-Order Stationarity · Lean proof

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.

Proved result

⌈264⋅(pp−1)2⋅((1+σgε)pp−1+(1+Δ⋅(L+ρ⋅ε)ε2)⋅(1+(1+σgε)1p−1⋅(σhL+ρ⋅ε+ρ⋅ε(L+ρ⋅ε)2)+(σhL+ρ⋅ε+ρ⋅ε(L+ρ⋅ε)2)pp−1+log⁡(2+(L+ρ⋅ε)2ρ⋅ε)⋅log⁡(2+d)⋅L+ρ⋅ερ⋅ε+log⁡(2+(L+ρ⋅ε)2ρ⋅ε)⋅(log⁡(2+d))pp−1⋅(σhρ⋅ε)pp−1+(log⁡(2+(L+ρ⋅ε)2ρ⋅ε))2⋅(1+(σhρ⋅ε)pp−1)))⌉+

OracleTemplate.Convergence LongTails.Setups.HeavyTailedHessianVector.spec
  OracleTemplate.DirectionalHeavyTailedSecondOrder.budget

Relevant previous results

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