← All setups

Mixed Relative Smooth Nonconvex — Nonconvex Optimization with Mixed Relative Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Mixed Relative Noise · Lean proof

Nonconvex Optimization with Mixed Relative Noise

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, where L>0, and a given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ for Δ≥0. The oracle returns unbiased stochastic gradients, with second moments controlled by gradient magnitudes and noise increments controlled jointly by gradient magnitudes and query distance. Consecutive pairs of calls share a sample; samples across pairs are independent. For ε>0, the goal is a measurable output x¯∈E with E∥∇f(x¯)∥≤ε, averaging over sampling and algorithm randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. Let Ω be a measurable sample space, and let M,r,σ≥0. The algorithm receives E, Ω, L, M, r, σ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Initial objective gap). The given point x0 satisfies f(x0)−f(x)≤Δ,x∈E.

Assumption 3 (Mixed relative noise). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. Define the centered error by e(x,ω)=g(x,ω)−∇f(x). For every x∈E, the random variable ∥e(x,ξ)∥2 is integrable for ξ∼ν, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν∥e(x,ξ)∥2≤r∥∇f(x)∥2+σ2. Moreover, for every x,y∈E, the same sample is used in the noise-increment bound Eξ∼ν∥e(x,ξ)−e(y,ξ)∥2≤r(∥∇f(x)∥2+∥∇f(y)∥2)+M2∥x−y∥2.

Queries may be made at any point of E. Let (ξj)j≥0 be measurable, independent random variables with common law ν, independent of the algorithm’s randomness. At call k≥0, a query xk∈E receives g(xk,ξ⌊k/2⌋). Thus calls 2j and 2j+1 use the same sample ξj, including when the second query depends on the first reply. Each evaluation counts as one oracle call.

After the allotted oracle calls, the output x¯ must be measurable, its gradient norm must be integrable, and EP[∥∇f(x¯)∥]≤ε, where P is the joint law of the sample sequence and the independent algorithm randomness.

Proved result

{02⋅L⋅Δ≤ε216777216⋅⌈1+(1+r)⋅L⋅Δε2+σ2ε2+min{M⋅σ⋅Δε3,L⋅Δ⋅σ2ε4}⌉+otherwise

OracleTemplate.Convergence LongTails.Setups.MixedRelativeSmoothNonconvex.spec
  OracleTemplate.MixedRelativeSmoothNonconvex.budget

Relevant previous results

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