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 -dimensional Euclidean space . Each worker contributes one
component to the average . Each
component has a Lipschitz gradient, and the initial objective gap to a
global lower bound is bounded. Workers compute at heterogeneous speeds
and communicate over directed links. Each worker’s oracle returns
batches of unbiased local gradient estimates with bounded variance,
using independent samples within and across workers. For a tolerance
, the goal is an
output satisfying over sampling and algorithm
randomness.
Index the workers by
, and write for their
components, where is a
nonnegative integer. With , the
optimization problem is The
algorithm receives , , the measurable sample space , the starting point , the bounds and , the tolerance , and the timing parameters
, , and .
Our assumptions:
Assumption 1 (Component smoothness and initial gap).
Each is differentiable, and for
all its gradient
satisfies where is the Euclidean norm. There is
a lower bound such
that
Assumption 2 (Local stochastic gradients). Worker
has a stream of measurable,
independent samples with common law on . The worker streams are mutually
independent, and the algorithm’s randomness is independent of the entire
sample array. The map
is jointly measurable. For every and , the vector is Bochner integrable, its
squared error is integrable, and where .
Computation and
communication.
A computation query at worker
specifies a point
and a positive integer batch size . If samples have already been used, the
worker returns the ordered batch
after time , where is its time per sample. Each
worker processes one batch at a time and ignores further computation
requests while a batch is pending. Different workers can compute
concurrently.
Every ordered pair of workers, including a worker paired with itself,
has a directed link. A message with payload bits is padded with zero bits. If submitted at time , it finishes at
where is the
previous finish time on that link, initially zero, is the latency, and is the time per transmitted bit.
The recipient receives the sender’s identity and the padded bit string.
Each link serves messages in submission order. Distinct links can
operate concurrently, and communication can overlap computation.
Elapsed time and accuracy.
For an elapsed-time budget , almost surely the algorithm must process only finitely many
events for every deadline . At time , a root worker designated by the
algorithm must produce a measurable output with integrable
squared gradient norm satisfying