Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience

By Vaishnavh Nagarajan, J. Kolter. 2019

105 citations recorded by the source corpus.

The ability of overparameterized deep networks to generalize well has been linked to the fact that stochastic gradient descent (SGD) finds solutions that lie in flat, wide minima in the training loss -- minima where the output of the network is resilient to small random noise added to its parameters. So far this observation has been used to provide generalization guarantees only for neural networks whose parameters are either \textit{stochastic} or \textit{compressed}. In this work, we present a general PAC-Bayesian framework that leverages this observation to provide a bound on the original network learned -- a network that is deterministic and uncompressed. What enables us to do this is a key novelty in our approach: our framework allows us to show that if on training data, the interactions between the weight matrices satisfy certain conditions that imply a wide training loss minimum, these conditions themselves {\em generalize} to the interactions between the matrices on test data, thereby implying a wide test loss minimum. We then apply our general framework in a setup where we assume that the pre-activation values of the network are not too small (although we assume this only on the training data). In this setup, we provide a generalization guarantee for the original (deterministic, uncompressed) network, that does not scale with product of the spectral norms of the weight matrices -- a guarantee that would not have been possible with prior approaches.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Probabilistic & Bayesian Methods, 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 Probabilistic & Bayesian Methods

In Statistical Learning Theory

Citations in the corpus

Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, methodology): “See also [43] for improvements via leveraging various properties of the inter-layer Jacobian and [39] for results with convolutional networks.”
Fantastic Generalization Measures and Where to Find Them (2019, methodology): “The empirically motivated measures from prior literature that we consider are based on sharpness measure (Keskar et al., 2016); Fisher-Rao measure (Liang et al., 2017); distance of trained weights from initialization (Nagarajan and Kolter, 2019b) and path norm (Neyshabur et al., 2015a).”
Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss (2019, background): “The theoretical understanding of data-dependent regularizers is sparse (see [57, 43, 2] for a few recent works.”
The Implicit and Explicit Regularization Effects of Dropout (2020, background): “Recent works (Arora et al., 2018; Nagarajan & Kolter, 2019; Wei & Ma, 2019a,b) support our stability-based regularization by bounding generalization of the model in terms of its Jacobian norms on the training data.”
On Measuring Excess Capacity in Neural Networks (2022, methodology): “[35] Vaishnavh Nagarajan and Zico Kolter.”
Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin (2019, methodology): “Our bound considers the Jacobian norms, hidden layer norms, and output margin on the training data, and avoids the exponential depth dependency when these quantities are well-behaved, as is the case in practice [Arora et al., 2018, Nagarajan and Kolter, 2019, Wei and Ma, 2019].”
The Effect of Network Width on Stochastic Gradient Descent and Generalization: an Empirical Study (2019, background): “…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 (Sculley et al., 2018).”
Uniform convergence may be unable to explain generalization in deep learning (2019, background): “One might then wonder if such a bound could be extended to the original classifier, like it was explored in Nagarajan & Kolter (2019) for deep networks.”
Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation (2019, methodology): “However, it is not obvious how to adapt the argument of Nagarajan & Kolter (2019) to activation functions whose derivatives are not piecewise-constant.”
The intriguing role of module criticality in the generalization of deep networks (2019, methodology): “Recently authors have emphasized on the role of distance to initialization rather than norm of the weights in generalization (Dziugaite & Roy, 2017; Nagarajan & Kolter, 2019b; Neyshabur et al., 2019; Long & Sedghi, 2019).”