Distributed Robust Learning

By Jiashi Feng, Huan Xu, Shie Mannor. 2014

56 citations recorded by the source corpus.

We propose a framework for distributed robust statistical learning on {\em big contaminated data}. The Distributed Robust Learning (DRL) framework can reduce the computational time of traditional robust learning methods by several orders of magnitude. We analyze the robustness property of DRL, showing that DRL not only preserves the robustness of the base robust learning method, but also tolerates contaminations on a constant fraction of results from computing nodes (node failures). More precisely, even in presence of the most adversarial outlier distribution over computing nodes, DRL still achieves a breakdown point of at least $ \lambda^*/2 $, where $ \lambda^* $ is the break down point of corresponding centralized algorithm. This is in stark contrast with naive division-and-averaging implementation, which may reduce the breakdown point by a factor of $ k $ when $ k $ computing nodes are used. We then specialize the DRL framework for two concrete cases: distributed robust principal component analysis and distributed robust regression. We demonstrate the efficiency and the robustness advantages of DRL through comprehensive simulations and predicting image tags on a large-scale image set.

Subfields: Artificial Intelligence, Computational Mechanics, 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

In Computational Mechanics

In Safety, Robustness & Interpretability

In Federated & Distributed Learning

Citations in the corpus

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…”
Byzantine Stochastic Gradient Descent (2018, methodology): “There has been a lot of recent work on Byzantine stochastic optimization, and in particular, SGD [6, 8, 13, 26, 27, 30].”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “While this objective is considered in a few recent works (Feng et al., 2014; Blanchard et al., 2017; Chen et al., 2017), a fundamental problem remains poorly understood, namely the optimal statistical performance of a robust learning algorithm.”
Distributed Statistical Machine Learning in Adversarial Settings (2017, methodology): “Byzantine Failures Convergence speed Local data size Estimation error One-shot 0 No iteration N/m≫ d √ d/N SGD 0 1/t No constraint ? BGD 0 exp(−t) No constraint √ d/N Robust one-shot [12] 2q + 1 ≤ m No iteration N/m≫ d √ dm/N”
Zeno: Byzantine-suspicious stochastic gradient descent (2018, background): “For this reason, fault tolerance in distributed settings has attracted increasing attention in the machine-learning community [1, 2, 4, 6, 17, 18, 19, 20].”
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).”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, unknown): “This procedure is straightforward to implement and is communication-efficient [6, 12].”
Learning from History for Byzantine Robust Optimization (2020, background): “Given the importance of this problem, it has received significant attention from the community with early works including (Feng et al., 2014; Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018).”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “For convex losses, the aggregation subroutines analyzed in the literature include geometric median (Feng et al., 2014; Chen et al., 2017), median and trimmed mean (Yin et al.”
Robust Federated Learning in a Heterogeneous Environment (2019, background): “This is considered in a few recent works, and much progress has been made (see [4, 5, 6, 7, 8]).”
On the Sample Complexity of Adversarial Multi-Source PAC Learning (2020, methodology): “Feng et al. (2014) provide a method for distributing the computation of any robust learning algorithm that operates on a single large dataset.”
Robust Learning from Untrusted Sources (2019, methodology): “Following (Feng et al., 2014), one baseline learns a separate linear model based on each of the source datasets.”
Zeno++: robust asynchronous SGD with arbitrary number of Byzantine workers (2019, background): “For this reason, fault tolerance in distributed settings has attracted increasing attention in the machine-learning community [1, 2, 3, 5, 13, 14, 15, 16].”
Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance (2018, background): “While fault-tolerance has been studied for distributed machine learning (Blanchard et al., 2017; Chen et al., 2017; Yin et al., 2018; Feng et al., 2014; Su & Vaidya, 2016a;b; Alistarh et al., 2018), much of the work on faulttolerant machine learning makes strong assumptions.”
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 Machine Learning in High Dimensions (2018, methodology): “Among the proposed algorithms, the robust one-shot aggregation algorithm [FXM14] uses only one round communication and hence is communication-efficient.”