Data to 14 Oct 2026

Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks

arXiv 1703.02930 ↗First posted 8 Mar 2017cs.LGcited by 311

Not on the map. Why?

Abstract (arXiv)

We prove new upper and lower bounds on the VC-dimension of deep neural networks with the ReLU activation function. These bounds are tight for almost the entire range of parameters. Letting W be the number of weights and L be the number of layers, we prove that the VC-dimension is O(W L log(W)), and provide examples with VC-dimension Omega( W L log(W/L) ). This improves both the previously known upper bounds and lower bounds. In terms of the number U of non-linear units, we prove a tight bound Theta(W U) on the VC-dimension. All of these bounds generalize to arbitrary piecewise linear activation functions, and also hold for the pseudodimensions of these function classes. Combined with previous results, this gives an intriguing range of dependencies of the VC-dimension on depth for networks with different non-linearities: there is no dependence for piecewise-constant, linear dependence for piecewise-linear, and no more than quadratic dependence for general piecewise-polynomial.

Key facts. Cited by 311 papers in the map (data through 14 Oct 2026). First posted on arXiv 8 Mar 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 47; 2022: 44; 2023: 50; 2024: 63; 2025: 54; 2026: 52.

311 papers.

Sort:

By area:

2024KAN: Kolmogorov-Arnold Networkscited by 649
2021Deep learning: a statistical viewpointcited by 240
2022Is Out-of-Distribution Detection Learnable?cited by 109
2021Deep Generative Learning via Schr"odinger Bridgecited by 104
2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
2023How Does Information Bottleneck Help Deep Learning?cited by 93
2021Provably Strict Generalisation Benefit for Equivariant Modelscited by 91
2023A Comprehensive Survey on Deep Graph Representation Learningcited by 72
2021Model Complexity of Deep Learning: A Surveycited by 65
2022Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spacescited by 51
2024Deep Networks Always Grok and Here is Whycited by 51
2021What can linearized neural networks actually say about generalization?cited by 49

38 more

2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
2021Domain Adversarial Neural Networks for Domain Generalization: When It Works and How to Improvecited by 46
2021Improved Regularization and Robustness for Fine-tuning in Neural Networkscited by 45
2022Deep Nonparametric Estimation of Operators between Infinite Dimensional Spacescited by 45
2021Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neuronscited by 40
2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 40
2022Why neural networks find simple solutions: the many regularizers of geometric complexitycited by 39
2022Large Language Models and the Reverse Turing Testcited by 38
2021Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sumscited by 37
2024On the expressiveness and spectral bias of KANscited by 37
2021An error analysis of generative adversarial networks for learning distributionscited by 36
2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
2021Quantifying and Improving Transferability in Domain Generalizationcited by 35
2021Generalization bounds via distillationcited by 34
2022Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guaranteescited by 34
2022Improving Self-Supervised Learning by Characterizing Idealized Representationscited by 34
2023WL meet VCcited by 31
2021Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spacescited by 30
2021Pay attention to your loss: understanding misconceptions about 1-Lipschitz neural networkscited by 30
2023Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivativescited by 30
2021Defending Against Image Corruptions Through Adversarial Augmentationscited by 28
2022How do noise tails impact on deep ReLU networks?cited by 25
2024The Real Tropical Geometry of Neural Networkscited by 24
2022Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Powercited by 23
2024What Do Learning Dynamics Reveal About Generalization in LLM Reasoning?cited by 23
2022Approximation bounds for norm constrained neural networks with applications to regression and GANscited by 22
2022Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformercited by 22
2022Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysiscited by 22
2025In-Context Learning Is Provably Bayesian Inference: A Generalization Theory for Meta-Learningcited by 22
2023Generalization bounds for neural ordinary differential equations and deep residual networkscited by 21
2024A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Modelscited by 20
2023Fantastic Generalization Measures are Nowhere to be Foundcited by 19
2023Deep Operator Learning Lessens the Curse of Dimensionality for PDEscited by 18
2021On the Equivalence between Neural Network and Support Vector Machinecited by 17
2021Learning Prediction Intervals for Regression: Generalization and Calibrationcited by 16
2021Universal Consistency of Deep Convolutional Neural Networkscited by 16
2021Provable Lifelong Learning of Representationscited by 15

50 most cited of 311 All 311 (JSON)