Descriptions may be stale. Consult the linked Lean sources.
Distributed Smooth
Nonconvex Optimization
We consider minimizing a differentiable, possibly nonconvex function
, where
is an integer. Its gradient
is -Lipschitz for , and a given point satisfies for a
global lower bound
and . A star network has
computing workers and a
coordinator. Each worker returns unbiased stochastic gradients with
variance at most , where
, using independent
samples across workers and calls. Computation and bit communication take
time. For , the
goal is an output
satisfying , where is the law of sampling and algorithm
randomness.
The optimization problem is with the
Euclidean norm . Worker
has computation
time . Communication has
latency and time per bit
. The algorithm receives
, a measurable sample space
, , , and
. The objective,
stochastic-gradient maps, and sampling distributions are accessed
through the oracles.
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
everywhere, and There exists such that
Assumption 2 (Stochastic gradients). For each worker
, there are a probability measure
on and a jointly measurable map .
For every , the map
is Bochner integrable,
its squared error is integrable, and
Assumption 3 (Independent sampling). Let be the joint law of sample streams
taking values in . Each
coordinate is measurable.
For each , the sequence is independent and
identically distributed with marginal law . The entire streams are independent
across workers. Algorithm randomness is independent of these
streams.
Assumption 4 (Computation and communication). The
network consists of coordinator
and workers , with
communication only between the coordinator and a worker. Queries may use
any point of . An
accepted evaluation at worker and
point takes time and returns where
is the number of evaluations
previously completed by that worker. Each worker can have at most one
pending evaluation; further evaluation requests while it is busy are
ignored. A pending evaluation may be aborted, in which case it produces
no reply and consumes no sample. The coordinator performs no gradient
evaluations.
Messages are finite bit strings. A payload of bits sent along a directed
coordinator–worker link takes time including a fixed -bit overhead. The receiver obtains the
sender’s identity and transmitted bits. Each directed link can carry at
most one pending message; further submissions on that directed link are
ignored until delivery. Distinct directed links can operate
concurrently, including opposite directions of the same link.
Computations at different workers and communication can also proceed
concurrently.
The resource budget is an elapsed-time deadline . The algorithm must have only
finitely many events up to every deadline , almost surely under , the joint law specified above. Its
output is
taken from a designated node at time . It must be measurable, must be
integrable under , and the
accuracy requirement is