mlsanityData to 7 Oct 2026

A faster and simpler algorithm for learning shallow networks

arXiv 2307.12496 ↗First posted 24 Jul 2023cs.LG cs.DS stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

We revisit the well-studied problem of learning a linear combination of k ReLU activations given labeled examples drawn from the standard d-dimensional Gaussian measure. Chen et al. [CDG+23] recently gave the first algorithm for this problem to run in poly(d,1/varepsilon) time when k = O(1), where varepsilon is the target error. More precisely, their algorithm runs in time (d/varepsilon)quasipoly(k) and learns over multiple stages. Here we show that a much simpler one-stage version of their algorithm suffices, and moreover its runtime is only (d/varepsilon)O(k2).

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 21 of its 28 references that are in the map. First posted on arXiv 24 Jul 2023.

Builds on

21 of 28 references.

References · 21

  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 79
  5. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 57
  6. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  7. 2017Learning ReLUs via Gradient Descentcited by 54
  8. 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
  9. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  10. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  11. 2020Approximation Schemes for ReLU Regressioncited by 34
  12. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
9 more
  1. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
  2. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  3. 2018Learning Two-layer Neural Networks with Symmetric Inputscited by 22
  4. 2018Learning One Convolutional Layer with Overlapping Patchescited by 21
  5. 2018Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Boundscited by 18
  6. 2015ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Timecited by 16
  7. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  8. 2018Learning One-hidden-layer Neural Networks under General Input Distributionscited by 7
  9. 2021Efficiently Learning Any One Hidden Layer ReLU Network From Queriescited by 6

Built on by

Cited by year

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

7 papers.

  1. 2024Provably learning a multi-head attention layercited by 21
  2. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  3. 2024On the hardness of learning under symmetriescited by 13
  4. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  5. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 5
  6. 2023Agnostically Learning Multi-index Models with Queriescited by 1
  7. 2025Provably Extracting the Features from a General Superpositioncited by 1