← All setups

Distributed Jacobian Local Extragradient — Distributed Root Finding under Strong Growth

Descriptions may be stale. Consult the linked Lean sources.

Distributed Root Finding under Strong Growth · Lean proof

Distributed Root Finding under Strong Growth

We seek a zero x⋆ of a Lipschitz map F:Rd→Rd in dimension d≥1. The map has a Lipschitz Jacobian and satisfies ⟨F(x),x−x⋆⟩≥μ∥x−x⋆∥2 at every point x, for some μ>0. Workers communicate over a rooted tree. At x, each worker uses a fresh independent sample to return an unbiased estimate of F(x) with second moment at most ρ∥F(x)∥2, where ρ≥1. Given a starting point within known distance of the zero and a tolerance ε>0, the goal is an output x¯ satisfying E∥x¯−x⋆∥2≤ε2 by an elapsed-time deadline, averaging over algorithm and oracle randomness.

Write E=Rd with its Euclidean inner product and norm. The equation to be solved is F(x)=0,x∈E. Let V={0,…,n−1} be the set of workers, where n≥1 is an integer. The algorithm receives d, n, the nonempty measurable sample space Ω, the tree root r, parent map p, depth function s and height bound h, the timing parameters τ,ℓ,β, the constants L,μ,ρ,M,R, the tolerance ε, and the starting point x0∈E.

Our assumptions:

Assumption 1 (Operator and Jacobian regularity). The map F is Fréchet differentiable on E. Its Jacobian J(x):E→E and the map itself satisfy, for every x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥,∥J(x)−J(y)∥op≤M∥x−y∥, where 0<μ≤L, M≥0, and ∥⋅∥op is the induced operator norm.

Assumption 2 (Growth about the solution). There is a zero x⋆∈E such that, for a radius R>0, ∥x0−x⋆∥≤R,⟨F(x),x−x⋆⟩≥μ∥x−x⋆∥2(x∈E).

Assumption 3 (Sampling and strong growth). Let (ξj)j≥0 be measurable, mutually independent samples with common probability law ν on Ω, independent of the algorithm’s randomness. On its (k+1)st completed query, for k≥0, worker i∈V returns gi(x,ξnk+i) at the queried point x∈E. Each gi:E×Ω→E is jointly measurable. For each i and x, gi(x,⋅) is Bochner integrable and ∥gi(x,⋅)∥2 is integrable under ν, with Eξ∼ν[gi(x,ξ)]=F(x),Eξ∼ν[∥gi(x,ξ)∥2]≤ρ∥F(x)∥2.

Assumption 4 (Tree topology and timing). The root r∈V, parent map p:V→V, depth function s:V→{0,1,…}, and integer h≥0 satisfy p(r)=r,s(r)=0,s(i)=s(p(i))+1(i≠r),s(i)≤h(i∈V). Each worker can have one computation pending. A query accepted at time t is ready at t+τ, where τ>0. Messages travel in either direction between a nonroot worker and its parent. For a payload of b bits, the communication oracle appends 64 zero bits, so a message accepted at time t is ready at t+ℓ+β(b+64), where ℓ≥0 is the latency and β≥0 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 T≥0, the algorithm must almost surely process only finitely many events at every deadline t∈[0,T]. At time T, its designated output worker must produce a measurable point x¯∈E with integrable squared error satisfying E[∥x¯−x⋆∥2]≤ε2.

Proved elapsed-time upper bound

{0R≤ε{max{65536⋅((τ⋅ρ⋅κ2+C(2⋅n))⋅(1+log⁡(d⋅q))+τ⋅κ⋅log⁡(Rε)+C(2+n⋅d⋅Rε⋅q)⋅(κT⋅max{log⁡(2⋅Rε⋅q),0})),0}whereT=min{⌊κ⌋+,⌊log⁡(n64⋅κ)log⁡(G)⌋+}whereq=1+32⋅ρ⋅M⋅R⋅GTμ64⋅κ⋅G≤nτ⋅⌈ρ⋅κ2⋅log⁡(R2ε2)⌉+otherwiseotherwisewhereκ=LμwhereG=2+ρ8+ρ2128whereC(x)=h⋅(l+β⋅(64+d⋅log⁡(x)))

DistributedTemplate.TimedConvergence LongTails.Setups.DistributedJacobianStrongGrowth.spec
  LongTails.Theorems.DistributedJacobianLocalExtragradient.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.