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

Peter L. Bartlett, Nick Harvey, Christopher Liaw, Abbas MehrabianJMLR 2019 · OpenReview

TL;DR

This paper establishes nearly tight bounds on the VC-dimension of deep neural networks with ReLU (and other piecewise linear) activation functions. The authors show that the complexity of these networks, measured by VC-dimension, scales as $O(WL \log W)$ with $W$ weights and $L$ layers, and is $\Theta(WU)$ with $U$ units, providing a more precise understanding of how network architecture impacts generalization.

What Problem Does This Paper Address?

Deep neural networks have achieved remarkable success in various machine learning tasks, but understanding their generalization capabilities remains a significant theoretical challenge. The VC-dimension is a fundamental concept in statistical learning theory that quantifies the complexity of a function class and provides bounds on how well a model trained on a finite dataset will perform on unseen data. For neural networks, the VC-dimension is influenced by several architectural parameters: the number of weights ($W$), the number of layers ($L$), and the number of non-linear units ($U$). While previous work established upper and lower bounds on the VC-dimension, these bounds were often loose, particularly concerning the interplay between depth and width. This paper aims to provide tighter, more precise bounds that better characterize the VC-dimension's dependence on these architectural choices, especially for the widely used ReLU activation function.

Methods

The core of the paper's contribution lies in developing new techniques to derive tighter VC-dimension bounds. For the lower bound, the authors refine the "bit extraction" technique, which was previously used to establish $\Omega(WL)$ bounds. By adapting this technique to extract multiple bits at a time, they achieve a stronger lower bound of $\Omega(WL \log(W/L))$. This technique is further supported by a theoretical result (Theorem 6) that suggests this bit extraction approach has an inherent barrier, implying that their $\Omega(WL \log(W/L))$ bound is likely near-optimal for this method.

For the upper bound, the authors build upon existing techniques for bounding the growth function of polynomially parametrized function classes, specifically adapting results from Goldberg and Jerrum (1995) and Bartlett et al. (1998). They provide a unified approach that yields improved bounds for piecewise polynomial activation functions, and specifically for piecewise linear functions like ReLU, they achieve $O(WL \log W)$.

A significant result is the tight $\Theta(WU)$ bound for the VC-dimension in terms of the number of units ($U$) and weights ($W$), which is achieved by combining their upper bound with existing lower bounds.

Datasets

Not discussed in the paper. The paper focuses on theoretical bounds for function classes defined by neural network architectures, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Depth Matters, But Logarithmically: The paper clarifies that for piecewise linear networks, the VC-dimension grows linearly with the number of layers ($L$) and logarithmically with the number of weights ($W$), specifically $O(WL \log W)$. This is a significant improvement over previous bounds and provides a more nuanced understanding of how depth impacts complexity.
  • Tightness is Achieved: The authors demonstrate that their derived upper and lower bounds for piecewise linear networks are nearly tight, differing only by a logarithmic factor in certain regimes. This suggests a more complete picture of the VC-dimension's behavior.
  • Unit Count is Crucial: A key finding is the tight $\Theta(WU)$ bound on the VC-dimension, highlighting that the number of non-linear units ($U$) is a critical factor, and its relationship with the number of weights ($W$) is linear.
  • Generalization to Piecewise Linear: The results are shown to generalize beyond ReLU to any piecewise linear activation function, making them broadly applicable.
  • Pseudodimension Connection: The bounds are also shown to hold for pseudodimensions, which are often considered a more appropriate complexity measure for real-valued function classes like those produced by neural networks.

Key Results

  • Lower Bound: For ReLU networks with $W$ parameters and $L$ layers, the VC-dimension is $\Omega(WL \log(W/L))$.
  • Upper Bound: For piecewise linear networks with $W$ parameters and $L$ layers, the VC-dimension is $O(WL \log W)$.
  • Combined Bound: For piecewise linear networks, the VC-dimension is nearly tight, $c \cdot WL \log(W/L) \le d(W, L) < C \cdot WL \log W$.
  • Unit-Based Bound: The VC-dimension is $\Theta(WU)$ for networks with $W$ parameters and $U$ units.
  • Generalization: These bounds apply to arbitrary piecewise linear activation functions and also hold for pseudodimensions.

Limitations and Future Work

  • Piecewise Polynomials: While the paper provides an upper bound for general piecewise polynomial activation functions ($O(WL^2 + WL \log W)$), closing the gap between this and the $\Omega(WL \log(W/L))$ lower bound for piecewise linear networks requires fundamentally new techniques.
  • Specific Regimes: The paper notes that in the theoretical regime where $L = \Theta(W)$, the bounds become $d(W, L) = \Theta(WL)$, which is also tight. However, there remains a narrow regime ($W^{0.99} \ll L \ll W$) where the bounds are not asymptotically tight, differing only in the logarithmic factor.
  • Empirical Validation: The paper is theoretical and does not include empirical validation on datasets. Future work could involve testing these theoretical insights on real-world tasks to see how well they predict generalization performance.
  • Other Activation Functions: The paper focuses on piecewise linear and piecewise polynomial functions. Extending these tight bounds to other common activation functions like sigmoid or tanh could be a valuable future direction.

Summary updated

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 $\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.
BibTeX
@article{bartlett2019nearly,
  author = {Peter L. Bartlett and Nick Harvey and Christopher Liaw and Abbas Mehrabian},
  title = {{Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=_WsoOv02-S4},
}

Loading related content...

Figure