Generalization bounds for deep learning

Abstract

Generalization in deep learning has been the topic of much recent theoretical and empirical research. Here we introduce desiderata for techniques that predict generalization errors for deep learning models in supervised learning. Such predictions should 1) scale correctly with data complexity; 2) scale correctly with training set size; 3) capture differences between architectures; 4) capture differences between optimization algorithms; 5) be quantitatively not too far from the true error (in particular, be non-vacuous); 6) be efficiently computable; and 7) be rigorous. We focus on generalization error upper bounds, and introduce a categorisation of bounds depending on assumptions on the algorithm and data. We review a wide range of existing approaches, from classical VC dimension to recent PAC-Bayesian bounds, commenting on how well they perform against the desiderata. We next use a function-based picture to derive a marginal-likelihood PAC-Bayesian bound. This bound is, by one definition, optimal up to a multiplicative constant in the asymptotic limit of large training sets, as long as the learning curve follows a power law, which is typically found in practice for deep learning problems. Extensive empirical analysis demonstrates that our marginal-likelihood PAC-Bayes bound fulfills desiderata 1-3 and 5. The results for 6 and 7 are promising, but not yet fully conclusive, while only desideratum 4 is currently beyond the scope of our bound. Finally, we comment on why this function-based bound performs significantly better than current parameter-based PAC-Bayes bounds.

References in corpus (39)

• MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Reconciling modern machine learning practice and the bias-variance trade-off
• Scaling Laws for Neural Language Models
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Robustness of a Network of Networks
• Deep Learning Scaling is Predictable, Empirically
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Bayesian Deep Learning and a Probabilistic Perspective of Generalization
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Fantastic Generalization Measures and Where to Find Them
• Scaling Laws for Autoregressive Generative Modeling
• Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes
• Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes
• Predicting the Generalization Gap in Deep Networks with Margin Distributions
• Uniform convergence may be unable to explain generalization in deep learning
• Deep learning generalizes because the parameter-function map is biased towards simple functions
• The arrival of the frequent: how bias in genotype-phenotype maps can steer populations to local optima
• Deep Convolutional Networks as shallow Gaussian Processes
• A Note on the PAC Bayesian Theorem
• A Modern Take on the Bias-Variance Tradeoff in Neural Networks
• A PAC-Bayesian Tutorial with A Dropout Bound
• Data-Dependent Stability of Stochastic Gradient Descent
• Energy-entropy competition and the effectiveness of stochastic gradient descent in machine learning
• A Primer on PAC-Bayesian Learning
• A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processes
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• A Fine-Grained Spectral Perspective on Neural Networks
• Rethinking Parameter Counting in Deep Models: Effective Dimensionality Revisited
• Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• Finite size corrections for neural network Gaussian processes
• Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variation
• Towards NNGP-guided Neural Architecture Search
• How noise affects the Hessian spectrum in overparameterized neural networks
• De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictors

Cited by in corpus (4)

• Evaluation of Complexity Measures for Deep Learning Generalization in Medical Image Analysis
• Why flatness does and does not correlate with generalization for deep neural networks
• Auditing Robot Learning for Safety and Compliance during Deployment
• Towards Comparative Physical Interpretation of Spatial Variability Aware Neural Networks: A Summary of Results