mlsanityData to 14 Oct 2026

Learning Narrow One-Hidden-Layer ReLU Networks

arXiv 2304.10524 ↗First posted 20 Apr 2023cs.LG cs.DS stat.MLcited by 14

Not on the map. Why?

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.

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

26 of 38 references.

References · 26

  1. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  2. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  3. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  4. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  5. 2017Failures of Gradient-Based Deep Learningcited by 80
  6. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  7. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  8. 2017Learning ReLUs via Gradient Descentcited by 54
  9. 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
  10. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  11. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  12. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
14 more
  1. 2020Approximation Schemes for ReLU Regressioncited by 34
  2. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  3. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
  4. 2016Distribution-Specific Hardness of Learning Neural Networkscited by 27
  5. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  6. 2016Polynomial-time Tensor Decompositions with Sum-of-Squarescited by 22
  7. 2018Learning Two-layer Neural Networks with Symmetric Inputscited by 22
  8. 2018Learning One Convolutional Layer with Overlapping Patchescited by 21
  9. 2018Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Boundscited by 18
  10. 2015ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Timecited by 16
  11. 2020Hardness of Learning Neural Networks with Natural Weightscited by 15
  12. 2018Learning One-hidden-layer Neural Networks under General Input Distributionscited by 7
  13. 2021Efficiently Learning Any One Hidden Layer ReLU Network From Queriescited by 6
  14. 2022Learning Polynomial Transformationscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 5; 2024: 5; 2025: 4.

14 papers.

Sort:

  1. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  2. 2024Provably learning a multi-head attention layercited by 21
  3. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  4. 2023On Single Index Models beyond Gaussian Datacited by 17
  5. 2024On the hardness of learning under symmetriescited by 13
  6. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 9
  7. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 9
  8. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  9. 2023A faster and simpler algorithm for learning shallow networkscited by 7
  10. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 6
  11. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  12. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
2 more
  1. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  2. 2023Most Neural Networks Are Almost Learnablecited by 2