Descriptions may be stale. Consult the linked Lean sources.
Distributed Nonconvex
Finite-Sum Optimization
We seek a stationary point of a possibly nonconvex objective on , the mean of differentiable worker objectives
in dimension . The aggregate
gradient is Lipschitz, and the gap from the given starting value to a
global lower bound is bounded. Each worker returns an unbiased estimate
of its own gradient with bounded variance, using independent samples
across evaluations and workers. Workers communicate through a central
node. For a tolerance , the goal is to return
within an
elapsed-time budget with , averaging over sampling and
algorithm randomness.
Write for the
objective at worker and use the Euclidean
norm throughout. The optimization problem is The algorithm
receives , , the measurable sample space , the starting point , the smoothness and
gap bounds and , the noise bounds , the tolerance , and the timing parameters
, , and .
Our assumptions:
Assumption 1 (Aggregate smoothness and initial gap).
Each is differentiable
everywhere. For every , There exists such that
Assumption 2 (Worker sampling and gradient
estimates). Worker has a sequence
of measurable
i.i.d. samples with law on
. The worker sequences are
mutually independent, and the algorithm’s randomness is independent of
the entire sample array. On its th
completed evaluation, indexed from zero, worker returns the query point and the vector , where
is jointly measurable. For each and , the vector is Bochner integrable, its
squared error is integrable, and
Assumption 3 (Star network and timing). The center
communicates with each of the
workers in both directions. Only workers perform gradient evaluations.
An evaluation at worker takes
time and may be aborted. While
an evaluation is pending, the worker ignores new evaluation requests.
Each directed link carries at most one message at a time and ignores
send requests while occupied. Computations at different workers and
transmissions on distinct directed links may proceed concurrently, and
communication may overlap computation. A payload of bits is transmitted with 64
trailing zero bits and arrives with the sender’s identity after time
where is the latency and is the time per transmitted bit.
Let be the elapsed-time
budget. Almost surely, every deadline must be reached with only
finitely many events through that deadline. At time , the algorithm’s designated output node
must provide a measurable point with integrable gradient norm
satisfying