← All setups

Distributed Mean-Squared Smooth Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Distributed Mean-Squared Smooth Nonconvex Optimization

We seek a stationary point of a differentiable, possibly nonconvex objective f:Rd→R in Euclidean dimension d≥0, given a starting point with bounded objective gap above a global lower bound. Workers on a star network have independent sample streams. Each completed query returns unbiased stochastic gradients at two points using one fresh sample. The gradients have bounded variance and are Lipschitz in mean square. Given ε>0, the goal is to return x¯∈Rd by an elapsed-time deadline with E∥∇f(x¯)∥2≤ε2, averaging over the samples and algorithm randomness.

The underlying optimization problem is infx∈Rdf(x). The algorithm receives the dimension d, the number of workers n≥1, the measurable sample space Ω, the starting point x0∈Rd, the bounds L>0, Δ≥0, and σ≥0, the tolerance ε, and the timing parameters (hi)i=1n, ℓ, and b described below. All norms are Euclidean.

Our assumptions:

Assumption 1 (Objective and initial gap). The function f is differentiable everywhere. There exists a∈R such that a≤f(x)for every x∈Rd,f(x0)−a≤Δ.

Assumption 2 (Worker sampling). For each worker i∈{1,…,n}, the samples (ξi,k)k≥0 are measurable, independent, and identically distributed with law μi on Ω. The worker streams are mutually independent, and the algorithm’s randomness is independent of the full sample array. On its (k+1)st completed query, worker i returns, for any requested x,y∈Rd, the pair (gi(x,ξi,k),gi(y,ξi,k)).

Assumption 3 (Gradient moments and mean-squared smoothness). Each gi:Rd×Ω→Rd is jointly measurable. For every x,y∈Rd and ξ∼μi, the vector gi(x,ξ) is Bochner integrable, both squared norms below are integrable, and E[gi(x,ξ)]=∇f(x),E∥gi(x,ξ)−∇f(x)∥2≤σ2,E∥gi(x,ξ)−gi(y,ξ)∥2≤L2∥x−y∥2.

The star has one communication-only hub and n computing workers. A paired query at worker i takes 2hi units of time, where hi>0. Each worker can have one query in progress. It may abort that query without consuming a sample. Further evaluation requests while the worker is busy are ignored.

Messages travel between the hub and a worker in either direction. A payload of m≥0 bits is transmitted with 64 appended zero bits and takes ℓ+b(m+64) units of time, where ℓ≥0 is the latency and b≥0 is the time per transmitted bit. The recipient receives the sender’s identity and the transmitted bits. Each directed link carries at most one message at a time and ignores new submissions while occupied. Distinct directed links can operate concurrently, including opposite directions on the same edge. Computations at different workers can overlap with one another and with communication.

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

Results

The differentiable objective f:Rd→R satisfies f(x0)−inff≤Δ. Worker streams are independent, with IID samples of law μi within worker i. Its jointly measurable oracle satisfies Eμigi(x,ξ)=∇f(x), Eμi∥gi(x,ξ)−∇f(x)∥2≤σ2, and Eμi∥gi(x,ξ)−gi(y,ξ)∥2≤L2∥x−y∥2. On the coordinator star, worker i takes 2hi>0 per same-sample pair. A q-bit message takes ℓ+bq. Each worker handles one computation and each directed link one message at a time; distinct links and computations can overlap. The target is E∥∇f(X)∥2≤ε2 under the execution law, with almost surely finitely many events through the deadline.

Elapsed-time upper bounds for stationarity under distributed mean-squared smoothness.
Result Oracle complexity Novelty Limitations
(1) MultilevelPipelineStationarity (Ours) (⋆⋆⋆) (review) O(Tc(1+S)+(1+K)max0≤j≤JTc(mj)2j)
(2) Rennala MVR (Tovmasyan et al. 2026, Thm. 5.2) O((K+S)Th(S)+Th(S)) (1): For ℓ=b=0, hi=i, n≥4S, K≥S, S>1, with a common sample law and the same smoothness bound L, O(Klog⁡(2+S)) versus O(KS1/4) for (2). Concurrent anchor batches also support paid links and worker-specific noise laws. (1) needs known fixed hi and has larger constants. With free links, equal hi, n≤S, K≥S, its bound loses a log⁡(2+S) factor. (2) assumes a common law, free links, S>1, 2K>1.
(3) Batched SGD (LongTails, n.d.) O((1+K)[Th(1+S)+C]) (1): Under the worker times, links and sampling conditions of (2), O(Klog⁡(2+S)) versus O(KS) for (3). (1) needs same-sample smoothness and a round trip per sample. For n=1, b=0, ℓ≥Sh1, K≥S≥1, its deadline is at least order KℓS versus O(Kℓ) for (3).
(4) Rennala SGD (Tyurin and Richtárik 2023, Thm. 7.5) O((1+K)Th(1+S)) (1): Under the worker times, links and sampling conditions of (2), O(Klog⁡(2+S)) versus O(KS) for (4). (1) also allows paid links. (1) requires same-sample gradient pairs and mean-squared smoothness. With free links, (4) uses single gradients and smoothness of f.

Abbr: K=LΔ/ε2, S=σ2/ε2, C=ℓ+b[1+dlog⁡(2+d+K+S)], ci=hi+C. For increasing rearrangement u(i), Tu(m)=min1≤k≤n(m+k)/∑i=1ku(i)−1. J=⌊min{log2⁡(1+K),log4⁡[(1+S)/(1+log⁡(1+S))]}⌋, mj=(1+J)4j+1{j=J}S.

LongTails: DistributedBatchedSgd. n.d. Lean convergence theorem and elapsed-time budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/DistributedBatchedSgd.lean.
Tovmasyan, Zhirayr, Artavazd Maranjyan, and Peter Richtárik. 2026. Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction. arXiv:2605.08871v1. https://doi.org/10.48550/arXiv.2605.08871.
Tyurin, Alexander, and Peter Richtárik. 2023. “Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model.” In Advances in Neural Information Processing Systems, edited by A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, vol. 36. Curran Associates, Inc. https://doi.org/10.52202/075280-0726.

Lean setup