Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network

Qinzi Zhang, Lewis Tseng

Abstract

In this paper, we focus on a popular DML framework -- the parameter server computation paradigm and iterative learning algorithms that proceed in rounds. We aim to reduce the communication complexity of Byzantine-tolerant DML algorithms in the single-hop radio network. Inspired by the CGC filter developed by Gupta and Vaidya, PODC 2020, we propose a gradient descent-based algorithm, Echo-CGC. Our main novelty is a mechanism to utilize the broadcast properties of the radio network to avoid transmitting the raw gradients (full $d$-dimensional vectors). In the radio network, each worker is able to overhear previous gradients that were transmitted to the parameter server. Roughly speaking, in Echo-CGC, if a worker "agrees" with a combination of prior gradients, it will broadcast the "echo message" instead of the its raw local gradient. The echo message contains a vector of coefficients (of size at most $n$) and the ratio of the magnitude between two gradients (a float). In comparison, the traditional approaches need to send $n$ local gradients in each round, where each gradient is typically a vector in an ultra-high dimensional space ($d\gg n$). The improvement on communication complexity of our algorithm depends on multiple factors, including number of nodes, number of faulty workers in an execution, and the cost function. We numerically analyze the improvement, and show that with a large number of nodes, Echo-CGC reduces $80\%$ of the communication under standard assumptions.

Introduction

Distributed Machine Learning (DML) has become the backbone of modern AI, enabling the training of massive models across clusters of worker nodes. However, two significant challenges persist in wireless and edge computing environments: the high communication cost of transmitting high-dimensional gradient vectors and the vulnerability to Byzantine (malicious or faulty) nodes that can disrupt the learning process.

Traditional Byzantine-tolerant algorithms often require workers to transmit full $d$-dimensional gradients in every round. In scenarios where $d$ (the number of parameters) is in the millions, this creates a massive bottleneck. Echo-CGC addresses this by leveraging the physical properties of single-hop radio networks, where transmissions are inherently broadcasted and can be overheard by all nodes in the vicinity.

The Echo-CGC Algorithm

Echo-CGC builds upon the Comparative Gradient Clipping (CGC) filter to provide robustness against Byzantine actors. The primary innovation is the "Echo" mechanism, which exploits the $d \gg n$ property of modern machine learning models.

Overhearing and Gradient Approximation

In a single-hop radio network, workers operate under a Time Division Multiple Access (TDMA) schedule. As workers transmit their gradients to the parameter server one by one, other workers overhear these transmissions. Each worker $j$ maintains a set of overheard gradients from the current round.

Instead of transmitting its own raw gradient $g_j^t$, worker $j$ attempts to project $g_j^t$ onto the span of the gradients it has already overheard. If the projection is sufficiently accurate—controlled by a deviation ratio $r$—the worker sends an "echo message" instead of the full vector.

Communication Efficiency

An echo message consists of a vector of coefficients (size $O(n)$) and a magnitude ratio. Since $n$ (the number of workers) is typically much smaller than $d$ (the dimensionality of the model), this representation is significantly more compact. The parameter server then "reconstructs" the gradient using the overheard history and the coefficients provided in the echo.

Mathematical Framework and Notation

The following table defines the key parameters and variables used in the Echo-CGC algorithm and its convergence analysis.

Table of notations used in the Echo-CGC algorithm.

Performance and Convergence

The authors provide a rigorous proof that Echo-CGC converges to the optimal solution $w^*$ even in the presence of $b$ Byzantine workers, provided the number of fault-free workers $h$ is sufficiently large.

Numerical simulations based on standard statistical assumptions (e.g., $L$-Lipschitz smoothness and bounded variance) demonstrate that Echo-CGC can achieve up to an 80% reduction in total communication bits compared to standard Byzantine-tolerant gradient descent. The efficiency of the algorithm is most pronounced when the data distribution across nodes is relatively homogeneous, allowing for more frequent successful "echoes."

Conclusion and Future Work

Echo-CGC represents a significant step forward in making Byzantine-tolerant DML practical for resource-constrained wireless networks. By turning overhearing—often viewed as a drawback—into a compression tool, it drastically reduces the energy footprint of distributed training. Future research will focus on extending these principles to multi-hop networks and exploring alternative similarity metrics, such as cosine similarity, to further refine the echo mechanism.

Summary updated

Abstract

In this paper, we focus on a popular DML framework -- the parameter server computation paradigm and iterative learning algorithms that proceed in rounds. We aim to reduce the communication complexity of Byzantine-tolerant DML algorithms in the single-hop radio network. Inspired by the CGC filter developed by Gupta and Vaidya, PODC 2020, we propose a gradient descent-based algorithm, Echo-CGC. Our main novelty is a mechanism to utilize the broadcast properties of the radio network to avoid transmitting the raw gradients (full $d$-dimensional vectors). In the radio network, each worker is able to overhear previous gradients that were transmitted to the parameter server. Roughly speaking, in Echo-CGC, if a worker "agrees" with a combination of prior gradients, it will broadcast the "echo message" instead of the its raw local gradient. The echo message contains a vector of coefficients (of size at most $n$) and the ratio of the magnitude between two gradients (a float). In comparison, the traditional approaches need to send $n$ local gradients in each round, where each gradient is typically a vector in an ultra-high dimensional space ($d\gg n$). The improvement on communication complexity of our algorithm depends on multiple factors, including number of nodes, number of faulty workers in an execution, and the cost function. We numerically analyze the improvement, and show that with a large number of nodes, Echo-CGC reduces $80\%$ of the communication under standard assumptions.
BibTeX
@inproceedings{zhang2020echo,
  author = {Qinzi Zhang and Lewis Tseng},
  title = {{Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network}},
  booktitle = {OPODIS},
  year = {2020},
  url = {https://openreview.net/forum?id=JP3m56f1Wei},
}
Figure