High-Dimensional Stationarity with Corrupted First-Order Queries
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Stationarity with Corrupted First-Order Queries
We seek a stationary point to tolerance
The underlying optimization problem is
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Corrupted first-order replies). There
exists a fixed map
After the allotted calls, the output
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CorruptedFirstOrderLowerBound (Ours) (review) | Lower bound: |
||
| (2) (Carmon et al. 2020,
Thm. 2) Randomized, exact oracle, |
Lower bound: |
(1) extends
(2) by prefixing |
(1) needs quartic
dimension versus |
| (3) (Carmon et al. 2020,
Thm. 1) Deterministic, exact oracle, |
Lower bound: |
(1) extends hardness to randomized algorithms and matches (3) on the clean deterministic restriction. | (1) needs quartic
dimension. For deterministic algorithms, prefixing (3)
with |
Abbr: