← All setups

Generalized Smoothness with Hessian-Vector Oracles

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On Euclidean Rd, f has a continuously differentiable gradient, f≥m, f(x0)−m≤Δ, and ∥∇2f(x)∥≤L0+L1∥∇f(x)∥. Jointly measurable, integrable, unbiased gradient and Hessian-vector estimators g(x,ξ),h(x,v,ξ) use IID samples of law P0, with joint sample law P. For every x,v, their integrable central moments satisfy EP0∥g−∇f(x)∥p≤σgp+αgp∥∇f(x)∥p and EP0∥h−∇2f(x)v∥q≤(σhq+αhq∥∇f(x)∥q)∥v∥q, where 1<p,q≤2. All scale parameters and Δ are nonnegative; ε>0. Target: a measurable returned point X with ∫∥∇f(X)∥dP≤ε. Costs count every gradient or HVP reply, including initialization, batches, guards and validation.

Comparison for GeneralizedAffineHessianVector.
Result Oracle complexity Novelty Limitations
(1) GuardedAffineHessianTransport (Ours) (⋆⋆⋆) (review) O(Cpℓb+1[(1+S/ε)b+(ΔHε2+ΔεR)⋅(1+S/ε)b/q⋅(1+αg+σg/R)b])
(2) RanSOM-E (Chayti and Fakhouri 2026), Theorem B.24, Remark B.26 As ε↓0, fixed remaining parameters, σg,Δ>0, L1+αh>0: O(ε−(b+1)) for q>p; O(ε−(2+b/q)) for q≤p. Accuracy exponents only; batch and initialization costs included. (1): for q>p, exponent max{b,2+b/q} replaces b+1, up to logs. At p=3/2,q=2: O(ε−7/2ℓ4) versus O(ε−4). For q≤p, matches exponent. Improvement over a proved bound, not a lower bound. (1) adds logarithmic overhead and a large p-dependent prefactor; Euclidean scope versus general norms.
(3) RanSOM-E (Chayti and Fakhouri 2026), Remark B.26, σg=0 Derived bound, including batches: O((1+αg)b[1+Δ(L0+σh)ε2+Δ(L1+αh)ε]). (1): No established improvement in this regime. (1): when αg>0, retains (1+αgR/ε)b/q and logarithmic overhead; worse accuracy dependence for fixed positive parameters.
(4) RanSOM (Chayti and Fakhouri 2026), Corollary 4.8 / B.27 Special case L1=αg=αh=0: O(1+(σg/ε)b+Δ(L0+σh)ε2⋅[1+(σg/ε)b/q]). (1): Scope extends to generalized curvature and affine noise through guarded localization in expectation. Matches the accuracy exponent on the common setup. (1): extra ℓb+1(1+σg/R)b overhead on the common setup, and a large p-dependent prefactor.
(5) NSGD-Hess (Fradin et al. 2026), Theorem 5.1 Special case L1=αg=αh=0, additionally L2-Lipschitz Hessian and operator-norm Hessian moments. For fixed positive parameters as ε↓0: O(ε−max{b,2+b/q}). (1): removes Lipschitz-Hessian regularity, weakens operator-norm moments to directional HVP moments, and permits generalized curvature and affine noise. Matches the leading accuracy exponent on the overlap. (1): extra logarithms and (1+σg/R)b factors in shared stochastic terms.
(6) HystereticAffineHessianTransport (Ours) (⋆⋆⋆) (review) O(Dp,qλ[Ub+ΔJε−2⋅(Ub/q+(1+αg)2Ub−2)]). Here U=1+αg+σg/ε, J=L0+σh+(L1+αh)(ε+σg/(1+αg)), Dp,q=232b+16q/(q−1)(b+1), λ=1+log⁡(2+U+ΔJ/ε2+(R+σg)/ε).
(7) RanSOM-E (Chayti and Fakhouri 2026), Theorem B.24, Remark B.26; derived accuracy exponents O(ε−(b+1)) for q>p, Δ,L1,σg>0, remaining parameters fixed; O(ε−(2+b/q)) for q≤p. Includes batches and initialization. (6): O(ε−mλ) for q>p, m=max{b,2+b/q}<b+1. At p=3/2,q=2: ε−7/2λ instead of ε−4. Matches exponent for q≤p.
Relative to (1): linear Δ up to logs; λ replaces ℓb+1. For Δ=ε−a, a>0, fixed positive other parameters, exponents (1+a)m→a+m.
(6): extra logarithm and large Dp,q; Euclidean scope versus general norms.
(8) RanSOM (Chayti and Fakhouri 2026), Corollary 4.8 / B.27; L1=αg=αh=0 O(1+(σg/ε)b+Δ(L0+σh)ε−2⋅[1+(σg/ε)b/q]). (6): Scope extends to generalized curvature and affine noise. (6): extra log. If b(1−1/q)>2, ΔL0≥σg2, σg≥ε, additional polynomial factor up to min{ΔL0/σg2,(σg/ε)b−2−b/q} (e.g. p<4/3,q=2).
(9) RanSOM-E (Chayti and Fakhouri 2026), Remark B.26; σg=0, derived bound O((1+αg)b[1+Δ(L0+σh)/ε2+Δ(L1+αh)/ε]). (6): matches polynomial accuracy dependence. Relative to (1), removes accuracy-dependent localization overhead when αg>0. (6): retains logarithm, Dp,q, and potentially larger αg dependence through (1+αg)b/q.

Abbr: HVP: Hessian-vector product; norms are Euclidean or their induced operator norms. b=p/(p−1), R=L0Δ+L1Δ+ε, S=σg+αgR, H=L0+σh+(L1+αh)R, Cp=2100b(1+b), and ℓ=1+log⁡(2+R/ε+ΔH/ε2+Δ/(εR)+S/ε). L2 denotes the Hessian Lipschitz constant. Asymptotic accuracy bounds hold with all other parameters fixed; other prior-work big-O constants may depend on p,q.

Chayti, El Mahdi, and Mohamad Fakhouri. 2026. RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization. https://doi.org/10.48550/arXiv.2602.06824.
Fradin, Adrien, Abdurakhmon Sadiev, Laurent Condat, and Peter Richtárik. 2026. Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2512.18713.

Lean setup