  We show that asymptotically, completely asynchronous stochastic gradient
procedures achieve optimal (even to constant factors) convergence rates for the
solution of convex optimization problems under nearly the same conditions
required for asymptotic optimality of standard stochastic gradient procedures.
Roughly, the noise inherent to the stochastic approximation scheme dominates
any noise from asynchrony. We also give empirical evidence demonstrating the
strong performance of asynchronous, parallel stochastic optimization schemes,
demonstrating that the robustness inherent to stochastic approximation problems
allows substantially faster parallel and asynchronous solution methods.
