Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?

Zhengyuan Zhou (1) , Panayotis Mertikopoulos (2) , Nicholas Bambos (1) , Peter W. Glynn (1) , Yinyu Ye (3) , Li-Jia Li (4) , Fei-Fei Li (4)

1 Department of Electrical Engineering [Stanford]
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
3 Department of Management Science and Engineering [Stanford]
4 Google Inc [Mountain View]

One of the most widely used training methods for large-scale machine learning problems is distributed asynchronous stochastic gradient descent (DASGD). However, a key issue in its implementation is that of delays: when a "worker" node asynchronously contributes a gradient update to the "master", the global model parameter may have changed, rendering this information stale. In massively parallel computing grids, these delays can quickly add up if a node is saturated, so the convergence of DASGD is uncertain under these conditions. Nevertheless, by using a judiciously chosen quasilinear step-size sequence, we show that it is possible to amortize these delays and achieve global convergence with probability 1, even under polynomially growing delays, reaffirming in this way the successful application of DASGD to large-scale optimization problems.

Domaines: Optimisation et contrôle [math.OC]

Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter W. Glynn, Yinyu Ye, et al.. Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?. ICML 2018 - 35th International Conference on Machine Learning, Jul 2018, Stockholm, Sweden. pp.1-10. ⟨hal-01891449⟩