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

Marco Mondelli; Andrea Montanari

AISTATS 2019poster60 citations

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 <

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 <