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

Abstract

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.

arXiv commentIn Neural Information Processing Systems (NeurIPS), Spotlight Presentation, 2023

References in corpus (11)

• Statistical Aspects of Wasserstein Distances
• The Heavy-Tail Phenomenon in SGD
• Multiplicative noise and heavy tails in stochastic optimization
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks
• Strength of Minibatch Noise in SGD
• Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
• Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions
• Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares