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

Marco Mondelli, Andrea Montanari
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

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 <
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 of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-mondelli19a %I PMLR %P 1051--1060 %U https://proceedings.mlr.press/v89/mondelli19a.html %V 89 %X 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 <
APA
Mondelli, M. & Montanari, A.. (2019). On the Connection Between Learning Two-Layer Neural Networks and Tensor Decomposition. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1051-1060 Available from https://proceedings.mlr.press/v89/mondelli19a.html.

Related Material