← All setups

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 f:Rd→R in Euclidean dimension d. Its gradient is L-Lipschitz for L>0, and its value at a given starting point lies within Δ≥0 of a global lower bound. For a tolerance ε>0, the oracle returns an approximate function value and a fixed gradient approximation at the query point, except on at most k calls in any possible history, where k is a nonnegative integer. The goal is an output x¯∈Rd satisfying ∥∇f(x¯)∥≤ε with failure probability at most δ∈[0,1/4].

The underlying optimization problem is infx∈Rdf(x). We use the Euclidean norm ∥⋅∥. The algorithm receives the dimension d∈{0,1,…}, the starting point x0∈Rd, and the parameters L,Δ,ε,k,δ.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere and satisfies ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈Rd.

Assumption 2 (Initial objective gap). There exists ℓ∈R such that ℓ≤f(x)for every x∈Rd,f(x0)−ℓ≤Δ.

Assumption 3 (Corrupted first-order replies). There exists a fixed map g:Rd→Rd satisfying ∥g(x)−∇f(x)∥≤ε/8,x∈Rd. At any query point x∈Rd, the oracle returns a pair (v,u)∈R×Rd. A reply is accurate when both conditions hold: |v−f(x)|≤ε2128L,u=g(x). Every finite history obtainable from any sequence of queries and any choices of oracle randomness contains at most k inaccurate replies. These replies may be arbitrary.

After the allotted oracle calls, the output must satisfy P(∥∇f(x¯)∥>ε)≤δ, where P is the joint law of the algorithm and oracle randomness, which are independent of one another.

Proved result

⌈16⋅L⋅Δε2⌉++5⋅k+4

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.