← All setups

Hessian Adaptive Cubic — Stochastic Convex Minimization with Hessians

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Convex Minimization with Hessians · Lean proof

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.

Proved result

3⋅⌈1000000000000000000⋅(1+(σg⋅Dε)2+σh⋅D2ε+(ρ⋅D3ε)27)⋅(1+log⁡((1+σhρ⋅D)⋅(1+(σg⋅Dε)2+σh⋅D2ε+(ρ⋅D3ε)27)))2⌉+

OracleTemplate.Convergence LongTails.Setups.HessianAdaptiveStochasticConvex.spec
  LongTails.Theorems.HessianAdaptiveCubic.budget

Relevant previous results

  • Artem Agafonov, Aslan Ashabokov, Dmitry Kamzolov, Alexander D’yakonov, Alexander Gasnikov, and Martin Takáč. Matching the Lower Bounds: Stochastic Contracting Cubic Newton and Its Optimal Acceleration. 2026 preprint, v2 (October 13; first submitted October 8). Complexity: O(1+(σgD/ε)2+σhD2/ε+(ρD3/ε)2/7) total stochastic gradient and Hessian oracle calls for E[f(wT)−f∗]≤ε, using Accelerated Stochastic Contracting Cubic Newton with known noise bounds; fixed cost of two gradient calls and one Hessian call per iteration.