Nonconvex Stationarity with Corrupted First-Order Queries
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Stationarity with Corrupted First-Order Queries
We seek an approximate stationary point of a differentiable, possibly
nonconvex function
The underlying optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Initial objective gap). There exists
Assumption 3 (Corrupted first-order replies). There
exists a fixed map
After the allotted oracle calls, the output must satisfy
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CorruptedFirstOrderDescent
(Ours) |
|||
| (2) Derived bound: majority-vote gradient descent (Nesterov 2018, sec. 1.2.3) | (1): Additive dependence
on |
(1) needs accurate function values in addition to gradients. | |
| (3) Stochastic line search (Scheinberg and Xie 2025, Thm. 6, corrupted value oracle) | High-probability hitting time above the oracle noise floor. Each trial uses one gradient and two value calls. Rates are incomparable across fault models. | (1) returns an |
(1) needs a known fault
cap |
Abbr: