← All setups

Separable Noise Linf Smooth Lower Bound — High-Dimensional Stationarity with Separable Noise

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Stationarity with Separable Noise · Lean proof

High-Dimensional Stationarity with Separable Noise

We seek a stationary point of a differentiable, possibly nonconvex objective f:Rd→R in high dimension d. Its gradient is L-Lipschitz from ℓ∞ to ℓ1, with L>0, and the given starting point x0 lies at most Δ above the finite infimum in objective value. At each query, the oracle uses a fresh independent real sample to return an unbiased gradient estimate whose coordinate standard deviations sum to at most S≥0. For tolerance ε>0, the goal is an output x¯∈Rd satisfying E∥∇f(x¯)∥1≤ε over algorithm and oracle randomness.

The optimization problem is infx∈Rdf(x). The algorithm receives d,L,S,Δ,ε and x0∈Rd. The dimension d∈N and the real parameters satisfy 230ε2≤LΔ,d≥2168(1+LΔε2(1+S2ε2))16.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is differentiable everywhere. Its Euclidean gradient satisfies ∥∇f(x)−∇f(y)∥1≤L∥x−y∥∞,x,y∈Rd. The infimum f⋆=infx∈Rdf(x) is finite and satisfies f(x0)−f⋆≤Δ.

Assumption 2 (Stochastic gradients with separable noise). On call k, a query at any x∈Rd returns g(x,ξk), where g:Rd×R→Rd is jointly measurable. The real random variables (ξk)k≥0 are independent with common law ν, and the sequence is independent of the algorithm’s randomness. For ξ∼ν and each fixed x, the vector g(x,ξ) is Bochner integrable. Writing ei(x,ξ)=gi(x,ξ)−∂if(x), each ei(x,ξ)2 is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),∑i=1dEξ∼ν[ei(x,ξ)2]≤S.

After the allotted oracle calls, the output x¯ must be measurable under the joint law of the algorithm’s randomness and the oracle samples. Its gradient norm ∥∇f(x¯)∥1 must be integrable under this law and satisfy E[∥∇f(x¯)∥1]≤ε.

Proved result

⌊L⋅Δ⋅(1+S2ε2)260⋅ε2⌋+

OracleTemplate.NonConvergence LongTails.Setups.HighDimensionalSeparableNoiseLinfSmooth.spec
  LongTails.Theorems.SeparableNoiseLinfSmoothLowerBound.budget

Relevant previous results