On the connection between learning two-layers neural networks and tensor decomposition

M. Mondelli, A. Montanari, ArXiv:1802.07301 (n.d.).

Preprint | Draft | English
Author
;
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∈ℝd, r hidden units with weights {wi}1≤i≤r and output y∈ℝ, i.e., y=∑ri=1σ(w𝖳ix), with activation functions given by low-degree polynomials. In particular, if σ(x)=a0+a1x+a3x3, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable 𝔼(y), when d3/2≪r≪d2. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors x, and output distributed according to a two-layer neural network with random isotropic weights, and under a certain complexity-theoretic assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time algorithm can substantially outperform current methods for tensor decomposition based on the sum-of-squares hierarchy. We also prove generalizations of this statement for higher degree polynomial activations, and non-random weight vectors. Remarkably, several existing algorithms for learning two-layer networks with rigorous guarantees are based on tensor decomposition. Our results support the idea that this is indeed the core computational difficulty in learning such networks, under the stated generative model for the data. As a side result, we show that under this model learning the network requires accurate learning of its weights, a property that does not hold in a more general setting.
Publishing Year
Date Published
2018-10-10
Journal Title
arXiv:1802.07301
Page
41
IST-REx-ID

Cite this

Mondelli M, Montanari A. On the connection between learning two-layers neural networks and tensor  decomposition. arXiv:180207301.
Mondelli, M., & Montanari, A. (n.d.). On the connection between learning two-layers neural networks and tensor  decomposition. ArXiv:1802.07301.
Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning Two-Layers Neural Networks and Tensor  Decomposition.” ArXiv:1802.07301, n.d.
M. Mondelli and A. Montanari, “On the connection between learning two-layers neural networks and tensor  decomposition,” arXiv:1802.07301. .
Mondelli M, Montanari A. On the connection between learning two-layers neural networks and tensor  decomposition. arXiv:1802.07301.
Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning Two-Layers Neural Networks and Tensor  Decomposition.” ArXiv:1802.07301.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1802.07301

Search this title in

Google Scholar