← All setups

Stochastic Convex Minimization with Hessians

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Convex Minimization with Hessians

We consider minimizing a convex function f:Rd→R over a nonempty compact convex set C, where d is a nonnegative integer. The gradient is differentiable everywhere, and the Hessian is Lipschitz on C. At each query, the oracle returns either an unbiased stochastic gradient or a possibly biased, symmetric positive semidefinite Hessian estimate, using independent, identically distributed samples. Both estimates have bounded mean-square error on C. For ε>0, the goal is a measurable output x¯ lying in C for every realization and satisfying E[f(x¯)−f(x⋆)]≤ε, where x⋆ minimizes f on C and expectation includes oracle and algorithm randomness.

The optimization problem is minx∈Cf(x). We use the Euclidean inner product and norm on Rd; ∥⋅∥op denotes the induced operator norm. The parameters satisfy D>0,ρ>0,σg≥0,σh≥0,ε>0. The algorithm receives only d, C, a given point x0, D, ρ, and σg; σh and ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Feasible set and minimizer). The set C⊆Rd is nonempty, compact, and convex, and x0∈C,∥x−y∥≤Dfor all x,y∈C. There is a fixed x⋆∈C such that f(x⋆)≤f(x) for every x∈C.

Assumption 2 (Convexity and Hessian regularity). The function f is differentiable on Rd, its gradient is differentiable on Rd, and f((1−t)x+ty)≤(1−t)f(x)+tf(y)(x,y∈Rd, t∈[0,1]). Its Hessian satisfies ∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥,x,y∈C.

Assumption 3 (Stochastic gradient and Hessian estimates). Let ν be a probability measure on a measurable sample space Ω. The maps g:Rd×Ω→Rd,H:Rd×Ω→L(Rd,Rd) are jointly measurable, where L(Rd,Rd) is the space of linear operators equipped with its operator norm and Borel sigma-algebra. For every x∈C, g(x,⋅) is Bochner integrable under ν, and both squared error norms below are integrable. They satisfy Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σg2,Eξ∼ν[∥H(x,ξ)−∇2f(x)∥op2]≤σh2. For every x∈C, ω∈Ω, and u,v∈Rd, ⟨u,H(x,ω)v⟩=⟨H(x,ω)u,v⟩,⟨u,H(x,ω)u⟩≥0.

At call k≥0, the algorithm chooses a point x∈Rd and requests either g(x,ξk) or H(x,ξk). The samples (ξk)k≥0 are measurable, mutually independent, and each has law ν; the algorithm’s randomness is independent of the entire sample sequence. Each request returns only the selected estimate and counts as one call toward a common budget. Queries may be made throughout Rd, while the stated oracle error and positivity conditions apply on C.

After the allotted calls, the output x¯ must be measurable and belong to C for every realization. The objective gap must be integrable and satisfy EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the algorithm’s randomness and the oracle sample sequence.

Results

Convex differentiable f:Rd→R has differentiable gradient and ρ-Lipschitz Hessian on a compact convex body C of diameter at most D; x0,x⋆∈C, x⋆∈arg⁡minCf, D,ρ,ε>0. Jointly measurable oracles use IID samples of law μ under P, with ∫g(x,ω)dμ=∇f(x), ∫∥g(x,ω)−∇f(x)∥2dμ≤σg2, and ∫∥H(x,ω)−∇2f(x)∥op2dμ≤σh2 on C. Hessian samples are symmetric PSD pointwise and may be biased; the stated moments are integrable. Target: measurable feasible output w with integrable gap and ∫[f(w)−f(x⋆)]dP≤ε.

Stochastic convex optimization with adaptive Hessian-noise tuning: HessianAdaptiveStochasticConvex.
Result Oracle complexity Novelty Limitations
(1) HessianAdaptiveCubic (Ours) (⋆⋆) (review) O(Q[1+log⁡((1+σh/(ρD))Q)]2) gradient and Hessian calls in total; two gradients and one Hessian per round.
(2) (Agafonov, Ashabokov, Kamzolov, et al. 2026), Thm. 5.1, Alg. 2 (M=ρ) O(1+σg2D2ε2+σhD2ε+(ρD3ε)2/7) total gradient and Hessian calls; same three calls per round. (1): Updates need no σh; stopping budget still does. Matches polynomial orders, with squared-logarithmic overhead. (1): Extra logarithm squared and larger leading constant; independent gradient/Hessian samples instead of allowing shared samples.
(3) Extra-Newton (Antonakopoulos et al. 2022), Thm. 3.2 (γ=D); unbiased-Hessian subclass O(1+σg2D2ε2+(σhD2ε)2/3+(ρD3+β0Dε)1/3) total gradient and Hessian calls. (1): On the unbiased PSD overlap, Hessian term (σhD2/ε)1/2 instead of (σhD2/ε)2/3; curvature (ρD3/ε)2/7 instead of (ρD3/ε)1/3, up to log squared. Gains matter when these dominate gradient noise, allowing for logarithms. Scope: biased PSD Hessians. (1): Needs ρ,σg in updates; requires PSD samples. (3) needs neither noise levels nor ρ.
(4) (Agafonov, Ashabokov, D’yakonov, et al. 2026), Thm. 4.1 and App. F.4; unconstrained, exact-gradient special case O(1+log+⁡max{η0,τ¯0}ρR+δ+log+⁡τ¯0η0+(ρR3ε)2/7+δR2ε) total calls, including gradient trials. Global ρ-Lipschitz Hessian; uniform error ∥H−∇2f∥op≤δ. (1): Supports constraints, stochastic gradients and RMS Hessian error. Full classes are incomparable; no established rate improvement. (1): Requires known ρ,σg and bounded C. (4) already adapts to ρ,δ and additionally covers generalized Hessian smoothness.

Abbr: σg,σh≥0: gradient and Hessian RMS errors; PSD: positive semidefinite. Q=1+σg2D2/ε2+(σhD2/ε)1/2+(ρD3/ε)2/7. One call returns one gradient or one Hessian. β0>0: Extra-Newton scale initialization. R=∥x0−x⋆∥ (at most D on the overlap); δ: uniform Hessian error; η0>0: initial regularization; τ¯0=max{4δ,2ρ∥∇f(x0)∥}; log+⁡t=max{0,log⁡t}.

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://doi.org/10.48550/arXiv.2609.32977.
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://doi.org/10.48550/arXiv.2610.11693.
Antonakopoulos, Kimon, Ali Kavis, and Volkan Cevher. 2022. “Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods.” Advances in Neural Information Processing Systems 35: 29859–72. https://doi.org/10.52202/068431-2165.

Lean setup