# Convergence rates for distributed stochastic optimization over random networks

arXiv: https://arxiv.org/abs/1803.07836 · HTML: https://mlsanity.com/paper/1803.07836/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2018.

## Built on by (most cited first, 16 of 16)

- [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021)
- [Decentralized Stochastic Optimization with Inherent Privacy Protection](https://mlsanity.com/paper/2205.03884/) (2022)
- [Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework](https://mlsanity.com/paper/2503.14353/) (2025)
- [Quantization enabled Privacy Protection in Decentralized Stochastic Optimization](https://mlsanity.com/paper/2208.04845/) (2022)
- [Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data](https://mlsanity.com/paper/2406.00621/) (2024)
- [Decentralized Federated Learning with Gradient Tracking over Time-Varying Directed Networks](https://mlsanity.com/paper/2409.17189/) (2024)
- [Accelerating Parallel Stochastic Gradient Descent via Non-blocking Mini-batches](https://mlsanity.com/paper/2211.00889/) (2022)
- [Decentralized Learning over Wireless Networks with Broadcast-Based Subgraph Sampling](https://mlsanity.com/paper/2310.16106/) (2023)
- [Faster Convergence with Less Communication: Broadcast-Based Subgraph Sampling for Decentralized Learning over Wireless Networks](https://mlsanity.com/paper/2401.13779/) (2024)
- [Adjacent Leader Decentralized Stochastic Gradient Descent](https://mlsanity.com/paper/2405.11389/) (2024)
- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (2025)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)
- [VALID: a Validated Algorithm for Learning in Decentralized Networks with Possible Adversarial Presence](https://mlsanity.com/paper/2405.07316/) (2024)
- [Distributed gradient methods under heavy-tailed communication noise](https://mlsanity.com/paper/2505.24464/) (2025)
- [Information Entropy-Based Scheduling for Communication-Efficient Decentralized Learning](https://mlsanity.com/paper/2507.17426/) (2025)
- [High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking](https://mlsanity.com/paper/2605.00281/) (2026)

## Abstract (arXiv)

We establish the O(frac1k) convergence rate for distributed stochastic gradient methods that operate over strongly convex costs and random networks. The considered class of methods is standard each node performs a weighted average of its own and its neighbors solution estimates (consensus), and takes a negative step with respect to a noisy version of its local functions gradient (innovation). The underlying communication network is modeled through a sequence of temporally independent identically distributed (i.i.d.) Laplacian matrices connected on average, while the local gradient noises are also i.i.d. in time, have finite second moment, and possibly unbounded support. We show that, after a careful setting of the consensus and innovations potentials (weights), the distributed stochastic gradient method achieves a (order-optimal) O(frac1k) convergence rate in the mean square distance from the solution. This is the first order-optimal convergence rate result on distributed strongly convex stochastic optimization when the network is random and/or the gradient noises have unbounded support. Simulation examples confirm the theoretical findings.