On the Connection Between Learning TwoLayer Neural Networks and Tensor Decomposition
[edit]
Proceedings of Machine Learning Research, PMLR 89:10511060, 2019.
Abstract
We establish connections between the problem of learning a twolayer 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 lowdegree polynomials. In particular, if $\sigma(x) = a_0+a_1x+a_3x^3$, we prove that no polynomialtime algorithm can outperform the trivial predictor that assigns to each example the response variable $E(y)$, when $d^{3/2}<< r <
Related Material


