# Learning Two Layer Rectified Neural Networks in Polynomial Time

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2018.

## Built on by (most cited first, 30 of 31)

- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis](https://mlsanity.com/paper/2201.08514/) (2022)
- [Hardness of Learning Neural Networks under the Manifold Hypothesis](https://mlsanity.com/paper/2406.01461/) (2024)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis](https://mlsanity.com/paper/2206.12802/) (2022)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [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)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [A faster and simpler algorithm for learning shallow networks](https://mlsanity.com/paper/2307.12496/) (2023)
- [Efficiently Learning Any One Hidden Layer ReLU Network From Queries](https://mlsanity.com/paper/2111.04727/) (2021)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learning](https://mlsanity.com/paper/2405.15920/) (2024)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields](https://mlsanity.com/paper/2305.00322/) (2023)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions](https://mlsanity.com/paper/2406.11640/) (2024)
- [Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees](https://mlsanity.com/paper/2502.16021/) (2025)
- [Overparameterized ReLU Neural Networks Learn the Simplest Models: Neural Isometry and Exact Recovery](https://mlsanity.com/paper/2209.15265/) (2022)
- [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)
- [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)
- [Training Neural Networks is existsmathbb R-complete](https://mlsanity.com/paper/2102.09798/) (2021)
- [Neural Optimization Kernel: Towards Robust Deep Learning](https://mlsanity.com/paper/2106.06097/) (2021)

## Abstract (arXiv)

Consider the following fundamental learning problem: given input examples x ∈ ℝd and their vector-valued labels, as defined by an underlying generative neural network, recover the weight matrices of this network. We consider two-layer networks, mapping ℝd to ℝm, with k non-linear activation units f(·), where f(x) = max x , 0 is the ReLU. Such a network is specified by two weight matrices, U^* ∈ ℝm × k, V^* ∈ ℝk × d, such that the label of an example x ∈ ℝd is given by U^* f(V^* x), where f(·) is applied coordinate-wise. Given n samples as a matrix X ∈ ℝd × n and the (possibly noisy) labels U^* f(V^* X) + E of the network on these samples, where E is a noise matrix, our goal is to recover the weight matrices U^* and V^*. In this work, we develop algorithms and hardness results under varying assumptions on the input and noise. Although the problem is NP-hard even for k=2, by assuming Gaussian marginals over the input X we are able to develop polynomial time algorithms for the approximate recovery of U^* and V^*. Perhaps surprisingly, in the noiseless case our algorithms recover U^*,V^* exactly, i.e., with no error. To the best of the our knowledge, this is the first algorithm to accomplish exact recovery. For the noisy case, we give the first polynomial time algorithm that approximately recovers the weights in the presence of mean-zero noise E. Our algorithms generalize to a larger class of rectified activation functions, f(x) = 0 when x≤ 0, and f(x) > 0 otherwise.