Byzantine-Tolerant Machine Learning

By Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, Julien Stainer. 2017

88 citations recorded by the source corpus.

The growth of data, the need for scalability and the complexity of models used in modern machine learning calls for distributed implementations. Yet, as of today, distributed machine learning frameworks have largely ignored the possibility of arbitrary (i.e., Byzantine) failures. In this paper, we study the robustness to Byzantine failures at the fundamental level of stochastic gradient descent (SGD), the heart of most machine learning algorithms. Assuming a set of $n$ workers, up to $f$ of them being Byzantine, we ask how robust can SGD be, without limiting the dimension, nor the size of the parameter space. We first show that no gradient descent update rule based on a linear combination of the vectors proposed by the workers (i.e, current approaches) tolerates a single Byzantine failure. We then formulate a resilience property of the update rule capturing the basic requirements to guarantee convergence despite $f$ Byzantine workers. We finally propose Krum, an update rule that satisfies the resilience property aforementioned. For a $d$-dimensional learning problem, the time complexity of Krum is $O(n^2 \cdot (d + \log n))$.

Subfields: Artificial Intelligence, Safety, Robustness & Interpretability

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 Safety, Robustness & Interpretability

Citations in the corpus

Byzantine-Resilient Secure Federated Learning (2020, methodology): “Hence, from Proposition 2 of [38], ∇C(w) converges almost surely to zero,”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “Most relevant is the work by Blanchard et al. (2017), who pro-pose to aggregate the gradients from worker machines using a robust procedure.”
Distributed Statistical Machine Learning in Adversarial Settings (2017, background): “In [5], the focus is to estimate the minimizer of the average cost over a given deterministic dataset; almost sure convergence is proved without an explicit characterization of convergence speed nor the statistical estimation errors.”
The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory (2018, background): “References [4, 30, 7] consider distributed SGD in a Byzantine adversarial setting, but in a message-passing system.”
On the Robustness of a Neural Network (2017, methodology): “This coarse-grained approach is the one taken by recent works on the robustness of machine learning [20], [21], [22].”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, background): “In particular, [BMGS17] assumes all the workers can access the whole data sample.”
Distributed Gradient Descent Algorithm Robust to an Arbitrary Number of Byzantine Attackers (2019, methodology): “Furthermore, if there are 30 Byzantine workers, Krum and median-mean algorithm cannot properly work.”
Robust Federated Learning in a Heterogeneous Environment (2019, background): “This is considered in a few recent works, and much progress has been made (see [4, 5, 6, 7, 8]).”
Defending Distributed Systems Against Adversarial Attacks: Consensus, Consensusbased Learning, and Statistical Learning (2020, background): “This difference is fundamental as can be seen from the analysis difference in [4] and [5].”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “This Byzantine-robust distributed learning problem has attracted attention in a recent line of work [3, 10, 17, 26, 61, 62, 69].”
Robust Distributed Gradient Descent with Arbitrary Number of Byzantine Attackers (2018, methodology): “In this case with Byzantine attackers, if one continues to use the classic batch gradient as in (5), the algorithm will fail to converge even if there is only one attacker [6, 7].”