# Distributed Random Reshuffling Methods with Improved Convergence

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 56 references that are in the map.
- First posted on arXiv 21 Jun 2023.

## Builds on (most cited first, 30 of 41)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data](https://mlsanity.com/paper/2005.11418/) (2020)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning](https://mlsanity.com/paper/2110.09993/) (2021)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [On the Influence of Bias-Correction on Distributed Stochastic Optimization](https://mlsanity.com/paper/1903.10956/) (2019)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Decentralized Proximal Gradient Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/1909.06479/) (2019)
- [Optimal Gradient Tracking for Decentralized Optimization](https://mlsanity.com/paper/2110.05282/) (2021)
- [Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequality](https://mlsanity.com/paper/2110.04926/) (2021)
- [Stochastic Learning under Random Reshuffling with Constant Step-sizes](https://mlsanity.com/paper/1803.07964/) (2018)
- [Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis](https://mlsanity.com/paper/2002.11534/) (2020)

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

- [Convergence of Decentralized Stochastic Subgradient-based Methods for Nonsmooth Nonconvex functions](https://mlsanity.com/paper/2403.11565/) (2024)
- [Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, H"older Geometry, and Composite Proximal Extensions](https://mlsanity.com/paper/2609.04578/) (2026)

## Abstract (arXiv)

This paper proposes two distributed random reshuffling methods, namely Gradient Tracking with Random Reshuffling (GT-RR) and Exact Diffusion with Random Reshuffling (ED-RR), to solve the distributed optimization problem over a connected network, where a set of agents aim to minimize the average of their local cost functions. Both algorithms invoke random reshuffling (RR) update for each agent, inherit favorable characteristics of RR for minimizing smooth nonconvex objective functions, and improve the performance of previous distributed random reshuffling methods both theoretically and empirically. Specifically, both GT-RR and ED-RR achieve the convergence rate of O(1/[(1-λ)1/3m1/3T2/3]) in driving the (minimum) expected squared norm of the gradient to zero, where T denotes the number of epochs, m is the sample size for each agent, and 1-λ represents the spectral gap of the mixing matrix. When the objective functions further satisfy the Polyak-Lojasiewicz (PL) condition, we show GT-RR and ED-RR both achieve O(1/[(1-λ)mT2]) convergence rate in terms of the averaged expected differences between the agents' function values and the global minimum value. Notably, both results are comparable to the convergence rates of centralized RR methods (up to constant factors depending on the network topology) and outperform those of previous distributed random reshuffling algorithms.