  Stochastic Gradient Descent (SGD) is very useful in optimization problems
with high-dimensional non-convex target functions, and hence constitutes an
important component of several Machine Learning and Data Analytics methods.
Recently there have been significant works on understanding the parallelism
inherent to SGD, and its convergence properties. Asynchronous, parallel SGD
(AsyncPSGD) has received particular attention, due to observed performance
benefits. On the other hand, asynchrony implies inherent challenges in
understanding the execution of the algorithm and its convergence, stemming from
the fact that the contribution of a thread might be based on an old (stale)
view of the state. In this work we aim to deepen the understanding of AsyncPSGD
in order to increase the statistical efficiency in the presence of stale
gradients. We propose new models for capturing the nature of the staleness
distribution in a practical setting. Using the proposed models, we derive a
staleness-adaptive SGD framework, MindTheStep-AsyncPSGD, for adapting the step
size in an online-fashion, which provably reduces the negative impact of
asynchrony. Moreover, we provide general convergence time bounds for a wide
class of staleness-adaptive step size strategies for convex target functions.
We also provide a detailed empirical study, showing how our approach implies
faster convergence for deep learning applications.
