← All setups

Nonnegative Sample Stationarity Lower Bound — 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 seek a stationary point of a possibly nonconvex objective f:E→R on a finite-dimensional Euclidean space E. The objective is the expectation of nonnegative sample losses with L-Lipschitz gradients, where L>0, and f(0)≤Δ for a given Δ>0. Each oracle call returns the gradients of one fresh, independently sampled loss at both queried points. For a tolerance ε>0, the goal is a measurable output x¯∈E satisfying E[∥∇f(x¯)∥]≤ε, with expectation over the oracle samples and the algorithm’s independent randomness.

The parameters satisfy 232ε≤LΔ. For a nonnegative integer r specifying the extra width, set n=⌊LΔ232ε⌋,m=[512(n+1)]2,d=221(2n3+1)nm2+r+1. The optimization problem is infx∈Ef(x), where E=(Rm×d)n carries the Euclidean norm ∥x∥2=∑j=1n∥xj∥F2, with ∥⋅∥F the Frobenius norm. The algorithm receives E, the sample space Ω={1,…,m}, the starting point x0=0, and the parameters L,Δ,ε.

Our assumptions:

Assumption 1 (Sample loss regularity). For each ω∈Ω, the loss ℓω:E→R is differentiable. Writing g(x,ω)=∇ℓω(x), we require for every x,y∈E and ω∈Ω that ℓω(x)≥0,∥g(x,ω)−g(y,ω)∥≤L∥x−y∥. The map (x,ω)↦g(x,ω) is jointly measurable.

Assumption 2 (Population objective and initial value). There is a probability distribution ν on Ω such that ω↦ℓω(x) is ν-integrable for every x∈E, and f(x)=Eω∼ν[ℓω(x)]for every x∈E,f(x0)≤Δ.

On call k, the algorithm may query any pair (x,y)∈E×E and receives (g(x,ξk),g(y,ξk)). The samples (ξk)k≥1 are independent random variables with common law ν, and the sample sequence is independent of the algorithm’s randomness. After the allotted calls, the output x¯ must be measurable, its gradient norm must be integrable, and E[∥∇f(x¯)∥]≤ε.

Proved result

(⌊L⋅Δ232⋅ε⌋+)3

OracleTemplate.NonConvergence LongTails.Setups.NonnegativeSmoothSampleLossEuclidean.spec
  LongTails.Theorems.NonnegativeSampleStationarityLowerBound.budget

Relevant previous results

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