← All setups

Minibatch Sign Sgd Upper Bound — Stochastic Stationarity with Coordinatewise Noise

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Stationarity with Coordinatewise Noise · Lean proof

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

Proved result

(⌈8⋅L⋅Δε2⌉++1)⋅(⌈16⋅S2ε2⌉++1)

OracleTemplate.Convergence LongTails.Setups.SeparableNoiseLinfSmooth.spec
  LongTails.Theorems.MinibatchSignSgdUpperBound.budget

Relevant previous results

  • Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed Optimisation for Non-Convex Problems. 2018. Complexity: O(B(1+Δ/(ηε))) stochastic-gradient calls for minibatch signSGD when ηLΣ/2+2SΣ/B≤ε/2, where η>0 is the step size, B≥1 is the integer batch size, LΣ=∑iLi sums the diagonal quadratic-majorant coefficients, and SΣ=∑iσi sums uniform coordinate noise standard-deviation bounds.
  • Hongyi Tao, Dingzhi Yu, and Lijun Zhang. When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ₁-norm Lower Bounds. 2026, arXiv preprint v1. Complexity: O((1+LΔ/ε2)(1+∥σ∥12/ε2)) stochastic-gradient calls for minibatch SignSGD and a uniformly sampled iterate, where σi uniformly bounds the noise standard deviation in coordinate i.