mlsanityData to 7 Oct 2026

Overparameterized ReLU Neural Networks Learn the Simplest Models: Neural Isometry and Exact Recovery

arXiv 2209.15265 ↗First posted 30 Sep 2022cs.LG cs.IT math.ITcited by 3

Not on the map. Why?

Abstract (arXiv)

The practice of deep learning has shown that neural networks generalize remarkably well even with an extreme number of learned parameters. This appears to contradict traditional statistical wisdom, in which a trade-off between model complexity and fit to the data is essential. We aim to address this discrepancy by adopting a convex optimization and sparse recovery perspective. We consider the training and generalization properties of two-layer ReLU networks with standard weight decay regularization. Under certain regularity assumptions on the data, we show that ReLU networks with an arbitrary number of parameters learn only simple models that explain the data. This is analogous to the recovery of the sparsest linear model in compressed sensing. For ReLU networks and their variants with skip connections or normalization layers, we present isometry conditions that ensure the exact recovery of planted neurons. For randomly generated data, we show the existence of a phase transition in recovering planted neural network models, which is easy to describe: whenever the ratio between the number of samples and the dimension exceeds a numerical threshold, the recovery succeeds with high probability; otherwise, it fails with high probability. Surprisingly, ReLU networks learn simple and sparse models that generalize well even when the labels are noisy . The phase transition phenomenon is confirmed through numerical experiments.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 33 of its 47 references that are in the map. First posted on arXiv 30 Sep 2022.

Builds on

33 of 47 references.

References · 33

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2020Denoising Diffusion Probabilistic Modelscited by 20,851
  3. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  6. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  7. 2018On Lazy Training in Differentiable Programmingcited by 671
  8. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  9. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  10. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  11. 2017Train longer, generalize better: closing the generalization gap in large batch training of neural networkscited by 278
  12. 2017Three Factors Influencing Minima in SGDcited by 270
21 more
  1. 2019Linearized two-layers neural networks in high dimensioncited by 155
  2. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  3. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  4. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  5. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 96
  6. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  7. 2017Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapescited by 84
  8. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  9. 2017Learning ReLUs via Gradient Descentcited by 54
  10. 2017An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysiscited by 52
  11. 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
  12. 2020Convex Geometry and Duality of Over-parameterized Neural Networkscited by 49
  13. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  14. 2022Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformerscited by 30
  15. 2021Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programscited by 25
  16. 2018Learning Two-layer Neural Networks with Symmetric Inputscited by 22
  17. 2021Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularizationcited by 21
  18. 2021Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Timecited by 14
  19. 2021Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutionscited by 14
  20. 2021The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Programcited by 11
  21. 2020How Many Factors Influence Minima in SGD?cited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2.

3 papers.

  1. 2023Efficient Compression of Overparameterized Deep Models through Low-Dimensional Learning Dynamicscited by 3
  2. 2024When Are Bias-Free ReLU Networks Effectively Linear Networks?cited by 3
  3. 2024Sequencing the Neurome: Towards Scalable Exact Parameter Reconstruction of Black-Box Neural Networkscited by 0