← All setups

Stationarity for Nonnegative Smooth Sample Losses

Descriptions may be stale. Consult the linked Lean sources.

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

Results

On a separable real Hilbert space, F(x)=Eξℓξ(x) with ℓξ(x)≥0 integrable for each x. Sample gradients are jointly measurable and L-Lipschitz in x for every sample, with L>0 and F(x0)≤Δ. Each pair call evaluates two gradients at queried points using one fresh IID sample. The target is a measurable X with E∥∇F(X)∥≤ε, ε>0.

Sufficient oracle budgets for expected stationarity with nonnegative smooth sample losses.
Result Oracle complexity Novelty Limitations
(1) NonnegativeSampleStationarity (Ours) (review) O(1+(LΔ/ε2)3/2) pair calls, including the initial batch.
(2) Normalized STORM (auto-math-bot 2026) O(1+(LΔ/ε2)3/2) pair calls on the shared class. (1): Matches the known rate and tuning. The sample-level formalization derives E∥∇ℓξ(x)∥2≤2LF(x). (1) requires nonnegative smooth losses. (2) allows mean-square smooth gradients with variance bounded by an affine function of the objective gap.
(3) SGD (Khaled and Richtárik 2020, Cor. 1) O(1+(LΔ/ε2)2) single gradients. Derived bound. (1): For R≥1, the gradient budget improves by a factor of order R, as in (2). For R≤1, the orders match. (1) needs same-sample pairs. (3) queries one point per sample and bounds the minimum expected squared gradient norm across iterates.
(4) SPIDER (Chen et al. 2023, Thm. 4) O(R(1+Γ2)+Λ2/ε2+R(1+Γ)Λ/ε) gradient evaluations. Derived bound for small ε at fixed parameters, LΔ>0. (1) covers samples violating the affine variance bound required by (4). On the overlap, its ε−3 coefficient is smaller when (1+Γ)Λ≫LΔ. (1) requires nonnegative smooth losses even on affine-variance problems. On the overlap its leading term is worse when (1+Γ)Λ≪LΔ; at Λ=0, (4) needs O(R(1+Γ2)).

Abbr: R=LΔ/ε2. The affine variance parameters Γ,Λ≥0 satisfy E∥∇ℓξ(x)−∇F(x)∥2≤Γ2∥∇F(x)∥2+Λ2.

auto-math-bot. 2026. Prove Normalized STORM Rate Under Expected-Smoothness Noise. LongTails repository, commit a1cfca4f. https://github.com/k3nfalt/longtails/blob/a1cfca4fccab244b3b16b30e6d7746af6183cfc8/LongTails/Theorems/NormalizedStormExpectedSmoothness.lean.
Chen, Ziyi, Yi Zhou, Yingbin Liang, and Zhaosong Lu. 2023. “Generalized-Smooth Nonconvex Optimization Is as Efficient as Smooth Nonconvex Optimization.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 5396–427. https://proceedings.mlr.press/v202/chen23ar.html.
Khaled, Ahmed, and Peter Richtárik. 2020. Better Theory for SGD in the Nonconvex World. https://doi.org/10.48550/arXiv.2002.03329.

Lean setup