← All setups

Scalar Holder Heavy Tail Stationarity — Scalar Hölder Stochastic Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Scalar Hölder Stochastic Stationarity · Lean proof

Scalar Hölder Stochastic Stationarity

We consider a differentiable, possibly nonconvex function f:R→R with a globally Hölder continuous derivative. A given point x0∈R has objective gap at most Δ>0 above a global lower bound. At x, the oracle returns an unbiased scalar estimate of f′(x) using a fresh independent sample; its error has uniformly bounded pth absolute moment for 1<p≤2, allowing heavy-tailed noise. For ε>0, the goal is a measurable output x¯∈R satisfying P(|f′(x¯)|>ε)≤1/3, where P is the joint law of the samples and the algorithm’s independent randomness.

The underlying optimization problem is infx∈Rf(x), with accuracy measured by stationarity. Fix a measurable sample space Ω and parameters H>0,0<ν≤1,Δ>0,σ≥0,1<p≤2,ε>0. The algorithm receives Ω, H, ν, Δ, σ, p, ε, and x0; the objective and sampling distribution are accessed through the oracle.

Our assumptions:

Assumption 1 (Hölder continuity). The function f is differentiable everywhere, and |f′(x)−f′(y)|≤H|x−y|ν,x,y∈R.

Assumption 2 (Lower bound and initial gap). There exists ℓ∈R such that ℓ≤f(x)for every x∈R,f(x0)−ℓ≤Δ.

Assumption 3 (Independent stochastic derivative oracle). There exist a probability measure μ on Ω and a jointly measurable function g:R×Ω→R. For each x∈R, both g(x,⋅) and |g(x,⋅)−f′(x)|p are integrable under μ, and Eξ∼μ[g(x,ξ)]=f′(x),Eξ∼μ[|g(x,ξ)−f′(x)|p]≤σp. At call k≥0, a query x∈R receives the scalar reply g(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.

Queries may be made at any point of R. After the allotted oracle calls, the output x¯ must be measurable and satisfy P(|f′(x¯)|>ε)≤13.

Proved result

⌈2200p−1⋅(1+1ν)⋅(1+H11+ν⋅Δν1+νε+(σε)pp−1⋅log⁡(2+H11+ν⋅Δν1+νε))⌉+

OracleTemplate.Convergence LongTails.Setups.ScalarHolderStochastic.spec OracleTemplate.ScalarHolderStochastic.budget

Relevant previous results

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