Nonconvex Optimization with Mixed Relative Noise
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Mixed Relative Noise
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Initial objective gap). The given
point
Assumption 3 (Mixed relative noise). There exist a
probability measure
Queries may be made at any point of
After the allotted oracle calls, the output
Results
On a second-countable real Hilbert space with its Borel structure,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) MixedRelativeSmoothNonconvex
(Ours) |
|||
| (2) SGD (Khaled and Richtárik
2020), Cor. 1 ( |
(1): No worse in order.
For |
(1) needs the increment
condition, shared-sample pairs and known |
|
| (3) Normalized STORM
(Liu et al.
2023), Thm. 3.3 / Cor. 3.4, |
Raw MSS; sample-gradient oracles on |
(1): Rate replaces |
(1) uses growing batches
and |
| (4) PAGE (Li et al. 2021), Cor. 4 (online). | Expected gradient-call count; |
(1): Matches known |
Abbr: