On the Connection Between Learning Two-Layer Neural Networks and Tensor Decomposition
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 BibTeX @InProceedings{pmlr-v89-mondelli19a, title = {On the Connection Between Learning Two-Layer Neural Networks and Tensor Decomposition}, author = {Mondelli, Marco and Montanari, Andrea}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1051--1060}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/mondelli19a/mondelli19a.pdf}, url = {https://proceedings.mlr.press/v89/mondelli19a.html}, 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 < Copy to Clipboard Download Endnote %0 Conference Paper %T On the Connection Between Learning Two-Layer Neural Networks and Tensor Decomposition %A Marco Mondelli %A Andrea Montanari %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings o