mlsanityData to 14 Oct 2026

Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations

arXiv 2107.10209 ↗First posted 21 Jul 2021cs.LG cs.DS stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

We present polynomial time and sample efficient algorithms for learning an unknown depth-2 feedforward neural network with general ReLU activations, under mild non-degeneracy assumptions. In particular, we consider learning an unknown network of the form f(x) = a^mathsfTσ(W^mathsfTx+b), where x is drawn from the Gaussian distribution, and σ(t) := max(t,0) is the ReLU activation. Prior works for learning networks with ReLU activations assume that the bias b is zero. In order to deal with the presence of the bias terms, our proposed algorithm consists of robustly decomposing multiple higher order tensors arising from the Hermite expansion of the function f(x). Using these ideas we also establish identifiability of the network parameters under minimal assumptions.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 22 of its 38 references that are in the map. First posted on arXiv 21 Jul 2021.

Builds on

22 of 38 references.

References · 22

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2021Convex optimizationcited by 2,515
  3. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  4. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  6. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  7. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  8. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  9. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  10. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  11. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  12. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
10 more
  1. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  2. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
  3. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  4. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  5. 2018Learning Two-layer Neural Networks with Symmetric Inputscited by 22
  6. 2013Smoothed Analysis of Tensor Decompositionscited by 19
  7. 2020Spectral Learning on Matrices and Tensorscited by 16
  8. 2013Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiabilitycited by 9
  9. 2018Smoothed Analysis in Unsupervised Learning via Decouplingcited by 9
  10. 2013Fourier PCA and Robust Tensor Decompositioncited by 8

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 2; 2023: 5; 2024: 3; 2025: 4.

15 papers.

Sort:

By area:

  1. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 28
  2. 2025Identifiability of Deep Polynomial Neural Networkscited by 12
  3. 2024Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Timecited by 11
  4. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  5. 2021Efficiently Learning Any One Hidden Layer ReLU Network From Queriescited by 6
  6. 2022Global Convergence of SGD On Two Layer Neural Netscited by 5
  7. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  8. 2023Global Convergence of SGD For Logistic Loss on Two Layer Neural Netscited by 3
  9. 2023Most Neural Networks Are Almost Learnablecited by 2
  10. 2023Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopescited by 2
  11. 2025Low-Rank Tensor Decompositions for the Theory of Neural Networkscited by 2
  12. 2023Training a Two Layer ReLU Network Analyticallycited by 1
3 more
  1. 2024On the Hardness of Learning One Hidden Layer Neural Networkscited by 1
  2. 2025Langevin Monte-Carlo Provably Learns Depth Two Neural Nets at Any Size and Datacited by 1
  3. 2025Provably Extracting the Features from a General Superpositioncited by 1