← All setups

Stochastic Local Hessian Accelerated — Stochastic Convex Local Hessian Regularity

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Convex Local Hessian Regularity · Lean proof

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⋆)>ε}≤β.

Proved result

Oracle 0:⌈280⋅(1+(M1⋅R2)13+(Rρ)23+(M0⋅R3ε)27+δ⋅R2ε+σ2⋅R2ε2)⋅(log⁡(2+Δε+δ⋅R2ε+M0⋅R3ε+M1⋅R2+(Rρ)2+1β+σ2⋅R2ε2))3⌉+ Oracle 1:⌈280⋅(1+(M1⋅R2)13+(Rρ)23+(M0⋅R3ε)27+δ⋅R2ε)⋅(log⁡(2+Δε+δ⋅R2ε+M0⋅R3ε+M1⋅R2+(Rρ)2+1β+σ2⋅R2ε2))3⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticLocalHessianConvex.spec
  LongTails.Theorems.StochasticLocalHessianAccelerated.budget

Relevant previous results

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