← All setups

Stochastic Convex Third-Order Regularity

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Convex Third-Order Regularity

We consider minimizing a convex, three-times continuously differentiable function f:Rd→R, where d≥0 is an integer, with L3-Lipschitz third derivative, L3>0. A given point x0 satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a global minimizer x⋆ and R,Δ>0. Each oracle call returns gradient and Hessian estimates using a shared sample, independently across calls. The gradient estimate is unbiased; their mean squared errors are bounded by σg2 and σh2, respectively, where σg,σh≥0. For ε>0, the goal is a measurable output x¯ within distance R of x0 for every realization, with f(x¯)−f(x⋆)≤ε with probability at least 2/3.

The optimization problem is minx∈Rdf(x). We use the Euclidean norm ∥⋅∥ and its induced operator and multilinear norms ∥⋅∥op. The algorithm receives d,x0,L3,R,Δ,ε,σg,σh.

Our assumptions:

Assumption 1 (Convexity and third-derivative regularity). The function f belongs to C3(Rd;R). For every x,y∈Rd and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇3f(x)−∇3f(y)∥op≤L3∥x−y∥. Here ∇3f(x) is the trilinear third derivative; equivalently, its norm is that of the second derivative of the gradient, viewed as a bilinear map into Rd.

Assumption 2 (Minimizer and initial bounds). There is a fixed x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 3 (Paired stochastic oracle). Let Ω be a measurable sample space with probability measure ν. There are jointly measurable maps g:Rd×Ω→Rd,H:Rd×Ω→L(Rd,Rd), where L(Rd,Rd) denotes the space of linear operators. For each fixed x∈Rd, the random vector g(x,ξ) is Bochner integrable for ξ∼ν, and both squared errors below are integrable. They satisfy Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σg2,Eξ∼ν[∥H(x,ξ)−∇2f(x)∥op2]≤σh2. The measurable samples (ξk)k≥0 are mutually independent with common law ν, and are independent of the algorithm’s randomness. At call k, a query x∈Rd returns the pair (g(x,ξk),H(x,ξk)). Both components use the same sample, and the pair counts as one oracle call.

Queries may be made anywhere in Rd. After the allotted oracle calls, the output x¯ must be measurable and satisfy ∥x¯−x0∥≤Rfor every realization, and the accuracy requirement is P(f(x¯)−f(x⋆)≤ε)≥23, where P is the joint law of the algorithm’s randomness and the oracle samples.

Results

Convex f∈C3(Rd) has globally L3-Lipschitz third derivative; a minimizer x⋆ satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ. Known L3,R,Δ,ε>0 and σg,σh≥0 tune (1). Jointly measurable oracles use fresh IID samples with law p: ∫g(x,ω)dp=∇f(x), ∫∥g(x,ω)−∇f(x)∥2dp≤σg2, and ∫∥H(x,ω)−∇2f(x)∥2dp≤σh2, with the corresponding integrability conditions. Hessians need not be unbiased, symmetric, or positive semidefinite. Target: measurable x^∈B¯(x0,R) and P{f(x^)−f(x⋆)≤ε}≥2/3 under the IID sampling law P.

Comparison for StochasticThirdDerivativeConvex.
Result Oracle complexity Novelty Limitations
(1) SymmetricThirdOrder (Ours) (⋆⋆⋆) (review) O([1+σhR2ε+(L3R4ε)1/5+σg2R2ε2]ℓ4) joint gradient–Hessian calls
(2) Accelerated stochastic contracting cubic Newton (Agafonov et al. 2026, Theorem 5.1) O(1+σg2R2ε2+σhR2ε+(L2R3ε)2/7) calls, including the fresh correction gradient; Markov conversion to 2/3 confidence. (1): Faster when deterministic terms dominate and (L3R4/ε)1/5ℓ4≪(L2R3/ε)2/7. Noise-free quartic f=∥x∥4, ∥x0∥=R: O((1+R4/ε)1/5ℓ4) versus O((1+R4/ε)2/7). (1) needs global regularity/oracles; (2) only L2-Lipschitz Hessian on the ball and PSD symmetric samples. Loses expected-error guarantee; ℓ4 overhead when noise dominates.
(3) AINE (Chen et al. 2026, Corollary 4.1) O([1+δR2ε+(L3R4ε)1/5]Λ) total value/gradient/inexact-Hessian calls, including inner solves. Special case: exact gradients, symmetric deterministic Hessian errors uniformly bounded by δ>0. (1) extends to finite-variance gradients and second-moment Hessian errors, with additive statistical cost. Matches polynomial orders at σg=0, σh=δ; logarithms omit initial derivative norms. (1) gives 2/3 confidence instead of deterministic accuracy; incurs ℓ4 overhead.

Abbr: ℓ=1+log⁡(2+Δ/ε+σhR2/ε+L3R4/ε); L2 is the Hessian Lipschitz constant on B¯(x0,R). Λ≥1 denotes the polylogarithmic inner-solve factor in Theorem 4.1 of (Chen et al. 2026), depending on δ−1,ε−1,L3,R(x0),∥∇kf(x0)∥ (k=1,2,3); R(x0) is its initial sublevel-set radius. Operator errors use spectral norms.

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.
Chen, Lesi, Chengchang Liu, Luo Luo, John C. S. Lui, and Jingzhao Zhang. 2026. Optimal Convex Optimization with Inexact Second-Order Oracles. https://arxiv.org/abs/2607.24520v3.

Lean setup