Research map / Architectures and efficiency / RNNs and normalization
On the Local Complexity of Linear Regions in Deep ReLU Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines local complexity (density of linear regions near data under noisy biases) for ReLU networks and proves links to local rank of features, total variation/adversarial robustness, and representation cost/weight decay.
Problem
How the local density of linear regions of ReLU networks near the data distribution relates to feature learning (local rank), adversarial robustness (total variation), and optimization/implicit regularization (representation cost, weight decay).
Approach
Defines local complexity as the expected density of nonlinear locus over the data distribution under Gaussian bias noise, gives an explicit gradient-based formula via the co-area formula, and proves bounds linking it to local rank, total variation, and representation cost.
Key results
- Local complexity and local rank show a tightly related sudden drop late in training on Gaussian map-estimation task; theory gives sum of local ranks bounded by LC/(c_bias eps^2) plus error terms.
- Drop in total variation and local complexity in terminal phase of training on MNIST corresponds to increased adversarial robustness.
- Empirically, local complexity is typically lower for networks trained with larger weight decay, consistent with a Theta(log 1/lambda) bound in the rich regime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| learn lower-dimensional feature representations | ReLU networks · Input data distribution | local complexity | Helped |
| train into the terminal phase | 4-layer MLP, 200 neurons per layer · Gaussian input and output data | local rank | Hurt |
| train into the terminal phase | 4-layer MLP, 200 neurons per layer · Gaussian input and output data | local complexity | Hurt |
| train into the terminal phase | 4-layer MLP, 200 neurons per layer · MNIST subset | local complexity | Hurt |
| train into the terminal phase | 4-layer MLP, 200 neurons per layer · MNIST subset | adversarial robustness | Helped |
| increase weight decay | ReLU networks · Training experiments | local complexity | Helped |
Surprising findings
- Empirically the bias term B is typically measured as 0 for fully connected networks of reasonable width, so the correction term is negligible in practice.
- The bound between total variation and local complexity may not fully explain their relationship during training; dynamics can be more complex than the theory predicts.
Limitations
- Focuses on ReLU; extension to general piecewise linear activations is only conjectured.
- Training dynamics of local complexity remain an open problem; implicit minimization is argued heuristically.
- Several bounds are loose and depend on constants like C_grad and B that may be hard to control; no generalization bounds yet.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: local complexity local rank total variation adversarial robustness
Builds on: Hanin & Rolnick linear region counting grokking linear region dynamics (Humayun et al.) representation cost (Jacot et al.) neural collapse geometric complexity
Closest papers by meaning
- The Computational Complexity of Counting Linear Regions in ReLU Neural Networks (NeurIPS 2025 · similarity 0.90)
- On the Expected Complexity of Maxout Networks (NeurIPS 2021 · similarity 0.90)
- Understanding Deep Neural Networks with Rectified Linear Units (ICLR 2018 · similarity 0.90)
- Towards Theoretical Analysis of Transformation Complexity of ReLU DNNs (ICML 2022 · similarity 0.89)
- Make Haste Slowly: A Theory of Emergent Structured Mixed Selectivity in Feature Learning ReLU Networks (ICLR 2025 · similarity 0.88)
- Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.