Are All Linear Regions Created Equal?

Matteo Gamba, Adrian Chmielewski-Anders, Josephine Sullivan, Hossein Azizpour, Mårten Björkman

Abstract: The number of linear regions has been studied as a proxy of complexity for ReLU networks. However, the empirical success of network compression techniques like pruning and knowledge distillation suggests that in the overparameterized setting, linear regions density might fail to capture the effective nonlinearity. In this work, we propose an efficient algorithm for discovering linear regions and use it to investigate the effectiveness of density in capturing the nonlinearity of trained VGGs and ResNets on CIFAR-10 and CIFAR-100. We contrast the results with a more principled nonlinearity measure based on function variation, highlighting the shortcomings of linear regions density. Furthermore, our measure of nonlinearity clearly correlates with model-wise deep double descent, connecting reduced test error with reduced nonlinearity and increased local similarity of linear regions.

Introduction

Deep neural networks utilizing ReLU activations are technically piecewise affine functions. This structure implies that they partition the input space into a vast collection of convex polytopes, known as linear regions. Within each of these regions, the network behaves as a simple linear function. Historically, researchers have used "linear region density"—the raw count of these regions—as a proxy for a network's expressivity or complexity.

However, this metric treats all regions as equally significant, ignoring the possibility that many regions might be nearly identical. This paper argues that density fails to capture "effective nonlinearity." A network could theoretically possess millions of regions but remain nearly linear if the transitions between those regions are subtle.

Methods: Measuring the "Wiggle"

To address the shortcomings of simple counting, the authors introduce two primary technical contributions:

  1. Adaptive Linear Region Discovery: Traditional counting methods rely on uniform sampling, which is often too coarse to find small regions or too computationally expensive if fine-grained. The authors propose an iterative algorithm that leverages the network's weights and biases to "hop" from one boundary to the next along a 1D path, efficiently recovering every region boundary.
  2. Absolute Deviation: Instead of counting boundaries, this metric measures the function's variation. Absolute deviation calculates the integral of the difference between the actual network output and a linear interpolation between two endpoints. This accounts for the slope, bias, and size of every linear region encountered along a path.
Visualizing absolute deviation vs. linear region counting.

Experimental Setup

The study evaluates these metrics using standard image classification benchmarks, CIFAR-10 and CIFAR-100, across VGG8 and ResNet18 architectures. To further probe complexity, the researchers introduced varying levels of label noise (up to 100%) to force models to learn increasingly complex and "noisy" decision boundaries.

Key Results: The Double Descent Connection

The most significant finding is the relationship between nonlinearity and Deep Double Descent. In this phenomenon, as models grow in size, test error typically decreases, then increases (overfitting), and finally decreases again in the overparameterized regime (the "second descent").

Absolute deviation tracks the double descent phenomenon.

The authors found that absolute deviation perfectly tracks this double descent curve. As shown in Figure 2, absolute deviation peaks exactly at the interpolation threshold—where the model is just large enough to fit the training set—and then decreases as the model enters the second descent. In contrast, linear region density increases monotonically with model width, failing to reflect the improved generalization and increased smoothness of larger models.

Additional findings include:

  • Poor Correlation: The Spearman rank correlation between density and absolute deviation was found to be near zero or negative, confirming that counting regions does not accurately measure functional nonlinearity.
  • Task Complexity: Absolute deviation correctly ranks task difficulty. Models trained on 100% noisy labels exhibited the highest absolute deviation, whereas density provided inconsistent rankings across architectures.
  • Regularization Effects: Data augmentation was found to significantly reduce absolute deviation, effectively "smoothing" the network's nonlinearity even when the number of linear regions remained high.

Conclusion and Future Work

This work demonstrates that overparameterized models do not necessarily become more complex in a functional sense; instead, they use their extra capacity to become smoother near the data manifold. While the current measures are limited to 1D paths, they provide a much more reliable indicator of generalization than traditional region counting. Future research may explore weighting linear regions by their contribution to the overall function to create a more robust, high-dimensional complexity metric.

Summary updated

Abstract

The number of linear regions has been studied as a proxy of complexity for ReLU networks. However, the empirical success of network compression techniques like pruning and knowledge distillation, suggest that in the overparameterized setting, linear regions density might fail to capture the effective nonlinearity. In this work, we propose an efficient algorithm for discovering linear regions and use it to investigate the effectiveness of density in capturing the nonlinearity of trained VGGs and ResNets on CIFAR-10 and CIFAR-100. We contrast the results with a more principled nonlinearity measure based on function variation, highlighting the shortcomings of linear regions density. Furthermore, interestingly, our measure of nonlinearity clearly correlates with model-wise deep double descent, connecting reduced test error with reduced nonlinearity, and increased local similarity of linear regions.
BibTeX
@inproceedings{gamba2022are,
  author = {Matteo Gamba and Adrian Chmielewski-Anders and Josephine Sullivan and Hossein Azizpour and Mårten Björkman},
  title = {{Are All Linear Regions Created Equal?}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=GVz79wN2XRn},
}
Figure