Descriptions may be stale. Consult the linked Lean sources.
Distributed Root
Finding under Strong Growth
We seek a zero of a
Lipschitz map in
dimension . The map has a
Lipschitz Jacobian and satisfies at every point
, for some . Workers communicate over a
rooted tree. At , each worker uses
a fresh independent sample to return an unbiased estimate of with second moment at most , where . Given a starting point within
known distance of the zero and a tolerance , the goal is an output
satisfying
by an elapsed-time deadline, averaging over algorithm and oracle
randomness.
Write with its
Euclidean inner product and norm. The equation to be solved is Let be the set of workers,
where is an integer. The
algorithm receives , , the nonempty measurable sample space
, the tree root , parent map , depth function and height bound , the timing parameters , the constants , the tolerance , and the starting point .
Our assumptions:
Assumption 1 (Operator and Jacobian regularity). The
map is Fréchet differentiable on
. Its Jacobian and the map itself satisfy,
for every , where , , and is the induced
operator norm.
Assumption 2 (Growth about the solution). There is a
zero such that, for a
radius ,
Assumption 3 (Sampling and strong growth). Let be measurable, mutually
independent samples with common probability law on , independent of the algorithm’s
randomness. On its st
completed query, for , worker
returns at the queried point
. Each is jointly
measurable. For each and , is Bochner integrable and
is integrable
under , with
Assumption 4 (Tree topology and timing). The root
, parent map , depth function , and integer satisfy Each worker can have one computation pending. A
query accepted at time is ready
at , where . Messages travel in either
direction between a nonroot worker and its parent. For a payload of
bits, the communication oracle
appends zero bits, so a message
accepted at time is ready at
where is the latency and is the time per transmitted
bit. The recipient receives the sender’s identity and the transmitted
bit string. Each directed edge can have one message pending. Submissions
to a busy worker’s computation oracle, to a busy directed edge, or to a
nonneighbor are ignored. Computations on distinct workers and
transmissions on distinct directed edges can overlap, including
transmissions in opposite directions and communication during
computation.
For an elapsed-time budget , the algorithm must almost surely
process only finitely many events at every deadline . At time , its designated output worker must
produce a measurable point with integrable squared error satisfying