We analyze the convergence of stochastic heavy ball (SHB) momentum in the smooth, strongly-convex setting. Kidambi et al. (2018) show that SHB (with small mini-batches) cannot attain an accelerated rate of convergence even for quadratics, and conjecture that the practical gain of SHB is a by-product of mini-batching. We substantiate this claim by showing that SHB can obtain an accelerated rate when the mini-batch size is larger than some threshold. In particular, for strongly-convex quadratics with condition number $\kappa$, we prove that SHB with the standard step-size and momentum parameters results in an $O\left(\exp(-\frac{T}{\sqrt{\kappa}}) + \sigma \right)$ convergence rate, where $T$ is the number of iterations and $\sigma^2$ is the variance in the stochastic gradients. To ensure convergence to the minimizer, we propose a multi-stage approach that results in a noise-adaptive $O\left(\exp\left(-\frac{T}{\sqrt{\kappa}} \right) + \frac{\sigma}{T}\right)$ rate. For general strongly-convex functions, we use the averaging interpretation of SHB along with exponential step-sizes to prove an $O\left(\exp\left(-\frac{T}{\kappa} \right) + \frac{\sigma^2}{T} \right)$ convergence to the minimizer in a noise-adaptive manner. Finally, we empirically demonstrate the effectiveness of the proposed algorithms.

我们在光滑、强凸的设置中分析了随机重球 (SHB) 动量的收敛性，证明了当小批量大小大于某个阈值时，SHB 可以获得加速收敛率。特别地，在具有条件数κ的强凸二次函数中，SHB 伴随标准步长和动量参数具有 O( exp(-T/√κ) + σ ) 收敛率，其中 T 是迭代次数，σ^2 是随机梯度的方差。为了确保收敛到最小值，我们提出了一种多阶段方法，得到了一种噪声自适应的 O( exp(-T/√κ) + σ/T ) 收敛率。对于一般的强凸函数，我们利用 SHB 的均值解释和指数步长证明了一种噪声自适应的 O( exp(-T/κ) + σ^2/T ) 最小值收敛率。最后，我们实证了所提出算法的有效性。

噪声适应（加速的）随机重球动量