CoChat
Sign Up
PreprintCited by 40

The Hidden Vulnerability of Distributed Learning in Byzantium

Mhamdi, El Mahdi El, Guerraoui, Rachid, Rouault, Sébastien·2018·arXiv
DOI 10.48550/arxiv.1802.07927arXiv 1802.07927
Open this paper in CoChat — free account

Abstract

While machine learning is going through an era of celebrated success, concerns have been raised about the vulnerability of its backbone: stochastic gradient descent (SGD). Recent approaches have been proposed to ensure the robustness of distributed SGD against adversarial (Byzantine) workers sending poisoned gradients during the training phase. Some of these approaches have been proven Byzantine-resilient: they ensure the convergence of SGD despite the presence of a minority of adversarial workers. We show in this paper that convergence is not enough. In high dimension $d \gg 1$, an adver\-sary can build on the loss function's non-convexity to make SGD converge to ineffective models. More precisely, we bring to light that existing Byzantine-resilient schemes leave a margin of poisoning of $Ω\left(f(d)\right)$, where $f(d)$ increases at least like $\sqrt{d~}$. Based on this leeway, we build a simple attack, and experimentally show its strong to utmost effectivity on CIFAR-10 and MNIST. We introduce Bulyan, and prove it significantly reduces the attackers leeway to a narrow $O( \frac{1}{\sqrt{d~}})$ bound. We empirically show that Bulyan does not suffer the fragility of existing aggregation rules and, at a reasonable cost in terms of required batch size, achieves convergence as if only non-Byzantine gradients had been used to update the model.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1802.07927

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Robust aggregation methods for Byzantine fault tolerance have been developed in distributed optimization, including Krum, coordinate-wise median and trimmed mean, and Bulyan.

    “The connection between robust aggregation and Byzantine fault tolerance has been worked out in distributed optimization: Krum (Blanchard et al., 2017), coordinate-wise median and trimmed mean as gradient aggregators (Yin et al., 2018), and Bulyan (El Mhamdi et al., 2018).”

    From RoPoLL: Robust Panel of LLM Judges (2026) · cites this paper as El Mhamdi et al., 2018

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 30

  1. Abadi, Martín, Barham, Paul, Chen, Jianmin, Chen, Zhifeng, Davis, Andy, Dean, Jeffrey, Devin, Matthieu, Ghemawat, Sanjay, Irving, Geoffrey, Isard, Michael, et al. Tensorflow: A system for large-scale machine learning. In Proceedings of the 12th USENIX Sympo- sium on Operating Systems Design and Implementation (OSDI). Savannah, Georgia, USA, 2016.
  2. Biggio, Battista and Laskov, Pavel. Poisoning attacks against support vector machines. In In International Conference on Machine Learning (ICML. Citeseer, 2012.
  3. Biggio, Battista and Roli, Fabio. Wild patterns: Ten years after the rise of adversarial machine learning. arXiv preprint arXiv:1712.03141, 2017. · arXiv
  4. Blanchard, Peva, El Mhamdi, El Mahdi, Guerraoui, Rachid, and Stainer, Julien. Machine learning with ad- versaries: Byzantine tolerant gradient descent. In Ad- vances in Neural Information Processing Systems 30, pp. 118-128.
  5. Bojarski, Mariusz, Del Testa, Davide, Dworakowski, Daniel, Firner, Bernhard, Flepp, Beat, Goyal, Prasoon, Jackel, Lawrence D, Monfort, Mathew, Muller, Urs, Zhang, Jiakai, et al. End to end learning for self-driving cars. arXiv preprint arXiv:1604.07316, 2016. · arXiv
  6. Bottou, Léon. Online learning and stochastic approxima- tions. Online learning in neural networks, 17(9):142, 1998.
  7. Bottou, Léon. Stochastic Gradient Descent Tricks, pp. 421-436. Springer Berlin Heidelberg, Berlin, Heidel- berg, 2012. ISBN 978-3-642-35289-8. doi: 10.1007/ 978-3-642-35289-8 25. URL https://doi.org/ 10.1007/978-3-642-35289-8_25. · DOI
  8. Chen, Yudong, Su, Lili, and Xu, Jiaming. Distributed sta- tistical machine learning in adversarial settings: Byzan- tine gradient descent. arXiv preprint arXiv:1705.05491, 2017. · arXiv
  9. Choromanska, Anna, Henaff, Mikael, Mathieu, Michael, Ben Arous, Gérard, and LeCun, Yann. The loss sur- faces of multilayer networks. In Artificial Intelligence and Statistics, pp. 192-204, 2015a.
  10. Choromanska, Anna, LeCun, Yann, and Ben Arous, Gérard. Open problem: The landscape of the loss sur- faces of multilayer networks. In Conference on Learning Theory, pp. 1756-1760, 2015b.
  11. Cisse, Moustapha, Bojanowski, Piotr, Grave, Edouard, Dauphin, Yann, and Usunier, Nicolas. Parseval net- works: Improving robustness to adversarial examples. In International Conference on Machine Learning, pp. 854-863, 2017.
  12. Cohen, Michael B, Lee, Yin Tat, Miller, Gary, Pachocki, Jakub, and Sidford, Aaron. Geometric median in nearly linear time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 9-21. ACM, 2016.
  13. Dean, Jeffrey, Corrado, Greg, Monga, Rajat, Chen, Kai, Devin, Matthieu, Mao, Mark, Senior, Andrew, Tucker, Paul, Yang, Ke, Le, Quoc V, et al. Large scale distributed deep networks. In Advances in neural information pro- cessing systems, pp. 1223-1231, 2012.
  14. El Mhamdi, El Mahdi and Guerraoui, Rachid. When neurons fail. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1028- 1037, May 2017. doi: 10.1109/IPDPS.2017. · DOI
  15. El Mhamdi, El Mahdi, Guerraoui, Rachid, and Rouault, Sébastien. On the robustness of a neural network. In 2017 IEEE 36th Symposium on Reliable Distributed Sys- tems (SRDS), pp. 84-93, Sept 2017. doi: 10.1109/SRDS. 2017. · DOI
  16. El Mhamdi, El Mahdi and Guerraoui, Rachid. When neu- rons fail -technical report. pp. 19, 2016. Biological Distributed Algorithms Workshop, Chicago.
  17. Gilmer, Justin, Metz, Luke, Faghri, Fartash, Schoenholz, Samuel S, Raghu, Maithra, Wattenberg, Martin, and Goodfellow, Ian. Adversarial spheres. arXiv preprint arXiv:1801.02774, 2018. · arXiv
  18. Holzinger, Andreas. Interactive machine learning for health informatics: when do we need the human-in-the- loop? Brain Informatics, 3(2):119-131, 2016.
  19. Kerlirzin, P and Vallet, F. Robustness in multilayer percep- trons. Neural computation, 5(3):473-482, 1993.
  20. Kerlirzin, Philippe. Etude de la robustesse des réseaux mul- ticouches. PhD thesis, Paris 11, 1994.
  21. Koh, Pang Wei and Liang, Percy. Understanding black- box predictions via influence functions. In International Conference on Machine Learning, pp. 1689-1698, 2017.
  22. Kumar, Atul, Mehta, Sameep, and Vijaykeerthy, Deepak. An introduction to adversarial machine learning. In In- ternational Conference on Big Data Analytics, pp. 293- 299. Springer, 2017.
  23. Lamport, Leslie, Shostak, Robert, and Pease, Marshall. The byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3): 382-401, 1982.
  24. Li, Mu, Andersen, David G, Park, Jun Woo, Smola, Alexander J, Ahmed, Amr, Josifovski, Vanja, Long, James, Shekita, Eugene J, and Su, Bor-Yiing. Scaling distributed machine learning with the parameter server. In OSDI, volume 1, pp. 3, 2014a.
  25. Li, Mu, Andersen, David G, Smola, Alexander J, and Yu, Kai. Communication efficient distributed machine learn- ing with the parameter server. In Advances in Neural Information Processing Systems, pp. 19-27, 2014b.
  26. Piuri, Vincenzo. Analysis of fault tolerance in artificial neural networks. Journal of Parallel and Distributed Computing, 61(1):18-48, 2001.
  27. Reddi, Sashank J, Zaheer, Manzil, Sra, Suvrit, Poczos, Barnabas, Bach, Francis, Salakhutdinov, Ruslan, and Smola, Alexander J. A generic approach for escaping saddle points. arXiv preprint arXiv:1709.01434, 2017. · arXiv
  28. Srivastava, Nitish, Hinton, Geoffrey, Krizhevsky, Alex, Sutskever, Ilya, and Salakhutdinov, Ruslan. Dropout: A simple way to prevent neural networks from overfit- ting. The Journal of Machine Learning Research, 15(1): 1929-1958, 2014.
  29. Su, Lili. Defending distributed systems against adversar- ial attacks: consensus, consensus-based learning, and statistical learning. PhD thesis, University of Illinois at Urbana-Champaign, 2017.
  30. Zhang, Sixin, Choromanska, Anna E, and LeCun, Yann. Deep learning with elastic averaging sgd. In Advances in Neural Information Processing Systems, pp. 685-693, 2015.

Cited by

Sorted by citations

Authors
Mhamdi, E. M. E., Guerraoui, R., & Rouault, S.
Venue
arXiv
Publisher
arXiv
Published
2018
DOI
10.48550/arxiv.1802.07927
arXiv
1802.07927
References
2
Type
Preprint
Licence
creativecommons.org/licenses/by-nc-sa/4.0/legalcode

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review