Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates

By Dong Yin, Yudong Chen, Kannan Ramchandran, Peter L. Bartlett. 2018

2,286 citations recorded by the source corpus.

In large-scale distributed learning, security issues have become increasingly important. Particularly in a decentralized environment, some computing units may behave abnormally, or even exhibit Byzantine failures---arbitrary and potentially adversarial behavior. In this paper, we develop distributed learning algorithms that are provably robust against such failures, with a focus on achieving optimal statistical performance. A main result of this work is a sharp analysis of two robust distributed gradient descent algorithms based on median and trimmed mean operations, respectively. We prove statistical error rates for three kinds of population loss functions: strongly convex, non-strongly convex, and smooth non-convex. In particular, these algorithms are shown to achieve order-optimal statistical error rates for strongly convex losses. To achieve better communication efficiency, we further propose a median-based distributed algorithm that is provably robust, and uses only one communication round. For strongly convex quadratic loss, we show that this algorithm achieves the same optimal error rate as the robust distributed gradient descent algorithms.

Subfields: Artificial Intelligence, Computer Networks and Communications, Safety, Robustness & Interpretability, 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

  1. Martin Jaggi
  2. Qiang Yang
  3. Peter Richtárik
  4. Percy Liang
  5. Jakub Konecný
  6. Dacheng Tao
  7. Philip S. Yu
  8. Sebastian U. Stich

In Computer Networks and Communications

  1. Cong Xie
  2. Martin Jaggi
  3. Oluwasanmi Koyejo
  4. Indranil Gupta
  5. Suhas N. Diggavi
  6. Deepesh Data
  7. Aryan Mokhtari
  8. Sai Praneeth Karimireddy

In Safety, Robustness & Interpretability

  1. Neil Zhenqiang Gong
  2. Vitaly Shmatikov
  3. Nicholas Carlini
  4. Florian Tramèr
  5. Nicolas Papernot
  6. Prateek Mittal
  7. Dawn Song
  8. Bo Li

In Federated & Distributed Learning

  1. Martin Jaggi
  2. Cong Xie
  3. Sai Praneeth Karimireddy
  4. Qiang Yang
  5. Virginia Smith
  6. Jianyu Wang
  7. Chaoyang He
  8. Jakub Konecný

Citations in the corpus