Nearly-tight VC-dimension and pseudodimension 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(WL\log (W))$, and provide examples with VC-dimension $\Omega (WL\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 (WU)$ 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.

Extended abstract appeared in COLT 2017; the upper bound was presented at the 2016 ACM Conference on Data Science. This version includes all the proofs and a refinement of the upper bound, Theorem 6. 16 pages, 2 figures

Cited by in corpus (72)

• Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks
• A Comprehensive Survey on Deep Graph Representation Learning
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Large Language Models and the Reverse Turing Test
• Fantastic Generalization Measures and Where to Find Them
• The Modern Mathematics of Deep Learning
• A Theoretical Analysis of Deep Q-Learning
• Deep learning generalizes because the parameter-function map is biased towards simple functions
• Deep Generalized Method of Moments for Instrumental Variable Analysis
• Convergence of Adversarial Training in Overparametrized Neural Networks
• A rate of convergence of Physics Informed Neural Networks for the linear second order elliptic PDEs
• Automatic Change-Point Detection in Time Series via Deep Learning
• Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks
• Approximation spaces of deep neural networks
• Deep Learning in current Neuroimaging: a multivariate approach with power and type I error control but arguable generalization ability
• Approximation bounds for norm constrained neural networks with applications to regression and GANs
• Imaging Conductivity from Current Density Magnitude using Neural Networks
• Generalization bounds via distillation
• What can linearized neural networks actually say about generalization?
• Approximation in shift-invariant spaces with deep ReLU neural networks
• Memory capacity of neural networks with threshold and ReLU activations
• Generalization Bounds for Neural Belief Propagation Decoders
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• On Deep Instrumental Variables Estimate
• Computational Separation Between Convolutional and Fully-Connected Networks
• Deep Quantile Regression: Mitigating the Curse of Dimensionality Through Composition
• Provably Strict Generalisation Benefit for Equivariant Models
• Learning Prediction Intervals for Regression: Generalization and Calibration
• PAC-Bayesian Margin Bounds for Convolutional Neural Networks
• Beyond Human-Level Accuracy: Computational Challenges in Deep Learning
• Learning from scarce information: using synthetic data to classify Roman fine ware pottery
• Near-Optimal Rapid MPC using Neural Networks: A Primal-Dual Policy Learning Framework
• Robustness to Augmentations as a Generalization metric
• Quantile regression with deep ReLU Networks: Estimators and minimax rates
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Quantifying and Improving Transferability in Domain Generalization
• Robust Nonparametric Regression with Deep Neural Networks
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms
• Deep Neural Networks for Choice Analysis: Extracting Complete Economic Information for Interpretation
• Functional Gradient Boosting based on Residual Network Perception
• De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictors
• Deep Dimension Reduction for Supervised Representation Learning
• Deep Generative Learning via Schrödinger Bridge
• Analysis of Deep Ritz Methods for Laplace Equations with Dirichlet Boundary Conditions
• On the Optimal Memorization Power of ReLU Neural Networks
• Convolutional neural networks for valid and efficient causal inference
• Defending Against Image Corruptions Through Adversarial Augmentations
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons
• Generative Learning With Euler Particle Transport
• Analytic function approximation by path norm regularized deep networks
• Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets
• Overestimation learning with guarantees
• An Accelerated Fitted Value Iteration Algorithm for MDPs with Finite and Vector-Valued Action Space
• Deep Networks as Logical Circuits: Generalization and Interpretation
• Leveraging Local Variation in Data: Sampling and Weighting Schemes for Supervised Deep Learning
• On the Provable Generalization of Recurrent Neural Networks
• A Deep Generative Approach to Conditional Sampling
• A Probabilistic Representation of Deep Learning
• Deep Neural Networks for Choice Analysis: Architectural Design with Alternative-Specific Utility Functions
• Uniform Convergence, Adversarial Spheres and a Simple Remedy
• On the generalization of bayesian deep nets for multi-class classification
• On the potential for open-endedness in neural networks
• Provable Lifelong Learning of Representations
• Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension
• VC dimension of partially quantized neural networks in the overparametrized regime
• Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion
• Notes on Deep Learning Theory
• Fast Jacobian-Vector Product for Deep Networks
• Learning the gravitational force law and other analytic functions
• Concurrent Training Improves the Performance of Behavioral Cloning from Observation
• When Are Solutions Connected in Deep Networks?