  We analyze the convergence of gradient-based optimization algorithms that
base their updates on delayed stochastic gradient information. The main
application of our results is to the development of gradient-based distributed
optimization algorithms where a master node performs parameter updates while
worker nodes compute stochastic gradients based on local information in
parallel, which may give rise to delays due to asynchrony. We take motivation
from statistical problems where the size of the data is so large that it cannot
fit on one computer; with the advent of huge datasets in biology, astronomy,
and the internet, such problems are now common. Our main contribution is to
show that for smooth stochastic problems, the delays are asymptotically
negligible and we can achieve order-optimal convergence results. In application
to distributed optimization, we develop procedures that overcome communication
bottlenecks and synchronization requirements. We show $n$-node architectures
whose optimization error in stochastic problems---in spite of asynchronous
delays---scales asymptotically as $\order(1 / \sqrt{nT})$ after $T$ iterations.
This rate is known to be optimal for a distributed system with $n$ nodes even
in the absence of delays. We additionally complement our theoretical results
with numerical experiments on a statistical machine learning task.
