Stronger generalization bounds for deep nets via a compression approach

By Sanjeev Arora, Rong Ge, Behnam Neyshabur, Yi Zhang. 2018

714 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Scaling & 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 Scaling & Learning Theory

Citations in the corpus

A Constructive Prediction of the Generalization Error Across Scales (2019, background): “Theoretical error bounds: Much attention has been given to theoretical explanations of the generalization capabilities of deep neural networks (Neyshabur et al., 2017a;b; Allen-Zhu et al., 2018a;b; Arora et al., 2018).”
Environmental drivers of systematicity and generalization in a situated agent (2019, background): “…on the desired level of explanation, such a question may ultimately be resolved by promising theoretical analyses of neural net generalization (Arora et al., 2018; Lampinen & Ganguli, 2018; Allen-Zhu et al., 2018; Arora et al., 2019), and some more general intuitions can be gleaned from…”
Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuning (2020, methodology): “By applying standard compression based generalization bounds, we can provide theoretical backing to the empirical connection between intrinsic dimension and generalization (Arora et al., 2018).”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, methodology): “Related, [5] leverages compression techniques for constructing tighter bounds.”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “In fact, empirical observations have been made and connected to generalization in [22, 1].”
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).”
PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, background): “This can partially explain their impressive generalization properties despite being substantially overparameterized (Arora et al., 2018).”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “A line of research proposed norm-based (e.g. Bartlett et al. (2017a)) and compression-based bounds (Arora et al., 2018).”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “Several works [6, 11, 24, 39] explain generalization by studying some other “complexity” of the learned networks.”
There Are Many Consistent Explanations of Unlabeled Data: Why You Should Average (2018, background): “Neural networks in general are known to be resilient to noise, explaining why both MT, Π and supervised models are flat along random directions (Arora et al., 2018).”
Task2Vec: Task Embedding for Meta-Learning (2019, background): “FIM has also been proposed for various regularization schemes [5, 8, 22, 27], to analyze learning dynamics of deep networks [4], and to overcome catastrophic forgetting [19].”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…Anthony and Bartlett, 2009), a vast literature have recently studied the connection between the generalization performance of deep neural networks and their architectures (Neyshabur et al., 2015, 2017a,b; Bartlett et al., 2017; Golowich et al., 2017; Arora et al., 2018c; Allen-Zhu et al., 2018a).”
Fantastic Generalization Measures and Where to Find Them (2019, background): “…have attempted to understand the generalization phenomenon in deep models from a theoretical perspective e.g. (Neyshabur et al., 2015b; Bartlett et al., 2017; Neyshabur et al., 2018a; Golowich et al., 2017; Arora et al., 2018; Nagarajan and Kolter, 2019a; Wei and Ma, 2019a; Long and Sedghi, 2019).”
The Description Length of Deep Learning models (2018, background): “Speciﬁcally for deep learning, (Arora et al., 2018) showed that compression leads to generalization bounds (see also (Dziugaite and Roy, 2017)).”
Compressing BERT: Studying the Effects of Weight Pruning on Transfer Learning (2020, background): “Interestingly, recent work used compression not to induce simplicity but to measure it (Arora et al., 2018).”
An analytic theory of generalization dynamics and transfer learning in deep linear networks (2018, background): “…theories that upper bound generalization error (Bartlett & Mendelson, 2002; Neyshabur et al., 2015; Dziugaite & Roy, 2017; Golowich et al., 2017; Neyshabur et al., 2017; Bartlett et al., 2017; Arora et al., 2018, e.g) in terms of various measures of network complexity yield very loose bounds.”
SNIP: Single-shot Network Pruning based on Connection Sensitivity (2018, methodology): “We would like to clarify that the above criterion (Equation 6) is different from the criteria used in early works by Mozer & Smolensky (1989) or Karnin (1990) which do not entirely capture the (1)Multiplicative coefficients (similar to c) were also used for subset regression in Breiman (1995).”
Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks (2018, background): “Neyshabur et al. [20], Keskar et al. [11], Neyshabur et al. [22], Bartlett et al. [4], Neyshabur et al. [23], Golowich et al. [7] and Arora et al. [1] suggested different norm, margin and sharpness based measures, to measure the capacity of neural networks, in an attempt to explain the…”