[edit]

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

*Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics*, PMLR 89:1051-1060, 2019.

#### Abstract

We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors $x$, $r$ hidden units with weights $w_i$ and output $y$, i.e., $y=\sum_{i=1}^r \sigma(w_i^{T} x)$, with activation functions given by low-degree polynomials. In particular, if $\sigma(x) = a_0+a_1x+a_3x^3$, we prove that no polynomial-time algorithm can outperform the trivial predictor that assigns to each example the response variable $E(y)$, when $d^{3/2}<< r <

#### Cite this Paper

```
``````
```

#### Related Material

```
```

```
```