# Beyond the storage capacity: data driven satisfiability transition

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2020.

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

- [Statistical mechanics of extensive-width Bayesian neural networks near interpolation](https://mlsanity.com/paper/2505.24849/) (2025)
- [Inversion dynamics of class manifolds in deep learning reveals tradeoffs underlying generalisation](https://mlsanity.com/paper/2303.05161/) (2023)
- [Random features and polynomial rules](https://mlsanity.com/paper/2402.10164/) (2024)
- [Restoring balance: principled under/oversampling of data for optimal classification](https://mlsanity.com/paper/2405.09535/) (2024)
- [Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation](https://mlsanity.com/paper/2501.18530/) (2025)
- [Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation](https://mlsanity.com/paper/2510.24616/) (2025)

## Abstract (arXiv)

Data structure has a dramatic impact on the properties of neural networks, yet its significance in the established theoretical frameworks is poorly understood. Here we compute the Vapnik-Chervonenkis entropy of a kernel machine operating on data grouped into equally labelled subsets. At variance with the unstructured scenario, entropy is non-monotonic in the size of the training set, and displays an additional critical point besides the storage capacity. Remarkably, the same behavior occurs in margin classifiers even with randomly labelled data, as is elucidated by identifying the synaptic volume encoding the transition. These findings reveal aspects of expressivity lying beyond the condensed description provided by the storage capacity, and they indicate the path towards more realistic bounds for the generalization error of neural networks.