Asynchronous Byzantine Machine Learning

By Georgios Damaskinos, El Mahdi El Mhamdi, Rachid Guerraoui, Rhicheek Patra, Mahsa Taziki. 2018

41 citations recorded by the source corpus.

Asynchronous distributed machine learning solutions have proven very effective so far, but always assuming perfectly functioning workers. In practice, some of the workers can however exhibit Byzantine behavior, caused by hardware failures, software bugs, corrupt data, or even malicious attacks. We introduce \emph{Kardam}, the first distributed asynchronous stochastic gradient descent (SGD) algorithm that copes with Byzantine workers. Kardam consists of two complementary components: a filtering and a dampening component. The first is scalar-based and ensures resilience against $\frac{1}{3}$ Byzantine workers. Essentially, this filter leverages the Lipschitzness of cost functions and acts as a self-stabilizer against Byzantine workers that would attempt to corrupt the progress of SGD. The dampening component bounds the convergence rate by adjusting to stale information through a generic gradient weighting scheme. We prove that Kardam guarantees almost sure convergence in the presence of asynchrony and Byzantine behavior, and we derive its convergence rate. We evaluate Kardam on the CIFAR-100 and EMNIST datasets and measure its overhead with respect to non Byzantine-resilient solutions. We empirically show that Kardam does not introduce additional noise to the learning procedure but does induce a slowdown (the cost of Byzantine resilience) that we both theoretically and empirically show to be less than $f/n$, where $f$ is the number of Byzantine failures tolerated and $n$ the total number of workers. Interestingly, we also empirically observe that the dampening component is interesting in its own right for it enables to build an SGD algorithm that outperforms alternative staleness-aware asynchronous competitors in environments with honest workers.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Can You Really Backdoor Federated Learning? (2019, background): “Under untargeted attacks (6; 15; 12), the goal of the adversary is to corrupt the model in such a way that it does not achieve a near-optimal performance on the main task at hand (e.”
Zeno++: Robust Fully Asynchronous SGD (2019, methodology): “We test the Byzantine-tolerance to the “sign-flipping” attack, which was proposed in (Damaskinos et al., 2018).”
Fast and Secure Distributed Learning in High Dimension (2019, methodology): “Even-though the property of (α, f)–Byzantine resilience is a sufficient, but not a necessary condition for (weak) Byzantine resilience, it has been so far used as the defacto standard [1, 4, 11] to guarantee (weak) Byzantine resilience for SGD.”
Distributed Gradient Descent Algorithm Robust to an Arbitrary Number of Byzantine Attackers (2019, background): “[26] consider an asynchronous distributed training scenario and propose algorithm Kardam that leverages the Lipschitzness of the cost function to filter out gradient information from attackers.”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “Byzantine-robust distributed learning Solving large scale learning problems in distributed systems has received much attention in recent years, where communication efficiency and Byzantine robustness are two important topics (Shamir et al., 2014; Lee et al., 2015; Yin et al., 2018b; Blanchard et al.”
Byzantine-Resilient Stochastic Gradient Descent for Distributed Learning: A Lipschitz-Inspired Coordinate-wise Median Approach (2019, background): “, [12]) as well as several recent Byzantine tolerant gradient descent algorithms [2] [9].”