← All setups

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 ε>0 for a possibly nonconvex function f:Rd→R in high dimension d. Its gradient is L-Lipschitz for L>0, and the value at a given starting point is within Δ>0 of a global lower bound. Except for at most k corrupted replies, each query returns an approximate function value and the value of a fixed, uniformly accurate gradient approximation, where k is a nonnegative integer. The goal is an output x¯∈Rd whose Euclidean gradient norm exceeds ε with probability at most δ∈[0,1/4].

The underlying optimization problem is infx∈Rdf(x). The algorithm receives d, L, Δ, ε, k, δ, and the starting point x0∈Rd. The dimension d is a positive integer, and the parameters satisfy LΔ≥226ε2,d≥232(⌊LΔ225ε2⌋+1)4.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is differentiable everywhere. With ∥⋅∥ denoting the Euclidean norm, its gradient satisfies ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈Rd. There exists ℓ∈R such that f(x)≥ℓ for every x∈Rd and f(x0)−ℓ≤Δ.

Assumption 2 (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,w)∈R×Rd. A reply is accurate if both conditions hold: |v−f(x)|≤ε2128L,w=g(x). Replies may depend on previous queries and replies. For every finite query sequence and every choice of oracle randomness along it, at most k replies fail the accuracy conditions.

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

Proved result

k+⌊L⋅Δ225⋅ε2⌋+

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.