Distributed Delayed Stochastic Optimization

Abstract

We analyze the convergence of gradient-based optimization algorithms that base their updates on delayed stochastic gradient information. The main application of our results is to the development of gradient-based distributed optimization algorithms where a master node performs parameter updates while worker nodes compute stochastic gradients based on local information in parallel, which may give rise to delays due to asynchrony. We take motivation from statistical problems where the size of the data is so large that it cannot fit on one computer; with the advent of huge datasets in biology, astronomy, and the internet, such problems are now common. Our main contribution is to show that for smooth stochastic problems, the delays are asymptotically negligible and we can achieve order-optimal convergence results. In application to distributed optimization, we develop procedures that overcome communication bottlenecks and synchronization requirements. We show $n$-node architectures whose optimization error in stochastic problems---in spite of asynchronous delays---scales asymptotically as $\order(1 / \sqrt{nT})$ after $T$ iterations. This rate is known to be optimal for a distributed system with $n$ nodes even in the absence of delays. We additionally complement our theoretical results with numerical experiments on a statistical machine learning task.

27 pages, 4 figures

References in corpus (3)

• Optimal Distributed Online Prediction using Mini-Batches
• Slow Learners are Fast
• Robust Distributed Online Prediction

Cited by in corpus (24)

• Speeding Up Distributed Machine Learning Using Codes
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Delay and Cooperation in Nonstochastic Bandits
• CONDENSE: A Reconfigurable Knowledge Acquisition Architecture for Future 5G IoT
• Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation
• Asynchronous Federated Learning with Differential Privacy for Edge Intelligence
• $\text{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression
• DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
• GradiVeQ: Vector Quantization for Bandwidth-Efficient Gradient Aggregation in Distributed CNN Training
• Error Compensated Distributed SGD Can Be Accelerated
• Asymptotic Convergence in Online Learning with Unbounded Delays
• Para-active learning
• MixML: A Unified Analysis of Weakly Consistent Parallel Learning
• Faster Distributed Deep Net Training: Computation and Communication Decoupled Stochastic Gradient Descent
• Optimal Gradient Checkpoint Search for Arbitrary Computation Graphs
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Adaptive Periodic Averaging: A Practical Approach to Reducing Communication in Distributed Learning
• Cache Replacement as a MAB with Delayed Feedback and Decaying Costs
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• Distributed stochastic optimization with large delays
• Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates
• Empirical Evaluation of Parallel Training Algorithms on Acoustic Modeling
• Asynchronous Stochastic Composition Optimization with Variance Reduction
• Online decentralized decision making with inequality constraints: an ADMM approach