Nonconvex Optimization with Hölder Noise
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Hölder Noise
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Unbiased stochastic gradients). There
exist a probability measure
Assumption 3 (Hölder noise increments). Define the
centered noise by
At call
After the allotted calls, the output
Results
On a separable real Hilbert space with its Borel measurable
structure,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) HolderNoiseMinimaxUpper
(Ours) |
|||
| (2) SGD/RSG (Ghadimi and Lan 2013), Cor. 2.2; finite-dimensional specialization | (1): Noise term reduced
by |
(1) needs centered Hölder regularity and paired same-sample access; guarantees expected norm rather than the stronger squared-norm criterion. | |
| (3) NSGD-MVR (Fradin et al.
2026), Thm. 4.2, |
(1): Scope extends the
distance exponent from |
(1) incurs an |
|
| (4) (LongTails
2026); raw Hölder increments, |
(1): Scope extends to
centered noise and |
Abbr: