Stronger generalization bounds for deep nets via a compression approach

Abstract

Deep nets generalize well despite having more parameters than the number of training samples. Recent works try to give an explanation using PAC-Bayes and Margin-based analyses, but do not as yet result in sample complexity bounds better than naive parameter counting. The current paper shows generalization bounds that're orders of magnitude better in practice. These rely upon new succinct reparametrizations of the trained net --- a compression that is explicit and efficient. These yield generalization bounds via a simple compression-based framework introduced here. Our results also provide some theoretical justification for widespread empirical success in compressing deep nets. Analysis of correctness of our compression relies upon some newly identified \textquotedblleft noise stability\textquotedblright properties of trained deep nets, which are also experimentally verified. The study of these properties and resulting generalization bounds are also extended to convolutional nets, which had eluded earlier attempts on proving generalization.

References in corpus (11)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• A Closer Look at Memorization in Deep Networks
• On the importance of single directions for generalization
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Spectrally-normalized margin bounds for neural networks
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Norm-Based Capacity Control in Neural Networks
• Hoeffding's inequality for sums of weakly dependent random variables

Cited by in corpus (48)

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Unsupervised Domain Adaptation through Self-Supervision
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Predicting the Generalization Gap in Deep Networks with Margin Distributions
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Environmental drivers of systematicity and generalization in a situated agent
• A Constructive Prediction of the Generalization Error Across Scales
• A Priori Estimates of the Population Risk for Residual Networks
• Approximation and Estimation for High-Dimensional Deep Learning Networks
• NICE: Noise Injection and Clamping Estimation for Neural Network Quantization
• Asymmetric Valleys: Beyond Sharp and Flat Local Minima
• On the Decision Boundary of Deep Neural Networks
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• Scaling Laws for Deep Learning
• Achieving Adversarial Robustness via Sparsity
• Generalization Bounds for Convolutional Neural Networks
• Wide-minima Density Hypothesis and the Explore-Exploit Learning Rate Schedule
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
• Minnorm training: an algorithm for training over-parameterized deep neural networks
• Pruning via Iterative Ranking of Sensitivity Statistics
• DNN or k-NN: That is the Generalize vs. Memorize Question
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Generalization Guarantees for Imitation Learning
• Layer-wise Learning of Stochastic Neural Networks with Information Bottleneck
• Interpreting Deep Learning: The Machine Learning Rorschach Test?
• Robustness to Augmentations as a Generalization metric
• Implicit Rugosity Regularization via Data Augmentation
• Stochastic Neural Network with Kronecker Flow
• Adversarial Parameter Defense by Multi-Step Risk Minimization
• A Deep Conditioning Treatment of Neural Networks
• A Limitation of the PAC-Bayes Framework
• Continual Learning from the Perspective of Compression
• Nonlinear Regression with a Convolutional Encoder-Decoder for Remote Monitoring of Surface Electrocardiograms
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Ranking Neural Checkpoints
• Gentle Local Robustness implies Generalization
• Revisiting hard thresholding for DNN pruning
• Adaptive Discriminative Regularization for Visual Classification
• The role of invariance in spectral complexity-based generalization bounds
• The Outer Product Structure of Neural Network Derivatives
• HALO: Learning to Prune Neural Networks with Shrinkage
• LRTuner: A Learning Rate Tuner for Deep Neural Networks
• Tangent Space Sensitivity and Distribution of Linear Regions in ReLU Networks
• Effect of Various Regularizers on Model Complexities of Neural Networks in Presence of Input Noise