Faster Convergence of Stochastic Accelerated Gradient Descent under
  Interpolation
Aaron Mishkin Mert Pilanci Mark Schmidt
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.