← All setups

Symmetric Third Order — Stochastic Convex Third-Order Regularity

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Convex Third-Order Regularity · Lean proof

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.

Proved result

⌈2100⋅(1+σh⋅R2ε+(L3⋅R4ε)15+σg2⋅R2ε2)⋅(1+log⁡(2+Δε+σh⋅R2ε+L3⋅R4ε))4⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticThirdDerivativeConvex.spec
  LongTails.Theorems.SymmetricThirdOrder.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.