Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On Parallel or Distributed Asynchronous Iterations with Unbounded Delays and Possible Out of Order Messages or Flexible Communication for Convex Optimization Problems and Machine Learning
We describe several features of parallel or distributed asynchronous iterative algorithms such as unbounded delays, possible out of order messages or flexible communication. We concentrate on the concept of macroiteratio…
SurveyAsynchronous Distributed Optimization with Delay-free Parameters
Existing asynchronous distributed optimization algorithms often use diminishing step-sizes that cause slow practical convergence, or use fixed step-sizes that depend on and decrease with an upper bound of the delays. Not…
Distributed OptimizationOn Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms
The need for scalable numerical solutions has motivated the development of asynchronous parallel algorithms, where a set of nodes run in parallel with little or no synchronization, thus computing with delayed information…
On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays
Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the it…
Distributed stochastic optimization with large delays
One of the most widely used methods for solving large-scale stochastic optimization problems is distributed asynchronous stochastic gradient descent (DASGD), a family of algorithms that result from parallelizing stochast…
Distributed ComputingStochastic Optimization