Learning from History for Byzantine Robust Optimization

Abstract

Byzantine robustness has received significant attention recently given its importance for distributed and federated learning. In spite of this, we identify severe flaws in existing algorithms even when the data across the participants is identically distributed. First, we show realistic examples where current state of the art robust aggregation rules fail to converge even in the absence of any Byzantine attackers. Secondly, we prove that even if the aggregation rules may succeed in limiting the influence of the attackers in a single round, the attackers can couple their attacks across time eventually leading to divergence. To address these issues, we present two surprisingly simple strategies: a new robust iterative clipping procedure, and incorporating worker momentum to overcome time-coupled attacks. This is the first provably robust method for the standard stochastic optimization setting. Our code is open sourced at https://github.com/epfml/byzantine-robust-optimizer.

arXiv commentICML 2021. v2 contains stronger theory; v3 fixes some errors in the proof

References in corpus (22)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Robust Aggregation for Federated Learning
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Revisiting Distributed Synchronous SGD
• The Hidden Vulnerability of Distributed Learning in Byzantium
• Can You Really Backdoor Federated Learning?
• Geometric median and robust estimation in Banach spaces
• Byzantine Stochastic Gradient Descent
• Measuring the Effects of Data Parallelism on Neural Network Training
• Robust Federated Learning in a Heterogeneous Environment
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation
• Attack-Resistant Federated Learning with Residual-based Reweighting
• A Little Is Enough: Circumventing Defenses For Distributed Learning
• Distributed Robust Learning
• An Improved Analysis of Stochastic Gradient Descent with Momentum
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent
• Distributed Momentum for Byzantine-resilient Learning
• Communication-Efficient Robust Federated Learning Over Heterogeneous Datasets
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• Randomized Reactive Redundancy for Byzantine Fault-Tolerance in Parallelized Learning

Cited by in corpus (8)

• Byzantine-Resilient Non-Convex Stochastic Gradient Descent
• Byzantine-Robust Variance-Reduced Federated Learning over Distributed Non-i.i.d. Data
• Approximate Byzantine Fault-Tolerance in Distributed Optimization
• A Survey on Fault-tolerance in Distributed Optimization and Machine Learning
• Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers
• Solon: Communication-efficient Byzantine-resilient Distributed Training via Redundant Gradients
• Linear Speedup in Personalized Collaborative Learning
• Secure Distributed Training at Scale