← All setups

Distributed Nonconvex Finite-Sum Optimization

Descriptions may be stale. Consult the linked Lean sources.

Distributed Nonconvex Finite-Sum Optimization

We seek a stationary point of a possibly nonconvex objective F on Rd, the mean of n≥1 differentiable worker objectives in dimension d≥0. The aggregate gradient is Lipschitz, and the gap from the given starting value to a global lower bound is bounded. Each worker returns an unbiased estimate of its own gradient with bounded variance, using independent samples across evaluations and workers. Workers communicate through a central node. For a tolerance ε>0, the goal is to return x¯∈Rd within an elapsed-time budget with E∥∇F(x¯)∥≤ε, averaging over sampling and algorithm randomness.

Write fi:Rd→R for the objective at worker i∈{1,…,n} and use the Euclidean norm throughout. The optimization problem is infx∈RdF(x),F(x)=1n∑i=1nfi(x). The algorithm receives d, n, the measurable sample space Ω, the starting point x0∈Rd, the smoothness and gap bounds L>0 and Δ≥0, the noise bounds σi≥0, the tolerance ε, and the timing parameters hi>0, ℓ≥0, and b≥0.

Our assumptions:

Assumption 1 (Aggregate smoothness and initial gap). Each fi is differentiable everywhere. For every x,y∈Rd, ∥∇F(x)−∇F(y)∥≤L∥x−y∥. There exists Flow∈R such that Flow≤F(x)for every x∈Rd,F(x0)−Flow≤Δ.

Assumption 2 (Worker sampling and gradient estimates). Worker i has a sequence (ξi,k)k≥0 of measurable i.i.d. samples with law μi on Ω. The worker sequences are mutually independent, and the algorithm’s randomness is independent of the entire sample array. On its kth completed evaluation, indexed from zero, worker i returns the query point x and the vector gi(x,ξi,k), where gi:Rd×Ω→Rd is jointly measurable. For each 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]≤σi2.

Assumption 3 (Star network and timing). The center communicates with each of the n workers in both directions. Only workers perform gradient evaluations. An evaluation at worker i takes time hi and may be aborted. While an evaluation is pending, the worker ignores new evaluation requests. Each directed link carries at most one message at a time and ignores send requests while occupied. Computations at different workers and transmissions on distinct directed links may proceed concurrently, and communication may overlap computation. A payload of m≥0 bits is transmitted with 64 trailing zero bits and arrives with the sender’s identity after time ℓ+b(m+64), where ℓ is the latency and b is the time per transmitted bit.

Let T≥0 be the elapsed-time budget. Almost surely, every deadline t∈[0,T] must be reached with only finitely many events through that deadline. At time T, the algorithm’s designated output node must provide a measurable point x¯ with integrable gradient norm satisfying E[∥∇F(x¯)∥]≤ε.

Results

The n≥1 differentiable functions fi on Rd have an L-smooth average F=n−1∑ifi with F(x0)−infF≤Δ. Component smoothness, gradient magnitudes and worker disagreement are unrestricted. Worker i takes hi>0 per unbiased gradient sample of fi, with variance at most σi2 and a jointly measurable oracle. Samples are IID within workers and independent across workers. On the dedicated star, each worker and each directed hub–worker link handles one request at a time, concurrently across resources. A q-bit transmission takes ℓ+bq. The hub targets E∥∇F(X)∥≤ε under the execution law.

Elapsed-time upper bounds for distributed stationarity with a smooth aggregate.
Result Oracle complexity Novelty Limitations
(1) MultiscaleAggregateStationarity (Ours) (⋆⋆) (review) O(K[C+ℓ+bB(nd)])
(2) Derived bound using single-modulus summation (Bonawitz et al. 2019) O(K[C+ℓ+bB(ndK)]) (1): Dyadic anchors remove K from the packet logarithm. For d≥1, K≫nd and bB(nd)≳C+ℓ, the time bound improves by a factor of order log⁡K/log⁡(2+nd). With fixed hardware and positive noise, computation dominates as ε→0.
(3) Amelie SGD (Tyurin and Richtárik 2024, Cor. 2) O(K[C+τ]), common σi=σ (1): Matches the computation term with common σ and sends finite packets despite unbounded disagreement. (3) prices a real vector, so its time has no specified bit equivalent. (1) requires fixed star service times. (3) allows general networks with time-varying speeds under service-time bounds and guarantees E∥∇F(X)∥2≤ε2.
(4) Leon SGD (Tyurin 2026, Thm. 1.7) O(K[C+d/w¯1]), common σi=σ, symmetric bandwidths, zero latency (1): Charges for transmitted bits and message latency. (4) measures bandwidth in real coordinates, so the elapsed-time rates are incomparable in bit units. (1) requires a star. (4) covers general bandwidth graphs and guarantees E∥∇F(X)∥2≤ε2.
(5) DistributedBatchedSgd (LongTails, n.d.) (homogeneous) O(K[min1≤m≤n(hm+s∑j≤m1/hj)+ℓ+bB(d+K+s)]) (1) allows distinct fi with only F smooth. On the overlap fi=F, σi=σ, its packet logarithm is smaller when nd≪K+s. (1) waits for every worker. One slow worker can make its compute term arbitrarily worse. (5) also guarantees E∥∇F(X)∥2≤ε2.

Abbr: K=1+LΔ/ε2, C=maxihi+∑ihiσi2/(n2ε2), B(u)=1+dlog⁡(2+u), s=σ2/ε2. In (3), τ is the maximum shortest-path time for a real vector. In (4), w¯1 is the minimum cut capacity in coordinates per unit time. In (5), h1≤⋯≤hn.

Bonawitz, Keith, Fariborz Salehi, Jakub Konečný, Brendan McMahan, and Marco Gruteser. 2019. “Federated Learning with Autotuned Communication-Efficient Secure Aggregation.” 2019 53rd Asilomar Conference on Signals, Systems, and Computers, 1222–26. https://doi.org/10.1109/IEEECONF44664.2019.9049066.
LongTails: DistributedBatchedSgd. n.d. Lean convergence theorem and elapsed-time budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/DistributedBatchedSgd.lean.
Tyurin, Alexander. 2026. Optimality in Decentralized Optimization Under Bandwidth Constraints. https://doi.org/10.48550/arXiv.2603.20735.
Tyurin, Alexander, and Peter Richtárik. 2024. “On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization.” Advances in Neural Information Processing Systems 37: 122652–705. https://doi.org/10.52202/079017-3898.

Lean setup