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
- Martin Jaggi
- Qiang Yang
- Peter Richtárik
- Percy Liang
- Jakub Konecný
- Dacheng Tao
- Philip S. Yu
- Sebastian U. Stich
In Computer Networks and Communications
- Cong Xie
- Martin Jaggi
- Oluwasanmi Koyejo
- Indranil Gupta
- Suhas N. Diggavi
- Deepesh Data
- Aryan Mokhtari
- Sai Praneeth Karimireddy
In Safety, Robustness & Interpretability
- Neil Zhenqiang Gong
- Vitaly Shmatikov
- Nicholas Carlini
- Florian Tramèr
- Nicolas Papernot
- Prateek Mittal
- Dawn Song
- Bo Li
In Federated & Distributed Learning
- Martin Jaggi
- Cong Xie
- Sai Praneeth Karimireddy
- Qiang Yang
- Virginia Smith
- Jianyu Wang
- Chaoyang He
- Jakub Konecný
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, background): “ correct model updates, making them difficult to detect. The catastrophic potential of Byzantine attacks has spurred line of work on Byzantine-resilient aggregation mechanisms for distributed learning [68, 97, 294, 21, 426, 133]. Byzantine-resilient defenses One popular defense mechanism against unta”
- How To Backdoor Federated Learning (2018, background): “Alternative aggregationmechanisms [13, 20, 68, 71], such as coordinate-wise or geometric medians, greatly reduce the accuracy of complex models on non-i.”
- FedML: A Research Library and Benchmark for Federated Machine Learning (2020, background): “…challenge, existing research focuses on developing new adversarial attack and defense techniques to make federated learning robust [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 22], and proposing methods such as differential privacy (DP) and secure multiparty computation (SMPC) to…”
- Byzantine-Resilient Secure Federated Learning (2020, background): “Existing works can be roughly classified into two main categories: 1) geometric median [9], [10] and 2) coordinate-wise median [11]–[13].”
- 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].”
- Backdoor Attacks on Federated Meta-Learning (2020, methodology): “The same assumption was made in [12, 13, 19, 16, 17, 20, 21], where outliers were detected and removed according to slightly different measures taken from the distribution of benign values (benign users were assumed to be the majority).”
- Salvaging Federated Learning by Local Adaptation (2020, background): “To ensure that malicious participants and other outliers cannot influence the joint model, robust aggregation replaces average by median (Yin et al., 2018; Chen et al., 2019):”
- Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning (2020, background): “The setup when adversaries can modify their local datasets to influence the global model has been studied in the literature in the context of non-secure federated learning [44], [45].”
- Robust Aggregation for Federated Learning (2019, methodology): “Byzantine robustness, resilience to arbitrary behavior of some devices [51], was studied in distributed optimization with gradient aggregation [5, 16, 20, 21, 23, 88].”
- FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, background): “Robustness against adversarial devices is another challenge in federated learning and distributed learning that has been studied in [Chen et al., 2017, Ghosh et al., 2019, Yin et al., 2018].”
- DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, methodology): “We will analyze D ETOX when A 0 computes the mean of the vote groups, and A 1 is geometric median, coordinate-wise median, or ↵ -trimmed mean [6].”
- Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “Distributed computing with Byzantine adversaries is a richly investigated topic since [LSP82], and has received recent attention in the context of large-scale distributed optimization and learning [CSX17,CWCP18,YCRB18,BMGS17].”
- Zeno++: Robust Fully Asynchronous SGD (2019, background): “Furthermore, although most of the previous work (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Feng et al., 2014; Su & Vaidya, 2016; 2018; Alistarh et al., 2018; Cao & Lai, 2018) assumes a majority of honest workers, this requirement is not guaranteed to be satisfied in practice.”
- Practical Distributed Learning: Secure Machine Learning with Communication-Efficient Local Updates (2019, methodology): “Approaches based on robust statistics are often used to address security issues in the PS architecture (Yin et al., 2018; Xie et al., 2018).”
- A Little Is Enough: Circumventing Defenses For Distributed Learning (2019, methodology): “, (pn)j} where the largest and smallest m elements are removed, regardless of their distance from the median [29].”
- Analyzing Federated Learning through an Adversarial Lens (2018, methodology): “…=1 , implying that the adversarial objective is We note that in contrast to previous threat models considered for Byzantine-resilient learning, the adversary’s aim is not to prevent convergence of the global model (Yin et al., 2018) or to cause it to converge to a bad minimum (Mhamdi et al., 2018).”
- 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.”
- Byzantine Stochastic Gradient Descent (2018, methodology): “Once re-normalized to have variance proxy V2, the hard instance in [31] yields exactly the same lower bound as our Theorem 4.”
- Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Theoretically, although several recent works have investigated convergence guarantees of variants of federated learning methods [52], few analyses allow for low participation [25], [42] or study directly the effect of dropped devices [50].”