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


Marco Mondelli, Andrea Montanari ;
Proceedings of Machine Learning Research, PMLR 89:1051-1060, 2019.


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 <

Related Material