Nearly-Tight VC-Dimension Bounds for Piecewise Linear Neural Networks
Abstract
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 $Ω( 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 $Θ(W U)$ on the VC-dimension. All of these results generalize to arbitrary piecewise linear activation functions.
Cite
Text
Harvey et al. "Nearly-Tight VC-Dimension Bounds for Piecewise Linear Neural Networks." Proceedings of the 2017 Conference on Learning Theory, 2017.Markdown
[Harvey et al. "Nearly-Tight VC-Dimension Bounds for Piecewise Linear Neural Networks." Proceedings of the 2017 Conference on Learning Theory, 2017.](https://mlanthology.org/colt/2017/harvey2017colt-nearlytight/)BibTeX
@inproceedings{harvey2017colt-nearlytight,
title = {{Nearly-Tight VC-Dimension Bounds for Piecewise Linear Neural Networks}},
author = {Harvey, Nick and Liaw, Christopher and Mehrabian, Abbas},
booktitle = {Proceedings of the 2017 Conference on Learning Theory},
year = {2017},
pages = {1064-1068},
volume = {65},
url = {https://mlanthology.org/colt/2017/harvey2017colt-nearlytight/}
}