# Learning Narrow One-Hidden-Layer ReLU Networks

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 38 references that are in the map.
- First posted on arXiv 20 Apr 2023.

## Builds on (most cited first, 26 of 26)

- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [SGD Learns the Conjugate Kernel Class of the Network](https://mlsanity.com/paper/1702.08503/) (2017)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [Learning One-hidden-layer ReLU Networks via Gradient Descent](https://mlsanity.com/paper/1806.07808/) (2018)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Learning Polynomials of Few Relevant Dimensions](https://mlsanity.com/paper/2004.13748/) (2020)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Learning Two Layer Rectified Neural Networks in Polynomial Time](https://mlsanity.com/paper/1811.01885/) (2018)
- [Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models](https://mlsanity.com/paper/2012.07774/) (2020)
- [Distribution-Specific Hardness of Learning Neural Networks](https://mlsanity.com/paper/1609.01037/) (2016)
- [Learning Deep ReLU Networks Is Fixed-Parameter Tractable](https://mlsanity.com/paper/2009.13512/) (2020)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Learning Two-layer Neural Networks with Symmetric Inputs](https://mlsanity.com/paper/1810.06793/) (2018)
- [Learning One Convolutional Layer with Overlapping Patches](https://mlsanity.com/paper/1802.02547/) (2018)
- [Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds](https://mlsanity.com/paper/1805.02677/) (2018)
- [ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time](https://mlsanity.com/paper/1510.03528/) (2015)
- [Hardness of Learning Neural Networks with Natural Weights](https://mlsanity.com/paper/2006.03177/) (2020)
- [Learning One-hidden-layer Neural Networks under General Input Distributions](https://mlsanity.com/paper/1810.04133/) (2018)
- [Efficiently Learning Any One Hidden Layer ReLU Network From Queries](https://mlsanity.com/paper/2111.04727/) (2021)
- [Learning Polynomial Transformations](https://mlsanity.com/paper/2204.04209/) (2022)

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

- [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Hardness of Learning Neural Networks under the Manifold Hypothesis](https://mlsanity.com/paper/2406.01461/) (2024)
- [On Single Index Models beyond Gaussian Data](https://mlsanity.com/paper/2307.15804/) (2023)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions](https://mlsanity.com/paper/2502.06443/) (2025)
- [A faster and simpler algorithm for learning shallow networks](https://mlsanity.com/paper/2307.12496/) (2023)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Gradient dynamics for low-rank fine-tuning beyond kernels](https://mlsanity.com/paper/2411.15385/) (2024)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees](https://mlsanity.com/paper/2502.16021/) (2025)
- [Most Neural Networks Are Almost Learnable](https://mlsanity.com/paper/2305.16508/) (2023)

## Abstract (arXiv)

We consider the well-studied problem of learning a linear combination of k ReLU activations with respect to a Gaussian distribution on inputs in d dimensions. We give the first polynomial-time algorithm that succeeds whenever k is a constant. All prior polynomial-time learners require additional assumptions on the network, such as positive combining coefficients or the matrix of hidden weight vectors being well-conditioned. Our approach is based on analyzing random contractions of higher-order moment tensors. We use a multi-scale analysis to argue that sufficiently close neurons can be collapsed together, sidestepping the conditioning issues present in prior work. This allows us to design an iterative procedure to discover individual neurons.