Descriptions may be stale. Consult the linked Lean sources.
Distributed
Minimization under Weak Interpolation
We minimize the average of smooth convex worker objectives on the
Euclidean space of
dimension . Their common
minimizer set is nonempty, the
given starting point lies within a known radius of , and the average satisfies quadratic
growth relative to . Workers
communicate through a hub and return unbiased local stochastic gradients
with bounded variance, using independent samples within and across
workers. For a tolerance , the goal is a
measurable output whose
expected squared Euclidean distance to is at most by the elapsed-time
deadline.
Let be the number of
workers, with local objectives for . Write . The
optimization problem is The
algorithm receives , , the measurable sample space , the worker computation times
, the latency , the time per bit , the smoothness constants , the growth constant , the radius , the noise bound , the tolerance , and the starting point . The parameters
satisfy .
Our assumptions:
Assumption 1 (Local convexity and smoothness). Each
is convex and differentiable on
, with
Assumption 2 (Common minimizers and quadratic
growth). Let
and write . There exists such that
Assumption 3 (Local stochastic gradients). Worker
has a sequence of measurable
i.i.d. samples with law on
. The worker sequences are
mutually independent, and the entire sample array is independent of the
algorithm’s randomness. At any query point , the worker returns
and , where counts its previously completed
evaluations. The map
is jointly measurable. For each
and , the vector is Bochner integrable and its
squared error is integrable, with
The star network consists of the computing workers and one communication
hub. An evaluation at worker
takes time . Each worker can
have one evaluation in progress and may abort it without consuming a
sample. An evaluation request made while the worker is busy is ignored.
Messages travel only between the hub and a worker. A payload of bits is transmitted with 64 appended
zero bits and takes time The recipient receives the
sender’s identity and the transmitted bits. Each directed link carries
at most one message at a time and ignores submissions while occupied.
Distinct directed links, including opposite directions of the same
connection, can operate concurrently with one another and with worker
computations.
For an elapsed-time budget , almost surely the algorithm must process finitely many
events at every deadline .
At time , its designated output
node must produce a measurable point with integrable
squared distance to satisfying
where the expectation is over the algorithm’s randomness and the worker
sample array.