Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
arXiv:1806.05358
Abstract
We study robust distributed learning that involves minimizing a non-convex loss function with saddle points. We consider the Byzantine setting where some worker machines have abnormal or even arbitrary and adversarial behavior. In this setting, the Byzantine machines may create fake local minima near a saddle point that is far away from any true local minimum, even when robust gradient estimators are used. We develop ByzantinePGD, a robust first-order algorithm that can provably escape saddle points and fake local minima, and converge to an approximate true local minimizer with low iteration complexity. As a by-product, we give a simpler algorithm and analysis for escaping saddle points in the usual non-Byzantine setting. We further discuss three robust gradient estimators that can be used in ByzantinePGD, including median, trimmed mean, and iterative filtering. We characterize their performance in concrete statistical settings, and argue for their near-optimality in low and high dimensional regimes.
arXiv commentICML 2019
References in corpus (28)
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
- Federated Optimization:Distributed Optimization Beyond the Datacenter
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- How to Escape Saddle Points Efficiently
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Generalized Byzantine-tolerant SGD
- Byzantine Stochastic Gradient Descent
- No bad local minima: Data independent training error guarantees for multilayer neural networks
- Sever: A Robust Meta-Algorithm for Stochastic Optimization
- Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- Gradient Descent Converges to Minimizers
- Robust Regression via Hard Thresholding
- First-order Methods Almost Always Avoid Saddle Points
- Being Robust (in High Dimensions) Can Be Practical
- The Power of Normalization: Faster Evasion of Saddle Points
- Neon2: Finding Local Minima via First-Order Oracles
- Accelerated Methods for Non-Convex Optimization
- Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
- Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
- Distributed Robust Learning
- High Dimensional Robust Sparse Regression
- Efficient Algorithms for Outlier-Robust Regression
- Byzantine-Tolerant Machine Learning
- Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
- Robust Sparse Estimation Tasks in High Dimensions
- First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time