Descriptions may be stale. Consult the linked Lean sources.
Distributed
Nonconvex Optimization with Free Broadcast
We consider minimizing on , where are integers and the
differentiable functions may be
nonconvex. The gradient of is
-Lipschitz, and component
gradients are root-mean-square Lipschitz with constant , where . At a given point , component gradient norms are bounded
by , and the gap above a
global lower bound is at most . Worker returns at on a star network with heterogeneous
computation times and free coordinator broadcasts. For , the goal is , where is the output and is the law of algorithm randomness.
The optimization problem is All vector
norms are Euclidean. There are
computing workers and one coordinator. Worker has computation time ; worker-to-coordinator
communication has latency
and time per bit . The
algorithm receives , and .
Our assumptions:
Assumption 1 (Smoothness). Each is differentiable everywhere. For
every ,
Assumption 2 (Initial bounds). There exists such that
A gradient query at worker may
use any . If
accepted at time , it returns the
queried point and the exact gradient at time . Each
worker processes at most one gradient query at a time; further queries
while it is occupied are ignored. A pending computation may be canceled.
Computations at different workers may proceed concurrently, and the
coordinator performs no gradient computations.
Communication uses finite binary messages along the star edges. A
message with payload bits carries
an additional bits. Its
transmission delay is A broadcast consists of messages from the
coordinator to the intended workers, each with zero delay. Each directed
edge holds at most one pending message; a further submission on that
edge is ignored until delivery. Different directed edges, including
opposite directions of the same edge, operate concurrently.
Communication may overlap computation, and workers exchange messages
through the coordinator.
For an elapsed-time budget , the algorithm returns a
measurable output at a designated
output node. Almost surely under ,
only finitely many computation, communication, and local scheduling
events may occur up to each deadline . The squared gradient norm must be integrable, and the
accuracy requirement is The budget measures elapsed time, including
computation and communication delays.