Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox
arXiv:1702.06269
Abstract
We present and analyze an approach for distributed stochastic optimization which is statistically optimal and achieves near-linear speedups (up to logarithmic factors). Our approach allows a communication-memory tradeoff, with either logarithmic communication but linear memory, or polynomial communication and a corresponding polynomial reduction in required memory. This communication-memory tradeoff is achieved through minibatch-prox iterations (minibatch passive-aggressive updates), where a subproblem on a minibatch is solved at each iteration. We provide a novel analysis for such a minibatch-prox procedure which achieves the statistical optimal rate regardless of minibatch size and smoothness, thus significantly improving on prior work.
Cited by in corpus (14)
- Don't Use Large Mini-Batches, Use Local SGD
- Least Squares Approximation for a Distributed System
- Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
- Stochastic Nonconvex Optimization with Large Minibatches
- The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
- A Distributed Hierarchical SGD Algorithm with Sparse Global Reduction
- Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
- Stochastic Optimization with Laggard Data Pipelines
- Inverse Multiobjective Optimization Through Online Learning
- Adaptive Periodic Averaging: A Practical Approach to Reducing Communication in Distributed Learning
- Communication-efficient Byzantine-robust distributed learning with statistical guarantee
- Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the Convergence Rate
- Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models
- Algorithmic Instabilities of Accelerated Gradient Descent