← All setups

Stochastic Stationarity with Coordinatewise Noise

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Stationarity with Coordinatewise Noise

We seek a stationary point of a differentiable, possibly nonconvex function f:Rd→R in dimension d. Its gradient is Lipschitz from ℓ∞ to ℓ1, and the given starting point has bounded objective gap above the infimum. At each query, the oracle uses a fresh independent sample to return an unbiased gradient estimate with a uniform bound on the sum of its coordinate standard deviations. For a tolerance ε>0, the goal is a measurable output x¯∈Rd satisfying E[∥∇f(x¯)∥1]≤ε, where the expectation includes both algorithm and oracle randomness.

Write f⋆ for the finite value of the optimization problem infx∈Rdf(x). The algorithm receives the dimension d∈{0,1,…}, the measurable sample space Ω, the starting point x0∈Rd, the smoothness constant L>0, the noise bound S≥0, the initial gap bound Δ≥0, and the tolerance ε.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is differentiable everywhere. For every x,y∈Rd and every r∈R satisfying |xi−yi|≤r for all i=1,…,d, its gradient satisfies ∥∇f(x)−∇f(y)∥1≤Lr. The starting point satisfies f(x0)−f⋆≤Δ.

Assumption 2 (Sampling and coordinatewise noise). At call k≥0 with query x∈Rd, the oracle returns g(x,ξk), where g:Rd×Ω→Rd is jointly measurable. The samples (ξk)k≥0 are independent measurable random variables with common law ν on Ω, and the entire sequence is independent of the algorithm’s randomness. For each fixed x and ξ∼ν, the vector g(x,ξ) is Bochner integrable and each coordinate error ei(x,ξ)=gi(x,ξ)−∂if(x) is square integrable. Their moments satisfy Eξ∼ν[g(x,ξ)]=∇f(x),∑i=1dEξ∼ν[ei(x,ξ)2]≤S.

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

Results

The differentiable f:Rd→R has finite infimum, f(x0)−inff≤Δ, and ∥∇f(x)−∇f(y)∥1≤L∥x−y∥∞. The jointly measurable oracle g(x,ξ) uses IID draws ξ∼p, with Epg(x,ξ)=∇f(x) and ∑isi(x)≤S at every x. For L,ε>0 and S,Δ≥0, the target is a measurable output X with E∥∇f(X)∥1≤ε.

Sufficient stochastic gradient calls for expected ℓ1-stationarity under SeparableNoiseLinfSmooth.
Result Oracle complexity Novelty Limitations
(1) MinibatchSignSgdUpperBound (Ours) (review) O((1+LΔε2)(1+S2ε2))
(2) (Tao et al. 2026, Thm. 1), fixed coordinate noise bounds O(1+LΔε2(1+∥σ∥12ε2)) (1): Formalizes the matching rate for ∥σ∥1=S, ε2≤LΔ. Noise of size S moving among all d coordinates gives S2 versus d2S2 in the noise term. (1) requires IID draws and gradient Lipschitzness. (2) allows conditionally unbiased independent batch samples and requires only |Rx(h)|≤L∥h∥∞2/2. (1) retains S2/ε2 when LΔ<ε2.
(3) (Bernstein et al. 2018, Thm. 1), batch size equals iteration count O(1+(M(1+Δ)+∥σ∥1ε)4) (1): On the separably smooth overlap with S=0 and fixed positive curvature and gap, separate batch tuning gives O(ε−2) versus O(ε−4) as ε↓0.
(4) Derived bound, retuned minibatch SignSGD (Bernstein et al. 2018) O((1+MΔε2)(1+∥σ∥12ε2)) (1): Matches the retuned rate for L=M, S=∥σ∥1. (3), (4) assume |Rx(h)|≤∑iLihi2/2 and fixed coordinate noise bounds. (1) allows the noise profile to vary with x.

Abbr: si(x)=(Ep|gi(x,ξ)−∂if(x)|2)1/2. Each σi uniformly bounds coordinate i’s noise standard deviation (conditional in (2)). Rx(h)=f(x+h)−f(x)−⟨∇f(x),h⟩, M=∑iLi.

Bernstein, Jeremy, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. 2018. “signSGD: Compressed Optimisation for Non-Convex Problems.” In Proceedings of the 35th International Conference on Machine Learning, edited by Jennifer Dy and Andreas Krause, vol. 80. Proceedings of Machine Learning Research. PMLR. https://doi.org/10.48550/arXiv.1802.04434.
Tao, Hongyi, Dingzhi Yu, and Lijun Zhang. 2026. When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-Norm Lower Bounds. https://doi.org/10.48550/arXiv.2605.06615.

Lean setup