A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate
arXiv:2003.12423
Abstract
In this paper, we propose a method of distributed stochastic gradient descent (SGD), with low communication load and computational complexity, and still fast convergence. To reduce the communication load, at each iteration of the algorithm, the worker nodes calculate and communicate some scalers, that are the directional derivatives of the sample functions in some \emph{pre-shared directions}. However, to maintain accuracy, after every specific number of iterations, they communicate the vectors of stochastic gradients. To reduce the computational complexity in each iteration, the worker nodes approximate the directional derivatives with zeroth-order stochastic gradient estimation, by performing just two function evaluations rather than computing a first-order gradient vector. The proposed method highly improves the convergence rate of the zeroth-order methods, guaranteeing order-wise faster convergence. Moreover, compared to the famous communication-efficient methods of model averaging (that perform local model updates and periodic communication of the gradients to synchronize the local models), we prove that for the general class of non-convex stochastic problems and with reasonable choice of parameters, the proposed method guarantees the same orders of communication load and convergence rate, while having order-wise less computational complexity. Experimental results on various learning problems in neural networks applications demonstrate the effectiveness of the proposed approach compared to various state-of-the-art distributed SGD methods.
References in corpus (16)
- PyTorch: An Imperative Style, High-Performance Deep Learning Library
- TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
- TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
- Optimal Distributed Online Prediction using Mini-Batches
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
- Parallel training of DNNs with Natural Gradient and Parameter Averaging
- Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
- Parallel SGD: When does averaging help?
- A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
- Experiments on Parallel Training of Deep Neural Network using Model Averaging
- Zeroth Order Nonconvex Multi-Agent Optimization over Networks
- Towards Gradient Free and Projection Free Stochastic Optimization
- A Distributed Hierarchical SGD Algorithm with Sparse Global Reduction