Compressing Heavy-Tailed Weight Matrices for Non-Vacuous Generalization Bounds

Abstract

Heavy-tailed distributions have been studied in statistics, random matrix theory, physics, and econometrics as models of correlated systems, among other domains. Further, heavy-tail distributed eigenvalues of the covariance matrix of the weight matrices in neural networks have been shown to empirically correlate with test set accuracy in several works (e.g. arXiv:1901.08276), but a formal relationship between heavy-tail distributed parameters and generalization bounds was yet to be demonstrated. In this work, the compression framework of arXiv:1802.05296 is utilized to show that matrices with heavy-tail distributed matrix elements can be compressed, resulting in networks with sparse weight matrices. Since the parameter count has been reduced to a sum of the non-zero elements of sparse matrices, the compression framework allows us to bound the generalization gap of the resulting compressed network with a non-vacuous generalization bound. Further, the action of these matrices on a vector is discussed, and how they may relate to compression and resilient classification is analyzed.

References in corpus (16)

• An overview of gradient descent optimization algorithms
• Wide Residual Networks
• Understanding deep learning requires rethinking generalization
• Powerlaw: a Python package for analysis of heavy-tailed distributions
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Spectrally-normalized margin bounds for neural networks
• Fantastic Generalization Measures and Where to Find Them
• Predicting the Generalization Gap in Deep Networks with Margin Distributions
• On the top eigenvalue of heavy-tailed random matrices
• Sharpness-Aware Minimization for Efficiently Improving Generalization
• Level statistics and localization transitions of Lévy matrices
• The Heavy-Tail Phenomenon in SGD
• Multiplicative noise and heavy tails in stochastic optimization
• Bayesian Neural Network Priors Revisited
• On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks
• Heavy-Tailed Universality Predicts Trends in Test Accuracies for Very Large Pre-Trained Deep Neural Networks

Cited by in corpus (2)

• Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks
• Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD