Source-linked AI summary
Complexity of Linear Regions in Deep Networks
Boris Hanin, David Rolnick
TL;DR
The paper asks whether neural networks used in practice attain the exponential linear-region complexity allowed by theory. It develops mathematical tools for counting regions and measuring their boundaries, finding linear region growth along one-dimensional subspaces at initialization and much lower-than-exponential practical complexity, consistent with experiments.
Problem
It is unclear whether typical piecewise linear networks before or after training approach their theoretical range from one region to exponentially many regions.
Method
The paper provides mathematical tools to analyze linear regions and boundary volume in piecewise linear networks before, during, and after training.
Results
At initialization, the average number of regions along any line segment is linear in neuron count, while boundary distance scales inversely with neuron count; experiments find complexity far below theoretical maxima.
Takeaways & Limitations
Practical expressivity likely falls significantly below theoretical expressivity, and some complexity measures of trained networks resemble those at initialization.
Takeaways & Limitations
The analysis does not address all notions of expressivity, and its total-region result on all of R remains future work.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper studies practical expressivity in piecewise linear networks by analyzing linear regions and their boundaries before and after training. Its theory and experiments indicate that practical complexity is far below theoretical exponential maxima.
- Motivation: Piecewise linear networks partition input space into linear regions, with each region assigned a distinct linear function.ReLU networks create these regions through successive layerwise boundary splits.
- Motivation: Exponential region counts are theoretically attainable, but slight weight and bias perturbations can severely reduce the structured regions supporting them.A sawtooth function with 2n teeth uses only 3n+4 neurons, yet Gaussian noise with standard deviation 0.1 greatly simplifies its regions.
- Contributions: The framework measures both the number of linear regions and the volume of boundaries between them as complexity indicators.Boundary volume also relates to the typical distance from an input to its region boundary.
- Results: At initialization, the average number of regions intersecting any line segment is linear in neuron count, far below the exponential theoretical bound.This result concerns one-dimensional subspaces through input space.
- Results: At initialization, the average distance from a sample point to the nearest region boundary is bounded below by a constant times the reciprocal of neuron count.The scaling is proportional to 1 divided by the number of neurons.
- Results: Empirically, region counts and nearest-boundary distances remain roughly constant during training and stay far below theoretical maxima.The authors state that this pattern is suggested by their theorem but is not a direct consequence of it.
- Conclusion: Overall, practical expressivity lags theoretical expressivity, while some complexity measures remain remarkably similar between trained networks and networks at initialization.The paper presents this as a conclusion supported jointly by theoretical and empirical findings.
2. Informal Overview of Results
The paper develops bounds showing that typical piecewise linear networks have complexity proportional to neuron count rather than exponential in depth, including higher-dimensional boundary measures and nearest-boundary distances.
- 1D regions: The average number of regions inside an input interval is proportional to neuron count times interval length.The result extends to regions intersected by any fixed one-dimensional curve in higher-dimensional input space.
- 1D regions: Theoretical upper bounds depend primarily on total neuron count, not how neurons are arranged across layers.This challenges the intuition that average region counts multiply by a factor greater than one at every layer.
- 1D regions: At initialization, the mean total number of linear regions is conjectured to be proportional to neuron count, based on the one-dimensional theory and experiments.The authors note that the available bounds become less sharp as the interval grows and plan to extend the theory to all of input space.
- Training behavior: The theory suggests that region counts along one-dimensional curves remain proportional to neuron count throughout training under well-behaved gradients and bias distributions.Experiments in Figures 5–6 empirically examine this heuristic.
- Higher-dimensional regions: For higher-dimensional networks, the paper studies boundary volume density as a generalization of region counting.The authors prove initialization bounds for average boundary volume in bounded input sets.
- Higher-dimensional regions: The average distance from a random input to its nearest region boundary is bounded below by a constant times 1/#{neurons}.The distance is linked to neuron sensitivity and provides a heuristic lower bound for typical distance to an adversarial example.
3. Experiments
Experiments on fully connected ReLU networks trained on MNIST show that region counts and nearest-boundary distances remain near their initialization scales, with an initial expansion or contraction pattern during training.
- 3.1. Number of Regions Along a Line: Experiments used fully connected networks with He normal weights and small random biases, trained on vectorized MNIST with Adam.Region counts were evaluated exactly along sampled lines through the origin and training examples.
- 3.1. Number of Regions Along a Line: Throughout training, region counts remain within a small constant of their initialization values and far below theoretical maxima.Counts decrease during early training before increasing again.
- 3.2. Distance to the Nearest Region Boundary: Nearest-boundary distance is well predicted by 1/#{neurons}, varying approximately between 0.4/#{neurons} and 1.5/#{neurons} during training.The normalized distance first increases rapidly and then decreases more slowly.
- 3.2. Distance to the Nearest Region Boundary: The normalized boundary distance suggests two training phases: regions first expand and then contract as test accuracy changes.The authors explicitly describe this interpretation as speculative and requiring further study.
- 3.2. Distance to the Nearest Region Boundary: For a depth-4, width-16 network, the log-distance distribution changes little during training, with a slight skew toward larger regions.Distances span many orders of magnitude.
- 3.3. Region Visualizations: Visualizations of a depth-3, width-64 network show regions expanding initially and then contracting during training.The regions were plotted within a plane in the 784-dimensional input space through three differently labeled examples.
- 3.3. Region Visualizations: Exact region enumeration remains tractable because the theory predicts relatively few regions.The procedure subdivides an initial region neuron by neuron and checks whether each new neuron splits each existing region.
4. Related Work
This work connects to research on depth expressivity, linear-region counting, training dynamics, and the gap between expressivity and learnability. Figure 8 also highlights qualitative differences from prior visualizations, potentially due to using ReLU rather than ReLU6.
- Prior work studies functions efficiently represented by deep but not shallow ReLU networks.
- Research on piecewise linear networks includes counting linear regions and examining how regions change during training.
- Figure 8 visualizes regions intersecting a two-dimensional plane through three MNIST examples for a depth-3, width-64 network.
- The visualization differs qualitatively from Novak et al. (2018), possibly because this work uses ReLU instead of ReLU6.
5. Formal Statement of Results
The formal results characterize region boundaries in random piecewise linear networks through geometric sets and expected volumes. Under distributional assumptions, the framework yields bounds involving neuron count, gradient and bias behavior, and distance to the nearest boundary.
- A generic depth-d fully connected ReLU network partitions R^nin into polytopes, with one linear function computed on each polytope.
- The boundary set B_N contains points where the network gradient is discontinuous, and B_N,k classifies local boundary strata by codimension k.
- Theorem 3 assumes conditional bias densities and a joint weight density; these conditions hold in particular for independent continuously distributed weights and biases at initialization.
- Theorem 3 gives the expected (n_in−k)-dimensional volume of B_N,k inside any bounded measurable set K.
- The average distance from a uniform sample in compact K to B_N is bounded below by c/(C_bias C_grad #{neurons}), with c independent of K.
6. Conclusions and Further Work
The paper concludes that practical expressivity, as measured by linear-region boundary complexity, is substantially below theoretical expressivity. Its findings suggest trained networks can resemble their initialized counterparts on these measures, while the paper does not offer a replacement theory for deep learning's success.
- The average boundary size depends on neuron count rather than network depth, both at initialization and during training.
- These results suggest deeper networks may not learn more complex functions than shallower networks under this complexity measure.
- Future work will test the interpretation on more complex tasks and examine higher-order statistics such as variance.
- The paper does not propose a replacement theory for the success of deep learning.
A. Formal Statement of Results for General Piecewise Linear Activations
The general result extends the analysis to continuous piecewise linear activations with T breakpoints, using neuron Jacobians, bias densities, and path-based activity conditions.
- General theorem: Theorem 6 treats fully connected scalar-output networks with continuous piecewise linear activation φ having T breakpoints.The theorem assumes random weights and biases satisfying the paper’s assumptions.
- Boundary measure: For k distinct neurons, the boundary-volume expression uses the k × n_in Jacobian and the joint density of their biases.The relevant density is evaluated at the neurons’ outputs shifted by selected activation breakpoints.
- Definitions: A neuron is good at x when an input-to-output path through it remains open at x.Openness means the activation derivative along each path neuron is nonzero.
- Boundary measure: The theorem’s boundary decomposition distinguishes points where exactly k neurons switch, producing an (n_in−k)-dimensional boundary component.Corollary 7 additionally assumes independent weights and biases plus a uniform bound on average products of gradients.
- Assumptions: If activation slopes never equal zero, the definition can omit the condition that neurons are good at x.This follows because every linear piece remains locally nonconstant.
Then we have the following upper bounds
The stated corollary bounds the expected distance from a uniformly sampled input to the nearest region boundary using the boundary-volume estimate.
- Upper bound: Corollary 8 applies to any compact K and a uniformly sampled x, under the gradient and bias-density bounds of Corollary 7.It asserts the existence of a constant c independent of K.
- Proof idea: The probability that x lies within ε of the boundary is controlled through the volume of the ε-tube around B_N.The argument uses the expected scaling of tube volume with ε times boundary volume.
- Consequence: Taking ε = c/#{neurons} yields the inverse-neuron scaling for the average distance to the nearest boundary.The tube-volume estimate supplies the connection between boundary measure and typical distance.
B. Outline of Proof of Theorem 6
The proof represents the network boundary through active neuron switching sets, decomposes it by codimension, and computes each component’s expected volume with the co-area formula.
- Boundary representation: Each neuron’s switching set S_z contains inputs where its pre-activation reaches one of φ’s breakpoints.The refined set excludes switches that do not affect the network output through an open path.
- Activity condition: If activation pieces have no zero slopes, the open set O is empty; for ReLU, O may be nonempty.The open set tracks inputs connected to nonconstant paths from input to output.
- Boundary decomposition: The set B_N is decomposed into pieces B_N,k where exactly k neurons turn from on to off.These pieces form the (n_in−k)-dimensional portions of the boundary.
- Local geometry: With probability 1, B_N,k is locally an (n_in−k)-dimensional hyperplane for each collection of k distinct neurons.The result follows from the corresponding switching constraints having the required codimension.
- Volume calculation: The expected volume of each boundary component is computed by mapping input volume through the neurons’ outputs and averaging over their bias densities.The formal calculation uses the co-area formula.
C.1. Proof of Proposition 9
The proof of Proposition 9 identifies the network’s boundary with neuron switching events that remain relevant to the output, then establishes the local derivative discontinuity criterion.
- Relevant switches: Only neurons with an open path to the output can contribute a switching event to B_N.A neuron at a breakpoint is irrelevant when no open path connects it to the output nearby.
- Boundary inclusion: At a relevant switching hyperplane, the network boundary follows unless contributions from other neurons exactly cancel the derivative jump.The proof states that this cancellation occurs with probability 0.
- Local linearity: Away from neuron breakpoint crossings, all pre-activations remain in fixed linear pieces locally, so the network’s derivatives are locally constant.This establishes that boundary points must lie in switching sets.
- Multiple switches: For k switching neurons, the refined switching set is locally the intersection of k hyperplanes.This yields the codimension-k structure used in the boundary decomposition.
- Expected volume: The expected volume calculation averages these switching intersections over conditional bias densities and applies the co-area formula.The remaining weights and biases are averaged afterward, using nonnegative integrands to commute expectation and integration.
D. Proof of Corollary 7
The proof establishes Corollary 7 by expressing boundary volumes through Jacobians and Gram determinants, then proving the bounds using initialization properties and induction over neurons. The inductive step restricts the network to successive piecewise-linear boundary pieces and reapplies the hypothesis.
- Upper bound: The upper bound follows from estimate (14), while the ReLU case additionally uses AM-GM and Jensen inequalities.The proof begins with Theorem 3 and invokes a result of Hanin & Nica for the required initialization estimate.
- Geometric representation: The k-dimensional boundary volume is represented using the Jacobian of k neuron outputs and the associated Gram matrix.The Gram identity identifies the determinant-based quantity with the k-dimensional volume spanned by the neuron gradients.
- Lower bound: The lower bound starts with k = 1 and proceeds by induction over collections of distinct neurons ordered by layer index.The base case combines lower bounds on the relevant integrand with Cauchy-Schwarz, Markov, Jensen, and a suitable choice of parameter.
- Initialization estimates: At initialization, neuron activation indicators are independent Bernoulli variables with parameter 1/2 for each fixed input.The proof also uses initialization variance and gradient estimates, including a width-dependent estimate whose implied constant depends on the fourth moment of the weight distribution.
- Inductive step: For the inductive step, each boundary piece becomes the domain of a restricted network satisfying the same assumptions, allowing the hypothesis to be applied to the remaining neurons.A second application of the inductive hypothesis completes the proof.
E. Proof of Corollary 8
The proof bounds the volume of tubular neighborhoods around compact piecewise-linear submanifolds by decomposing them according to face dimension. Applying this geometric lemma with Markov’s inequality yields the claimed inverse-neuron boundary-distance scale.
- Tubular-neighborhood lemma: Lemma 12 decomposes a compact continuous piecewise-linear submanifold into interiors of pieces by dimension and bounds its ε-tubular neighborhood.The argument proceeds from maximal-dimensional pieces to lower-dimensional strata using normal bundles.
- Geometric measure: The tubular-neighborhood bound uses the unit-ball volume ω_d in the relevant dimension.The notation is defined as the volume of the radius-one ball in R^d.
- Application to the network: For a uniformly chosen x in K = [0, 1]^n_in, Markov’s inequality and Lemma 12 bound the probability of lying near the boundary.Choosing ε as a small constant times 1/(C_grad #{neurons}) completes the proof.