Descriptions may be stale. Consult the linked Lean sources.
Distributed
Hessian-Lipschitz Nonconvex Optimization
We consider minimizing a nonconvex function , where is an integer, using stochastic
gradients on a star network. The gradient is -Lipschitz and the Hessian is -Lipschitz, with and . A given point satisfies , where
is a global lower
bound and . Workers
return unbiased gradient estimates with variance at most , where , using independent sample
streams. Computation and bit communication incur specified elapsed
times. For , the
goal is a measurable output
satisfying , where is the joint law of sampling and
independent algorithm randomness.
The optimization problem is We use the
Euclidean norm on and
its induced operator norm on linear maps.
The network consists of a coordinator and workers. Worker has computation time
; communication has latency
and time per bit . The algorithm receives ,
the times , and
the measurable sample space .
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
everywhere, its gradient is differentiable everywhere, and, for all
, There exists such that
Assumption 2 (Stochastic gradients and sampling).
For each worker , there are a
probability measure on and a jointly measurable map
For every , the map
is Bochner integrable
under , its squared error is
integrable, and Under a joint sampling law , worker has measurable samples that are independent
and identically distributed with law . The entire streams are independent
across workers. Sampling is independent of the algorithm’s randomness.
The functions , measures , and joint law are not algorithm inputs.
Assumption 3 (Computation and communication). A
worker may query any . An accepted query at
worker completes after units of time and returns the queried
point together with , where counts that worker’s previously
completed queries. Each worker has at most one pending computation:
further computation requests while it is busy are ignored. A pending
computation may be aborted without consuming a sample. The coordinator
performs no gradient computations.
Communication is available only between the coordinator and a worker,
in either direction. A message with an -bit payload is delivered, together with
its sender’s identity, after units of time; the
additional bits are included in
the transmitted message. Each directed link admits at most one pending
message, and submissions on an occupied directed link are ignored.
Distinct directed links operate concurrently, including opposite
directions of the same edge, and communication may overlap
computation.
For an elapsed-time budget , the algorithm must complete only
finitely many events almost surely at every deadline in . Its output is taken from a
designated network node at time .
It must be measurable, with integrable under , and satisfy The budget measures elapsed
time, including computation and communication.