We consider stochastic optimization with delayed gradients where, at each
time step $t$, the algorithm makes an update using a stale stochastic gradient
from step $t - d_t$ for some arbitrary delay $d_t$. This setting abstracts
asynchronous distributed optimization where a central server receives gradient
updates computed by worker machines. These machines can experience computation
and communication loads that might vary significantly over time. In the general
non-convex smooth optimization setting, we give a simple and efficient
algorithm that requires $O( \sigma^2/\epsilon^4 + \tau/\epsilon^2 )$ steps for
finding an $\epsilon$-stationary point $x$, where $\tau$ is the \emph{average}
delay $\smash{\frac{1}{T}\sum_{t=1}^T d_t}$ and $\sigma^2$ is the variance of
the stochastic gradients. This improves over previous work, which showed that
stochastic gradient decent achieves the same rate but with respect to the
\emph{maximal} delay $\max_{t} d_t$, that can be significantly larger than the
average delay especially in heterogeneous distributed systems. Our experiments
demonstrate the efficacy and robustness of our algorithm in cases where the
delay distribution is skewed or heavy-tailed.

论文考虑带有延迟梯度的随机优化问题，在异步分布式优化中证明了一种简单有效的算法，它可以在统计学意义下达到最优结果。