# Learning Two-layer Neural Networks with Symmetric Inputs

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

## Key facts

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

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

- [C-Mixup: Improving Generalization in Regression](https://mlsanity.com/paper/2210.05775/) (2022)
- [A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network](https://mlsanity.com/paper/2102.02410/) (2021)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Identifiability of Deep Polynomial Neural Networks](https://mlsanity.com/paper/2506.17093/) (2025)
- [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)
- [Scaffolding Sets](https://mlsanity.com/paper/2111.03135/) (2021)
- [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)
- [Global Convergence of SGD On Two Layer Neural Nets](https://mlsanity.com/paper/2210.11452/) (2022)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [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)
- [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)
- [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 give a new algorithm for learning a two-layer neural network under a general class of input distributions. Assuming there is a ground-truth two-layer network  y = A σ(Wx) + xi,  where A,W are weight matrices, xi represents noise, and the number of neurons in the hidden layer is no larger than the input or output, our algorithm is guaranteed to recover the parameters A,W of the ground-truth network. The only requirement on the input x is that it is symmetric, which still allows highly complicated and structured input. Our algorithm is based on the method-of-moments framework and extends several results in tensor decompositions. We use spectral algorithms to avoid the complicated non-convex optimization in learning neural networks. Experiments show that our algorithm can robustly learn the ground-truth neural network with a small number of samples for many symmetric input distributions.