Securing Distributed Gradient Descent in High Dimensional Statistical Learning

By Lili Su, Jiaming Xu. 2018

65 citations recorded by the source corpus.

We consider unreliable distributed learning systems wherein the training data is kept confidential by external workers, and the learner has to interact closely with those workers to train a model. In particular, we assume that there exists a system adversary that can adaptively compromise some workers; the compromised workers deviate from their local designed specifications by sending out arbitrarily malicious messages. We assume in each communication round, up to q out of the m workers suffer Byzantine faults. Each worker keeps a local sample of size n and the total sample size is $N=nm$. We propose a secured variant of the gradient descent method that can tolerate up to a constant fraction of Byzantine workers, i.e., $q/m = O(1)$. Moreover, we show the statistical estimation error of the iterates converges in $O(łog N)$ rounds to $O(\sqrtq/N + \sqrtd/N )$, where d is the model dimension. As long as $q=O(d)$, our proposed algorithm achieves the optimal error rate $O(\sqrtd/N )$. Our results are obtained under some technical assumptions. Specifically, we assume strongly-convex population risk. Nevertheless, the empirical risk (sample version) is allowed to be non-convex. The core of our method is to robustly aggregate the gradients computed by the workers based on the filtering procedure proposed by Steinhardt et al. \citeSteinhardt18. On the technical front, deviating from the existing literature on robustly estimating a finite-dimensional mean vector, we establish a \em uniform concentration of the sample covariance matrix of gradients, and show that the aggregated gradient, as a function of model parameter, converges uniformly to the true gradient function. To get a near-optimal uniform concentration bound, we develop a new matrix concentration inequality, which might be of independent interest.

Subfields: Artificial Intelligence, Computer Networks and Communications

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

Citations in the corpus

Data Encoding for Byzantine-Resilient Distributed Optimization (2019, methodology): “from a probability distribution) and analyze gradient descent [12], [20], [22], [24], [28].”
A Comprehensive Survey of Privacy-preserving Federated Learning (2021, background): “Therefore, they (weight update, gradient update and the final model) contain sensitive information of local data [133, 142, 167].”
Privacy and Robustness in Federated Learning: Attacks and Defenses (2020, background): “…cross-silo FL (H2B), which contains up to hundred clients, data poisoning attacks are completely ineffective; model poisoning attacks are unlikely to play a major risk when the clients involved are bound by contract and their software stacks professionally maintained (e.g., in banks, hospitals).”
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.”
Federated Learning for Healthcare: Systematic Review and Architecture Proposal (2022, background): “Su and Xu [65] propose a modification of the gradient descent method capable of tolerating input data from adversarial workers.”
Threats to Federated Learning: A Survey (2020, background): “Exchanging gradients during FL training can result in serious privacy leakage [Phong et al. , 2018; Su and Xu, 2018; Melis et al. , 2019; Zhu et al. , 2019].”
Learning from History for Byzantine Robust Optimization (2020, background): “There have also been attempts to use recent breakthroughs in robust high-dimensional aggregators (Di-akonikolas et al., 2018; Su & Xu, 2018; El-Mhamdi & Guerraoui, 2019; Data et al., 2019; Data & Diggavi, 2020).”
Byzantine-Robust Learning on Heterogeneous Datasets via Resampling (2020, background): “There has been signiﬁcant recent work of the case when the workers have identical data distributions (Blanchard et al., 2017; Chen et al., 2017; Mhamdi et al., 2018; Alistarh et al., 2018; Mhamdi et al., 2018; Yin et al., 2018a,b; Su and Xu, 2018; Damaskinos et al., 2019).”