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 in dimension
. Its gradient is Lipschitz from
to , 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 , the
goal is a measurable output satisfying , where the expectation includes
both algorithm and oracle randomness.
Write for the finite
value of the optimization problem The
algorithm receives the dimension , the measurable sample
space , the starting point
, the smoothness
constant , the noise bound
, the initial gap bound
, and the tolerance
.
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
everywhere. For every and every satisfying for all , its gradient satisfies
The starting point satisfies .
Assumption 2 (Sampling and coordinatewise noise). At
call with query , the oracle returns
, where
is jointly measurable. The samples are independent
measurable random variables with common law on , and the entire sequence is
independent of the algorithm’s randomness. For each fixed and , the vector is Bochner integrable and each
coordinate error is
square integrable. Their moments satisfy
After the allotted oracle calls, the output must be measurable, its gradient
norm must
be integrable, and it must satisfy
Proved result
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:
stochastic-gradient calls for minibatch signSGD when , where is the step size, is the integer batch size, sums the diagonal
quadratic-majorant coefficients, and 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:
stochastic-gradient calls for minibatch SignSGD and a uniformly sampled
iterate, where uniformly
bounds the noise standard deviation in coordinate .