Robust Federated Learning in a Heterogeneous Environment

By Avishek Ghosh, Justin Hong, Dong Yin, Kannan Ramchandran. 2019

262 citations recorded by the source corpus.

We study a recently proposed large-scale distributed learning paradigm, namely Federated Learning, where the worker machines are end users' own devices. Statistical and computational challenges arise in Federated Learning particularly in the presence of heterogeneous data distribution (i.e., data points on different devices belong to different distributions signifying different clusters) and Byzantine machines (i.e., machines that may behave abnormally, or even exhibit arbitrary and potentially adversarial behavior). To address the aforementioned challenges, first we propose a general statistical model for this problem which takes both the cluster structure of the users and the Byzantine machines into account. Then, leveraging the statistical model, we solve the robust heterogeneous Federated Learning problem \emph{optimally}; in particular our algorithm matches the lower bound on the estimation error in dimension and the number of data points. Furthermore, as a by-product, we prove statistical guarantees for an outlier-robust clustering algorithm, which can be considered as the Lloyd algorithm with robust estimation. Finally, we show via synthetic as well as real data experiments that the estimation error obtained by our proposed algorithm is significantly better than the non-Byzantine-robust algorithms; in particular, we gain at least by 53\% and 33\% for synthetic and real data experiments, respectively, in typical settings.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

On the Outsized Importance of Learning Rates in Local Update Methods (2020, background): “…topics including differential privacy (McMahan et al., 2018; Augenstein et al., 2020), fairness (Mohri et al., 2019; Li et al., 2020b), robustness (Ghosh et al., 2019; Bagdasaryan et al., 2018; Sun et al., 2019), and communication-efficiency (Konečný et al., 2016; Sattler et al., 2019; Basu et…”
FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, background): “Robustness against adversarial devices is another challenge in federated learning and distributed learning that has been studied in [Chen et al., 2017, Ghosh et al., 2019, Yin et al., 2018].”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “from a probability distribution) and analyze gradient descent [12], [20], [22], [24], [28].”
Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data (2020, unknown): “A different line of work (Chen et al., 2018; Data & Diggavi, 2019; 2020a; Data et al., 2019; 2021; Ghosh et al., 2019; Li et al., 2019a; Rajput et al., 2019) provide robustness with heterogeneous data, but without local iterations or sampling of clients: Chen et al.”
A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection (2019, background): “ue to malicious parties. Along this line, Gu et al. [71] present a multi-party collaborative learning system to fulﬁll model accountability in trusted execution environment environments. Ghosh et al. [66] consider the model robustness upon Byzantine parties (or abnormal and adversarial parties). Ano”
TiFL: A Tier-based Federated Learning System (2020, background): “[10] proposes a general statistical model for Byzantine machines and clients with data heterogeneity that clusters based on data distribution.”
Federated Learning on Non-IID Data: A Survey (2021, methodology): “The first similarity evaluation approach is reported in [93, 68, 39, 38] by comparing the loss values of different cluster models.”
Federated Learning Meets Blockchain in Edge Computing: Opportunities and Challenges (2021, background): “Further, to solve the heterogeneous issues in the FL training, the work in [87] proposes a robust FL framework in heterogeneous environments where device clients may behave abnormally due to its behaviours and data points at different devices have different distributions.”
Clustered Federated Learning: Model-Agnostic Distributed Multitask Optimization Under Privacy Constraints (2019, result): “[2] propose a clustering approach, similar to the one presented in this paper.”
Federated learning with hierarchical clustering of local updates to improve training on non-IID data (2020, methodology): “[18] use K-means to cluster client updates for the purpose of identifying and isolating byzantine clusters of clients prior to the averaging step.”
No Fear of Heterogeneity: Classifier Calibration for Federated Learning with Non-IID Data (2021, background): “There are also heuristic approaches that divide clients into different clusters based on their learning tasks (objectives) and perform aggregation only within the cluster [33, 34, 22, 35].”
An Efficient Framework for Clustered Federated Learning (2020, methodology): “The formulation of clustered FL has been considered in two recent works [36, 10].”
Byzantine-Robust Learning on Heterogeneous Datasets via Resampling (2020, methodology): “Ghosh et al. (2019) assume that all workers belong to an apriori ﬁxed number of clusters and use an outlier-robust clustering method to recover these clusters.”
Manipulating the Byzantine: Optimizing Model Poisoning Attacks and Defenses for Federated Learning (2021, background): “We note that, defending the real-world non-iid FL settings from the worst case model poisoning attacks is a well-known challenging task [17], [19], [18] and a limitation of DnC in its current form.”
Decentralized Federated Learning: A Survey and Perspective (2023, background): “…values indicating the relative strength of the respective FL approach in that domain. metrics, which are the focal points of current state-of-the-art (SOTA) research and worthy of further investigation [33], [34], [35], [36], [37], [38], [39], [40], [41], [42], [43], [44], [45], [46], [47], [48].”
Federated Machine Learning: Survey, Multi-Level Classification, Desirable Criteria and Future Directions in Communication and Networking Systems (2021, background): “In [63], the authors propose a statistical model that takes into consideration the cluster structure of clients’ data.”
Secure Byzantine-Robust Machine Learning (2020, methodology): “Byzantine robust rules for non-i.i.d dataset have appeared only recently [21, 13].”