← All setups

Bandwidth-Limited Distributed Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Bandwidth-Limited Distributed Nonconvex Optimization

We seek a stationary point of a possibly nonconvex objective f on Rd, where d≥0 is the dimension. The objective averages differentiable worker functions, has a Lipschitz gradient, and admits a lower bound with a prescribed gap from the initial value. Each worker returns a batch of unbiased local gradient estimates with bounded variance, using independent samples within and across workers. Workers have heterogeneous computation times and communicate over directed links with latency and per-bit costs. For tolerance ε>0, the goal is an output x¯ satisfying E∥∇f(x¯)∥2≤ε2, averaging over sampling and algorithm randomness.

With n≥1 workers and local functions fi:Rd→R, the optimization problem is infx∈Rdf(x),f(x)=1n∑i=1nfi(x). All norms are Euclidean. The algorithm receives d, n, the measurable sample space Ω, the starting point x0∈Rd, the smoothness constant L>0, the initial gap bound Δ≥0, the noise bound σ≥0, the tolerance ε, the worker computation times hi>0, the link latency ℓ≥0, and the transmission time per bit b≥0.

Our assumptions:

Assumption 1 (Aggregate smoothness and initial gap). Each fi is differentiable on Rd. There exists a∈R such that, for all x,y∈Rd, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,a≤f(x),f(x0)−a≤Δ.

Assumption 2 (Local stochastic gradients). Worker i has a sequence (ξi,k)k≥0 of independent measurable samples with common law μi on Ω. The worker sequences are mutually independent, and the algorithm’s randomness is independent of the entire sample array. Each map gi:Rd×Ω→Rd is jointly measurable. For every x∈Rd and ξ∼μi, the vector gi(x,ξ) is Bochner integrable, its squared error is integrable, and Eξ∼μi[gi(x,ξ)]=∇fi(x),Eξ∼μi[∥gi(x,ξ)−∇fi(x)∥2]≤σ2.

An idle worker i accepts a query consisting of a point x∈Rd and an integer batch size m≥1. After mhi units of time it returns the ordered list (gi(x,ξi,k),…,gi(x,ξi,k+m−1)), where k is the number of samples already used by that worker. A worker ignores further computation requests while its batch is pending. Different workers may compute concurrently.

Every ordered pair of workers, including a worker paired with itself, has a directed link. Messages on each link are queued in submission order. A message submitted at time t with a payload of q≥0 bits is ready for delivery at time max{t,c}+ℓ+b(q+64), where c is the completion time of the preceding message on that link, or zero for the first message. The receiver obtains the sender’s identity and the payload followed by the 64 zero bits included in the transmission cost. Distinct directed links may transmit concurrently, and communication may overlap computation.

For an elapsed-time budget T≥0, almost surely every deadline s∈[0,T] must be reached with only finitely many events through that deadline. At time T, the algorithm’s designated root worker must produce a measurable output x¯∈Rd with integrable squared gradient norm satisfying E[∥∇f(x¯)∥2]≤ε2.

Results

On Rd, F=n−1∑ifi has L-Lipschitz gradient and F(x0)−infF≤Δ. The fi are differentiable and their gradients may differ arbitrarily. Jointly measurable local oracles are unbiased with variance at most σ2. Samples are IID within each worker and independent across workers. Worker i processes one batch at a time at hi>0 per sample. Each ordered pair has a separate FIFO link. Links operate concurrently with each other and with computation. A B-bit packet including its header takes ℓ+bB time. For n≥1, L,ε>0 and Δ,σ,ℓ,b≥0, the target is a measurable output X with E∥∇F(X)∥2≤ε2 under the execution law.

Elapsed-time upper bounds for smooth nonconvex optimization with heterogeneous workers and finite-bit links.
Result Oracle complexity Novelty Limitations
(1) FiniteBitLeon (Ours) (⋆⋆) (review) O(K[C+ℓ+b(1+mlog⁡(2+nd))])
(2) Derived bound: full-range modulus (LongTails 2026) O(K[C+ℓ+b(1+mlog⁡(2+nd+K))]) (1): Multiscale anchors remove K from the packet-size logarithm. For σ=cε and other parameters fixed and positive (n≥2, d≥1), total time falls from O(ε−2log⁡(1/ε)) to O(ε−2) as ε→0. Sampling or latency can mask the gain. (1) stores leaf iterates and maintains a tree of anchors.
(3) Leon SGD (Tyurin 2026, Thm. 1.7) O(K[C+τd/(n−1)]) on a complete graph, n≥2, with zero latency and exact real coordinates. (1) preserves the sampling-time dependence using finite binary packets and accounts for latency. The different transmission units preclude a total-time comparison. (1) requires a complete multiport network and has large constants. (3) allows general connected bidirectional graphs.

Abbr: K=1+LΔ/ε2, C=maxihi+σ2∑ihi/(n2ε2), m=⌈d/n⌉. In (3), τ is the time per exact real coordinate on each link.

LongTails. 2026. Finite-Bit Decentralized Optimization with Heterogeneous Gradients. Repository companion note. https://github.com/k3nfalt/longtails/blob/6e7483f02c02983e8232511543e935eb2529cd15/LongTails/Theorems/FiniteBitLeon.md.
Tyurin, Alexander. 2026. Optimality in Decentralized Optimization Under Bandwidth Constraints. arXiv:2603.20735v1 [math.OC]. https://doi.org/10.48550/arXiv.2603.20735.

Lean setup