mlsanityData to 7 Oct 2026

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

arXiv 2205.09072 ↗First posted 18 May 2022cs.LG stat.MLcited by 21

Not on the map. Why?

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.

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

Builds on

36 of 56 references.

References · 36

  1. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  4. 2018On Lazy Training in Differentiable Programmingcited by 671
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  6. 2017Exploring Generalization in Deep Learningcited by 595
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  8. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  9. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  10. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  11. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
  12. 2020Directional convergence and alignment in deep learningcited by 172
24 more
  1. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  2. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  3. 2020Implicit Regularization in Deep Learning May Not Be Explainable by Normscited by 118
  4. 2019A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Casecited by 113
  5. 2019How do infinite width bounded norm networks look in function space?cited by 105
  6. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  7. 2017Implicit Regularization in Deep Learningcited by 90
  8. 2018Gradient Descent Quantizes ReLU Network Featurescited by 57
  9. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  10. 2020Revealing the Structure of Deep Neural Networks via Convex Dualitycited by 54
  11. 2022Implicit Regularization Towards Rank Minimization in ReLU Networkscited by 53
  12. 2020Convex Geometry and Duality of Over-parameterized Neural Networkscited by 49
  13. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  14. 2019Gradient Dynamics of Shallow Univariate ReLU Networkscited by 46
  15. 2020Implicit Regularization in ReLU Networks with the Square Losscited by 45
  16. 2021Continuous vs. Discrete Optimization of Deep Neural Networkscited by 34
  17. 2021On Margin Maximization in Linear and ReLU Networkscited by 34
  18. 2020The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networkscited by 33
  19. 2019Neural tangent kernels, transportation mappings, and universal approximationcited by 30
  20. 2020Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale of Symmetrycited by 17
  21. 2021Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry IIcited by 16
  22. 2020Shallow Univariate ReLu Networks as Splines: Initialization, Loss Surface, Hessian, & Gradient Flow Dynamicscited by 13
  23. 2021Ridgeless Interpolation with Shallow ReLU Networks in 1D is Nearest Neighbor Curvature Extrapolation and Provably Generalizes on Lipschitz Functionscited by 8
  24. 2019Path Length Bounds for Gradient Descent and Flowcited by 6

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 9; 2024: 7; 2025: 2.

21 papers.

Sort:

By area:

  1. 2022On the Implicit Bias in Deep-Learning Algorithmscited by 84
  2. 2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
  3. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  4. 2023The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networkscited by 23
  5. 2023Leveraging the two timescale regime to demonstrate convergence of neural networkscited by 18
  6. 2023Implicit Bias of Gradient Descent for Two-layer ReLU and Leaky ReLU Networks on Nearly-orthogonal Datacited by 18
  7. 2023Penalising the biases in norm regularisation enforces sparsitycited by 17
  8. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  9. 2024Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Contextcited by 14
  10. 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
  11. 2024Simplicity Bias of Two-Layer Networks beyond Linearly Separable Datacited by 11
  12. 2024Directional Convergence Near Small Initializations and Saddles in Two-Homogeneous Neural Networkscited by 10
9 more
  1. 2024Topological obstruction to the training of shallow ReLU neural networkscited by 6
  2. 2022Nonlinear Advantage: Trained Networks Might Not Be As Complex as You Thinkcited by 4
  3. 2024Provable Privacy Attacks on Trained Shallow Neural Networkscited by 4
  4. 2023Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithmscited by 2
  5. 2023The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learningcited by 2
  6. 2024Symmetry & Critical Pointscited by 2
  7. 2025Understanding Nonlinear Implicit Bias via Region Counts in Input Spacecited by 2
  8. 2025A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorizationcited by 1
  9. 2024Disentangle Sample Size and Initialization Effect on Perfect Generalization for Single-Neuron Targetcited by 0