← All setups

Nonnegative Sample Stationarity — Stationarity for Nonnegative Smooth Sample Losses

Descriptions may be stale. Consult the linked Lean sources.

Stationarity for Nonnegative Smooth Sample Losses · Lean proof

Stationarity for Nonnegative Smooth Sample Losses

We consider minimizing a possibly nonconvex expected loss f:E→R on a separable real Hilbert space E. Every sample loss is nonnegative and has an L-Lipschitz gradient, where L>0. A given starting point x0∈E satisfies f(x0)≤Δ for a bound Δ≥0. Each oracle call returns the sample gradients at two queried points using a single fresh independent sample. For a tolerance ε>0, the goal is a measurable output x¯∈E satisfying E[∥∇f(x¯)∥]≤ε, with expectation over the algorithm and oracle randomness.

Let (Ω,F) be the sample space, p a probability law on it, and ℓ(x,ω) the loss at x∈E for sample ω∈Ω. The optimization problem is infx∈Ef(x),f(x)=Eω∼p[ℓ(x,ω)]. The algorithm receives E with its Borel structure, (Ω,F), x0, L, Δ, and ε.

Our assumptions:

Assumption 1 (Sample losses). For every x∈E, the function ℓ(x,⋅) is p-integrable. For every ω∈Ω, the function ℓ(⋅,ω) is differentiable on E. Its gradient g(x,ω)=∇xℓ(x,ω) is jointly measurable in (x,ω). For all x,y∈E and ω∈Ω, ℓ(x,ω)≥0,∥g(x,ω)−g(y,ω)∥≤L∥x−y∥.

Assumption 2 (Paired gradient queries). The oracle samples (ξk)k≥0 are independent random variables with common law p. The sample sequence is independent of the algorithm’s randomness. On call k, a query (x,y)∈E×E receives the reply (g(x,ξk),g(y,ξk)).

After the allotted oracle calls, the output x¯ must be measurable, its gradient norm must be integrable, and E[∥∇f(x¯)∥]≤ε.

Proved result

⌈8192⋅(1+L⋅Δε2)3⌉+

OracleTemplate.Convergence LongTails.Setups.NonnegativeSmoothSampleLoss.spec
  LongTails.Theorems.NonnegativeSampleStationarity.budget

Relevant previous results

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