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

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

## 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 (most cited first, 22 of 22)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (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)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (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)
- [Learning Deep ReLU Networks Is Fixed-Parameter Tractable](https://mlsanity.com/paper/2009.13512/) (2020)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Learning Two-layer Neural Networks with Symmetric Inputs](https://mlsanity.com/paper/1810.06793/) (2018)
- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [Spectral Learning on Matrices and Tensors](https://mlsanity.com/paper/2004.07984/) (2020)
- [Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability](https://mlsanity.com/paper/1304.8087/) (2013)
- [Smoothed Analysis in Unsupervised Learning via Decoupling](https://mlsanity.com/paper/1811.12361/) (2018)
- [Fourier PCA and Robust Tensor Decomposition](https://mlsanity.com/paper/1306.5825/) (2013)

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

- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Identifiability of Deep Polynomial Neural Networks](https://mlsanity.com/paper/2506.17093/) (2025)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [Efficiently Learning Any One Hidden Layer ReLU Network From Queries](https://mlsanity.com/paper/2111.04727/) (2021)
- [Global Convergence of SGD On Two Layer Neural Nets](https://mlsanity.com/paper/2210.11452/) (2022)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Global Convergence of SGD For Logistic Loss on Two Layer Neural Nets](https://mlsanity.com/paper/2309.09258/) (2023)
- [Most Neural Networks Are Almost Learnable](https://mlsanity.com/paper/2305.16508/) (2023)
- [Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes](https://mlsanity.com/paper/2311.10972/) (2023)
- [Low-Rank Tensor Decompositions for the Theory of Neural Networks](https://mlsanity.com/paper/2508.18408/) (2025)
- [Training a Two Layer ReLU Network Analytically](https://mlsanity.com/paper/2304.02972/) (2023)
- [On the Hardness of Learning One Hidden Layer Neural Networks](https://mlsanity.com/paper/2410.03477/) (2024)
- [Langevin Monte-Carlo Provably Learns Depth Two Neural Nets at Any Size and Data](https://mlsanity.com/paper/2503.10428/) (2025)
- [Provably Extracting the Features from a General Superposition](https://mlsanity.com/paper/2512.15987/) (2025)

## 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.