  We present a generalization of Nesterov's accelerated gradient descent
algorithm. Our algorithm (AGNES) provably achieves acceleration for smooth
convex minimization tasks with noisy gradient estimates if the noise intensity
is proportional to the magnitude of the gradient. Nesterov's accelerated
gradient descent does not converge under this noise model if the constant of
proportionality exceeds one. AGNES fixes this deficiency and provably achieves
an accelerated convergence rate no matter how small the signal to noise ratio
in the gradient estimate. Empirically, we demonstrate that this is an
appropriate model for mini-batch gradients in overparameterized deep learning.
Finally, we show that AGNES outperforms stochastic gradient descent with
momentum and Nesterov's method in the training of CNNs.
