Descriptions may be stale. Consult the linked Lean sources.
Graph
Quantized Minibatch SGD
We consider minimizing a differentiable, possibly nonconvex function
with
-Lipschitz gradient, where and . A given starting point satisfies for a global lower
bound and . Workers communicate over a
connected graph with heterogeneous computation times and edge
bandwidths. Their oracles return independent, identically distributed
unbiased stochastic gradients with variance at most , where . We analyze quantized
minibatch SGD with a uniformly sampled iterate. For , the goal is a
measurable output
satisfying , with expectation over sampling
and algorithm randomness.
The optimization problem is where
and is the Euclidean norm. There
are workers, indexed by
, and a simple
undirected graph .
Worker has computation time per stochastic gradient. The
bandwidth parameters satisfy for all . The algorithm receives , the measurable sample space , , , , , , , , and .
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
everywhere, and there exists such that Here ,
, , and .
Assumption 2 (Stochastic gradients and sampling).
There exist a probability measure on and a jointly measurable map
such that, for every , The vector is Bochner integrable, and its
squared error is integrable, under . Under a joint law , worker has a measurable sequence of independent
samples with common law . These
entire sequences are independent across workers. Algorithm randomness is
independent of the sample array.
Assumption 3 (Computation and graph communication).
The graph is connected, and each
edge satisfies A computation request at worker
specifies any point and an integer batch
size . If samples have already been consumed
there, the request takes time
and returns the list
Each worker has at most one outstanding computation; requests submitted
while it is busy are ignored. Different workers may compute
concurrently.
Communication transmits finite bit strings along edges. A payload of
bits carries an additional
bits and takes time from to . Each directed edge has its own serial
queue: transmission starts at the later of its submission time and the
preceding transmission’s completion time. Opposite directions and
different edges may operate concurrently, including during computation.
Self-messages take zero time, and messages to other nonneighbors are
discarded. Delivered messages identify their sender. A designated root
is one of the workers and
supplies the output.
Our result is algorithm-specific: we analyze quantized minibatch SGD.
Its tuning consists of an integer , batch sizes with , a step size
, an integer quantization
width , and a radius function
. These
choices depend only on the algorithm inputs.
To define the quantizer at ,
let For each coordinate , set Thus clipping precedes coordinatewise
quantization. Starting from the given , define the local averages and
iterates by Both the local averages and their weighted
aggregate are quantized with the same quantizer at the current
iterate.
The algorithm selects
uniformly from
using its own randomness, independently of the sample array. The sampled
output is . The distributed
realization must satisfy the following restrictions for every sample
array and every realization of the algorithm randomness. At every
deadline and every intermediate stage, the root’s output is either or . Worker has consumed at most samples. Whenever it has an
outstanding computation, there is an integer such that it has consumed exactly
samples and the outstanding
request is the batch of size at
. There must also exist a finite
deterministic completion deadline, uniform over sample arrays and
algorithm randomness, at which the process terminates with root output
and exactly samples consumed at each worker.
These restrictions apply for every stochastic-gradient map and
sample-array law, rather than only for a particular objective.
A budget measures elapsed
time under the computation and communication costs above. At every
deadline , the distributed
process must terminate after finitely many events almost surely. Let
be the joint law of the
independent algorithm randomness and sample array, and let be the root’s output at deadline
. The output must be measurable,
its squared gradient norm must be integrable under , and the accuracy requirement is