Byzantine Stochastic Gradient Descent

Abstract

This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of the $m$ machines which allegedly compute stochastic gradients every iteration, an $\alpha$-fraction are Byzantine, and can behave arbitrarily and adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds $\epsilon$-approximate minimizers of convex functions in $T=\tilde{O}(\frac{1}{{\epsilon }^{2}m}+\frac{{\alpha }^2}{{\epsilon }^2})$ iterations. In contrast, traditional mini-batch SGD needs $T=O\left(\frac{1}{{\epsilon }^{2}m}\right)$ iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sampling complexity and time complexity.

References in corpus (11)

• Federated Learning: Strategies for Improving Communication Efficiency
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Generalized Byzantine-tolerant SGD
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• AIDE: Fast and Communication Efficient Distributed Optimization
• Tight Complexity Bounds for Optimizing Composite Objectives
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Distributed Robust Learning
• Efficient Algorithms for Outlier-Robust Regression

Cited by in corpus (39)

• Robust Aggregation for Federated Learning
• Robust Federated Learning in a Heterogeneous Environment
• Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation
• Attack-Resistant Federated Learning with Residual-based Reweighting
• Towards Communication-efficient and Attack-Resistant Federated Edge Learning for Industrial Internet of Things
• Phocas: dimensional Byzantine-resilient stochastic gradient descent
• Secure Byzantine-Robust Machine 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
• RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• 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
• Cybersecurity in Distributed and Fully-Decentralized Optimization: Distortions, Noise Injection, and ADMM
• Optimal query complexity for private sequential learning against eavesdropping
• SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics
• Byzantine Fault-Tolerant Distributed Machine Learning Using Stochastic Gradient Descent (SGD) and Norm-Based Comparative Gradient Elimination (CGE)
• Byzantine-Resilient Secure Federated Learning
• Byzantine-Resilient Stochastic Gradient Descent for Distributed Learning: A Lipschitz-Inspired Coordinate-wise Median Approach
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Excess risk bounds in robust empirical risk minimization
• ByGARS: Byzantine SGD with Arbitrary Number of Attackers
• Approximate Byzantine Fault-Tolerance in Distributed Optimization
• Resilience in Collaborative Optimization: Redundant and Independent Cost Functions
• Mitigating Sybil Attacks on Differential Privacy based Federated Learning
• On the Sample Complexity of Adversarial Multi-Source PAC Learning
• Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding
• On the Strategyproofness of the Geometric Median
• Towards Bidirectional Protection in Federated Learning
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee
• Distributed Byzantine Tolerant Stochastic Gradient Descent in the Era of Big Data
• Secure Distributed Training at Scale
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience
• Model Linkage Selection for Cooperative Learning
• Resilient Consensus-based Multi-agent Reinforcement Learning with Function Approximation
• Zeno++: Robust Fully Asynchronous SGD