Research map / Optimization / Distributed and compressed
Don't Compress Gradients in Random Reshuffling: Compress Gradient Differences
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies gradient compression combined with without-replacement sampling (random reshuffling), proposing Q-RR, DIANA-RR (compressing gradient differences with n shifts per worker), and local-step variants Q-NASTYA and DIANA-NASTYA.
Problem
Gradient compression in distributed learning has only been analyzed with with-replacement sampling, while random reshuffling (without-replacement) is empirically and theoretically better; their combination was unexplored, and naive combination gives no gain over QSGD.
Approach
Apply DIANA-style control shifts to compress gradient differences rather than gradients, using n shift vectors per worker (one per data point in the permutation) so compression variance vanishes and RR's O(1/T^2) advantage is retained in distributed settings; extend to local steps (DIANA-NASTYA).
Key results
- On logistic regression (mushrooms, w8a, a9a with Rand-k), DIANA-RR reaches the lowest functional suboptimality among non-local methods, outperforming QSGD, DIANA, and Q-RR, while Q-RR behaves similarly to QSGD.
- DIANA-NASTYA noticeably outperforms FedCOM and FedPAQ in the local-step logistic regression experiments, while Q-NASTYA performs comparably to them.
- On ResNet-18 training on CIFAR-10 with 10 workers, DIANA-RR outperforms DIANA, and Q-RR performs similarly to QSGD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| compress gradient differences using DIANA-style shifts instead of compressing gradients directly | Q-RR (DIANA-RR) · mushrooms, w8a, and a9a | functional suboptimality | Helped |
| use random reshuffling with direct gradient compression instead of with-replacement sampling | QSGD (Q-RR) · mushrooms, w8a, and a9a | functional suboptimality | No clear effect |
| add random reshuffling to DIANA without adding per-example shifts (ablation) | DIANA (DIANA-RR-1S) · mushrooms, w8a, and a9a | functional suboptimality | No clear effect |
| replace the n individual shifts with a single worker-side shift (ablation) | DIANA-RR · mushrooms, w8a, and a9a | functional suboptimality | Hurt |
| add DIANA-style variance reduction to Q-NASTYA | Q-NASTYA (DIANA-NASTYA) · mushrooms, w8a, and a9a | functional suboptimality | Helped |
| use Q-NASTYA instead of FedCOM or FedPAQ | local methods · mushrooms, w8a, and a9a | functional suboptimality | No clear effect |
| use random reshuffling with direct gradient compression instead of with-replacement sampling | QSGD (Q-RR) · CIFAR-10 | Top-1 accuracy | No clear effect |
| add random reshuffling and per-example shifts to DIANA | DIANA (DIANA-RR) · CIFAR-10 | Top-1 accuracy | Helped |
Surprising findings
- Naive combination of random reshuffling with quantization (Q-RR) gives no theoretical or empirical improvement over QSGD because compression variance dominates the RR variance.
Limitations
- Theoretical results are for strongly convex problems; neural network experiments are empirical only.
- DIANA-RR requires n shift vectors per worker, increasing memory (DIANA-RR-1S is a cheaper variant with weaker performance).
- Additive O(n(1+ω)) complexity term from shift learning.
Experimental setup
Datasets: mushrooms w8a a9a CIFAR-10
Benchmarks: mushrooms w8a a9a CIFAR-10
Metrics: functional suboptimality f(x_t)-f(x*) top-1 validation accuracy gradient norm loss value
Baselines: QSGD DIANA FedCOM FedPAQ EF21-SGD Q-RR
Builds on: DIANA NASTYA FedRR QSGD FedCOM
Closest papers by meaning
- Random Reshuffling: Simple Analysis with Vast Improvements (NeurIPS 2020 · similarity 0.90)
- Quantized Compressive Sampling of Stochastic Gradients for Efficient Communication in Distributed Deep Learning (AAAI 2020 · similarity 0.89)
- Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.87)
- Achieving Lossless Gradient Sparsification via Mapping to Alternative Space in Federated Learning (ICML 2024 · similarity 0.86)
- Methods with Local Steps and Random Reshuffling for Generally Smooth Non-Convex Federated Optimization (ICLR 2025 · similarity 0.86)
- Reshuffling Resampling Splits Can Improve Generalization of Hyperparameter Optimization (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.