On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization

Abstract

For SGD based distributed stochastic optimization, computation complexity, measured by the convergence rate in terms of the number of stochastic gradient calls, and communication complexity, measured by the number of inter-node communication rounds, are two most important performance metrics. The classical data-parallel implementation of SGD over $N$ workers can achieve linear speedup of its convergence rate but incurs an inter-node communication round at each batch. We study the benefit of using dynamically increasing batch sizes in parallel SGD for stochastic non-convex optimization by charactering the attained convergence rate and the required number of communication rounds. We show that for stochastic non-convex optimization under the P-L condition, the classical data-parallel SGD with exponentially increasing batch sizes can achieve the fastest known $O(1/(NT))$ convergence with linear speedup using only $\log (T)$ communication rounds. For general stochastic non-convex optimization, we propose a Catalyst-like algorithm to achieve the fastest known $O(1/\sqrt{NT})$ convergence with only $O(\sqrt{NT}\log (\frac{T}{N}))$ communication rounds.

arXiv commentA short version is accepted to ICML 2019

Cited by in corpus (17)

• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Taming Resource Heterogeneity In Distributed ML Training With Dynamic Batching
• Federated Accelerated Stochastic Gradient Descent
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning
• LASG: Lazily Aggregated Stochastic Gradients for Communication-Efficient Distributed Learning
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• What Do We Mean by Generalization in Federated Learning?
• To Talk or to Work: Flexible Communication Compression for Energy Efficient Federated Learning over Heterogeneous Mobile Edge Devices
• Federated Composite Optimization
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• Distributed Optimization over Block-Cyclic Data
• Stagewise Enlargement of Batch Size for SGD-based Learning
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes
• Machine Learning on Volatile Instances
• Federated Submodel Optimization for Hot and Cold Data Features
• Communication-Censored Distributed Stochastic Gradient Descent
• Invexifying Regularization of Non-Linear Least-Squares Problems