On sample complexity of neural networks

We consider functions defined by deep neural networks as definable objects in an o-miminal expansion of the real field, and derive an almost linear (in the number of weights) bound on sample complexity of such networks.

cs.LG stat.ML Computer Science Mathematics

Paper

Similar papers

Generalization Bounds for Neural Networks via Approximate Description LengthAmit Daniely, Elad Granot2019 · Neural Information Processing Systems · 24 citations In Library

Size-Independent Sample Complexity of Neural NetworksNoah Golowich, A. Rakhlin, Ohad Shamir2017 · Annual Conference Computational Learning Theory · 640 citations In Library

Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample ComplexityAnastasis Kratsios, Greg Cousins, H. Borde et al.2026 · arXiv.org · 2 citations In Library

On the Complexity of Learning Neural NetworksLe Song, S. Vempala, John Wilmes et al.2017 · Neural Information Processing Systems · 63 citations In Library

The Sample Complexity of One-Hidden-Layer Neural NetworksGal Vardi, Ohad Shamir, Nathan Srebro2022 · arXiv (Cornell University) · 11 citations In Library

On Size-Independent Sample Complexity of ReLU NetworksMark Sellke2023 · arXiv (Cornell University) In Library

Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal ApproximationAnastasis Kratsios, Simone Brugiapaglia, Bum Jun Kim et al.2026 · 0 citations In Library

On the Number of Linear Functions Composing Deep Neural Network: Towards a Refined Definition of Neural Networks ComplexityYuuki Takai, Akiyoshi Sannai, Matthieu Cordonnier2020 · arXiv (Cornell University) · 5 citations In Library

Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz AugmentationColin Wei, Tengyu Ma2019 · Neural Information Processing Systems · 128 citations In Library

Initialization-Dependent Sample Complexity of Linear Predictors and Neural NetworksRoey Magen, Ohad Shamir2023 · Neural Information Processing Systems · 2 citations In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal