Descriptions may be stale. Consult the linked Lean sources.
Bandwidth-Limited
Distributed Nonconvex Optimization
We seek a stationary point of a possibly nonconvex objective on , where is the dimension. The objective
averages differentiable worker functions, has a Lipschitz gradient, and
admits a lower bound with a prescribed gap from the initial value. Each
worker returns a batch of unbiased local gradient estimates with bounded
variance, using independent samples within and across workers. Workers
have heterogeneous computation times and communicate over directed links
with latency and per-bit costs. For tolerance , the goal is an output
satisfying , averaging over sampling and
algorithm randomness.
With workers and local
functions , the
optimization problem is All norms are
Euclidean. The algorithm receives , , the measurable sample space , the starting point , the smoothness
constant , the initial gap
bound , the noise bound
, the tolerance , the worker computation times
, the link latency , and the transmission time per
bit .
Our assumptions:
Assumption 1 (Aggregate smoothness and initial gap).
Each is differentiable on . There exists such that, for all ,
Assumption 2 (Local stochastic gradients). Worker
has a sequence of independent
measurable samples with common law on . The worker sequences are mutually
independent, and the algorithm’s randomness is independent of the entire
sample array. Each map
is jointly measurable. For every and , the vector is Bochner integrable, its
squared error is integrable, and
An idle worker accepts a query
consisting of a point and an integer batch
size . After units of time it returns the
ordered list
where is the number of samples
already used by that worker. A worker ignores further computation
requests while its batch is pending. Different workers may compute
concurrently.
Every ordered pair of workers, including a worker paired with itself,
has a directed link. Messages on each link are queued in submission
order. A message submitted at time with a payload of bits is ready for delivery at
time
where is the completion time of
the preceding message on that link, or zero for the first message. The
receiver obtains the sender’s identity and the payload followed by the
zero bits included in the
transmission cost. Distinct directed links may transmit concurrently,
and communication may overlap computation.
For an elapsed-time budget , almost surely every deadline must be reached with only
finitely many events through that deadline. At time , the algorithm’s designated root worker
must produce a measurable output with integrable
squared gradient norm satisfying