  We consider the setting where a master wants to run a distributed stochastic
gradient descent (SGD) algorithm on $n$ workers, each having a subset of the
data. Distributed SGD may suffer from the effect of stragglers, i.e., slow or
unresponsive workers who cause delays. One solution studied in the literature
is to wait at each iteration for the responses of the fastest $k<n$ workers
before updating the model, where $k$ is a fixed parameter. The choice of the
value of $k$ presents a trade-off between the runtime (i.e., convergence rate)
of SGD and the error of the model. Towards optimizing the error-runtime
trade-off, we investigate distributed SGD with adaptive~$k$, i.e., varying $k$
throughout the runtime of the algorithm. We first design an adaptive policy for
varying $k$ that optimizes this trade-off based on an upper bound on the error
as a function of the wall-clock time that we derive. Then, we propose and
implement an algorithm for adaptive distributed SGD that is based on a
statistical heuristic. Our results show that the adaptive version of
distributed SGD can reach lower error values in less time compared to
non-adaptive implementations. Moreover, the results also show that the adaptive
version is communication-efficient, where the amount of communication required
between the master and the workers is less than that of non-adaptive versions.
