  This paper presents a sufficient condition for stochastic gradients not to
slow down the convergence of Nesterov's accelerated gradient method. The new
condition has the strong-growth condition by Schmidt \& Roux as a special case,
and it also allows us to (i) model problems with constraints and (ii) design
new types of oracles (e.g., oracles for finite-sum problems such as SAGA). Our
results are obtained by revisiting Nesterov's accelerated algorithm and are
useful for designing stochastic oracles without changing the underlying
first-order method.
