← All setups

Stationarity for Nonnegative Smooth Sample Losses

Descriptions may be stale. Consult the linked Lean sources.

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¯)∥]≤ε.

Results

Let L,Δ,ε>0 and R=LΔ/ε2≥264. Each ℓi≥0 has an L-Lipschitz gradient, and F=Eiℓi satisfies F(0)≤Δ. Any randomized adaptive algorithm may query two points per call, receiving only their gradients for the same fresh IID sample. The target is E∥∇F(x^)∥≤ε.

Necessary oracle budgets for stationarity with nonnegative smooth sample losses in Euclidean space.
Result Oracle complexity Novelty Limitations
(1) NonnegativeSampleStationarityLowerBound (Ours) (⋆⋆) (review) Lower bound: s3+1=Ω(R3/2) pair calls. The hard instance uses m=[512(s+1)]2 equiprobable samples and dimension Θ(s11) at minimum width.
(2) (Peng et al. 2026, Thm. 3.1) Lower bound: Ω(m+mR) component calls for m≥m0, ε2≤c0LΔ and fixed failure probability 0<δ<p0. Two calls simulate one uniform pair. (1) proves Ω(R3/2) for nonnegative losses with bounded initial risk. (2) gives that order at m≍R under a gap bound. Whether shifting its components to nonnegativity preserves F(0)≤O(Δ) is open. (1) ties m to accuracy and hides sample indices and values. (2) permits adaptive component selection and returns component values and gradients.
(3) (Arjevani et al. 2022, Thm. 3, Eq. (24)) Lower bound: Ω(ΔL¯σε3+σ2ε2) same-sample pair calls for ε≤cL¯Δ. (1) establishes hardness under individual smoothness, nonnegativity and bounded initial risk. (3) gives the same order formally at L¯=L, σ2=LΔ for a mean-squared smooth oracle. (1) covers gradient-only replies. (3) also allows exact objective values.

Abbr: s=⌊R/232⌋; m is the component count. In (2), (3), Δ bounds F(0)−infF. In (3), L¯ is the mean-squared smoothness parameter and σ2 bounds the oracle variance. m0,c0,p0,c are universal constants.

Arjevani, Yossi, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. 2022. Lower Bounds for Non-Convex Stochastic Optimization. https://doi.org/10.48550/arXiv.1912.02365.
Peng, Yuxing, Zhiqing Tang, and Weijia Jia. 2026. Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization Under Individual Smoothness. https://doi.org/10.48550/arXiv.2609.00045.

Lean setup