← 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 d-dimensional Euclidean space Rd. Each worker contributes one component to the average F. Each component has a Lipschitz gradient, and the initial objective gap to a global lower bound is bounded. Workers compute at heterogeneous speeds and communicate over directed links. Each worker’s oracle returns batches of unbiased local gradient estimates with bounded variance, using independent samples within and across workers. For a tolerance ε>0, the goal is an output x¯ satisfying E[∥∇F(x¯)∥2]≤ε2 over sampling and algorithm randomness.

Index the n≥1 workers by i=1,…,n, and write fi:Rd→R for their components, where d is a nonnegative integer. With F(x)=1n∑i=1nfi(x), the optimization problem is infx∈RdF(x). The algorithm receives d, n, the measurable sample space Ω, the starting point x0∈Rd, the bounds (Li,σi)i=1n and Δ, the tolerance ε, and the timing parameters (hi)i=1n, ℓ, and b.

Our assumptions:

Assumption 1 (Component smoothness and initial gap). Each fi is differentiable, and for all x,y∈Rd its gradient satisfies ∥∇fi(x)−∇fi(y)∥≤Li∥x−y∥,Li≥0, where ∥⋅∥ is the Euclidean norm. There is a lower bound a∈R such that a≤F(x)for every x∈Rd,F(x0)−a≤Δwith Δ≥0.

Assumption 2 (Local stochastic gradients). Worker i has a stream (ξi,k)k≥0 of measurable, independent samples with common law μi on Ω. The worker streams are mutually independent, and the algorithm’s randomness is independent of the entire sample array. The 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]≤σi2, where σi≥0.

Computation and communication.

A computation query at worker i specifies a point x∈Rd and a positive integer batch size m. If k samples have already been used, the worker returns the ordered batch (gi(x,ξi,k+j))j=0m−1 after time mhi, where hi>0 is its time per sample. Each worker processes one batch at a time and ignores further computation requests while a batch is pending. Different workers can compute concurrently.

Every ordered pair of workers, including a worker paired with itself, has a directed link. A message with q≥0 payload bits is padded with 64 zero bits. If submitted at time t, it finishes at max{t,tprev}+ℓ+b(q+64), where tprev is the previous finish time on that link, initially zero, ℓ≥0 is the latency, and b≥0 is the time per transmitted bit. The recipient receives the sender’s identity and the padded bit string. Each link serves messages in submission order. Distinct links can operate concurrently, and communication can overlap computation.

Elapsed time and accuracy.

For an elapsed-time budget T≥0, almost surely the algorithm must process only finitely many events for every deadline s∈[0,T]. At time T, a root worker designated by the algorithm 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 is bounded below, F(x0)−infF≤Δ, and ∇fi is Li-Lipschitz. Worker i has a jointly measurable unbiased gradient oracle with variance at most σi2. Samples are IID within workers and independent across workers. Workers compute in parallel, one batch per worker at a time, at hi>0 time per sample. Computation and communication can overlap. The complete multiport network serves each directed link in FIFO order. An m-bit message takes ℓ+bm time. Here n≥1, Li,σi,Δ,ℓ,b≥0, and ε>0. By the deadline, the execution returns a measurable X with Eexec∥∇F(X)∥2≤ε2 and almost surely completes only finitely many events.

Elapsed-time upper bounds for distributed component-smooth nonconvex stationarity.
Result Oracle complexity Novelty Limitations
(1) MultirateDistributedStationarity (Ours) (⋆⋆⋆) (review) O(H+σ2h―nε2+rC(d,r)+qLh―+qnε2(σLh―)2)
(2) FiniteBitLeon (Tyurin 2026) O((1+qLF)[H+vh¯+C(⌈d/n⌉,1)]) (1): On the same network with Li=L≍LF, σi=σ, recurring compute time falls from H+vh¯ to h¯+v(h―)2. Also weights each worker’s variance separately. (1) needs local smoothness. Curvature cancellation can give LF≪L¯. Each link carries d coordinates instead of ⌈d/n⌉, with an additional log⁡r in the bits per coordinate.
(3) Malenia SGD (Tyurin and Richtárik 2023, Thm. A.4) O(qLF(H+vh¯)), free communication (1): For Li=L≍LF, σi=σ, qL≥1, ℓ=b=0, pays H+vh¯ once. Recurring time replaces H by h¯ and the noise coefficient h¯ by (h―)2. At σ=0 the recurring gain is H/h¯. (1) needs hi,Li,σi for scheduling. (3) uses global smoothness and a common variance bound without knowing worker speeds.
(4) Ringleader ASGD (Maranjyan and Richtárik 2026, sec. 5.2) O(qLRL(H+vh¯)), fixed speeds, free communication (1): With 2J−g workers of time 4g per group g=0,…,J, Li=σi=Δ=1, LF≍1, ε=n−2, d≤n, ℓ=b=0, total time is O(n7log2⁡n) versus O(n8) for (3), (4). Fixed ℓ,b add only O(n5log⁡n) to (1) here. (1) needs individual smoothness, noise and timing parameters. (4) uses aggregate smoothness LRL and schedules workers without knowing their speeds.
(5) Modified Ringleader ASGD (Maranjyan and Richtárik 2026, App. C.3) Fixed-speed specialization, free communication: O((1+qLRL)(H+vh¯)) (1): With fixed hi, Li=L≍LF, σi=σ, ℓ=b=0, recurring compute time uses h¯+v(h―)2 instead of H+vh¯. (1) requires known, fixed hi. (5) also gives a deadline under unknown, time-varying worker speeds.
(6) Rescaled ASGD (Mahran et al. 2026, Cor. 4.2)

O(qLF(H+vh¯)+qLmaxHhharm[ρH+h¯σ2+ζ2ε])

Free communication

(1) drops pairwise harmonic periods and the bound ∥∇fi∥2≤ζ2+ρ2∥∇F∥2. On that overlap with Li=L≍LF, σi=σ, ℓ=b=0, recurring time falls to h¯+v(h―)2, removing the staleness penalties. (1) needs individual Li,σi in addition to worker times.

Abbr: a¯=n−1∑iai for worker-indexed expressions, H=maxihi, hharm=1/(1/h)―, q=Δ/ε2, r=1+qL¯, v=σ2/(nε2) for common variance bound σ2. C(k,s)=ℓ+b[1+k(1+log⁡(n(d+1)s))]. LF is global smoothness, Lmax=maxiLi, and LRL is the mixed-point smoothness constant, LF≤LRL≤L2―. Pairwise harmonic periods satisfy max(hi,hj)/min(hi,hj)∈N.

Mahran, Ammar, Artavazd Maranjyan, and Peter Richtárik. 2026. “Rescaled Asynchronous SGD: Optimal Distributed Optimization Under Data and System Heterogeneity.” Proceedings of the 43rd International Conference on Machine Learning. https://doi.org/10.48550/arXiv.2605.13434.
Maranjyan, Artavazd, and Peter Richtárik. 2026. “Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity Under Data Heterogeneity.” The Fourteenth International Conference on Learning Representations. https://doi.org/10.48550/arXiv.2509.22860.
Tyurin, Alexander. 2026. FiniteBitLeon. LongTails Lean theorem, revision 6e7483f0. https://github.com/k3nfalt/longtails/blob/6e7483f02c02983e8232511543e935eb2529cd15/LongTails/Theorems/FiniteBitLeon.lean.
Tyurin, Alexander, and Peter Richtárik. 2023. “Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model.” Advances in Neural Information Processing Systems 36. https://doi.org/10.52202/075280-0726.

Lean setup