  It has been experimentally observed that the efficiency of distributed
training with stochastic gradient (SGD) depends decisively on the batch size
and -- in asynchronous implementations -- on the gradient staleness.
Especially, it has been observed that the speedup saturates beyond a certain
batch size and/or when the delays grow too large. We identify a data-dependent
parameter that explains the speedup saturation in both these settings. Our
comprehensive theoretical analysis, for strongly convex, convex and non-convex
settings, unifies and generalized prior work directions that often focused on
only one of these two aspects. In particular, our approach allows us to derive
improved speedup results under frequently considered sparsity assumptions. Our
insights give rise to theoretically based guidelines on how the learning rates
can be adjusted in practice. We show that our results are tight and illustrate
key findings in numerical experiments.
