Accelerating Gossip SGD with Periodic Global Averaging

Abstract

Communication overhead hinders the scalability of large-scale distributed training. Gossip SGD, where each node averages only with its neighbors, is more communication-efficient than the prevalent parallel SGD. However, its convergence rate is reversely proportional to quantity $1-\beta$ which measures the network connectivity. On large and sparse networks where $1-\beta \to 0$, Gossip SGD requires more iterations to converge, which offsets against its communication benefit. This paper introduces Gossip-PGA, which adds Periodic Global Averaging into Gossip SGD. Its transient stage, i.e., the iterations required to reach asymptotic linear speedup stage, improves from $\Omega ({\beta }^4{n}^3/(1-\beta {)}^4)$ to $\Omega ({\beta }^4{n}^3{H}^4)$ for non-convex problems. The influence of network topology in Gossip-PGA can be controlled by the averaging period $H$. Its transient-stage complexity is also superior to Local SGD which has order $\Omega (n^3{H}^4)$. Empirical results of large-scale training on image classification (ResNet50) and language modeling (BERT) validate our theoretical findings.

arXiv commentAccepted to ICML 2021

References in corpus (18)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Don't Use Large Mini-Batches, Use Local SGD
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• D${}^2$: Decentralized Training over Decentralized Data
• Stochastic Gradient Push for Distributed Deep Learning
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Parallel SGD: When does averaging help?
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• On the Influence of Bias-Correction on Distributed Stochastic Optimization

Cited by in corpus (1)

• Sign Bit is Enough: A Learning Synchronization Framework for Multi-hop All-reduce with Ultimate Compression