# Federated Random Reshuffling with Compression and Variance Reduction

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 50 references that are in the map.
- First posted on arXiv 8 May 2022.

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

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Sparse Communication for Distributed Gradient Descent](https://mlsanity.com/paper/1704.05021/) (2017)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [SCAFFOLD: Stochastic Controlled Averaging for Federated Learning](https://mlsanity.com/paper/1910.06378/) (2019)
- [Federated Learning with Compression: Unified Analysis and Sharp Guarantees](https://mlsanity.com/paper/2007.01154/) (2020)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [Natural Compression for Distributed Deep Learning](https://mlsanity.com/paper/1905.10988/) (2019)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization](https://mlsanity.com/paper/1806.08054/) (2018)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)

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

- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation](https://mlsanity.com/paper/2410.08305/) (2024)
- [LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression](https://mlsanity.com/paper/2403.04348/) (2024)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration](https://mlsanity.com/paper/2509.10439/) (2025)
- [Improving Accelerated Federated Learning with Compression and Importance Sampling](https://mlsanity.com/paper/2306.03240/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptions](https://mlsanity.com/paper/2512.21521/) (2025)
- [BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training](https://mlsanity.com/paper/2601.12400/) (2026)
- [Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization](https://mlsanity.com/paper/2608.06563/) (2026)

## Abstract (arXiv)

Random Reshuffling (RR), which is a variant of Stochastic Gradient Descent (SGD) employing sampling without replacement, is an immensely popular method for training supervised machine learning models via empirical risk minimization. Due to its superior practical performance, it is embedded and often set as default in standard machine learning software. Under the name FedRR, this method was recently shown to be applicable to federated learning (Mishchenko et al.,2021), with superior performance when compared to common baselines such as Local SGD. Inspired by this development, we design three new algorithms to improve FedRR further: compressed FedRR and two variance reduced extensions: one for taming the variance coming from shuffling and the other for taming the variance due to compression. The variance reduction mechanism for compression allows us to eliminate dependence on the compression parameter, and applying additional controlled linear perturbations for Random Reshuffling, introduced by Malinovsky et al.(2021) helps to eliminate variance at the optimum. We provide the first analysis of compressed local methods under standard assumptions without bounded gradient assumptions and for heterogeneous data, overcoming the limitations of the compression operator. We corroborate our theoretical results with experiments on synthetic and real data sets.