Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach

Abstract

Modern neural networks are highly overparameterized, with capacity to substantially overfit to training data. Nevertheless, these networks often generalize well in practice. It has also been observed that trained networks can often be "compressed" to much smaller representations. The purpose of this paper is to connect these two empirical observations. Our main technical result is a generalization bound for compressed networks based on the compressed size. Combined with off-the-shelf compression algorithms, the bound leads to state of the art generalization guarantees; in particular, we provide the first non-vacuous generalization guarantees for realistic architectures applied to the ImageNet classification problem. As additional evidence connecting compression and generalization, we show that compressibility of models that tend to overfit is limited: We establish an absolute limit on expected compressibility as a function of expected generalization error, where the expectations are over the random choice of training examples. The bounds are complemented by empirical results that show an increase in overfitting implies an increase in the number of bits required to describe a trained network.

16 pages, 1 figure. Accepted at ICLR 2019

References in corpus (7)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications
• The Marginal Value of Adaptive Gradient Methods in Machine Learning
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• A PAC-Bayesian Tutorial with A Dropout Bound

Cited by in corpus (55)

• The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Are All Layers Created Equal?
• What Do Compressed Deep Neural Networks Forget?
• User-friendly introduction to PAC-Bayes bounds
• On Warm-Starting Neural Network Training
• Identity Crisis: Memorization and Generalization under Extreme Overparameterization
• Generalization Bounds via Information Density and Conditional Information Density
• Asymmetric Valleys: Beyond Sharp and Flat Local Minima
• Entropic gradient descent algorithms and wide flat minima
• Rethinking Parameter Counting in Deep Models: Effective Dimensionality Revisited
• Understanding Generalization through Visualizations
• How does Weight Correlation Affect the Generalisation Ability of Deep Neural Networks
• On the Benefits of Invariance in Neural Networks
• The intriguing role of module criticality in the generalization of deep networks
• Dissecting Hessian: Understanding Common Structure of Hessian in Neural Networks
• Understanding Generalization in Deep Learning via Tensor Methods
• Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network
• Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks
• Robustness to Pruning Predicts Generalization in Deep Neural Networks
• For self-supervised learning, Rationality implies generalization, provably
• PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
• Spectral Pruning: Compressing Deep Neural Networks via Spectral Analysis and its Generalization Error
• PAC-Bayes Bounds for Meta-learning with Data-Dependent Prior
• Neural Complexity Measures
• Norm-based generalisation bounds for multi-class convolutional neural networks
• Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks
• Scaling Up Exact Neural Network Compression by ReLU Stability
• Information-Theoretic Local Minima Characterization and Regularization
• Does the Data Induce Capacity Control in Deep Learning?
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
• Train Flat, Then Compress: Sharpness-Aware Minimization Learns More Compressible Models
• How Tight Can PAC-Bayes be in the Small Data Regime?
• RATT: Leveraging Unlabeled Data to Guarantee Generalization
• PAC-Bayesian Transportation Bound
• Uniform Convergence, Adversarial Spheres and a Simple Remedy
• Comparing Comparators in Generalization Bounds
• Gentle Local Robustness implies Generalization
• Dissecting Non-Vacuous Generalization Bounds based on the Mean-Field Approximation
• Explaining generalization in deep learning: progress and fundamental limits
• The role of invariance in spectral complexity-based generalization bounds
• Information-Theoretic Understanding of Population Risk Improvement with Model Compression
• Generalisation in fully-connected neural networks for time series forecasting
• Semantically Robust Unpaired Image Translation for Data with Unmatched Semantics Statistics
• Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets
• Deep Networks as Logical Circuits: Generalization and Interpretation
• Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• A Revision of Neural Tangent Kernel-based Approaches for Neural Networks
• Compression Implies Generalization
• Notes on Deep Learning Theory
• Maximum Multiscale Entropy and Neural Network Regularization
• A note on regularised NTK dynamics with an application to PAC-Bayesian training
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD
• A Probabilistic Approach to Neural Network Pruning