Corrupted First Order Descent — Nonconvex Stationarity with Corrupted First-Order Queries
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Stationarity with Corrupted First-Order Queries · Lean proof
Nonconvex
Stationarity with Corrupted First-Order Queries
We seek an approximate stationary point of a differentiable, possibly
nonconvex function in Euclidean
dimension . Its gradient is -Lipschitz for , and its value at a given starting
point lies within of a
global lower bound. For a tolerance , the oracle returns an
approximate function value and a fixed gradient approximation at the
query point, except on at most
calls in any possible history, where is a nonnegative integer. The goal is
an output
satisfying with failure probability at most
.
The underlying optimization problem is We use the
Euclidean norm . The
algorithm receives the dimension , the starting point
, and the
parameters .
Our assumptions:
Assumption 1 (Smoothness). The function is Fréchet differentiable everywhere
and satisfies
Assumption 2 (Initial objective gap). There exists
such that
Assumption 3 (Corrupted first-order replies). There
exists a fixed map satisfying
At any query point , the oracle returns a
pair . A
reply is accurate when both conditions hold: Every finite history obtainable from any sequence
of queries and any choices of oracle randomness contains at most inaccurate replies. These replies may
be arbitrary.
After the allotted oracle calls, the output must satisfy where is the joint law of the algorithm and
oracle randomness, which are independent of one another.
Proved result
OracleTemplate.Convergence LongTails.Setups.CorruptedFirstOrderNonconvex.spec
LongTails.Theorems.CorruptedFirstOrderDescent.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.