Timezone: »

Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?
Zhengyuan Zhou · Panayotis Mertikopoulos · Nicholas Bambos · Peter Glynn · Yinyu Ye · Li-Jia Li · Li Fei-Fei

Thu Jul 12 09:15 AM -- 12:00 PM (PDT) @ Hall B #13

One of the most widely used optimization methods for large-scale machine learning problems is distributed asynchronous stochastic gradient descent (DASGD). However, a key issue that arises here is that of delayed gradients: 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 the computational throughput of 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 when the delays grow at a polynomial rate. In this way, our results help reaffirm the successful application of DASGD to large-scale optimization problems.

Author Information

Zhengyuan Zhou (Stanford University)
Panayotis Mertikopoulos (CNRS)
Nicholas Bambos (Stanford University)
Peter Glynn (Stanford University)
Yinyu Ye
Li-Jia Li (Google)
Li Fei-Fei (Stanford University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors