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

Abstract

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.

Published as a conference paper at ICLR 2019

Cited by in corpus (29)

• Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss
• Fantastic Generalization Measures and Where to Find Them
• Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Lost in Pruning: The Effects of Pruning Neural Networks beyond Test Accuracy
• The Implicit and Explicit Regularization Effects of Dropout
• How does Weight Correlation Affect the Generalisation Ability of Deep Neural Networks
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• The intriguing role of module criticality in the generalization of deep networks
• Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network
• Evaluation of Complexity Measures for Deep Learning Generalization in Medical Image Analysis
• Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks
• PAC-Bayes Bounds for Meta-learning with Data-Dependent Prior
• De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictors
• Norm-based generalisation bounds for multi-class convolutional neural networks
• Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
• RATT: Leveraging Unlabeled Data to Guarantee Generalization
• Stable Rank Normalization for Improved Generalization in Neural Networks and GANs
• PAC-Bayesian Transportation Bound
• Uniform Convergence, Adversarial Spheres and a Simple Remedy
• Explaining generalization in deep learning: progress and fundamental limits
• Learning Augmentation Distributions using Transformed Risk Minimization
• Compression Implies Generalization
• Identifying and Exploiting Structures for Reliable Deep Learning
• Ridgeless Interpolation with Shallow ReLU Networks in $1D$ is Nearest Neighbor Curvature Extrapolation and Provably Generalizes on Lipschitz Functions
• Using noise resilience for ranking generalization of deep neural networks
• From deep to Shallow: Equivalent Forms of Deep Networks in Reproducing Kernel Krein Space and Indefinite Support Vector Machines
• The Probabilistic Fault Tolerance of Neural Networks in the Continuous Limit