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

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

## Key facts

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

## Built on by (most cited first, 30 of 311)

- [KAN: Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2404.19756/) (2024)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [Deep Generative Learning via Schr"odinger Bridge](https://mlsanity.com/paper/2106.10410/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [Provably Strict Generalisation Benefit for Equivariant Models](https://mlsanity.com/paper/2102.10333/) (2021)
- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (2021)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [Deep Networks Always Grok and Here is Why](https://mlsanity.com/paper/2402.15555/) (2024)
- [What can linearized neural networks actually say about generalization?](https://mlsanity.com/paper/2106.06770/) (2021)
- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [Domain Adversarial Neural Networks for Domain Generalization: When It Works and How to Improve](https://mlsanity.com/paper/2102.03924/) (2021)
- [Improved Regularization and Robustness for Fine-tuning in Neural Networks](https://mlsanity.com/paper/2111.04578/) (2021)
- [Deep Nonparametric Estimation of Operators between Infinite Dimensional Spaces](https://mlsanity.com/paper/2201.00217/) (2022)
- [Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons](https://mlsanity.com/paper/2102.05363/) (2021)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Why neural networks find simple solutions: the many regularizers of geometric complexity](https://mlsanity.com/paper/2209.13083/) (2022)
- [Large Language Models and the Reverse Turing Test](https://mlsanity.com/paper/2207.14382/) (2022)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [On the expressiveness and spectral bias of KANs](https://mlsanity.com/paper/2410.01803/) (2024)
- [An error analysis of generative adversarial networks for learning distributions](https://mlsanity.com/paper/2105.13010/) (2021)
- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [Quantifying and Improving Transferability in Domain Generalization](https://mlsanity.com/paper/2106.03632/) (2021)
- [Generalization bounds via distillation](https://mlsanity.com/paper/2104.05641/) (2021)
- [Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guarantees](https://mlsanity.com/paper/2206.02659/) (2022)
- [Improving Self-Supervised Learning by Characterizing Idealized Representations](https://mlsanity.com/paper/2209.06235/) (2022)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)

## 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.