Nearlytight VCdimension bounds for piecewise linear neural networks
[edit]
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:10641068, 2017.
Abstract
We prove new upper and lower bounds on the VCdimension 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 VCdimension is $O(W L \log(W))$, and provide examples with VCdimension $Ω( W L \log(W/L) )$. This improves both the previously known upper bounds and lower bounds. In terms of the number $U$ of nonlinear units, we prove a tight bound $Θ(W U)$ on the VCdimension. All of these results generalize to arbitrary piecewise linear activation functions.
Related Material


