[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 wi and output y, i.e., y=∑ri=1σ(wTix), with activation functions given by low-degree polynomials. In particular, if σ(x)=a0+a1x+a3x3, 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