Nonconvex Optimization with Expected Smoothness
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Expected Smoothness
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Lower bound and initial gap). There
exists
Assumption 3 (Unbiasedness and expected smoothness).
There exist a probability measure
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) NormalizedStormExpectedSmoothness
(Ours) |
|||
| (2) NSTORM (Upadhyay et al. 2026), Thm. 2(i), derived bound | (1): |
(1) needs ABC structure; (2) also handles distance-growing BG noise beyond ABC. | |
| (3) SGD (Khaled and Richtárik 2020), Cor. 1 | (1) reduces the leading
stochastic term by |
(1) needs MSS and
same-sample pairs (two gradients); (3) needs single
gradients and only objective smoothness |
|
| (4) SPIDER (Chen et al. 2023), Thm. 4, derived bound; affine-variance special case | (1): scope extends to ABC
without affine variance. For |
(1) has a worse |
|
| (5) SPIDER-SFO (Fang et al. 2018),
Thm. 1; bounded-variance special case |
(1) matches the known
rate at |
Abbr: MSS: mean-square smoothness; ABC: the
displayed function-gap variance bound; BG: Blum–Gladyshev noise.