Query complexity of nonconvex optimization with bounded unbiased noise

How many fresh-sample stochastic gradient queries are needed to reach expected gradient norm at most ε in smooth nonconvex optimization? The objective has initial gap Δ and L-Lipschitz gradient; noise is unbiased, fixed-law and uniformly bounded by σ, with one independent sample per adaptive query.

Why it matters and what counts as progress

Why it matters: Uniformly bounded noise is stricter than bounded variance, so an earlier lower-bound oracle does not by itself settle this minimax rate.

What counts as progress: Prove a matching Ω(ΔL/ε²+ΔLσ²/ε⁴) lower bound in the small-ε regime, or improve an algorithm under these same noise assumptions.

How the problem developed

2019 · Partial result [1][2]
Arjevani et al. Proved the minimax stochastic lower bound under bounded variance; their rare-revelation oracle need not have uniformly bounded individual errors, leaving the bounded-noise extension open.
24 Aug 2026 · Reported claim [2]
Jikai Jin and GPT-5.6 Sol The preprint claims a matching lower bound for the K=1 fresh-sample model when every gradient-noise vector is uniformly bounded, closing the stated gap for this oracle model.

AI contribution

A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise

Jikai Jin

In the paper’s small-ε regime, a randomized adaptive method using one independent fresh sample per query needs Ω(ΔL/ε² + ΔLσ²/ε⁴) queries to reach expected gradient norm at most ε for smooth nonconvex objectives with gap Δ, L-Lipschitz gradient and uniformly bounded, unbiased fixed-law gradient noise.

AI involvementAI-autonomous

ImportanceNotable

Technical verificationFormal (human)

Human understandingFew