Corrupted First Order Lower Bound — 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 · Lean proof
High-Dimensional
Stationarity with Corrupted First-Order Queries
We seek a stationary point to tolerance for a possibly nonconvex
function in high
dimension . Its gradient is -Lipschitz for , and the value at a given starting
point is within of a
global lower bound. Except for at most corrupted replies, each query returns
an approximate function value and the value of a fixed, uniformly
accurate gradient approximation, where is a nonnegative integer. The goal is
an output
whose Euclidean gradient norm exceeds with probability at most
.
The underlying optimization problem is The
algorithm receives , , , , , , and the starting point . The dimension is a positive integer, and the
parameters satisfy
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
everywhere. With denoting
the Euclidean norm, its gradient satisfies There exists such that for every and .
Assumption 2 (Corrupted first-order replies). There
exists a fixed map satisfying
At any
query point , the
oracle returns a pair . A
reply is accurate if both conditions hold: Replies may depend on previous queries and replies. For
every finite query sequence and every choice of oracle randomness along
it, at most replies fail the
accuracy conditions.
After the allotted calls, the output must satisfy where is the joint law of the independent
algorithm and oracle randomness.
Proved result
OracleTemplate.NonConvergence LongTails.Setups.HighDimensionalCorruptedFirstOrderNonconvex.spec
LongTails.Theorems.CorruptedFirstOrderLowerBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.