# On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias

arXiv: https://arxiv.org/abs/2205.09072 · HTML: https://mlsanity.com/paper/2205.09072/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 56 references that are in the map.
- First posted on arXiv 18 May 2022.

## Builds on (most cited first, 30 of 36)

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process](https://mlsanity.com/paper/1904.09080/) (2019)
- [Implicit Regularization in Deep Learning May Not Be Explainable by Norms](https://mlsanity.com/paper/2005.06398/) (2020)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1709.01953/) (2017)
- [Gradient Descent Quantizes ReLU Network Features](https://mlsanity.com/paper/1803.08367/) (2018)
- [SGD Learns the Conjugate Kernel Class of the Network](https://mlsanity.com/paper/1702.08503/) (2017)
- [Revealing the Structure of Deep Neural Networks via Convex Duality](https://mlsanity.com/paper/2002.09773/) (2020)
- [Implicit Regularization Towards Rank Minimization in ReLU Networks](https://mlsanity.com/paper/2201.12760/) (2022)
- [Convex Geometry and Duality of Over-parameterized Neural Networks](https://mlsanity.com/paper/2002.11219/) (2020)
- [A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network](https://mlsanity.com/paper/2102.02410/) (2021)
- [Gradient Dynamics of Shallow Univariate ReLU Networks](https://mlsanity.com/paper/1906.07842/) (2019)
- [Implicit Regularization in ReLU Networks with the Square Loss](https://mlsanity.com/paper/2012.05156/) (2020)
- [Continuous vs. Discrete Optimization of Deep Neural Networks](https://mlsanity.com/paper/2107.06608/) (2021)
- [On Margin Maximization in Linear and ReLU Networks](https://mlsanity.com/paper/2110.02732/) (2021)
- [The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks](https://mlsanity.com/paper/2006.01005/) (2020)

## Built on by (most cited first, 21 of 21)

- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data](https://mlsanity.com/paper/2210.07082/) (2022)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks](https://mlsanity.com/paper/2303.01456/) (2023)
- [Penalising the biases in norm regularisation enforces sparsity](https://mlsanity.com/paper/2303.01353/) (2023)
- [Leveraging the two timescale regime to demonstrate convergence of neural networks](https://mlsanity.com/paper/2304.09576/) (2023)
- [Implicit Bias of Gradient Descent for Two-layer ReLU and Leaky ReLU Networks on Nearly-orthogonal Data](https://mlsanity.com/paper/2310.18935/) (2023)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)
- [Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Context](https://mlsanity.com/paper/2410.01774/) (2024)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [Directional Convergence Near Small Initializations and Saddles in Two-Homogeneous Neural Networks](https://mlsanity.com/paper/2402.09226/) (2024)
- [Simplicity Bias of Two-Layer Networks beyond Linearly Separable Data](https://mlsanity.com/paper/2405.17299/) (2024)
- [Topological obstruction to the training of shallow ReLU neural networks](https://mlsanity.com/paper/2410.14837/) (2024)
- [Nonlinear Advantage: Trained Networks Might Not Be As Complex as You Think](https://mlsanity.com/paper/2211.17180/) (2022)
- [Provable Privacy Attacks on Trained Shallow Neural Networks](https://mlsanity.com/paper/2410.07632/) (2024)
- [Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms](https://mlsanity.com/paper/2302.12261/) (2023)
- [The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning](https://mlsanity.com/paper/2308.03215/) (2023)
- [Symmetry & Critical Points](https://mlsanity.com/paper/2408.14445/) (2024)
- [Understanding Nonlinear Implicit Bias via Region Counts in Input Space](https://mlsanity.com/paper/2505.11370/) (2025)
- [A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorization](https://mlsanity.com/paper/2506.20344/) (2025)
- [Disentangle Sample Size and Initialization Effect on Perfect Generalization for Single-Neuron Target](https://mlsanity.com/paper/2405.13787/) (2024)

## Abstract (arXiv)

We study the dynamics and implicit bias of gradient flow (GF) on univariate ReLU neural networks with a single hidden layer in a binary classification setting. We show that when the labels are determined by the sign of a target network with r neurons, with high probability over the initialization of the network and the sampling of the dataset, GF converges in direction (suitably defined) to a network achieving perfect training accuracy and having at most O(r) linear regions, implying a generalization bound. Unlike many other results in the literature, under an additional assumption on the distribution of the data, our result holds even for mild over-parameterization, where the width is tildeO(r) and independent of the sample size.