Descriptions may be stale. Consult the linked Lean sources.
Distributed
Mean-Squared Smooth Nonconvex Optimization
We seek a stationary point of a differentiable, possibly nonconvex
objective in Euclidean
dimension , given a starting
point with bounded objective gap above a global lower bound. Workers on
a star network have independent sample streams. Each completed query
returns unbiased stochastic gradients at two points using one fresh
sample. The gradients have bounded variance and are Lipschitz in mean
square. Given , the
goal is to return by an elapsed-time
deadline with , averaging over the samples and
algorithm randomness.
The underlying optimization problem is The
algorithm receives the dimension ,
the number of workers , the
measurable sample space , the
starting point ,
the bounds , , and , the tolerance , and the timing parameters
, , and described below. All norms are
Euclidean.
Our assumptions:
Assumption 1 (Objective and initial gap). The
function is differentiable
everywhere. There exists such that
Assumption 2 (Worker sampling). For each worker
, the samples
are
measurable, independent, and identically distributed with law on . The worker streams are mutually
independent, and the algorithm’s randomness is independent of the full
sample array. On its st
completed query, worker returns,
for any requested , the pair
Assumption 3 (Gradient moments and mean-squared
smoothness). Each
is jointly measurable. For every and , the vector is Bochner integrable, both
squared norms below are integrable, and
The star has one communication-only hub and computing workers. A paired query at
worker takes units of time, where . Each worker can have one query
in progress. It may abort that query without consuming a sample. Further
evaluation requests while the worker is busy are ignored.
Messages travel between the hub and a worker in either direction. A
payload of bits is
transmitted with 64 appended zero bits and takes units of time, where is the latency and is the time per transmitted bit.
The recipient receives the sender’s identity and the transmitted bits.
Each directed link carries at most one message at a time and ignores new
submissions while occupied. Distinct directed links can operate
concurrently, including opposite directions on the same edge.
Computations at different workers can overlap with one another and with
communication.
Let be the elapsed-time
budget. Almost surely, every deadline must be reached with only
finitely many events. At time ,
the algorithm’s designated output node must return a measurable point
with integrable squared
gradient norm satisfying