Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks

By Peter L. Bartlett, Nick Harvey, Christopher Liaw, Abbas Mehrabian. 2017

548 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Scaling & Learning Theory

Citations in the corpus

Beyond human-level accuracy: computational challenges in deep learning (2019, background): “Recent prior work shows that deep neural network model capacity—the volume of concepts (data) it can learn—grows with O(lp logp), where l is a measure of the model’s depth [16].”
Deep Active Learning with a Neural Architecture Search (2018, background): “[3] showed a nearly tight bound for the VC-dimension of deep neural networks.”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “A line of research proposed norm-based (e.g. Bartlett et al. (2017a)) and compression-based bounds (Arora et al., 2018).”
Fantastic Generalization Measures and Where to Find Them (2019, background): “Theorem 1 (Bartlett et al. (2019)) Let F be the class of feed-forward networks with a ﬁxed computation graph of depth d and ReLU activations.”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, background): “Another direction is to study the generalization ability based on the norms of weight matrices in neural networks (Neyshabur et al., 2015; 2017a;b; Bartlett et al., 2017; Liang et al., 2017; Golowich et al., 2017; Dziugaite and Roy, 2017; Wu et al., 2017).”
The Kolmogorov-Arnold representation theorem revisited (2020, unknown): “The fact that deep networks can do bit encoding and decoding eﬃciently has been used to prove (nearly) sharp bounds of the VC dimension for deep ReLU networks in [2] and also for a diﬀerent construction to obtain approximation rates of very deep networks with ﬁxed with; see [29].”
Neural network approximation (2020, background): “The upper bound in this theorem follows from Theorem 8 in (Bartlett et al. 2019).”
A Theoretical Analysis of Deep Q-Learning (2019, background): “t al. (2019) propose various norms computed from the networks parameters and establish capacity bounds based upon these norms. In addition, Maass (1994); Bartlett et al. (1999); Schmidt-Hieber(2020+);Bartlett et al. (2019); Klusowski and Barron (2016); Barron and Klusowski(2018); Suzuki(2019); Bauer”
Provable Lifelong Learning of Representations (2021, background): “Here we assume that a single such combination can be learned efficiently (i.e., a neural network with a small, single hidden layer) [Bartlett et al., 2019].”
Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks (2019, background): “For example, generalization error is related to various complexity measures (Bartlett et al., 1999; Bartlett & Mendelson, 2002; Bartlett et al., 2017a;b; Neyshabur et al., 2017; Golowich et al., 2017; Dziugaite & Roy, 2017; Neyshabur et al., 2018; E et al., 2018), local properties…”
Non-delusional Q-learning and value-iteration (2018, background): “Then the VC-dimension of this network follows from bounds given in [2].”
Deep Generative Learning via Schrödinger Bridge (2021, background): “Since the diameter of NN φ under d NN is at most B , we have )) where c is a constant which may vary on different places, the ﬁrst inequality follows from the chaining Theorem 8.1.3 in (Vershynin, 2018), the second inequality holds due to see (Bartlett et al., 2019).”
Functional Gradient Boosting based on Residual Network Perception (2018, methodology): “When the activation function is piece-wise linear, such as Relu function σ ( x ) = max { 0 , x } , reasonable bounds on these quantities are given by Bartlett et al. (1998; 2017).”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, background): “In fact, as shown in [6] (Equation(2)), for neural networks there is a tight connection between the number of parameters W , the number of layers H and their VC-Dimension Ω(HW log(W/H)) ≤ VC-Dimension ≤ O(HW logW ).”