← All setups

Stochastic Convex Local Hessian Regularity

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Convex Local Hessian Regularity

We consider minimizing a twice continuously differentiable convex function f:Rd→R, where d is a nonnegative integer. Its Hessian is locally Lipschitz with a bound depending on the gradient norm. A given point x0 has bounded distance and objective gap to a global minimizer x⋆. Two oracles return unbiased stochastic gradients with bounded variance using independent identically distributed samples, and deterministic uniformly accurate Hessian approximations. For ε>0 and β∈(0,1), the goal is a measurable output x¯ satisfying P{f(x¯)−f(x⋆)>ε}≤β, where P is the joint law of oracle and algorithm randomness.

The optimization problem is minx∈Rdf(x). We use the Euclidean norm ∥⋅∥ and its induced operator norm ∥⋅∥op on linear maps from Rd to itself. The parameters satisfy M0,M1,δ,σ≥0,ρ,R,Δ,ε>0,β∈(0,1). The algorithm receives d, the measurable sample space Ω, x0∈Rd, and all the parameters M0,M1,ρ,δ,σ,R,Δ,ε,β.

Our assumptions:

Assumption 1 (Convexity and initialization). The function f belongs to C2(Rd) and satisfies, for every x,y∈Rd and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y). There is a global minimizer x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 2 (Local Hessian regularity). For every x,y∈Rd with ∥y−x∥≤ρ, ∥∇2f(y)−∇2f(x)∥op≤(M0+M1∥∇f(x)∥)∥y−x∥.

Assumption 3 (Stochastic gradients and approximate Hessians). There are a probability measure ν on Ω, a jointly measurable map g:Rd×Ω→Rd, and a measurable map H taking each point in Rd to a linear operator on Rd. For every x∈Rd, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable under ξ∼ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σ2,∥H(x)−∇2f(x)∥op≤δ. The sample sequence (ξk)k≥0 consists of measurable, mutually independent random variables with common law ν, and is independent of the algorithm’s randomness. At the kth oracle call, a gradient query at x returns g(x,ξk), while a Hessian query at x returns the deterministic operator H(x).

Queries to either oracle may be made at any point of Rd. Gradient calls and Hessian calls have separately counted budgets. After the allotted calls, the output x¯∈Rd must be measurable and satisfy P{f(x¯)−f(x⋆)>ε}≤β.

Results

Convex f∈C2(Rd) has a minimizer x⋆, ∥x0−x⋆∥≤R, and f(x0)−f(x⋆)≤Δ. For ∥y−x∥≤ρ, ∥∇2f(y)−∇2f(x)∥≤(M0+M1∥∇f(x)∥)∥y−x∥. IID samples have law p0 under P; jointly measurable g has integrable unbiased gradients ∫g(x,ω)dp0=∇f(x) and integrable squared error with integral at most σ2. Measurable deterministic H satisfies ∥H(x)−∇2f(x)∥≤δ. Here M0,M1,δ,σ≥0, R,Δ,ρ,ε>0, and 0<β<1. Target: measurable output with P{f(out)−f(x⋆)>ε}≤β.

Comparison for StochasticLocalHessianConvex.
Result Oracle complexity Novelty Limitations
(1) StochasticLocalHessianAccelerated (Ours) (⋆⋆) (review) G: O((B+C+D+S)ℓ3);
H: O((B+C+D)ℓ3)
(2) (Agafonov, Ashabokov, Kamzolov, et al. 2026), Thm. 5.1. Derived bound; M1=0 G: O(1+S/β2+D/β+C/β2/7);
H: omit S/β2. Ball restriction, symmetrization/PSD shift, batching and Markov.
(1): Scope extends to M1>0. For M1=0, ρ=R, noise-dominated costs improve from O(Sβ−2) to O(Sℓ3) when β−2≫ℓ3. (1): ℓ3 overhead at fixed confidence; larger leading constant. Requires deterministic Hessians and Δ,β; lacks expected-gap guarantee.
(3) (Agafonov, Ashabokov, D’yakonov, et al. 2026), Thm. 4.1, Cor. F.6; σ=0 H: O(BJ+C+D);
G: O(BJ+C+D+log+⁡(τ¯0/η0)+BQJ2/3). Includes backtracking.
(1): Scope extends exact gradients to unbiased finite-variance gradients under local gradient-dependent Hessian variation. (1): Requires all setup parameters; (3) is parameter-free. Extra ℓ3 on polynomial Hessian terms; only probabilistic accuracy.
(4) (Agafonov et al. 2024), Thm. 3.2. Derived bound; M1=0 G: O(1+S/β2+D/β+(M0R3/(βε))1/3);
H: omit S/β2. Batching and Markov.
(1): Scope extends to M1>0. On M1=0, curvature exponent 2/7 replaces 1/3, up to ℓ3; confidence dependence becomes logarithmic. (1): Deterministic Hessians; needs Δ,β; lacks expected-gap guarantee. Noise term pays ℓ3 at fixed confidence; larger leading constant.

Abbr: G,H: gradient and Hessian calls, including batches. B=1+(M1R2)1/3+(R/ρ)2/3, C=(M0R3/ε)2/7, D=δR2/ε, S=σ2R2/ε2. ℓ=log⁡(2+Δ/ε+δR2/ε+M0R3/ε+M1R2+(R/ρ)2+β−1+S). For (3), η0>0 is the initial regularization guess, g0=∥∇f(x0)∥, τ¯0=max{4δ,2(M0+M1g0)g0,2g0/ρ}, J=1+log+⁡(max{η0,τ¯0}R2/ε), r0=min{ρ/2,1/(6M1)}, g¯=max∥x−x⋆∥≤(1+2/3)R∥∇f(x)∥, Q=log+⁡((δ+g¯/r0)/(δ+M0r0)). log+⁡t=max{0,log⁡t}, log+⁡0=0, and 1/0=+∞ in r0; the displayed bound is vacuous if Q=+∞.

Agafonov, Artem, Aslan Ashabokov, Alexander D’yakonov, Martin Takáč, Alexander Gasnikov, and Dmitry Kamzolov. 2026. Optimal Parameter-Free Second-Order Acceleration with Inexact Hessians Under Generalized Smoothness. https://arxiv.org/abs/2609.32977v1.
Agafonov, Artem, Aslan Ashabokov, Dmitry Kamzolov, Alexander D’yakonov, Alexander Gasnikov, and Martin Takáč. 2026. Matching the Lower Bounds: Stochastic Contracting Cubic Newton and Its Optimal Acceleration. https://arxiv.org/abs/2610.11693v2.
Agafonov, Artem, Dmitry Kamzolov, Alexander Gasnikov, et al. 2024. Advancing the Lower Bounds: An Accelerated, Stochastic, Second-Order Method with Optimal Adaptation to Inexactness. https://arxiv.org/abs/2309.01570v3.

Lean setup