  Distributed Stochastic Gradient Descent (SGD) when run in a synchronous
manner, suffers from delays in runtime as it waits for the slowest workers
(stragglers). Asynchronous methods can alleviate stragglers, but cause gradient
staleness that can adversely affect the convergence error. In this work, we
present a novel theoretical characterization of the speedup offered by
asynchronous methods by analyzing the trade-off between the error in the
trained model and the actual training runtime(wallclock time). The main novelty
in our work is that our runtime analysis considers random straggling delays,
which helps us design and compare distributed SGD algorithms that strike a
balance between straggling and staleness. We also provide a new error
convergence analysis of asynchronous SGD variants without bounded or
exponential delay assumptions. Finally, based on our theoretical
characterization of the error-runtime trade-off, we propose a method of
gradually varying synchronicity in distributed SGD and demonstrate its
performance on CIFAR10 dataset.
