Robust Federated Learning in a Heterogeneous Environment

Abstract

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.

arXiv commentFixing technical issues. Please discard any previous version

References in corpus (14)

• Federated Learning with Non-IID Data
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Geometric median and robust estimation in Banach spaces
• Generalized Byzantine-tolerant SGD
• Byzantine Stochastic Gradient Descent
• CoCoA: A General Framework for Communication-Efficient Distributed Optimization
• Alternating Minimization for Mixed Linear Regression
• Being Robust (in High Dimensions) Can Be Practical
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• Distributed Robust Learning
• RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets

Cited by in corpus (31)

• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Federated Learning: A Signal Processing Perspective
• A Field Guide to Federated Optimization
• Clustered Federated Learning Architecture for Network Anomaly Detection in Large Scale Heterogeneous IoT Networks
• Federated Continual Learning via Knowledge Fusion: A Survey
• Federated Learning for Healthcare Informatics
• Hierarchical Personalized Federated Learning Over Massive Mobile Edge Computing Networks
• Secure Byzantine-Robust Machine Learning
• No Fear of Heterogeneity: Classifier Calibration for Federated Learning with Non-IID Data
• TornadoAggregate: Accurate and Scalable Federated Learning via the Ring-Based Architecture
• Differentially Private Federated Clustering over Non-IID Data
• Learning from History for Byzantine Robust Optimization
• An Optimal Transport Approach to Personalized Federated Learning
• Heterogeneity for the Win: One-Shot Federated Clustering
• On the Outsized Importance of Learning Rates in Local Update Methods
• Contrastive encoder pre-training-based clustered federated learning for heterogeneous data
• Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing
• Communication-Efficient Robust Federated Learning Over Heterogeneous Datasets
• Federated Learning with Intermediate Representation Regularization
• Federated Learning on Non-IID Data: A Survey
• Secure Byzantine-Robust Distributed Learning via Clustering
• Byzantine-Robust Variance-Reduced Federated Learning over Distributed Non-i.i.d. Data
• Resource-Constrained Federated Learning with Heterogeneous Labels and Models
• Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers
• FedSEAL: Semi-Supervised Federated Learning with Self-Ensemble Learning and Negative Learning
• Distributed Newton Can Communicate Less and Resist Byzantine Workers
• An Energy Consumption Model for Electrical Vehicle Networks via Extended Federated-learning
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• TiFL: A Tier-based Federated Learning System
• Dynamic Attention-based Communication-Efficient Federated Learning
• Probabilistic Inference for Learning from Untrusted Sources