Communication trade-offs for synchronized distributed SGD with large step size

Abstract

Synchronous mini-batch SGD is state-of-the-art for large-scale distributed machine learning. However, in practice, its convergence is bottlenecked by slow communication rounds between worker nodes. A natural solution to reduce communication is to use the \emph{`local-SGD'} model in which the workers train their model independently and synchronize every once in a while. This algorithm improves the computation-communication trade-off but its convergence is not understood very well. We propose a non-asymptotic error analysis, which enables comparison to \emph{one-shot averaging} i.e., a single communication round among independent workers, and \emph{mini-batch averaging} i.e., communicating at every step. We also provide adaptive lower bounds on the communication frequency for large step-sizes ($t^{-\alpha }$, $\alpha \in (1/2,1)$) and show that \emph{Local-SGD} reduces communication by a factor of $O\left(\frac{\sqrt{T}}{P^{3/2}}\right)$, with $T$ the total number of gradients and $P$ machines.

References in corpus (32)

• Federated Learning: Strategies for Improving Communication Efficiency
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Optimal Distributed Online Prediction using Mini-Batches
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Slow Learners are Fast
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• AIDE: Fast and Communication Efficient Distributed Optimization
• Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• CoCoA: A General Framework for Communication-Efficient Distributed Optimization
• Parallel SGD: When does averaging help?
• GPU Asynchronous Stochastic Gradient Descent to Speed Up Neural Network Training
• Deep learning with Elastic Averaging SGD
• Optimality guarantees for distributed statistical estimation
• Distributed learning with compressed gradients
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Asynchronous stochastic convex optimization
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity
• Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
• The ZipML Framework for Training Models with End-to-End Low Precision: The Cans, the Cannots, and a Little Bit of Deep Learning
• Asynchronous Parallel Stochastic Gradient Descent - A Numeric Core for Scalable Distributed Machine Learning Algorithms
• Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization?
• Fast Asynchronous Parallel Stochastic Gradient Decent
• A Stochastic Large-scale Machine Learning Algorithm for Distributed Features and Observations

Cited by in corpus (7)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Don't Use Large Mini-Batches, Use Local SGD
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
• Faster Non-Convex Federated Learning via Global and Local Momentum