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
The underlying optimization problem is
Our assumptions:
Assumption 1 (Hölder continuity). The function
Assumption 2 (Lower bound and initial gap). There
exists
Assumption 3 (Independent stochastic derivative
oracle). There exist a probability measure
Queries may be made at any point of
Results
Differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) ScalarHolderHeavyTailStationarity
(Ours) |
|||
| (2) (Liu 2025), Cor. 11
(Thm. 17), restricted to |
(1): For |
(1): Dimension one only;
(2) allows every |
|
| (3) Derived bound: dyadic probing, clipped estimation, union-bound bisection; random-search ingredient (Chewi et al. 2023) | (1): Removes |
(1): No order gain when
|
|
| (4) (Chewi et al. 2023),
Thm. 3; exact-gradient special case |
(1): Matches known rate
at |
(1): Much larger proved
prefactor, at least |
|
| (5) (Liu 2025), Cor. 12
(Thm. 17), parameter-free; restricted to |
(1): No established adaptivity improvement. | (1): Needs |
Abbr: