Byzantine-Resilient Non-Convex Stochastic Gradient Descent
arXiv:2012.14368
Abstract
We study adversary-resilient stochastic distributed optimization, in which machines can independently compute stochastic gradients, and cooperate to jointly optimize over their local objective functions. However, an -fraction of the machines are , in that they may behave in arbitrary, adversarial ways. We consider a variant of this procedure in the challenging case. Our main result is a new algorithm SafeguardSGD which can provably escape saddle points and find approximate local minima of the non-convex objective. The algorithm is based on a new concentration filtering technique, and its sample and time complexity bounds match the best known theoretical bounds in the stochastic, distributed setting when no Byzantine machines are present. Our algorithm is very practical: it improves upon the performance of all prior methods when training deep neural networks, it is relatively lightweight, and it is the first method to withstand two recently-proposed Byzantine attacks.
V1.5 polishes writing and V2 rewrites the experiments
References in corpus (11)
- Federated Learning: Strategies for Improving Communication Efficiency
- Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
- Generalized Byzantine-tolerant SGD
- Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation
- On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
- Stochastic Cubic Regularization for Fast Nonconvex Optimization
- A Little Is Enough: Circumventing Defenses For Distributed Learning
- Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
- Distributed Robust Learning
- Learning from History for Byzantine Robust Optimization
- Byzantine-Resilient Stochastic Gradient Descent for Distributed Learning: A Lipschitz-Inspired Coordinate-wise Median Approach