← All setups

Gated Perturbed Escape Sosp — Variance-Only Second-Order Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Variance-Only Second-Order Stationarity · Lean proof

Variance-Only Second-Order Stationarity

We consider minimizing a possibly nonconvex function f:E→R on a positive-dimensional finite-dimensional real inner product space E. The function is twice continuously differentiable, with L-Lipschitz gradient and ρ-Lipschitz Hessian, where L,ρ>0. A given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ≥0. The oracle returns unbiased stochastic gradients from independent, identically distributed samples, with variance at most σ2, where σ≥0. For ε>0 and δ∈(0,1) satisfying ρε≤L2, the goal is a measurable output x¯∈E satisfying ∥∇f(x¯)∥≤ε and ⟨v,∇2f(x¯)v⟩≥−ρε∥v∥2 for every v∈E, with probability at least 1−δ.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The Hessian ∇2f(x):E→E is the derivative of the gradient. The algorithm receives E, the measurable sample space Ω, L, ρ, σ, Δ, ε, δ, and x0.

Our assumptions:

Assumption 1 (Smoothness). The function f belongs to C2(E;R), and, for every x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥.

Assumption 2 (Initial objective gap). The given starting point satisfies f(x0)−f(x)≤Δ,x∈E.

Assumption 3 (Stochastic gradient oracle). There are a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. The samples (ξk)k≥0 are measurable, mutually independent random variables with common law ν under a joint probability law Q on ΩN. At its kth query x∈E, the oracle returns g(x,ξk).

For every fixed x∈E, the map 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. Any algorithm randomness is independent of the sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the algorithm must return a measurable output x¯ such that P(∥∇f(x¯)∥≤ε,⟨v,∇2f(x¯)v⟩≥−ρε∥v∥2for every v∈E)≥1−δ, where P is the joint law of the algorithm randomness and the sample sequence with law Q.

Proved result

⌈240⋅(log⁡(4096⋅log⁡(20480⋅dimR⁡(E))⋅Lρ⋅ε⋅(1+ρ⋅Δε⋅ε)δ))2⋅(log⁡(20480⋅dimR⁡(E)))4⋅Lρ⋅ε⋅(1+ρ⋅Δε⋅ε)⌉+⋅(⌈254⋅(log⁡(20480⋅dimR⁡(E)))4⋅(1+dimR⁡(E)⋅σ2⋅ρL⋅ε⋅ε+σ2ε2)⌉++1)

OracleTemplate.Convergence LongTails.Setups.VarianceOnlySecondOrder.spec OracleTemplate.GatedPerturbedEscapeSosp.budget

Relevant previous results

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