Convergence Analysis of Accelerated Stochastic Gradient Descent Under the Growth Condition
研究了强凸目标下加速随机梯度下降在增长条件（随机梯度方差受乘性噪声和加性常数约束）下的收敛性，分析了四种加速方法的表现，发现DAM+在强乘性噪声下仍能加速，并提出了尾平均方案使收敛速率接近理论下界。
We study the convergence of accelerated stochastic gradient descent (SGD) 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+). Although 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 with SGD), even under the growth condition. In particular, NAM, RMM, and iDAM+ enjoy acceleration only with a mild multiplicative noise, whereas 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.