# BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 68 references that are in the map.
- First posted on arXiv 31 Jan 2022.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [Federated Learning with Cooperating Devices: A Consensus Approach for Massive IoT Networks](https://mlsanity.com/paper/1912.13163/) (2019)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!](https://mlsanity.com/paper/2011.01697/) (2020)
- [An Exact Quantized Decentralized Gradient Descent Algorithm](https://mlsanity.com/paper/1806.11536/) (2018)
- [SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimization](https://mlsanity.com/paper/2005.07041/) (2020)
- [A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization](https://mlsanity.com/paper/2006.07013/) (2020)
- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [textttDeepSqueeze: Decentralization Meets Error-Compensated Compression](https://mlsanity.com/paper/1907.07346/) (2019)
- [Linear Convergent Decentralized Optimization with Compression](https://mlsanity.com/paper/2007.00232/) (2020)

## Built on by (most cited first, 30 of 41)

- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [Momentum Tracking: Momentum Acceleration for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2209.15505/) (2022)
- [EControl: Fast Distributed Optimization with Compression and Error Control](https://mlsanity.com/paper/2311.05645/) (2023)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2305.07612/) (2023)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compression](https://mlsanity.com/paper/2305.09896/) (2023)
- [Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence](https://mlsanity.com/paper/2305.11420/) (2023)
- [A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regret](https://mlsanity.com/paper/2301.08869/) (2023)
- [DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2202.00255/) (2022)
- [LoCo: Low-Bit Communication Adaptor for Large-scale Model Training](https://mlsanity.com/paper/2407.04480/) (2024)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression](https://mlsanity.com/paper/2310.19059/) (2023)
- [A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning](https://mlsanity.com/paper/2309.09977/) (2023)
- [Decentralized Personalized Federated Learning based on a Conditional Sparse-to-Sparser Scheme](https://mlsanity.com/paper/2404.15943/) (2024)
- [Communication-efficient Vertical Federated Learning via Compressed Error Feedback](https://mlsanity.com/paper/2406.14420/) (2024)
- [Differential error feedback for communication-efficient decentralized learning](https://mlsanity.com/paper/2406.18418/) (2024)
- [Problem-dependent convergence bounds for randomized linear gradient compression](https://mlsanity.com/paper/2411.12898/) (2024)
- [Scalable Decentralized Learning with Teleportation](https://mlsanity.com/paper/2501.15259/) (2025)
- [Communication Compression for Decentralized Learning with Operator Splitting Methods](https://mlsanity.com/paper/2205.03779/) (2022)
- [Communication-Efficient Federated Optimization over Semi-Decentralized Networks](https://mlsanity.com/paper/2311.18787/) (2023)
- [Sparse Training for Federated Learning with Regularized Error Correction](https://mlsanity.com/paper/2312.13795/) (2023)
- [Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/2508.04950/) (2025)
- [AdaGossip: Adaptive Consensus Step-size for Decentralized Deep Learning with Communication Compression](https://mlsanity.com/paper/2404.05919/) (2024)
- [Tight analyses of first-order methods with error feedback](https://mlsanity.com/paper/2506.05271/) (2025)
- [DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication](https://mlsanity.com/paper/2512.13583/) (2025)

## Abstract (arXiv)

Communication efficiency has been widely recognized as the bottleneck for large-scale decentralized machine learning applications in multi-agent or federated environments. To tackle the communication bottleneck, there have been many efforts to design communication-compressed algorithms for decentralized nonconvex optimization, where the clients are only allowed to communicate a small amount of quantized information (aka bits) with their neighbors over a predefined graph topology. Despite significant efforts, the state-of-the-art algorithm in the nonconvex setting still suffers from a slower rate of convergence O((G/T)2/3) compared with their uncompressed counterpart, where G measures the data heterogeneity across different clients, and T is the number of communication rounds. This paper proposes BEER, which adopts communication compression with gradient tracking, and shows it converges at a faster rate of O(1/T). This significantly improves over the state-of-the-art rate, by matching the rate without compression even under arbitrary data heterogeneity. Numerical experiments are also provided to corroborate our theory and confirm the practical superiority of BEER in the data heterogeneous regime.