Distributed delayed stochastic optimization
Alekh Agarwal, John C. Duchi · 2012
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 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. We show n-node architectures whose optimization error in stochastic problems-in spite of asynchronous delays-scales asymptotically as O(1/√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 logistic regression task.
Cited by 243 works. doi:10.1109/cdc.2012.6426626
Authors
References
- A Stochastic Approximation Method
- Parallel and Distributed Computation: Numerical Methods
- RCV1: A New Benchmark Collection for Text Categorization Research
- Introduction to optimization
- Distributed Subgradient Methods for Multi-Agent Optimization
- Problem complexity and method efficiency in optimization
- PROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
- Slow Learners are Fast
- Slow Learners are Fast
- Primal-dual subgradient methods for convex problems