Mean-Squared Hölder Nonconvex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Mean-Squared Hölder Nonconvex Optimization
We consider finding an approximate stationary point of a
differentiable, possibly nonconvex function
The underlying 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 (Mean-squared Hölder continuity). For
every
At call
After the allotted calls, the output
Results
On a second-countable real Hilbert space with its Borel measurable
structure,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) DyadicVarianceReductionHolder
(Ours) |
|||
| (2) SGD (Ghadimi and Lan 2013), Cor. 2.2 | (1): Leading noise term
gains |
(1): Needs Hölder
regularity, paired access, and |
|
| (3) SPIDER (Fang et al. 2018),
Thm. 1; special case |
(1): Scope extends
mean-squared Lipschitz regularity to |
(1): Extra |
|
| (4) Derived bound: SPIDER recursion (Fang et al. 2018) under the stated Hölder condition | (1): Leading-term gain
|
(1): Extra |
|
| (5) NSGD-MVR (Fradin et al.
2026), Thm. 4.1, |
(1): Ramp overlap, |
(1): Requires the
second-moment Hölder bound. |
|
| (6) Adaptive STORM (Cutkosky and Orabona
2020), Thm. 1; sample gradients |
Derived total bound: |
(1): Scope extends to
Hölder sample regularity with |
(1): Needs known |
Abbr: