Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates

Abstract

In large-scale distributed learning, security issues have become increasingly important. Particularly in a decentralized environment, some computing units may behave abnormally, or even exhibit Byzantine failures -- arbitrary and potentially adversarial behavior. In this paper, we develop distributed learning algorithms that are provably robust against such failures, with a focus on achieving optimal statistical performance. A main result of this work is a sharp analysis of two robust distributed gradient descent algorithms based on median and trimmed mean operations, respectively. We prove statistical error rates for three kinds of population loss functions: strongly convex, non-strongly convex, and smooth non-convex. In particular, these algorithms are shown to achieve order-optimal statistical error rates for strongly convex losses. To achieve better communication efficiency, we further propose a median-based distributed algorithm that is provably robust, and uses only one communication round. For strongly convex quadratic loss, we show that this algorithm achieves the same optimal error rate as the robust distributed gradient descent algorithms.

ICML 2018

References in corpus (13)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Loss minimization and parameter estimation with heavy tails
• AIDE: Fast and Communication Efficient Distributed Optimization
• Robust Regression via Hard Thresholding
• Robust empirical mean Estimators
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Distributed Robust Learning
• Byzantine-Tolerant Machine Learning
• Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model
• Sub-Gaussian estimators of the mean of a random vector

Cited by in corpus (113)

• Robust Aggregation for Federated Learning
• How To Backdoor Federated Learning
• A Blockchain-based Decentralized Federated Learning Framework with Committee Consensus
• Analyzing Federated Learning through an Adversarial Lens
• FedML: A Research Library and Benchmark for Federated Machine Learning
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Threats to Federated Learning: A Survey
• Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks
• Ditto: Fair and Robust Federated Learning Through Personalization
• DeepSight: Mitigating Backdoor Attacks in Federated Learning Through Deep Model Inspection
• Federated Learning: A Signal Processing Perspective
• Local Model Poisoning Attacks to Byzantine-Robust Federated Learning
• Byzantine Stochastic Gradient Descent
• Byzantine-Robust Federated Machine Learning through Adaptive Model Averaging
• Robust Federated Learning in a Heterogeneous Environment
• A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee
• Edge Intelligence: Architectures, Challenges, and Applications
• Attack of the Tails: Yes, You Really Can Backdoor Federated Learning
• Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer
• An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning
• Fedstellar: A Platform for Decentralized Federated Learning
• FedRecAttack: Model Poisoning Attack to Federated Recommendation
• Salvaging Federated Learning by Local Adaptation
• Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation
• Attack-Resistant Federated Learning with Residual-based Reweighting
• Dynamic Defense Against Byzantine Poisoning Attacks in Federated Learning
• Shielding Federated Learning: Robust Aggregation with Adaptive Client Selection
• A Little Is Enough: Circumventing Defenses For Distributed Learning
• Phocas: dimensional Byzantine-resilient stochastic gradient descent
• Mitigating Bias in Federated Learning
• SAFELearning: Enable Backdoor Detectability In Federated Learning With Secure Aggregation
• A Reputation Mechanism Is All You Need: Collaborative Fairness and Adversarial Robustness in Federated Learning
• Secure Byzantine-Robust Machine Learning
• Auto-weighted Robust Federated Learning with Corrupted Data Sources
• FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping
• Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
• PEPPER: Empowering User-Centric Recommender Systems over Gossip Learning
• Federated Learning Meets Multi-objective Optimization
• A Four-Pronged Defense Against Byzantine Attacks in Federated Learning
• Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks
• Learning from History for Byzantine Robust Optimization
• Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation
• Towards Reliable Participation in UAV-Enabled Federated Edge Learning on Non-IID Data
• Basil: A Fast and Byzantine-Resilient Approach for Decentralized Training
• Backdoor Attacks on Federated Meta-Learning
• RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent
• Resisting Backdoor Attacks in Federated Learning via Bidirectional Elections and Individual Perspective
• Byzantines can also Learn from History: Fall of Centered Clipping in Federated Learning
• Robust Distributed Optimization With Randomly Corrupted Gradients
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• Shielding Collaborative Learning: Mitigating Poisoning Attacks through Client-Side Detection
• Secure Aggregation with Heterogeneous Quantization in Federated Learning
• Securing Federated Sensitive Topic Classification against Poisoning Attacks
• Turning Privacy-preserving Mechanisms against Federated Learning
• Distributed Momentum for Byzantine-resilient Learning
• DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation
• Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing
• Byzantine-Robust and Privacy-Preserving Framework for FedML
• Federated Learning for Malware Detection in IoT Devices
• Free-rider Attacks on Model Aggregation in Federated Learning
• Optimal query complexity for private sequential learning against eavesdropping
• BlockFLA: Accountable Federated Learning via Hybrid Blockchain Architecture
• Byzantine-Resilient Secure Federated Learning
• Byzantine-Resilient Stochastic Gradient Descent for Distributed Learning: A Lipschitz-Inspired Coordinate-wise Median Approach
• Federated Noisy Client Learning
• Excess risk bounds in robust empirical risk minimization
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• ByGARS: Byzantine SGD with Arbitrary Number of Attackers
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Byzantine-Robust Variance-Reduced Federated Learning over Distributed Non-i.i.d. Data
• Towards cost-effective and resource-aware aggregation at Edge for Federated Learning
• From low probability to high confidence in stochastic convex optimization
• Security of Deep Learning Methodologies: Challenges and Opportunities
• Mitigating Sybil Attacks on Differential Privacy based Federated Learning
• Influence Function based Data Poisoning Attacks to Top-N Recommender Systems
• Distributed Newton Can Communicate Less and Resist Byzantine Workers
• Byzantine-resilient Decentralized Stochastic Gradient Descent
• Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers
• On the Sample Complexity of Adversarial Multi-Source PAC Learning
• SLSGD: Secure and Efficient Distributed On-device Machine Learning
• Byzantine Resilient Distributed Multi-Task Learning
• Robust Federated Learning with Attack-Adaptive Aggregation
• WAFFLE: Watermarking in Federated Learning
• FAT: Federated Adversarial Training
• DiPSeN: Differentially Private Self-normalizing Neural Networks For Adversarial Robustness in Federated Learning
• Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding
• Towards Bidirectional Protection in Federated Learning
• Covert Model Poisoning Against Federated Learning: Algorithm Design and Optimization
• MANDERA: Malicious Node Detection in Federated Learning via Ranking
• Defending Against Diverse Attacks in Federated Learning Through Consensus-Based Bi-Level Optimization
• Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method
• Simeon -- Secure Federated Machine Learning Through Iterative Filtering
• ByzShield: An Efficient and Robust System for Distributed Training
• Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee
• A robust fusion-extraction procedure with summary statistics in the presence of biased sources
• Security and Privacy Issues and Solutions in Federated Learning for Digital Healthcare
• Data-Free Evaluation of User Contributions in Federated Learning
• Federated Learning via Plurality Vote
• On Provable Backdoor Defense in Collaborative Learning
• Robustness Against Outliers For Deep Neural Networks By Gradient Conjugate Priors
• Differential Privacy and Byzantine Resilience in SGD: Do They Add Up?
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience
• Secure Distributed Training at Scale
• Combining Differential Privacy and Byzantine Resilience in Distributed SGD
• Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications
• BadVFL: Backdoor Attacks in Vertical Federated Learning
• Attacks on Robust Distributed Learning Schemes via Sensitivity Curve Maximization
• Zeno++: Robust Fully Asynchronous SGD
• Bristle: Decentralized Federated Learning in Byzantine, Non-i.i.d. Environments
• PipAttack: Poisoning Federated Recommender Systems forManipulating Item Promotion
• Distributed Byzantine Tolerant Stochastic Gradient Descent in the Era of Big Data
• Model Linkage Selection for Cooperative Learning