# Generalization bounds for deep learning

arXiv: https://arxiv.org/abs/2012.04115 · HTML: https://mlsanity.com/paper/2012.04115/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2020.

## Built on by (most cited first, 30 of 38)

- [Out-of-Domain Generalization in Dynamical Systems Reconstruction](https://mlsanity.com/paper/2402.18377/) (2024)
- [Deep neural networks have an inbuilt Occam's razor](https://mlsanity.com/paper/2304.06670/) (2023)
- [On Margins and Derandomisation in PAC-Bayes](https://mlsanity.com/paper/2107.03955/) (2021)
- [A PAC-Bayesian Generalization Bound for Equivariant Networks](https://mlsanity.com/paper/2210.13150/) (2022)
- [Improving Zero-shot Generalization in Offline Reinforcement Learning using Generalized Similarity Functions](https://mlsanity.com/paper/2111.14629/) (2021)
- [An Analysis of Attention via the Lens of Exchangeability and Latent Variable Models](https://mlsanity.com/paper/2212.14852/) (2022)
- [A Comprehensive Benchmark of Machine and Deep Learning Across Diverse Tabular Datasets](https://mlsanity.com/paper/2408.14817/) (2024)
- [Why flatness does and does not correlate with generalization for deep neural networks](https://mlsanity.com/paper/2103.06219/) (2021)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [Generalization Bound and New Algorithm for Clean-Label Backdoor Attack](https://mlsanity.com/paper/2406.00588/) (2024)
- [A path-norm toolkit for modern networks: consequences, promises and challenges](https://mlsanity.com/paper/2310.01225/) (2023)
- [Reward Generalization in RLHF: A Topological Perspective](https://mlsanity.com/paper/2402.10184/) (2024)
- [Sparsity-aware generalization theory for deep neural networks](https://mlsanity.com/paper/2307.00426/) (2023)
- [Can DPO Learn Diverse Human Values? A Theoretical Scaling Law](https://mlsanity.com/paper/2408.03459/) (2024)
- [Double-descent curves in neural networks: a new perspective using Gaussian processes](https://mlsanity.com/paper/2102.07238/) (2021)
- [Investigating Generalization by Controlling Normalized Margin](https://mlsanity.com/paper/2205.03940/) (2022)
- [On the Limitations of Fractal Dimension as a Measure of Generalization](https://mlsanity.com/paper/2406.02234/) (2024)
- [Auditing Robot Learning for Safety and Compliance during Deployment](https://mlsanity.com/paper/2110.05702/) (2021)
- [Quantile-constrained Wasserstein projections for robust interpretability of numerical and machine learning models](https://mlsanity.com/paper/2209.11539/) (2022)
- [A Two-Scale Complexity Measure for Deep Learning Models](https://mlsanity.com/paper/2401.09184/) (2024)
- [Physics-based reward driven image analysis in microscopy](https://mlsanity.com/paper/2404.14146/) (2024)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Exploiting the equivalence between quantum neural networks and perceptrons](https://mlsanity.com/paper/2407.04371/) (2024)
- [Evaluation of Complexity Measures for Deep Learning Generalization in Medical Image Analysis](https://mlsanity.com/paper/2103.03328/) (2021)
- [Optimisation & Generalisation in Networks of Neurons](https://mlsanity.com/paper/2210.10101/) (2022)
- [Deep learning for psi-weakly dependent processes](https://mlsanity.com/paper/2302.00333/) (2023)
- [Partial-Multivariate Model for Forecasting](https://mlsanity.com/paper/2408.09703/) (2024)
- [Kernel Interpolation as a Bayes Point Machine](https://mlsanity.com/paper/2110.04274/) (2021)
- [A New Measure of Model Redundancy for Compressed Convolutional Neural Networks](https://mlsanity.com/paper/2112.04857/) (2021)
- [Confidence Dimension for Deep Learning based on Hoeffding Inequality and Relative Evaluation](https://mlsanity.com/paper/2203.09082/) (2022)

## Abstract (arXiv)

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.