← All setups

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 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.

Results

Let f:Rd→R have L-Lipschitz gradient and f(x0)−inff≤Δ, with L,ε>0 and Δ≥0. A clean reply at x gives a value within ε2/(128L) of f(x) and a fixed vector g(x) satisfying ∥g(x)−∇f(x)∥≤ε/8. On every reachable history, at most k replies may be replaced adaptively by arbitrary pairs. The target is Pr(∥∇f(xout)∥>ε)≤δ for 0≤δ≤1/4.

Sufficient oracle budgets for nonconvex stationarity under adaptive corruption.
Result Oracle complexity Novelty Limitations
(1) CorruptedFirstOrderDescent (Ours) (⋆⋆⋆) (review) O(1+k+LΔ/ε2) joint value–gradient calls
(2) Derived bound: majority-vote gradient descent (Nesterov 2018, sec. 1.2.3) O((k+1)(1+LΔ/ε2)) gradient calls, including 2k+1 per vote (1): Additive dependence on k saves a factor of order min{k+1,T} for k,T≥1. At k≍T≥1, O(T2) falls to O(T). Rates match at k=0. (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 ε-stationary point for every admissible fault pattern. (3) bounds the time to visit one under probabilistic faults with bounded value errors. (1) needs a known fault cap k and repeatable clean gradients. (3) allows stochastic gradients without a fault cap.

Abbr: T=LΔ/ε2.

Nesterov, Yurii. 2018. Lectures on Convex Optimization. 2nd ed. Vol. 137. Springer Optimization and Its Applications. Springer. https://doi.org/10.1007/978-3-319-91578-4.
Scheinberg, Katya, and Miaolan Xie. 2025. Stochastic Adaptive Optimization with Unreliable Inputs: A Unified Framework for High-Probability Complexity Analysis. https://doi.org/10.48550/arXiv.2511.19411.

Lean setup