Nonconvex Optimization with ABC Noise
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with ABC Noise
We consider a differentiable, possibly nonconvex function
The underlying optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Finite infimum and initial gap). There
exists
Assumption 3 (Independent unbiased oracle with ABC
noise). There exist a probability measure
Queries may be made at any point of
Results
A differentiable, possibly nonconvex function
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AbcNoiseSgdUpperBound (Ours) (review) | |||
| (2) SGD (Khaled and
Richtárik 2020), Cor. 1 and Lemma 2; |
(1): Matches known rate and tuning knowledge; Hilbert-space formalization. Uniform sampling already follows from Lemma 2 at constant cost. | (1): Larger displayed
constants on the |
|
| (3) RSG (Ghadimi and Lan
2013), Cor. 2.2; special case |
(1): Scope: ABC noise
instead of bounded variance, already covered by (2).
Matches known rate on |
Abbr: