Non-vacuous Generalization Bounds at the ImageNet Scale: a PAC-Bayesian Compression Approach

By Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, Peter Orbanz. 2018

236 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Efficiency & Compression, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Efficiency & Compression

In Statistical Learning Theory

Citations in the corpus

The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks (2018, background): “We can study why randomly-initialized feed-forward networks seem to contain winning tickets and potential implications for theoretical study of generalization (Zhou et al., 2018; Arora et al., 2018) and optimization (Anonymous, 2019a).”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “Dziugaite & Roy (2017); Zhou et al. (2019) used the PAC-Bayes approach to compute non-vacuous generalization bounds for MNIST and ImageNet, respectively.”
Information-Theoretic Local Minima Characterization and Regularization (2019, methodology): “…DNNs have been proposed based on norm, margin, Lipschitz constant, compression and robustness (Bartlett & Mendelson, 2002; Neyshabur et al., 2015b; Sokoli ´ c et al., 2017; Xu & Mannor, 2012; Bartlett et al., 2017; Zhou et al., 2019; Dziugaite & Roy, 2017; Arora et al., 2018; Jiang et al., 2019).”
Probabilistic Symmetries and Invariant Neural Networks (2020, methodology): “Weight-sharing might be viewed as a form of pre-training compression; recent work uses PAC-Bayes theory to demonstrate the benefits of compressibility of trained networks (Arora et al., 2018; Zhou et al., 2019), and Lyle et al.”
Asymmetric Valleys: Beyond Sharp and Flat Local Minima (2019, background): “Discussions on the generalization bound of neural networks can be found in [6, 39, 37, 31, 38, 4, 52].”
The Effect of Network Width on Stochastic Gradient Descent and Generalization: an Empirical Study (2019, background): “…bounds are usually too loose for practical tasks (Harvey et al., 2017; Neyshabur et al., 2017; Bartlett et al., 2017; Dziugaite & Roy, 2017; Zhou et al., 2018; Nagarajan & Kolter, 2018), and practical approaches to hyper-parameter optimization are often developed in an ad-hoc fashion…”
Understanding Generalization through Visualizations (2019, background): “n that depends on the training data, as opposed to a learned single predictor. These bounds often yield sample complexity bounds worse than naive parameter counting, however (Dziugaite and Roy, 2017; Zhou et al., 2018) show that PAC-Bayes theory does provide meaningful generalization bounds for “ﬂat”
Uniform convergence may be unable to explain generalization in deep learning (2019, background): “The ones that are small for realistic dataset sizes hold either only on a compressed network (Arora et al., 2018) or a stochastic network (Langford & Caruana, 2001) or a network that has been further modified via optimization or more than one of the above (Dziugaite & Roy, 2017; Zhou et al., 2019).”
What Do Compressed Deep Neural Networks Forget (2019, background): “Zhou et al. (2019) conduct an experiment which shows that networks which are pruned subsequent to training are more sensitive to the corruption of labels at training time.”
The intriguing role of module criticality in the generalization of deep networks (2019, methodology): “…(Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et al., 2019; Long & Sedghi, 2019; Wei & Ma, 2019), or they use approaches similar to PAC-Bayes (McAllester, 1999; Dziugaite & Roy, 2017; Neyshabur et al., 2017; 2018; Arora et al., 2018; Nagarajan & Kolter, 2019a; Zhou et al., 2019).”
On Warm-Starting Neural Network Training (2019, background): “These articles have investigated generalization by studying classifier margin [38, 39], loss geometry [40, 19, 41], and measurements of complexity [42, 43], sensitivity [44], or compressiblity [45].”
Are All Layers Created Equal? (2019, methodology): “Moreover, by tweaking existing analyses with additional whole-layer robustness condition, some PAC-Bayes based bounds can also be potentially improved (Wang et al., 2018; Arora et al., 2018; Zhou et al., 2019).”
User-friendly introduction to PAC-Bayes bounds (2021, background): “Indeed, since then, a wide range of papers, from very theoretical to very computational, studied PAC-Bayes bounds for deep networks [125, 147, 208, 118, 195, 112, 190, 31, 75, 156, 185, 157, 57, 104, 181].”