Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data

By Deepesh Data, Suhas N. Diggavi. 2020

49 citations recorded by the source corpus.

We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our heterogeneous data setting where workers compute stochastic gradients, we derive a new matrix concentration result, which may be of independent interest. We provide convergence analyses for smooth strongly-convex and non-convex objectives and show that our convergence rates match that of vanilla SGD in the Byzantine-free setting. In order to bound the heterogeneity, we assume that the gradients at different workers have bounded deviation from each other, and we also provide concrete bounds on this deviation in the statistical heterogeneous data model.

Subfields: Artificial Intelligence, 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 Statistics and Probability

Citations in the corpus

Byzantine-Robust Learning on Heterogeneous Datasets via Resampling (2020, background): “Very recent work (Data and Diggavi, 2020) extend the theoretical analysis to non-convex, strongly-convex and non-i.i.d setup under a gradient dissimilarity assumption and propose a gradient compression scheme on top of it.”
Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning (2021, background): “Implications of our study: Numerous recent works have proposed sophisticated aggregation rules for FL with strong theoretical robustness guarantees [2], [10], [20], [21], [41], [50], [68], [70].”
Learning from History for Byzantine Robust Optimization (2020, background): “Numerous variations have been proposed which can handle non-iid data with varying degrees of success (Li et al., 2019; Ghosh et al., 2019; Chen et al., 2019; Peng et al., 2020; Data & Diggavi, 2020; He et al., 2020a; El-Mhamdi et al., 2020; Dong et al., 2020).”