Byzantine Stochastic Gradient Descent

By Dan Alistarh, Zeyuan Allen-Zhu, Jerry Zheng Li. 2018

324 citations recorded by the source corpus.

This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of the $m$ machines which allegedly compute stochastic gradients every iteration, an $\alpha$-fraction are Byzantine, and can behave arbitrarily and adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds $\varepsilon$-approximate minimizers of convex functions in $T = \tilde{O}\big( \frac{1}{\varepsilon^2 m} + \frac{\alpha^2}{\varepsilon^2} \big)$ iterations. In contrast, traditional mini-batch SGD needs $T = O\big( \frac{1}{\varepsilon^2 m} \big)$ iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sampling complexity and time complexity.

Subfields: Artificial Intelligence, Statistics and Probability, Optimization & Training, Federated & Distributed Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Attack of the Tails: Yes, You Really Can Backdoor Federated Learning (2020, background): “Using robust estimation to defend against byzantine attacks has been studied extensively [66, 67, 68, 69, 70, 24, 71].”
Robust Aggregation for Federated Learning (2019, background): “Byzantine robustness, resilience to arbitrary behavior of some devices [51], was studied in distributed optimization with gradient aggregation [5, 16, 20, 21, 23, 88].”
DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, neutral): “We note that [18] presents an alternative approach that does not ﬁt easily under either category, but requires convexity of the underlying loss function.”
Zeno++: Robust Fully Asynchronous SGD (2019, background): “…tolerance to Byzantine failures (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Feng et al., 2014; Su & Vaidya, 2016; 2018; Xie et al., 2019b; Alistarh et al., 2018; Cao & Lai, 2018; Xie et al., 2019c) has become an important topic in the distributed machine learning literature.”
Distributed Learning over Unreliable Networks (2018, background): “Also, in Blanchard et al. (2017); Yin et al. (2018); Alistarh et al. (2018) They study the Byzantine-robust distributed learning when Byzantine worker included in the network.”
Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms (2019, background): “[2] developed a variant of SGD based on detecting Byzantine nodes.”
Zeno: Byzantine-suspicious stochastic gradient descent (2018, methodology): “Alistarh et al. [1] propose a Byzantine-resilient SGD variant different from the robust aggregation rules.”
Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation (2019, background): “Most of the existing Byzantine-tolerant machine-learning algorithms (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Feng et al., 2014; Su & Vaidya, 2016a;b; Alistarh et al., 2018) focus on the protection of distributed Stochastic Gradient Descent (SGD).”
Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer (2019, background): “Median and geometric-median based robust aggregation rules are also extensively explored [55], [51], [5].”
Manipulating the Byzantine: Optimizing Model Poisoning Attacks and Defenses for Federated Learning (2021, background): “All the robust AGRs for FL tend to remove/attenuate malicious gradients based on one or more of the following criteria: 1) distances from the benign gradients [8], [5], [31], [2], [39], 2) distributional differences with the benign gradients [5], [35], 3) difference in Lp-norms of the benign and mal”
Vertical Federated Learning: Concepts, Advances, and Challenges (2022, background): “Non-targeted backdoor attacks, similar to Byzantine attacks [143] that are typically studied in HFL, aim to hurt the convergence or the performance of the original task by using adversarial samples [141, 33], noisy samples or missing features[33].”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “• Challenges due to non-convexity: When F is convex, gradient descent (GD) equipped with a robust gradient estimator is guaranteed to find an approximate global minimizer (with accuracy depending on the fraction of Byzantine machines) (Chen et al., 2017; Yin et al., 2018a; Alistarh et al., 2018).”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, background): “Similar to ours, the concurrent work [AAZL18] considers the scenario where data is generated and stored in a distributed fashion at the workers.”
Learning from History for Byzantine Robust Optimization (2020, methodology): “Examples include Byzantine SGD (Alistarh et al., 2018) which only works for convex problems, and some heuristic scoring rules such as (Regatti & Gupta, 2020).”
Byzantine-Resilient Stochastic Gradient Descent for Distributed Learning: A Lipschitz-Inspired Coordinate-wise Median Approach (2019, background): “For example, the authors in [9] considered asynchronous SGD, while the authors in [10] used historical information to remove suspicious workers from future considerations.”
Robust Federated Learning in a Heterogeneous Environment (2019, background): “Byzantine-robustness: The robustness and security issues in distributed learning has received much attention ([25, 26]).”
Byzantine Fault-Tolerant Parallelized Stochastic Gradient Descent for Linear Regression (2019, background): “The problem of Byzantine faulty workers in parallelized SGD for machine learning has received considerable attention in recent years [1], [3], [6]–[10], [14], [16].”