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 using ReLU activations are essentially massive piecewise linear functions. The input space is partitioned into many "linear regions," where the network behaves like a simple affine transformation ($y = Wx + b$). Historically, researchers have used the density of these regions—simply counting how many there are—to estimate a model's expressivity or complexity.

However, the authors argue that "counting" is a poor metric. A network could have millions of tiny linear regions that are nearly identical (low effective nonlinearity), or a few regions with wildly different slopes (high effective nonlinearity). Furthermore, existing methods to count these regions are either mathematically intractable for large networks or rely on "uniform sampling," which often misses small regions. This paper introduces a more principled measure of nonlinearity called absolute deviation.

Methods

The paper contributes two major technical components:

  1. Adaptive Linear Region Discovery: Instead of jumping across the input space with a fixed step size, the authors developed an algorithm that analytically finds the exact boundaries of linear regions along a 1D path. By solving the linear equations induced by each ReLU layer, the algorithm "travels" from one boundary to the next, ensuring no regions are missed regardless of how small they are.
  2. Absolute Deviation: To quantify "effective" nonlinearity, the authors measure the area between the actual network function and a simple linear interpolation between two points. Unlike density, this metric accounts for the slope, bias, and size of every region along the path.
Visualizing linear regions and the absolute deviation metric along a 1D path.

The researchers evaluated their methods on standard image classification benchmarks, CIFAR-10 and CIFAR-100, using VGG8 and ResNet18 architectures trained under various conditions, including clean labels, noisy labels, and different levels of data augmentation.

Key Insights and Results

The study reveals that density is a "fragile" metric. The number of linear regions often fails to correlate with a model's actual performance or the complexity of the task. In some cases, the correlation between region density and actual nonlinearity is even negative (e.g., Spearman rank correlation as low as -0.15 for VGG8).

The Double Descent Connection

A striking finding is the link to Deep Double Descent. As models increase in width, their test error first decreases, then increases (overfitting), and finally decreases again (the second descent). The authors found that absolute deviation follows this error curve, peaking at the interpolation threshold and then decreasing. Meanwhile, region density continues to increase monotonically with model width. This suggests that as very large models generalize better, they actually become "smoother" and less nonlinear.

Absolute deviation and density vs. ResNet base width, showing the correlation between deviation and the double descent error curve.

Sensitivity to Noise and Regularization

Models forced to memorize noisy labels exhibit much higher absolute deviation than those trained on clean data. They become "wigglier" to fit the noise, even if their region count doesn't change proportionally. Additionally, absolute deviation clearly distinguishes between "vanilla" models and those using data augmentation (which promotes smoothness), whereas density struggles to show a consistent difference.

Limitations and Future Work

While the proposed method is more principled, it currently measures nonlinearity along 1D paths in the input space. While "data-driven paths" are used to stay near the data manifold, this doesn't capture the full high-dimensional geometry of the regions. Furthermore, the adaptive discovery algorithm still requires sequential passes through the network layers, which can be slow for extremely deep architectures. Future work could explore weighting regions by their contribution to the output to create an even more robust 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