Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent

By Yudong Chen, Lili Su, Jiaming Xu. 2017

599 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 łe m for an arbitrarily small but fixed constant ε>0. The parameter estimate converges in O(łog 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 log 3 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, Optimization & Training, 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

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

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 limit the inﬂu-ence of individual participants, several robust, “Byzantine-tolerant” aggregation schemes have been proposed (Blan-chard et al., 2017; El Mhamdi et al., 2018; Damaskinos et al., 2019; Rajput et al., 2019; Chen et al., 2017).”
DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, methodology): “Byzantine-tolerant ML has been extensively studied in recent years [13, 14, 15, 16, 17, 2], establishing that while average-based gradient methods are susceptible to adversarial nodes, median-based update methods can in some cases achieve better convergence, while being robust to some attacks.”
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 satisﬁed in practice.”
A Little Is Enough: Circumventing Defenses For Distributed Learning (2019, background): “In the very heart of distributed learning lies the assumption that the parameters of the trained network across the workers are independent and identically distributed (i.i.d.) (Chen et al., 2017b; Blanchard et al., 2017; Yin et al., 2018).”
Analyzing Federated Learning through an Adversarial Lens (2018, background): “…also has a connection to a line of work on defending against Byzantine adversaries which consider a threat model where the malicious agents can send arbitrary gradient updates (Blanchard et al., 2017; Chen et al., 2017b; Mhamdi et al., 2018; Chen et al., 2018; Yin et al., 2018) to the server.”
Byzantine Stochastic Gradient Descent (2018, background): “Despite signiﬁcant recent interest, e.g. [8, 11, 15, 33, 34, 38, 39], to the best of our knowledge, prior to our work there were no algorithms for stochastic optimization in high dimensions that achieved any of the four objectives highlighted above.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “The work of Chen et al. (2017) considers only strongly convex losses, and seeks to circumvent the above issue by grouping the worker machines into mini-batches; however, their rate (cid:101) O ( √ still falls short of being optimal, and in particular their algorithm fails even when there is only…”
The Hidden Vulnerability of Distributed Learning in Byzantium (2018, background): “, 2017) and theoretically (Chen et al., 2017), variants of the Median were considered as GAR candidates.”
Zeno: Byzantine-suspicious stochastic gradient descent (2018, methodology): “For example, Chen et al. [4], Su and Vaidya [17, 18] use geometric median as the aggregation rule.”
Generalized Byzantine-tolerant SGD (2018, methodology): “The failure resilience of distributed machine-learning systems has attracted increasing attention (Blanchard et al., 2017; Chen et al., 2017) in the community.”
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).”
Byzantine-Robust Federated Machine Learning through Adaptive Model Averaging (2019, methodology): “…statistics (e.g. median estimators) for updating the aggregated model (Blanchard et al. 2017; Mhamdi, Guerraoui, and Rouault 2018; Yin et al. 2018; Chen, Su, and Xu 2017), which can be computational expensive for large models and number of clients compared to standard aggregation rules such as…”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, background): “Apart from preserving privacy for individual users, edge AI also needs to be robust to errors and adversarial attackers, as the decentralized nature makes it easy to be unreliable in the learning process or even completely controlled by external attackers [74].”
Robust Federated Learning in a Heterogeneous Environment (2019, background): “[6] Yudong Chen, Lili Su, and Jiaming Xu.”