← All setups

Distributed Nonconvex Optimization with Free Broadcast

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

F=n−1∑i=1nfi on Rd, with differentiable fi, L-Lipschitz ∇F, and n−1∑i∥∇fi(x)−∇fi(y)∥2≤L^2∥x−y∥2. A global lower bound Flow satisfies F(x0)−Flow≤Δ, and ∥∇fi(x0)∥≤G. Here d,n≥1, L,L^,ε>0, Δ,G≥0. Exact local gradients take hi>0 time. The star has dedicated concurrent uplinks costing ℓ+bB per B-bit packet, ℓ,b≥0, and free server broadcasts; one pending computation per worker and one packet per directed link, with computation and communication allowed concurrently. Our constructions use free shared randomness and uncharged arithmetic/coding, with known setup parameters. Target: ∫∥∇F(xout(ω))∥2dP(ω)≤ε2, under the algorithm’s execution law P.

Sufficient elapsed-time bounds for DistributedFreeBroadcastSmoothNonconvex.
Result Oracle complexity Novelty Limitations
(1) DashaFreeBroadcastDeterministic (Ours) (review) Elapsed-time upper bound, optimized deadline; a sufficient bound is O(min1≤k≤d{Kk[H+bk(1+log⁡Kk+log⁡log⁡C)]}+bdlog(2+Gdεn)).
(2) DashaFreeBroadcastDeterministicSimplified (Ours) (review) Closed-form elapsed-time upper bound: for n≥2, O(RH+bQ[1+Δ(λ+dmin{λ,L^/n})ε2]
+bdΦ); for n=1, O(R[H+bd(1+log⁡R+log⁡(1+log⁡d))]). Upper-bounds (1)’s deadline, with a larger universal prefactor.
(3) DASHA (Tyurin and Richtárik 2022), Thm. 6.1, Cor. 6.2. Derived bound: mean-square form. Sufficient O(nNk) total local-gradient calls; O(Nk) rounds and O(d+kNk) exact-real coordinates uploaded per worker, 1≤k≤d. No finite-bit elapsed-time bound. (1), (2): Matches known rounds. Formalization: finite-bit messages and verified elapsed time; no established rate improvement or comparable bit-level time bound. (1), (2): Needs G for packet ranges. Pathwise range growth incurs logarithmic bit costs; elapsed times and exact-real coordinate counts are not comparable.

Abbr: λ=min{L,L^}, H=maxihi+ℓ+b, R=1+λΔ/ε2; Kk=1+Δ(λ+L^d/(kn))/ε2; C=2+d+nL^/λ+Gd/(εn). Q=1+log⁡(1+Δ(λ+L^/n)/ε2)+log⁡(1+log⁡(nd)), J=1+log⁡(1+log⁡(dR)), Φ=min{GQJ/(εn), J+log⁡(1+G2Q/(nε2)), 1+log⁡(ndR)}. For (3), ωk=d/k−1 and Nk=1+Δ[λ+L^ωk(2ωk+1)/n]/ε2; initialization is included. Logs are natural; k is an integer.

Tyurin, Alexander, and Peter Richtárik. 2022. DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization. https://doi.org/10.48550/arXiv.2202.01268.

Lean setup