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 行为将越来越类似于幂律分布。

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

Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient  Descent

Gradient clipping is a commonly used technique to stabilize the training
process of neural networks. A growing body of studies has shown that gradient
clipping is a promising technique for dealing with the heavy-tailed behavior
that emerged in stochastic optimization as well. While gradient clipping is
significant, its theoretical guarantees are scarce. Most theoretical guarantees
only provide an in-expectation analysis and only focus on optimization
performance. In this paper, we provide high probability analysis in the
non-convex setting and derive the optimization bound and the generalization
bound simultaneously for popular stochastic optimization algorithms with
gradient clipping, including stochastic gradient descent and its variants of
momentum and adaptive stepsizes. With the gradient clipping, we study a
heavy-tailed assumption that the gradients only have bounded $\alpha$-th
moments for some $\alpha \in (1, 2]$, which is much weaker than the standard
bounded second-moment assumption. Overall, our study provides a relatively
complete picture for the theoretical guarantee of stochastic optimization
algorithms with clipping.

使用梯度裁剪技术在随机优化算法中研究梯度的截尾行为和其理论保证。