Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning

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

104 citations recorded by the source corpus.

We study robust distributed learning that involves minimizing a non-convex loss function with saddle points. We consider the Byzantine setting where some worker machines have abnormal or even arbitrary and adversarial behavior. In this setting, the Byzantine machines may create fake local minima near a saddle point that is far away from any true local minimum, even when robust gradient estimators are used. We develop ByzantinePGD, a robust first-order algorithm that can provably escape saddle points and fake local minima, and converge to an approximate true local minimizer with low iteration complexity. As a by-product, we give a simpler algorithm and analysis for escaping saddle points in the usual non-Byzantine setting. We further discuss three robust gradient estimators that can be used in ByzantinePGD, including median, trimmed mean, and iterative filtering. We characterize their performance in concrete statistical settings, and argue for their near-optimality in low and high dimensional regimes.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistics and Probability

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 Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

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].”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “from a probability distribution) and analyze gradient descent [12], [20], [22], [24], [28].”
Defending Distributed Systems Against Adversarial Attacks: Consensus, Consensusbased Learning, and Statistical Learning (2020, background): “Significant progress has been made [2, 24, 25, 19, 10, 8].”
RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets (2018, unknown): “Other related work in this context includes (Yin et al. 2018b) that targets escaping saddle points of nonconvex optimization problems under Byzantine attacks, and (Chen et al. 2018a) that leverages a gradient-coding based algorithm for robust learning.”
On the Sample Complexity of Adversarial Multi-Source PAC Learning (2020, background): “Another related general direction is the research on Byzantine-resilient distributed learning, which has seen signiﬁcant interest recently, e.g. (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; 2019; Alistarh et al., 2018).”
Robust Federated Learning in a Heterogeneous Environment (2019, methodology): “This is considered in a few recent works, and much progress has been made (see [4, 5, 6, 7, 8]).”
Distributed Gradient Descent Algorithm Robust to an Arbitrary Number of Byzantine Attackers (2019, methodology): “These algorithms in [20]–[28] can successfully converge to the neighborhood of the population minimizer even if up to half of all workers are compromised.”
Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data (2020, unknown): “On the other hand, [CSX17,BMGS17,YCRB18,AAL18,SX19,XKG19b,YCRB19] provide robustness, but with no local iterations or sampling of clients; furthermore, they assume homogeneous (either same or i.i.d.) data across all clients.”
Byzantine-Robust Learning on Heterogeneous Datasets via Resampling (2020, methodology): “For example, (Yin et al., 2018a) assumes the gradients have bounded variance and skewness whereas others like K RUM , R FA , B ULYAN does not.”
Federated Variance-Reduced Stochastic Gradient Descent With Robustness to Byzantine Attacks (2019, background): “Related works also include adversarial learning in distributed principal component analysis [17], escaping from saddle points in non-convex distributed learning under Byzantine attacks [18], and leveraging redundant gradients to improve robustness [19], [20].”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, methodology): “Therefore, our robust gradient descent results can still be applied to these settings; (2) It is possible to extend our results to non-convex settings by combining our robust gradient descent methods with proper saddle-points escaping schemes; such extension has been pursued recently in a follow-up ”