We prove new convergence rates for a generalized version of stochastic
Nesterov acceleration under interpolation conditions. Unlike previous analyses,
our approach accelerates any stochastic gradient method which makes sufficient
progress in expectation. The proof, which proceeds using the estimating
sequences framework, applies to both convex and strongly convex functions and
is easily specialized to accelerated SGD under the strong growth condition. In
this special case, our analysis reduces the dependence on the strong growth
constant from $\rho$ to $\sqrt{\rho}$ as compared to prior work. This
improvement is comparable to a square-root of the condition number in the worst
case and address criticism that guarantees for stochastic acceleration could be
worse than those for SGD.

我们在插值条件下证明了随机 Nesterov 加速的新的收敛速度。不同于以往的分析，我们的方法可以加速任何在期望中取得足够进展的随机梯度方法。证明使用估计序列框架进行，适用于凸函数和强凸函数，并且可以轻松推广到满足强生长条件的加速 SGD。在这种特殊情况下，我们的分析将强生长常数的依赖性从 ρ 减小到√ρ，相对于以前的工作来说，这一改进相当于最坏情况下条件数的平方根，并解决了对于随机加速的保证可能不如 SGD 的批评。