Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks

Abstract

Recent advances in large-scale distributed learning algorithms have enabled communication-efficient training via SignSGD. Unfortunately, a major issue continues to plague distributed learning: namely, Byzantine failures may incur serious degradation in learning accuracy. This paper proposes Election Coding, a coding-theoretic framework to guarantee Byzantine-robustness for SignSGD with Majority Vote, which uses minimum worker-master communication in both directions. The suggested framework explores new information-theoretic limits of finding the majority opinion when some workers could be malicious, and paves the road to implement robust and efficient distributed learning algorithms. Under this framework, we construct two types of explicit codes, random Bernoulli codes and deterministic algebraic codes, that can tolerate Byzantine attacks with a controlled amount of computational redundancy. For the Bernoulli codes, we provide upper bounds on the error probability in estimating the majority opinion, which give useful insights into code design for tolerating Byzantine attacks. As for deterministic codes, we construct an explicit code which perfectly tolerates Byzantines, and provide tight upper/lower bounds on the minimum required computational redundancy. Finally, the Byzantine-tolerance of the suggested coding schemes is confirmed by deep learning experiments on Amazon EC2 using Python with MPI4py package.

arXiv commentAccepted at NeurIPS 2020

References in corpus (16)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• Speeding Up Distributed Machine Learning Using Codes
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• The Hidden Vulnerability of Distributed Learning in Byzantium
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• ATOMO: Communication-efficient Learning via Atomic Sparsification
• Byzantine Stochastic Gradient Descent
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• Communication-Computation Efficient Gradient Coding
• signSGD with Majority Vote is Communication Efficient And Fault Tolerant
• Approximate Gradient Coding via Sparse Random Graphs

Cited by in corpus (5)

• Attack of the Tails: Yes, You Really Can Backdoor Federated Learning
• An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning
• Communication-Computation Efficient Secure Aggregation for Federated Learning
• What Do We Mean by Generalization in Federated Learning?
• Byzantine-resilient Decentralized Stochastic Gradient Descent