A recent line of empirical studies has demonstrated that SGD might exhibit a heavy-tailed behavior in practical settings, and the heaviness of the tails might correlate with the overall performance. In this paper, we investigate the emergence of such heavy tails. Previous works on this problem only considered, up to our knowledge, online (also called single-pass) SGD, in which the emergence of heavy tails in theoretical findings is contingent upon access to an infinite amount of data. Hence, the underlying mechanism generating the reported heavy-tailed behavior in practical settings, where the amount of training data is finite, is still not well-understood. Our contribution aims to fill this gap. In particular, we show that the stationary distribution of offline (also called multi-pass) SGD exhibits 'approximate' power-law tails and the approximation error is controlled by how fast the empirical distribution of the training data converges to the true underlying data distribution in the Wasserstein metric. Our main takeaway is that, as the number of data points increases, offline SGD will behave increasingly 'power-law-like'. To achieve this result, we first prove nonasymptotic Wasserstein convergence bounds for offline SGD to online SGD as the number of data points increases, which can be interesting on their own. Finally, we illustrate our theory on various experiments conducted on synthetic data and neural networks.

我们研究了随机梯度下降（SGD）在实际环境中可能展现出重尾行为，并且尾部的重度可能与整体性能有相关性。我们的贡献在于填补了单次通过（online）SGD和多次通过（offline）SGD之间在实际数据量有限情况下，生成重尾行为的机制仍不够清楚的空白。我们证明了离线SGD的稳态分布呈现了“近似”的幂律尾，并且近似误差由训练数据的经验分布在Wasserstein距离下收敛于真实潜在数据分布的速度所控制。随着数据点数量的增加，离线SGD行为将越来越类似于幂律分布。

离线（多通道）随机梯度下降法中的近似重尾问题