High-Dimensional Nonconvex Optimization with ABC Noise
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Nonconvex Optimization with ABC Noise
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Parameter and dimension regime). The
parameters satisfy
Assumption 2 (Smoothness and initial gap). The
function
Assumption 3 (IID stochastic gradients with ABC
noise). There exist a probability measure
Queries may be made at any point of
Results
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AbcNoiseLowerBound
(Ours) |
Necessary |
||
| (2) (Arjevani et
al. 2022; Carmon et al. 2019), Thms. 3 and 2 ( |
Necessary |
(1): adds |
(1): quartic dimension
requirement; much worse universal constant on |
| (3) Derived bound from (Arjevani et al. 2022), Thm. 3; lower-offset model | Necessary |
(1): same |
|
| (4) (Huang et al. 2022),
Thm. 1; synchronous zero-respecting algorithms, |
Necessary |
(1): arbitrary randomized algorithms with one IID oracle; (4) restricts algorithms and uses compression. Rates are not comparable across these models and accuracy criteria. |
Abbr: