Distributed Statistical Machine Learning in Adversarial Settings

By Yudong Chen, Lili Su, Jiaming Xu. 2017

293 citations recorded by the source corpus.

We consider the distributed statistical learning problem over decentralized systems that are prone to adversarial attacks. This setup arises in many practical applications, including Google's Federated Learning. Formally, we focus on a decentralized system that consists of a parameter server and m working machines; each working machine keeps N/m data samples, where N is the total number of samples. In each iteration, up to q of the m working machines suffer Byzantine faults -- a faulty machine in the given iteration behaves arbitrarily badly against the system and has complete knowledge of the system. Additionally, the sets of faulty machines may be different across iterations. Our goal is to design robust algorithms such that the system can learn the underlying true parameter, which is of dimension d, despite the interruption of the Byzantine attacks. In this paper, based on the geometric median of means of the gradients, we propose a simple variant of the classical gradient descent method. We show that our method can tolerate q Byzantine failures up to 2(1+ε)q ≤ for an arbitrarily small but fixed constant ε > 0. The parameter estimate converges in O(log N) rounds with an estimation error on the order of max{√dq/N, √d/N, which is larger than the minimax-optimal error rate √d/N in the centralized and failure-free setting by at most a factor of √q. The total computational complexity of our algorithm is of O((Nd/m) log N) at each working machine and O(md + kd log3 N) at the central server, and the total communication cost is of O(m d log N). We further provide an application of our general results to the linear regression problem. A key challenge arises in the above problem is that Byzantine failures create arbitrary and unspecified dependency among the iterations and the aggregated gradients. To handle this issue in the analysis, we prove that the aggregated gradient, as a function of model parameter, converges uniformly to the true gradient function.

Subfields: Artificial Intelligence, ML Systems & Hardware, Privacy & Security

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 ML Systems & Hardware

In Privacy & Security

Citations in the corpus

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.”
Local Model Poisoning Attacks to Byzantine-Robust Federated Learning (2019, background): “, Krum [9], Bulyan [42], trimmed mean [66], median [66], and others [14]) that were claimed to be robust against Byzantine failures of certain worker devices.”
Attack of the Tails: Yes, You Really Can Backdoor Federated Learning (2020, methodology): “[65] propose using geometric median to tolerate byzantine attacks in gradient descent.”
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].”
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].”
Zeno++: Robust Fully Asynchronous SGD (2019, background): “In particular, 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…”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, methodology): “A recent line of work (Blanchard et al., 2017; Chen et al., 2017) studies this problem under a synchronous training setup, where compute nodes evaluate gradient updates and ship them to a parameter server (PS) which stores and updates the global model.”
Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent (2017, methodology): “∗The full version of this paper is available as [1] †This is the corresponding author”
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).”
Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance (2018, methodology): “For instance, a common assumption is that no more than 50% of the workers are faulty (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Su & Vaidya, 2016a; Alistarh et al., 2018).”
FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping (2020, background): “Byzantine-robust FL methods [9], [12], [29], [46], [48] aim to address malicious clients.”
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].”
Byzantine-Tolerant Distributed Coordinate Descent (2019, background): “Distributed computing with Byzantine adversaries has a rich history since the work of [5], and has received recent attention in the context of large-scale distributed optimization and learning [3], [4], [6].”