← All setups

Abc Noise Lower Bound — High-Dimensional Nonconvex Optimization with ABC Noise

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Nonconvex Optimization with ABC Noise · Lean proof

High-Dimensional Nonconvex Optimization with ABC Noise

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R, where d is a positive integer, with finite infimum f⋆ and an L-Lipschitz gradient, where L>0. The oracle returns g(x,ξ) at x, using independent real samples ξ with a common probability law. Its replies are unbiased and satisfy E∥g(x,ξ)−∇f(x)∥2≤2A(f(x)−f⋆)+B∥∇f(x)∥2+C, where A,B,C≥0. For a tolerance ε>0, the goal is a measurable output x¯∈Rd satisfying E∥∇f(x¯)∥≤ε, with expectation over oracle samples and independent algorithm randomness.

The optimization problem is infx∈Rdf(x). Throughout, ∥⋅∥ denotes the Euclidean norm. A starting point x0∈Rd and an initial-gap bound Δ∈R are given. The algorithm receives d,L,A,B,C,Δ,ε, and x0.

Our assumptions:

Assumption 1 (Parameter and dimension regime). The parameters satisfy d∈N,L>0,A,B,C≥0,ε>0,226ε2≤LΔ,d≥240(1+LΔε2(1+B+AΔ+Cε2))4. In particular, these conditions imply Δ>0 and d>0.

Assumption 2 (Smoothness and initial gap). The function f is Fréchet differentiable everywhere, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈Rd. Its infimum f⋆ is finite, and f⋆=infx∈Rdf(x)∈R,f(x0)−f⋆≤Δ.

Assumption 3 (IID stochastic gradients with ABC noise). There exist a probability measure ν on R and a jointly measurable map g:Rd×R→Rd. At call k, a query x∈Rd receives g(x,ξk), where (ξk)k≥0 is a sequence of measurable, mutually independent random variables with common law ν. This sequence is independent of the algorithm’s randomness. For every fixed x∈Rd, the vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable for ξ∼ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤2A(f(x)−f⋆)+B∥∇f(x)∥2+C.

Queries may be made at any point of Rd. Let P denote the joint law of the oracle samples and the independent algorithm randomness. After the allotted oracle calls, the output x¯ must be measurable, its gradient norm must be P-integrable, and it must satisfy EP[∥∇f(x¯)∥]≤ε.

Proved result

⌊L⋅Δ⋅(1+B+A⋅Δε2+Cε2)253⋅ε2⌋+

OracleTemplate.NonConvergence LongTails.Setups.HighDimensionalAbcNoiseNonconvex.spec
  LongTails.Theorems.AbcNoiseLowerBound.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.