BEER Gradient Tracking with Communication Compression for Decentralized Nonconvex Optimization
Algorithms AIMech:BeerGradientTrackingWithCommunicationCompressionForDecentralizedNonconvexOptimization DRAFT
Aliases: BEER, BEER Decentralized Compressed Gradient Tracking, Gradient Tracking with Communication Compression for Decentralized Nonconvex Optimization
A communication-compressed decentralized nonconvex optimization algorithm (BEER) that couples EF21-style Markov contractive error-feedback states H^t in R^(d x n) (tracking parameters X^t) and G^t in R^(d x n) (tracking gradient-tracking vectors V^t) with decentralized gossip mixing over a symmetric doubly-stochastic matrix W via X^(t+1) = X^t + gamma * H^t (W - I) - eta * V^t, H^(t+1) = H^t + C(X^(t+1) - H^t), V^(t+1) = V^t + gamma * G^t (W - I) + grad F(X^(t+1)) - grad F(X^t), and G^(t+1) = G^t + C(V^(t+1) - G^t), achieving a fast O(1/T) nonconvex stationarity rate with arbitrary alpha-contractive (possibly biased) compressors without bounded gradient-dissimilarity assumptions.
Identity Notes & Concept Scope
Introduced by Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtarik, and Yuejie Chi (NeurIPS 2022, Vol. 35, pp. 31653-31667; arXiv:2201.13320). Distinct from Choco-SGD (Koloskova et al., ICML 2019; Round 382), which compresses only model parameters without gradient tracking and attains a slower O(1/sqrt(T)) rate under bounded inter-client gradient dissimilarity; and distinct from EF21 (Richtarik, Sokolov, & Fatkhullin, NeurIPS 2021; Round 380), which operates on a centralized master-worker star topology rather than a decentralized peer-to-peer graph with dual parameter and gradient-tracking control variates.
Claims & Grounded Evidence
4 Claims
Mechanism
#beer-coupled-ef21-parameter-and-gradient-tracking-invariance-mechanism
BEER maintains compressed control variates H^t for parameters X^t and G^t for gradient-tracking estimates V^t using an alpha-contractive compressor C satisfying E||C(x) - x||^2 <= (1 - alpha)||x||^2 (Definition 2.2), and because H^t (W - I) (1/n) 1 = 0 and G^t (W - I) (1/n) 1 = 0 for doubly-stochastic W, Lemma B.3 establishes the exact global invariants v_bar^t = (1/n) sum_{i=1}^n grad f_i(x_i^t) and x_bar^(t+1) = x_bar^t - (eta/n) sum_{i=1}^n grad f_i(x_i^t) for all t >= 0.
Scope
#beer-fast-o-1-over-t-nonconvex-and-linear-pl-rate-scope
For L-smooth nonconvex objectives over a graph with spectral gap rho = 1 - sigma_max(W - (1/n) 1*1^T) > 0, Theorem 1 proves that BEER with gamma = Theta(alpha * rho) and eta = Theta(gamma * rho^2 * alpha / L) attains E||grad f(x_hat)||^2 <= epsilon^2 in T = O(L / (rho^3 * alpha^2 * epsilon^2)) communication rounds without data-heterogeneity assumptions, while Theorem 2 proves linear convergence O((1 / (mu * rho^3 * alpha^2)) log(1/epsilon)) under the Polyak-Lojasiewicz condition (Assumption 2) and minibatch size b = Theta(sigma^2 / (rho * alpha * epsilon^2)).
Limitation
#beer-cubic-spectral-gap-and-dual-message-transmission-limitation
Each iteration transmits two compressed vectors (Q_h^(t+1) and Q_g^(t+1)) per node and stores four d-dimensional state vectors per node (x_i^t, h_i^t, v_i^t, g_i^t), and the theoretical communication complexity scales inversely with the cube of the graph spectral gap rho^3 and the square of the contraction factor alpha^2.
Application
#beer-heterogeneous-nonconvex-logistic-regression-and-cnn-training-application
Applied to decentralized nonconvex logistic regression with nonconvex regularizer on the a9a dataset and 1-hidden-layer neural network training on unshuffled heterogeneous MNIST across 10-node ring topologies using biased Top-k and unbiased Rand-k / gsgn compressors.
⚠️ Curated Limitations & Negative Results
- Requires two compressed vector transmissions and four full-dimensional state vectors per node per iteration.
- Requires O(sigma^2 / (rho * alpha * epsilon^2)) minibatch size per iteration in the stochastic setting.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:FederatedLearning
Federated Learning
|
related_match | AIO:FederatedLearning covers distributed model optimization across networked data silos, whereas BEER is a decentralized peer-to-peer nonconvex optimization method combining gradient tracking with EF21 communication compression. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r557-primary-pdf
|
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtarik, Yuejie Chi
|
primary paper
full_text
|
ID: https://openalex.org/W7133239078
sha256:7f6492f9472e…
|
r557-arxiv-abs
|
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtarik, Yuejie Chi
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/2201.13320
sha256:c359aa3a6d7c…
|
r557-metadata-cr
|
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtarik, Yuejie Chi
|
primary paper
abstract_only
|
ID: https://openalex.org/W7133239078
sha256:8345aaf73caa…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T10:40:00Z
Updated: 2026-10-19T10:40:00Z
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories