Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent

Abstract

We consider the problem of distributed statistical machine learning in adversarial settings, where some unknown and time-varying subset of working machines may be compromised and behave arbitrarily to prevent an accurate model from being learned. This setting captures the potential adversarial attacks faced by Federated Learning -- a modern machine learning paradigm that is proposed by Google researchers and has been intensively studied for ensuring user privacy. Formally, we focus on a distributed system consisting of a parameter server and $m$ working machines. Each working machine keeps $N/m$ data samples, where $N$ is the total number of samples. The goal is to collectively learn the underlying true model parameter of dimension $d$. In classical batch gradient descent methods, the gradients reported to the server by the working machines are aggregated via simple averaging, which is vulnerable to a single Byzantine failure. In this paper, we propose a Byzantine gradient descent method based on the geometric median of means of the gradients. We show that our method can tolerate $q\le (m-1)/2$ Byzantine failures, and the parameter estimate converges in $O(\log N)$ rounds with an estimation error of $\sqrt{d(2q+1)/N}$, hence approaching the optimal error rate $\sqrt{d/N}$ in the centralized and failure-free setting. The total computational complexity of our algorithm is of $O((Nd/m)\log N)$ at each working machine and $O(md+kd{\log }^{3}N)$ at the central server, and the total communication cost is of $O(md\log N)$. We further provide an application of our general results to the linear regression problem. A key challenge arises in the above problem is that Byzantine failures create arbitrary and unspecified dependency among the iterations and the aggregated gradients. We prove that the aggregated gradient converges uniformly to the true gradient function.

References in corpus (6)

• Revisiting Distributed Synchronous SGD
• Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm
• The Landscape of Empirical Risk for Non-convex Losses
• Distributed Robust Learning
• Communication-Efficient Distributed Statistical Inference
• Byzantine-Tolerant Machine Learning

Cited by in corpus (28)

• How To Backdoor Federated Learning
• The Hidden Vulnerability of Distributed Learning in Byzantium
• Federated Learning: A Signal Processing Perspective
• Generalized Byzantine-tolerant SGD
• Byzantine Stochastic Gradient Descent
• A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee
• Edge Intelligence: Architectures, Challenges, and Applications
• An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning
• Dynamic Defense Against Byzantine Poisoning Attacks in Federated Learning
• A Survey on Vulnerability of Federated Learning: A Learning Algorithm Perspective
• Phocas: dimensional Byzantine-resilient stochastic gradient descent
• Auto-weighted Robust Federated Learning with Corrupted Data Sources
• Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks
• Practical Differentially Private and Byzantine-resilient Federated Learning
• Training Fair Models in Federated Learning without Data Privacy Infringement
• Robust Distributed Optimization With Randomly Corrupted Gradients
• Byzantines can also Learn from History: Fall of Centered Clipping in Federated Learning
• Shielding Collaborative Learning: Mitigating Poisoning Attacks through Client-Side Detection
• Distributed Momentum for Byzantine-resilient Learning
• Finite-time Guarantees for Byzantine-Resilient Distributed State Estimation with Noisy Measurements
• Auxo: Efficient Federated Learning via Scalable Client Clustering
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers
• Efficient learning with robust gradient descent
• Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding
• Robust learning with anytime-guaranteed feedback
• Communication-efficient Byzantine-robust distributed learning with statistical guarantee
• Bristle: Decentralized Federated Learning in Byzantine, Non-i.i.d. Environments