Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network
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 dev...
Main Authors: | , |
---|---|
Format: | Article in Journal/Newspaper |
Language: | unknown |
Published: |
arXiv
2020
|
Subjects: | |
Online Access: | https://dx.doi.org/10.48550/arxiv.2011.07447 https://arxiv.org/abs/2011.07447 |
id |
ftdatacite:10.48550/arxiv.2011.07447 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.2011.07447 2023-05-15T16:01:45+02:00 Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network Zhang, Qinzi Tseng, Lewis 2020 https://dx.doi.org/10.48550/arxiv.2011.07447 https://arxiv.org/abs/2011.07447 unknown arXiv Creative Commons Attribution 4.0 International https://creativecommons.org/licenses/by/4.0/legalcode cc-by-4.0 CC-BY Distributed, Parallel, and Cluster Computing cs.DC Machine Learning cs.LG Networking and Internet Architecture cs.NI FOS Computer and information sciences Article CreativeWork article Preprint 2020 ftdatacite https://doi.org/10.48550/arxiv.2011.07447 2022-03-10T15:06:05Z 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. Article in Journal/Newspaper DML DataCite Metadata Store (German National Library of Science and Technology) |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Distributed, Parallel, and Cluster Computing cs.DC Machine Learning cs.LG Networking and Internet Architecture cs.NI FOS Computer and information sciences |
spellingShingle |
Distributed, Parallel, and Cluster Computing cs.DC Machine Learning cs.LG Networking and Internet Architecture cs.NI FOS Computer and information sciences Zhang, Qinzi Tseng, Lewis Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network |
topic_facet |
Distributed, Parallel, and Cluster Computing cs.DC Machine Learning cs.LG Networking and Internet Architecture cs.NI FOS Computer and information sciences |
description |
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. |
format |
Article in Journal/Newspaper |
author |
Zhang, Qinzi Tseng, Lewis |
author_facet |
Zhang, Qinzi Tseng, Lewis |
author_sort |
Zhang, Qinzi |
title |
Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network |
title_short |
Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network |
title_full |
Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network |
title_fullStr |
Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network |
title_full_unstemmed |
Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network |
title_sort |
echo-cgc: a communication-efficient byzantine-tolerant distributed machine learning algorithm in single-hop radio network |
publisher |
arXiv |
publishDate |
2020 |
url |
https://dx.doi.org/10.48550/arxiv.2011.07447 https://arxiv.org/abs/2011.07447 |
genre |
DML |
genre_facet |
DML |
op_rights |
Creative Commons Attribution 4.0 International https://creativecommons.org/licenses/by/4.0/legalcode cc-by-4.0 |
op_rightsnorm |
CC-BY |
op_doi |
https://doi.org/10.48550/arxiv.2011.07447 |
_version_ |
1766397491759022080 |