← All setups

Fair Relative Energy Nonconvex — Nonconvex Optimization with Symmetric Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Symmetric Noise · Lean proof

Nonconvex Optimization with Symmetric Noise

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and a given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ≥0. The oracle returns g(x,ξ)∈E, with symmetric noise having tail radius r≥0 and relative-energy regularity parameter κ≥0. Consecutive pairs of calls share a sample ξ, independently across pairs. For ε>0, the goal is a measurable output x¯∈E satisfying E∥∇f(x¯)∥≤ε, where expectation includes sampling and independent algorithm randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, equipped with its Borel sigma-algebra. Let Ω be a measurable sample space. The algorithm receives E, Ω, L, κ, r, Δ, ε, and x0; it accesses f through the oracle described below.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is Fréchet differentiable everywhere, and, for every x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,f(x0)−f(x)≤Δ.

Assumption 2 (Symmetry and tail radius). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. Define the noise by e(x,ω)=g(x,ω)−∇f(x). For every x∈E, under ξ∼ν, e(x,ξ)=d−e(x,ξ),Pξ∼ν(∥e(x,ξ)∥>r)≤164. Here equality in distribution is equality of the induced probability measures on E.

Assumption 3 (Relative-energy regularity). For every x,y∈E, the noise evaluated with the same sample satisfies Eξ∼ν[(∥e(x,ξ)−e(y,ξ)∥r+∥e(x,ξ)∥+∥e(y,ξ)∥)2]≤κ2∥x−y∥2. The ratio is defined to be zero when its denominator is zero.

Oracle queries may be made at any point of E. Let (ξj)j≥0 be measurable, mutually independent sample variables, each with law ν, and independent of the algorithm’s randomness. Index calls starting at zero. At query xk∈E, call k returns g(xk,ξ⌊k/2⌋). Thus calls 2j and 2j+1 use the same sample, including when the second query depends on the first reply.

After the allotted oracle calls, the output x¯ must be measurable and satisfy EP∥∇f(x¯)∥≤ε,∥∇f(x¯)∥∈L1(P), where P is the joint law of the samples and the algorithm’s independent randomness.

Proved result

⌈266⋅(1+log⁡((r+ε)2+L⋅Δε2))⋅((r+ε)2+L⋅Δε2+min{κ⋅ε,L}⋅(r+ε)2⋅Δε4)⌉+

OracleTemplate.Convergence LongTails.Setups.RelativeEnergySymmetricNonconvex.spec
  LongTails.Theorems.FairRelativeEnergyNonconvex.budget

Relevant previous results

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