Heavy-ball momentum with decaying learning rates is widely used with SGD for optimizing deep learning models. In contrast to its empirical popularity, the understanding of its theoretical property is still quite limited, especially under the standard anisotropic gradient noise condition for quadratic regression problems. Although it is widely conjectured that heavy-ball momentum method can provide accelerated convergence and should work well in large batch settings, there is no rigorous theoretical analysis. In this paper, we fill this theoretical gap by establishing a non-asymptotic convergence bound for stochastic heavy-ball methods with step decay scheduler on quadratic objectives, under the anisotropic gradient noise condition. As a direct implication, we show that heavy-ball momentum can provide $\tilde{\mathcal{O}}(\sqrt{\kappa})$ accelerated convergence of the bias term of SGD while still achieving near-optimal convergence rate with respect to the stochastic variance term. The combined effect implies an overall convergence rate within log factors from the statistical minimax rate. This means SGD with heavy-ball momentum is useful in the large-batch settings such as distributed machine learning or federated learning, where a smaller number of iterations can significantly reduce the number of communication rounds, leading to acceleration in practice.

本文通过建立随机重球方法在二次目标函数和异性梯度噪声条件下的非渐近收敛界，证明了重球动量可以在 SGD 的偏差项上提供加速收敛，同时与随机方差项相比，仍然能够实现接近最优的收敛速度，从而在统计极小化速度的对数因素范围内整体收敛，该结果意味着带有重球动量的 SGD 在大批量设置中（例如分布式机器学习或联邦学习）中非常有用，其中更少的迭代次数可以显著减少通信轮数，进而加速实践计算。

具向异性梯度噪声的随机重力球法加速收敛