Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
arXiv:2106.08882
Abstract
Geometric median (\textsc{Gm}) is a classical method in statistics for achieving a robust estimation of the uncorrupted data; under gross corruption, it achieves the optimal breakdown point of 0.5. However, its computational complexity makes it infeasible for robustifying stochastic gradient descent (SGD) for high-dimensional optimization problems. In this paper, we show that by applying \textsc{Gm} to only a judiciously chosen block of coordinates at a time and using a memory mechanism, one can retain the breakdown point of 0.5 for smooth non-convex problems, with non-asymptotic convergence rates comparable to the SGD with \textsc{Gm}.
References in corpus (28)
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
- Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning
- On the Convergence of FedAvg on Non-IID Data
- Robust Aggregation for Federated Learning
- Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
- Optimal Distributed Online Prediction using Mini-Batches
- Federated Optimization in Heterogeneous Networks
- Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
- Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
- Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks
- Sparsified SGD with Memory
- Local SGD Converges Fast and Communicates Little
- Sever: A Robust Meta-Algorithm for Stochastic Optimization
- Learning with Bad Training Data via Iterative Trimmed Loss Minimization
- Backdoor Embedding in Convolutional Neural Network Models via Invisible Perturbation
- Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
- Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance
- The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
- Understanding Top-k Sparsification in Distributed Deep Learning
- Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
- Unified Optimal Analysis of the (Stochastic) Gradient Method
- Distributed Robust Learning
- Approximate Steepest Coordinate Descent
- Faster Non-Convex Federated Learning via Global and Local Momentum
- Byzantine Fault-Tolerant Distributed Machine Learning Using Stochastic Gradient Descent (SGD) and Norm-Based Comparative Gradient Elimination (CGE)
- Efficient Greedy Coordinate Descent for Composite Problems