Nonconvex Optimization with Symmetric Noise
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Symmetric 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 (Symmetry and tail radius). There exist
a probability measure
Assumption 3 (Relative-energy regularity). For every
Oracle queries may be made at any point of
After the allotted oracle calls, the output
Results
On a separable real Hilbert space with its Borel structure,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) FairRelativeEnergyNonconvex
(Ours) |
|||
| (2) NSGD-MVR (Fradin et al. 2026,
Thm. 4.2, v2), |
(1): On symmetric
overlap, |
(1) needs exact symmetry;
choose |
|
| (3) NSGD-MVR (Fradin et al. 2026,
Thm. 4.2, v2), |
(1): Matches polynomial
rate on symmetric overlap for |
(1) needs symmetry and
pays an extra |
|
| (4) N-SGD (Armacki et al. 2026, Thm. 1, v2); derived bound | (1): No density
condition. Rates are not comparable in |
(1) needs shared-sample pairs and relative-energy regularity; guarantees expectation rather than high probability. |
Abbr: The relative-energy ratio is zero when its
denominator is zero.