Complexity of Linear Regions in Deep Networks

Abstract

It is well-known that the expressivity of a neural network depends on its architecture, with deeper networks expressing more complex functions. In the case of networks that compute piecewise linear functions, such as those with ReLU activation, the number of distinct linear regions is a natural measure of expressivity. It is possible to construct networks with merely a single region, or for which the number of linear regions grows exponentially with depth; it is not clear where within this range most networks fall in practice, either before or after training. In this paper, we provide a mathematical framework to count the number of linear regions of a piecewise linear network and measure the volume of the boundaries between these regions. In particular, we prove that for networks at initialization, the average number of regions along any one-dimensional subspace grows linearly in the total number of neurons, far below the exponential upper bound. We also find that the average distance to the nearest region boundary at initialization scales like the inverse of the number of neurons. Our theory suggests that, even after training, the number of linear regions is far below exponential, an intuition that matches our empirical observations. We conclude that the practical expressivity of neural networks is likely far below that of the theoretical maximum, and that this gap can be quantified.

ICML 2019

Cited by in corpus (37)

• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• Multifidelity Modeling for Physics-Informed Neural Networks (PINNs)
• Empirical Studies on the Properties of Linear Regions in Deep Neural Networks
• Uncertainty Quantification for Sparse Deep Learning
• When are Deep Networks really better than Decision Forests at small sample sizes, and how?
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
• CKConv: Continuous Kernel Convolution For Sequential Data
• Zen-NAS: A Zero-Shot NAS for High-Performance Deep Image Recognition
• How benign is benign overfitting?
• The Local Elasticity of Neural Networks
• Implicit Rugosity Regularization via Data Augmentation
• Understanding and Accelerating Neural Architecture Search with Training-Free and Theory-Grounded Metrics
• Proxy-Normalizing Activations to Match Batch Normalization while Removing Batch Dependence
• Deep ReLU Networks Preserve Expected Length
• Model Complexity of Deep Learning: A Survey
• Optimal Function Approximation with Relu Neural Networks
• Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
• Moment-Based Domain Adaptation: Learning Bounds and Algorithms
• Scaling Up Exact Neural Network Compression by ReLU Stability
• SMILE: Self-Distilled MIxup for Efficient Transfer LEarning
• Hyperplane Arrangements of Trained ConvNets Are Biased
• Reachability Analysis of Convolutional Neural Networks
• Student Specialization in Deep ReLU Networks With Finite Width and Input Dimension
• Depth separation beyond radial functions
• On the Number of Linear Functions Composing Deep Neural Network: Towards a Refined Definition of Neural Networks Complexity
• Theoretical Analysis of the Advantage of Deepening Neural Networks
• Investigating the Compositional Structure Of Deep Neural Networks
• What training reveals about neural network complexity
• Using activation histograms to bound the number of affine regions in ReLU feed-forward neural networks
• Deep Networks as Logical Circuits: Generalization and Interpretation
• Neural networks behave as hash encoders: An empirical study
• Complexity for deep neural networks and other characteristics of deep feature representations
• On the Expected Complexity of Maxout Networks
• Gradient representations in ReLU networks as similarity functions
• Understanding Interpretability by generalized distillation in Supervised Classification
• Identifying and Exploiting Structures for Reliable Deep Learning
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations