# Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks

arXiv: https://arxiv.org/abs/2106.03795 · HTML: https://mlsanity.com/paper/2106.03795/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 69 references that are in the map.
- First posted on arXiv 7 Jun 2021.

## Builds on (most cited first, 30 of 41)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [Channel Pruning for Accelerating Very Deep Neural Networks](https://mlsanity.com/paper/1707.06168/) (2017)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Comparing Rewinding and Fine-tuning in Neural Network Pruning](https://mlsanity.com/paper/2003.02389/) (2020)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learning](https://mlsanity.com/paper/2010.05627/) (2020)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Mean Field Analysis of Neural Networks: A Central Limit Theorem](https://mlsanity.com/paper/1808.09372/) (2018)
- [Traditional and Heavy-Tailed Self Regularization in Neural Network Models](https://mlsanity.com/paper/1901.08276/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [A Rigorous Framework for the Mean Field Limit of Multilayer Neural Networks](https://mlsanity.com/paper/2001.11443/) (2020)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [An Overview of Neural Network Compression](https://mlsanity.com/paper/2006.03669/) (2020)
- [On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks](https://mlsanity.com/paper/1912.00018/) (2019)

## Built on by (most cited first, 30 of 44)

- [Structured Pruning for Deep Convolutional Neural Networks: A survey](https://mlsanity.com/paper/2303.00566/) (2023)
- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [AlphaPruning: Using Heavy-Tailed Self Regularization Theory for Improved Layer-wise Pruning of Large Language Models](https://mlsanity.com/paper/2410.10912/) (2024)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)
- [Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions](https://mlsanity.com/paper/2301.11885/) (2023)
- [Generalization Bounds with Data-dependent Fractal Dimensions](https://mlsanity.com/paper/2302.02766/) (2023)
- [A Three-regime Model of Network Pruning](https://mlsanity.com/paper/2305.18383/) (2023)
- [Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning](https://mlsanity.com/paper/2206.02604/) (2022)
- [Deep neural networks with dependent weights: Gaussian Process mixture limit, heavy tails, sparsity and compressibility](https://mlsanity.com/paper/2205.08187/) (2022)
- [Dimensionality Reduced Training by Pruning and Freezing Parts of a Deep Neural Network, a Survey](https://mlsanity.com/paper/2205.08099/) (2022)
- [Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares](https://mlsanity.com/paper/2206.01274/) (2022)
- [Minimum Description Length and Generalization Guarantees for Representation Learning](https://mlsanity.com/paper/2402.03254/) (2024)
- [Model Balancing Helps Low-data Training and Fine-tuning](https://mlsanity.com/paper/2410.12178/) (2024)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networks](https://mlsanity.com/paper/2406.04657/) (2024)
- [Heavy-Tailed Regularization of Weight Matrices in Deep Neural Networks](https://mlsanity.com/paper/2304.02911/) (2023)
- [Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry](https://mlsanity.com/paper/2410.15637/) (2024)
- [Heavy-Tail Phenomenon in Decentralized SGD](https://mlsanity.com/paper/2205.06689/) (2022)
- [Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD](https://mlsanity.com/paper/2306.08125/) (2023)
- [Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tails](https://mlsanity.com/paper/2405.17529/) (2024)
- [Generalization Guarantees via Algorithm-dependent Rademacher Complexity](https://mlsanity.com/paper/2307.02501/) (2023)
- [Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent](https://mlsanity.com/paper/2310.18455/) (2023)
- [Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clipping](https://mlsanity.com/paper/2403.02051/) (2024)
- [Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrization](https://mlsanity.com/paper/2507.09093/) (2025)
- [ARA: Adaptive Rank Allocation for Efficient Large Language Model SVD Compression](https://mlsanity.com/paper/2510.19389/) (2025)
- [Cyclic and Randomized Stepsizes Invoke Heavier Tails in SGD than Constant Stepsize](https://mlsanity.com/paper/2302.05516/) (2023)
- [Tighter Generalisation Bounds via Interpolation](https://mlsanity.com/paper/2402.05101/) (2024)
- [Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priors](https://mlsanity.com/paper/2502.15540/) (2025)

## Abstract (arXiv)

Neural network compression techniques have become increasingly popular as they can drastically reduce the storage and computation requirements for very large networks. Recent empirical studies have illustrated that even simple pruning strategies can be surprisingly effective, and several theoretical studies have shown that compressible networks (in specific senses) should achieve a low generalization error. Yet, a theoretical characterization of the underlying cause that makes the networks amenable to such simple compression schemes is still missing. In this study, we address this fundamental question and reveal that the dynamics of the training algorithm has a key role in obtaining such compressible networks. Focusing our attention on stochastic gradient descent (SGD), our main contribution is to link compressibility to two recently established properties of SGD: (i) as the network size goes to infinity, the system can converge to a mean-field limit, where the network weights behave independently, (ii) for a large step-size/batch-size ratio, the SGD iterates can converge to a heavy-tailed stationary distribution. In the case where these two phenomena occur simultaneously, we prove that the networks are guaranteed to be 'ℓp-compressible', and the compression errors of different pruning techniques (magnitude, singular value, or node pruning) become arbitrarily small as the network size increases. We further prove generalization bounds adapted to our theoretical framework, which indeed confirm that the generalization error will be lower for more compressible networks. Our theory and numerical study on various neural networks show that large step-size/batch-size ratios introduce heavy-tails, which, in combination with overparametrization, result in compressibility.