Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks

Abstract

This paper deals with distributed finite-sum optimization for learning over networks in the presence of malicious Byzantine attacks. To cope with such attacks, most resilient approaches so far combine stochastic gradient descent (SGD) with different robust aggregation rules. However, the sizeable SGD-induced stochastic gradient noise makes it challenging to distinguish malicious messages sent by the Byzantine attackers from noisy stochastic gradients sent by the 'honest' workers. This motivates us to reduce the variance of stochastic gradients as a means of robustifying SGD in the presence of Byzantine attacks. To this end, the present work puts forth a Byzantine attack resilient distributed (Byrd-) SAGA approach for learning tasks involving finite-sum optimization over networks. Rather than the mean employed by distributed SAGA, the novel Byrd- SAGA relies on the geometric median to aggregate the corrected stochastic gradients sent by the workers. When less than half of the workers are Byzantine attackers, the robustness of geometric median to outliers enables Byrd-SAGA to attain provably linear convergence to a neighborhood of the optimal solution, with the asymptotic learning error determined by the number of Byzantine workers. Numerical tests corroborate the robustness to various Byzantine attacks, as well as the merits of Byrd- SAGA over Byzantine attack resilient distributed SGD.

References in corpus (17)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Geometric median and robust estimation in Banach spaces
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• D${}^2$: Decentralized Training over Decentralized Data
• Generalized Byzantine-tolerant SGD
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Adversary-resilient Distributed and Decentralized Statistical Inference and Machine Learning: An Overview of Recent Advances Under the Byzantine Threat Model
• The Internet of Things: Secure Distributed Inference
• Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation
• Distributed Robust Learning
• BRIDGE: Byzantine-resilient Decentralized Gradient Descent
• Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structure
• Distributed SAGA: Maintaining linear convergence rate with limited communication

Cited by in corpus (25)

• Robust Aggregation for Federated Learning
• Survey on Federated Learning Threats: concepts, taxonomy on attacks and defences, experimental study and challenges
• An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning
• Enhanced Security and Privacy via Fragmented Federated Learning
• Towards Communication-efficient and Attack-Resistant Federated Edge Learning for Industrial Internet of Things
• Combating Interference for Over-the-Air Federated Learning: A Statistical Approach via RIS
• Threats and Defenses in Federated Learning Life Cycle: A Comprehensive Survey and Challenges
• BEV-SGD: Best Effort Voting SGD for Analog Aggregation Based Federated Learning against Byzantine Attackers
• Expert System Gradient Descent Style Training: Development of a Defensible Artificial Intelligence Technique
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• Robust Distributed Optimization With Randomly Corrupted Gradients
• BadSampler: Harnessing the Power of Catastrophic Forgetting to Poison Byzantine-robust Federated Learning
• Byzantine-Robust Variance-Reduced Federated Learning over Distributed Non-i.i.d. Data
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Resource-constrained Federated Edge Learning with Heterogeneous Data: Formulation and Analysis
• Fused Deep Features Based Classification Framework for COVID-19 Classification with Optimized MLP
• On the Strategyproofness of the Geometric Median
• Federated Multi-Armed Bandits Under Byzantine Attacks
• Defending Against Diverse Attacks in Federated Learning Through Consensus-Based Bi-Level Optimization
• MANDERA: Malicious Node Detection in Federated Learning via Ranking
• Fake News and Phishing Detection Using a Machine Learning Trained Expert System
• Byzantine-Robust Decentralized Stochastic Optimization over Static and Time-Varying Networks
• Determining Sentencing Recommendations and Patentability Using a Machine Learning Trained Expert System
• Secure Distributed Training at Scale
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters