← All setups

Scalar Hölder Stochastic Stationarity

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Differentiable f:R→R satisfies |f′(x)−f′(y)|≤H|x−y|ν and f≥flow with f(x0)−flow≤Δ. Here H,Δ,ε>0, 0<ν≤1, σ≥0, and 1<p≤2. A jointly measurable oracle g has integrable values and central pth moments, ∫g(x,ω)dμ=f′(x) and ∫|g(x,ω)−f′(x)|pdμ≤σp. Samples are IID with law μ under a probability measure P. Target: measurable X with P(|f′(X)|>ε)≤1/3.

Scalar stochastic stationarity under a Hölder derivative: ScalarHolderStochastic.
Result Oracle complexity Novelty Limitations
(1) ScalarHolderHeavyTailStationarity (Ours) (⋆⋆) (review) O(2200/(p−1)(1+ν−1)
⋅[1+A+Qlog⁡(2+A)])
(2) (Liu 2025), Cor. 11 (Thm. 17), restricted to d=1 Oν,p((1+A1+1/ν)(1+Q)) (1): For A,Q≥1, additive A+Qlog⁡(2+A) replaces A1+1/νQ. At ν=1,p=2: O(HΔσ2/ε4) becomes O(HΔ/ε+(σ2/ε2)log⁡(2+HΔ/ε)). (1): Dimension one only; (2) allows every d. Probability guarantee replaces expected gradient-norm accuracy. Enormous prefactor.
(3) Derived bound: dyadic probing, clipped estimation, union-bound bisection; random-search ingredient (Chewi et al. 2023) Oν,p(1+A+Qlog⁡(2+A)
⋅log⁡log⁡(3+A))
(1): Removes log⁡log⁡(3+A) when Qlog⁡(2+A)≳A, via noisy backtracking with arbitrary sign changes; e.g., fixed positive H,Δ,σ and ε→0. (1): No order gain when A≳Qlog⁡(2+A)log⁡log⁡(3+A); retains the large constant blow-up.
(4) (Chewi et al. 2023), Thm. 3; exact-gradient special case σ=0, ν=1 O(1+HΔ/ε) (1): Matches known rate at σ=0,ν=1. Scope: allows Hölder derivatives and unbiased heavy-tailed noise, 1<p≤2. (1): Much larger proved prefactor, at least 2200.
(5) (Liu 2025), Cor. 12 (Thm. 17), parameter-free; restricted to d=1 Oν,p(1+A+(Δ/ε)4
+(H/ε)4/ν+Q2)
(1): No established adaptivity improvement. (1): Needs H,ν,Δ,σ,p for tuning; (5) does not. Dimension one only; no expected gradient-norm guarantee.

Abbr: A=H1/(1+ν)Δν/(1+ν)/ε, Q=(σ/ε)p/(p−1); costs count individual gradient-oracle calls, including estimation samples. Oν,p fixes ν,p; rate comparisons fix these parameters. In (2), (5), a uniformly selected block average with expected gradient norm at most ε/3 gives the target by Markov’s inequality. log is natural; ≳ suppresses fixed factors.

Chewi, Sinho, Sébastien Bubeck, and Adil Salim. 2023. “On the Complexity of Finding Stationary Points of Smooth Functions in One Dimension.” Proceedings of the 34th International Conference on Algorithmic Learning Theory, Proceedings of machine learning research, vol. 201: 358–74. https://proceedings.mlr.press/v201/chewi23a.html.
Liu, Zijian. 2025. Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications. https://doi.org/10.48550/arXiv.2508.07473.

Lean setup