← All setups

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

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.

Results

Let f:Rd→R have L-Lipschitz gradient and f(x0)−inff≤Δ, with L,ε>0. Assume T≥226 and d≥232(1+⌊T/225⌋)4. A randomized algorithm may query anywhere. Along every history, all replies except at most k at query points x have the form (v,g(x)), where |v−f(x)|≤ε2/(128L) and a fixed g satisfies ∥g(x)−∇f(x)∥≤ε/8 everywhere. The target is Pr∗(∥∇f(xout)∥>ε)≤δ for prescribed 0≤δ≤1/4.

Lower bounds for finding a stationary point with corrupted first-order replies
Result Oracle complexity Novelty Limitations
(1) CorruptedFirstOrderLowerBound (Ours) (review) Lower bound: Ω(k+LΔ/ε2) joint value–gradient calls.
(2) (Carmon et al. 2020, Thm. 2)
Randomized, exact oracle, k=0
Lower bound: Ω(LΔ/ε2) all-derivative calls. (1) extends (2) by prefixing k uninformative replies, formalizing the clean-rate extension. The additive k dominates when k≫T. (1) needs quartic dimension versus d≳T2log⁡T in (2). It covers first-order access and failure at the returned point. (2) covers all derivatives and all iterates through the budget.
(3) (Carmon et al. 2020, Thm. 1)
Deterministic, exact oracle, k=0
Lower bound: Ω(LΔ/ε2) all-derivative calls. (1) extends hardness to randomized algorithms and matches (3) on the clean deterministic restriction. (1) needs quartic dimension. For deterministic algorithms, prefixing (3) with k uninformative replies already gives the derived bound Ω(k+LΔ/ε2) in dimension d≳T.

Abbr: T=LΔ/ε2; Pr∗ denotes outer probability; Ω denotes a necessary budget up to a universal factor.

Carmon, Yair, John C. Duchi, Oliver Hinder, and Aaron Sidford. 2020. “Lower Bounds for Finding Stationary Points I.” Mathematical Programming 184: 71–120. https://doi.org/10.1007/s10107-019-01406-y.

Lean setup