← All setups

Hysteretic Affine Hessian Transport — Generalized Smoothness with Hessian-Vector Oracles

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smoothness with Hessian-Vector Oracles · Lean proof

Generalized Smoothness with Hessian-Vector Oracles

We consider minimizing a possibly nonconvex function f:Rd→R, where d≥0 is an integer. The function f is (L0,L1)-smooth with L0,L1≥0 and has a continuously differentiable gradient. A given point x0∈Rd has objective gap at most Δ≥0 above a global lower bound. The oracle returns either an unbiased stochastic gradient or an unbiased stochastic Hessian-vector product, using independent samples and allowing heavy-tailed, gradient-dependent errors. For ε>0, the goal is a measurable output x¯∈Rd with integrable gradient norm satisfying E∥∇f(x¯)∥≤ε, averaging over sampling and independent algorithm randomness.

The optimization problem is infx∈Rdf(x). We use the Euclidean norm ∥⋅∥ and its induced operator norm ∥⋅∥op. Let Ω be a measurable sample space. The noise parameters satisfy σg,αg,σh,αh≥0,1<p≤2,1<q≤2. The algorithm receives d, Ω, L0, L1, σg, αg, σh, αh, p, q, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Generalized smoothness). The function f is differentiable everywhere, its gradient is continuously differentiable, and ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈Rd. Here ∇2f(x) is a linear operator on Rd.

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

Assumption 3 (Stochastic gradient and Hessian-vector access). There exist a probability measure ν on Ω and jointly measurable maps g:Rd×Ω→Rd,h:(Rd×Rd)×Ω→Rd. 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 respective error norms to powers p and q are integrable, with Eξ∼ν[∥g(x,ξ)−∇f(x)∥p]≤σgp+αgp∥∇f(x)∥p,Eξ∼ν[∥h(x,v,ξ)−∇2f(x)v∥q]≤(σhq+αhq∥∇f(x)∥q)∥v∥q. At call k, a gradient query at x returns g(x,ξk), while a Hessian-vector query at (x,v) returns h(x,v,ξk). The measurable samples (ξk)k≥0 are mutually independent with common law ν, and are independent of the algorithm’s randomness.

Queries may use any x,v∈Rd. Each call requests one of the two replies, and both query types count toward a single oracle-call budget. After the allotted calls, the output x¯ must be measurable and satisfy EP[∥∇f(x¯)∥]≤ε, with ∥∇f(x¯)∥ integrable under P, the joint law of the samples and the algorithm’s randomness.

Proved result

⌈232⋅pp−1+16⋅qq−1+64⋅(pp−1+1)⋅(1+log⁡(2+(1+σgε+αg)+Δ⋅(L0+σh+(L1+αh)⋅(ε+σg1+αg))ε2+L0⋅Δ+L1⋅Δ+ε+σgε))⋅((1+σgε+αg)pp−1+Δ⋅(L0+σh+(L1+αh)⋅(ε+σg1+αg))ε2⋅((1+σgε+αg)pp−1q+(1+αg)2⋅(1+σgε+αg)pp−1−2))⌉+

OracleTemplate.Convergence LongTails.Setups.GeneralizedAffineHessianVector.spec
  OracleTemplate.HystereticAffineHessianTransport.budget

Relevant previous results

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