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

Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtárik, Yuejie Chi

Introduction

In the era of massive-scale machine learning, decentralized optimization has emerged as a critical paradigm for training models across distributed networks, such as IoT devices or mobile phones in Federated Learning. The primary challenge in these environments is the communication bottleneck: transmitting high-dimensional model updates across a network is often significantly slower than local computation. While communication compression (e.g., quantization or sparsification) is a standard remedy, it typically introduces noise that degrades convergence rates or requires restrictive assumptions.

The authors of "BEER: Better comprEssion for dEcentRalized optimization" introduce a novel algorithm that breaks these traditional trade-offs. BEER achieves a fast $O(1/T)$ convergence rate for nonconvex optimization—matching the rate of uncompressed methods—while operating without the "bounded gradient" or "bounded dissimilarity" assumptions that plague existing compressed decentralized algorithms.

The Challenge: Heterogeneity and Compression Noise

Existing state-of-the-art algorithms for compressed decentralized optimization, such as CHOCO-SGD, often struggle in nonconvex settings. They typically suffer from two main issues:

  1. Slower Convergence: Many compressed methods converge at a rate of $O(T^{-2/3})$, which is theoretically inferior to the $O(1/T)$ rate achievable by uncompressed decentralized algorithms.
  2. Restrictive Assumptions: To handle the noise from compression and data heterogeneity, these methods often rely on "Bounded Gradient" or "Bounded Dissimilarity" assumptions. These assume that local gradients or datasets across different nodes are not too different, an assumption that rarely holds in real-world, highly heterogeneous (non-IID) data scenarios.

The BEER Algorithm: Double Tracking with Compressed Surrogates

The core innovation of BEER is the synergistic integration of Gradient Tracking and Biased Communication Compression.

  • Gradient Tracking: Each node maintains an estimate of the global gradient by communicating with its neighbors. This allows the algorithm to "track" the global objective even when local datasets are extremely diverse.
  • Compressed Surrogates: Inspired by the EF21 error-feedback mechanism, BEER maintains two control sequences ($H^t$ and $G^t$) that act as compressed "stand-ins" for model parameters and global gradient estimates. Instead of communicating raw values, nodes communicate compressed differences between current values and their previous surrogates.

By "double tracking" both the model and the gradient estimate using these surrogates, BEER effectively cancels out the noise introduced by both data heterogeneity and communication compression.

Theoretical Results

BEER is the first compressed decentralized algorithm to achieve the $O(1/T)$ rate for nonconvex problems without requiring bounded gradient assumptions. Furthermore, under the Polyak-Łojasiewicz (PL) condition—a common generalization of strong convexity—BEER achieves a linear convergence rate.

Convergence rates of BEER under smooth and PL assumptions.

Key Results and Empirical Performance

The theoretical superiority of BEER is summarized in the table below, highlighting its faster rate and lack of strong assumptions compared to other leading methods.

Comparison of BEER with state-of-the-art compressed decentralized algorithms.

The authors validated these theoretical claims through experiments on standard benchmarks designed to simulate high data heterogeneity, such as the a9a dataset and MNIST. In these tests, BEER consistently outperformed CHOCO-SGD. While CHOCO-SGD often hit an "error floor" due to heterogeneity, BEER converged to the same high-accuracy solutions as uncompressed methods but with significantly fewer communication bits.

Conclusion

BEER demonstrates that communication efficiency does not have to come at the cost of convergence speed or robustness to data heterogeneity. By combining gradient tracking with a clever surrogate-based compression scheme, it provides a powerful tool for decentralized learning in realistic, non-IID environments.

Summary updated

BibTeX
@inproceedings{zhao2022beer,
  author = {Haoyu Zhao and Boyue Li and Zhize Li and Peter Richtárik and Yuejie Chi},
  title = {{BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=yP2If-sVPr_},
}
Figure