  We study the convergence of accelerated stochastic gradient descent for
strongly convex objectives under the growth condition, which states that the
variance of stochastic gradient is bounded by a multiplicative part that grows
with the full gradient, and a constant additive part. Through the lens of the
growth condition, we investigate four widely used accelerated methods:
Nesterov's accelerated method (NAM), robust momentum method (RMM), accelerated
dual averaging method (DAM+), and implicit DAM+ (iDAM+). While these methods
are known to improve the convergence rate of SGD under the condition that the
stochastic gradient has bounded variance, it is not well understood how their
convergence rates are affected by the multiplicative noise. In this paper, we
show that these methods all converge to a neighborhood of the optimum with
accelerated convergence rates (compared to SGD) even under the growth
condition. In particular, NAM, RMM, iDAM+ enjoy acceleration only with a mild
multiplicative noise, while DAM+ enjoys acceleration even with a large
multiplicative noise. Furthermore, we propose a generic tail-averaged scheme
that allows the accelerated rates of DAM+ and iDAM+ to nearly attain the
theoretical lower bound (up to a logarithmic factor in the variance term). We
conduct numerical experiments to support our theoretical conclusions.
