# Bayes Complexity of Learners vs Overfitting

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 16 references that are in the map.
- First posted on arXiv 13 Mar 2023.

## Builds on (most cited first, 14 of 14)

- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Consistency and fluctuations for stochastic gradient Langevin dynamics](https://mlsanity.com/paper/1409.0578/) (2014)
- [Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes](https://mlsanity.com/paper/1605.06444/) (2016)
- [Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses](https://mlsanity.com/paper/1509.05753/) (2015)
- [On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators](https://mlsanity.com/paper/1610.06665/) (2016)
- [Natural Langevin Dynamics for Neural Networks](https://mlsanity.com/paper/1712.01076/) (2017)

## Built on by (most cited first, 1 of 1)

- [Information-Theoretic Framework for Understanding Modern Machine-Learning](https://mlsanity.com/paper/2506.07661/) (2025)

## Abstract (arXiv)

We introduce a new notion of complexity of functions and we show that it has the following properties: (i) it governs a PAC Bayes-like generalization bound, (ii) for neural networks it relates to natural notions of complexity of functions (such as the variation), and (iii) it explains the generalization gap between neural networks and linear schemes. While there is a large set of papers which describes bounds that have each such property in isolation, and even some that have two, as far as we know, this is a first notion that satisfies all three of them. Moreover, in contrast to previous works, our notion naturally generalizes to neural networks with several layers. Even though the computation of our complexity is nontrivial in general, an upper-bound is often easy to derive, even for higher number of layers and functions with structure, such as period functions. An upper-bound we derive allows to show a separation in the number of samples needed for good generalization between 2 and 4-layer neural networks for periodic functions.