← All setups

Distributed Root Finding under Strong Growth

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

The L-Lipschitz map F:Rd→Rd has an M-Lipschitz Jacobian, F(x⋆)=0, ∥x0−x⋆∥≤R, and ⟨F(x),x−x⋆⟩≥μ∥x−x⋆∥2 with 0<μ≤L. On fresh IID samples, each worker’s jointly measurable oracle satisfies Egi(x)=F(x) and E∥gi(x)∥2≤ρ∥F(x)∥2, ρ≥1. The n workers form a rooted tree of depth at most h. Each worker handles one call at a time, taking τ>0; each directed edge carries one message at a time, taking λ+βb for b bits. Distinct workers and directed edges can operate concurrently. The target is E∥x^−x⋆∥2≤ε2 under the execution law.

Elapsed-time upper bounds for distributed root finding under strong growth.
Result Oracle complexity Novelty Limitations
(1) DistributedJacobianLocalExtragradient (Ours) (⋆⋆) (review) Elapsed-time upper bound. 0 if R≤ε. For R>ε:
n<64κG: O(τ(1+ρκ2J)).
n≥64κG: O((τρκ2+C(n))H+τκJ+C(ndu)(κ/T)[log⁡(2u)]+).
(2) Serial extragradient (Novoselov et al. 2026, Prop. F.4) Pairwise strongly monotone. One worker, elapsed time O(τρκ(1+J)). (1): On the overlap, O(τκJ) versus O(τρκJ) when n≥64κG, J≳ρκTH and C(ndR/ε)≲Tτ. Also covers quasi-strong monotonicity. (1) needs a Lipschitz Jacobian. For n<64κG and J≥1, its bound costs a factor κ more. Startup can also dominate.
(3) Common-query minibatch extragradient (Novoselov et al. 2026, Eq. (34)) Pairwise strongly monotone. O(κmax{1,ρ/n}(1+J)) exact-vector rounds, one call per worker per round. No finite-bit time bound. (1): On a depth-h tree, local steps cut the latency term by T when hλ≍Tτ, βdlog⁡(ndR/ε)≲λ, n≥64κGT and J≳ρκTH. Gain over the cheaper of (2), (3) is then of order min{ρ,T} against uncharged bits. (1) adds Jacobian regularity and startup cost. Depth T grows at most logarithmically in n: at ρ=20, T=10 requires n≳4⋅1010κ.
(4) LESGD (Wang and Kale 2026, Thm. 1) Expected restricted gap of averaged iterates for Lipschitz monotone operators with uniformly bounded variance. (1), (4): Rates are not comparable across the distance and restricted-gap targets and noise models.
(5) LIPPAX (Wang and Kale 2026, Thm. 4) Expected restricted gap under monotonicity, Lipschitz continuity, bounded variance, a globally bounded operator and a quadratic Taylor remainder bound. (1), (5): Rates are not comparable across these operator classes and accuracy targets.

Abbr: κ=L/μ, J=log⁡(R/ε) for R>ε, G=2+ρ/8+ρ2/128, C(s)=h(λ+βdlog⁡(2+s)). In the parallel branch, T=min{⌊κ⌋,⌊log⁡(n/(64κ))/log⁡G⌋} is the local step count, q=1+32ρMRGT/μ, u=R/(εq), H=1+log⁡(dq), and [a]+=max{a,0}.

Novoselov, Kirill, Yuriy Dorn, Darina Dvinskikh, and Alexander Gasnikov. 2026. Optimal Rates for Federated Variational Inequalities under different relaxations of bounded variance assumption. https://doi.org/10.48550/arXiv.2610.12641.
Wang, Guanghui, and Satyen Kale. 2026. Faster Rates For Federated Variational Inequalities. https://doi.org/10.48550/arXiv.2602.09164.

Lean setup