Beyond the storage capacity: data driven satisfiability transition

Abstract

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.

arXiv comment5 pages, 2 figures

References in corpus (16)

• Understanding Deep Convolutional Networks
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Classification and Geometry of General Perceptual Manifolds
• The simplest model of jamming
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Phase coexistence and finite-size scaling in random combinatorial problems
• Linear Readout of Object Manifolds
• Intrinsic dimension estimation for locally undersampled data
• Statistical learning theory of structured data
• Statistics of shared components in complex component systems
• Exploring the Function Space of Deep-Learning Machines
• Counting the learnable functions of structured data
• Random geometric graphs in high dimension
• Learning Data Manifolds with a Cutting Plane Method
• Generalization from correlated sets of patterns in the perceptron

Cited by in corpus (13)

• A statistical mechanics framework for Bayesian deep neural networks beyond the infinite-width limit
• Statistical learning theory of structured data
• Random geometric graphs in high dimension
• Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures
• Random features and polynomial rules
• Space of Functions Computed by Deep-Layered Machines
• Inversion dynamics of class manifolds in deep learning reveals tradeoffs underlying generalisation
• Exploring fundamental laws of classical mechanics via predicting the orbits of planets based on neural networks
• Satisfiability transition in asymmetric neural networks
• Critical properties of the SAT/UNSAT transitions in the classification problem of structured data
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation