# On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition

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

## Key facts

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

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

- [Tensor Networks Meet Neural Networks: A Survey and Future Perspectives](https://mlsanity.com/paper/2302.09019/) (2023)
- [Identifiability of Deep Polynomial Neural Networks](https://mlsanity.com/paper/2506.17093/) (2025)
- [Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence](https://mlsanity.com/paper/2411.08798/) (2024)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Finite Sample Identification of Wide Shallow Neural Networks with Biases](https://mlsanity.com/paper/2211.04589/) (2022)
- [The Rate of Convergence of Variation-Constrained Deep Neural Networks](https://mlsanity.com/paper/2106.12068/) (2021)
- [Provable Identifiability of Two-Layer ReLU Neural Networks via LASSO Regularization](https://mlsanity.com/paper/2305.04267/) (2023)
- [Achieving Small Test Error in Mildly Overparameterized Neural Networks](https://mlsanity.com/paper/2104.11895/) (2021)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Low-Rank Tensor Decompositions for the Theory of Neural Networks](https://mlsanity.com/paper/2508.18408/) (2025)
- [Reconfigurable Low-latency Memory System for Sparse Matricized Tensor Times Khatri-Rao Product on FPGA](https://mlsanity.com/paper/2109.08874/) (2021)
- [Sharp asymptotics on the compression of two-layer neural networks](https://mlsanity.com/paper/2205.08199/) (2022)
- [Towards Programmable Memory Controller for Tensor Decomposition](https://mlsanity.com/paper/2207.08298/) (2022)

## Abstract (arXiv)

We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors boldsymbol x ∈ mathbb Rd, r hidden units with weights boldsymbol wi1≤ i ≤ r and output y∈ mathbb R, i.e., y=sumi=1r σ( boldsymbol wimathsf Tboldsymbol x), with activation functions given by low-degree polynomials. In particular, if σ(x) = a0+a1x+a3x3, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable mathbb E(y), when d3/2ll rll d2. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors boldsymbol x, and output distributed according to a two-layer neural network with random isotropic weights, and under a certain complexity-theoretic assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time algorithm can substantially outperform current methods for tensor decomposition based on the sum-of-squares hierarchy. We also prove generalizations of this statement for higher degree polynomial activations, and non-random weight vectors. Remarkably, several existing algorithms for learning two-layer networks with rigorous guarantees are based on tensor decomposition. Our results support the idea that this is indeed the core computational difficulty in learning such networks, under the stated generative model for the data. As a side result, we show that under this model learning the network requires accurate learning of its weights, a property that does not hold in a more general setting.