Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load
This work addresses straggler mitigation in distributed machine learning, offering an incremental improvement over prior methods by adapting both worker count and computation load dynamically.
The paper tackles the problem of stragglers in distributed stochastic gradient descent (SGD) by modeling communication and computation times with random variables, resulting in a scheme that improves convergence speed and reduces computation load, with a slight increase in communication load.
In distributed machine learning, a central node outsources computationally expensive calculations to external worker nodes. The properties of optimization procedures like stochastic gradient descent (SGD) can be leveraged to mitigate the effect of unresponsive or slow workers called stragglers, that otherwise degrade the benefit of outsourcing the computation. This can be done by only waiting for a subset of the workers to finish their computation at each iteration of the algorithm. Previous works proposed to adapt the number of workers to wait for as the algorithm evolves to optimize the speed of convergence. In contrast, we model the communication and computation times using independent random variables. Considering this model, we construct a novel scheme that adapts both the number of workers and the computation load throughout the run-time of the algorithm. Consequently, we improve the convergence speed of distributed SGD while significantly reducing the computation load, at the expense of a slight increase in communication load.