Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks

Abstract

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 '${\ell }_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.

References in corpus (11)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Channel Pruning for Accelerating Very Deep Neural Networks
• Comparing Rewinding and Fine-tuning in Neural Network Pruning
• Traditional and Heavy-Tailed Self Regularization in Neural Network Models
• Multiplicative noise and heavy tails in stochastic optimization
• On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks
• Generalization bounds via distillation
• Quantitative Propagation of Chaos for SGD in Wide Neural Networks
• Robustness to Pruning Predicts Generalization in Deep Neural Networks
• Compressing Heavy-Tailed Weight Matrices for Non-Vacuous Generalization Bounds

Cited by in corpus (1)

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