Nonconvex Optimization with Hölder Noise
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Hölder Noise
We consider a differentiable, possibly nonconvex function
The underlying optimization problem is
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Unbiased gradients and Hölder noise).
There exist a probability distribution
The sample sequence
After the allotted calls, the output
Results
On
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) HolderNoiseMinimaxLowerBound
(Ours) |
Lower bound; failure through pair-call
budget |
||
| (2) (Arjevani et al. 2023), Thm. 3, (24); mean-squared-smooth special case | Lower bound; failure through |
(1): extends hardness to
every |
(1): larger dimension
requirement versus |
| (3) (Arjevani et al. 2023), Thm. 3, (23); bounded-variance superclass | Lower bound; failure through |
(1): re-establishes
hardness inside the Hölder subclass; recovers the |
|
| (4) (Jin 2026), Thm. 4.1; bounded-error, single-point model | Lower bound; failure through |
(1): proves Hölder-class hardness despite paired queries. (4) uses discontinuous noise and one point per fresh sample; rates are not comparable. |
Abbr: