← All setups

Dasha Free Broadcast Deterministic Simplified — Distributed Nonconvex Optimization with Free Broadcast

Descriptions may be stale. Consult the linked Lean sources.

Distributed Nonconvex Optimization with Free Broadcast · Lean proof

Distributed Nonconvex Optimization with Free Broadcast

We consider minimizing F(x)=n−1∑i=1nfi(x) on Rd, where n,d≥1 are integers and the differentiable functions fi:Rd→R may be nonconvex. The gradient of F is L-Lipschitz, and component gradients are root-mean-square Lipschitz with constant L^, where L,L^>0. At a given point x0, component gradient norms are bounded by G≥0, and the gap above a global lower bound is at most Δ≥0. Worker i returns ∇fi(x) at x on a star network with heterogeneous computation times and free coordinator broadcasts. For ε>0, the goal is EP∥∇F(x¯)∥2≤ε2, where x¯ is the output and P is the law of algorithm randomness.

The optimization problem is infx∈RdF(x). All vector norms are Euclidean. There are n computing workers and one coordinator. Worker i has computation time hi>0; worker-to-coordinator communication has latency ℓ≥0 and time per bit b≥0. The algorithm receives d,n,(hi)i=1n,ℓ,b,L,L^,Δ,G,ε, and x0.

Our assumptions:

Assumption 1 (Smoothness). Each fi is differentiable everywhere. For every x,y∈Rd, ∥∇F(x)−∇F(y)∥≤L∥x−y∥,1n∑i=1n∥∇fi(x)−∇fi(y)∥2≤L^2∥x−y∥2.

Assumption 2 (Initial bounds). There exists Flow∈R such that F(x)≥Flowfor every x∈Rd,F(x0)−Flow≤Δ,∥∇fi(x0)∥≤Gfor i=1,…,n.

A gradient query at worker i may use any x∈Rd. If accepted at time t, it returns the queried point and the exact gradient ∇fi(x) at time t+hi. 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 m payload bits carries an additional 64 bits. Its transmission delay is {0,from the coordinator to a worker,ℓ+b(m+64),from a worker to the coordinator. 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 T≥0, the algorithm returns a measurable output x¯∈Rd at a designated output node. Almost surely under P, only finitely many computation, communication, and local scheduling events may occur up to each deadline t≤T. The squared gradient norm must be integrable, and the accuracy requirement is EP[∥∇F(x¯)∥2]≤ε2. The budget measures elapsed time, including computation and communication delays.

Proved elapsed-time upper bound

222⋅{0min{2⋅min{L,Lhat}⋅Δ,G2}≤ε2{max{1+min{L,Lhat}⋅Δε2,0}⋅((max0≤a<nh(a))+l+64⋅b+b⋅d⋅max{2+log⁡(1+min{L,Lhat}⋅Δε2)+log⁡(1+log⁡(d)),0})n=1max{1+min{L,Lhat}⋅Δε2,0}⋅((max0≤a<nh(a))+l+64⋅b)+b⋅max{(2+log⁡(1+Δ⋅(min{L,Lhat}+Lhatn)ε2)+log⁡(1+log⁡(n⋅d)))⋅(1+Δ⋅(min{L,Lhat}+d⋅min{min{L,Lhat},Lhatn})ε2)+d⋅min{Gε⋅n⋅(2+log⁡(1+Δ⋅(min{L,Lhat}+Lhatn)ε2)+log⁡(1+log⁡(n⋅d)))⋅(1+log⁡(1+log⁡(d⋅(1+min{L,Lhat}⋅Δε2)))),min{1+log⁡(1+log⁡(d⋅(1+min{L,Lhat}⋅Δε2)))+log⁡(1+G2⋅(2+log⁡(1+Δ⋅(min{L,Lhat}+Lhatn)ε2)+log⁡(1+log⁡(n⋅d)))n⋅ε2),1+log⁡(n⋅d⋅(1+min{L,Lhat}⋅Δε2))}},0}otherwiseotherwise

DistributedTemplate.TimedConvergence LongTails.Setups.DistributedFreeBroadcastSmoothNonconvex.spec
  LongTails.Theorems.DashaFreeBroadcastDeterministicSimplified.budget

Relevant previous results

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