On the Connection Between Learning Two-Layers 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 $\mathbf{x}\in {\mathbb{R}}^d$, $r$ hidden units with weights $\{{\mathbf{w}}_i{\}}_{1\le i\le r}$ and output $y\in \mathbb{R}$, i.e., $y={\sum }_{i=1}^r\sigma ({\mathbf{w}}_i^{\mathsf{T}}\mathbf{x})$, with activation functions given by low-degree polynomials. In particular, if $\sigma (x)=a_0+a_{1}x+a_3{x}^3$, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable $\mathbb{E}(y)$, when $d^{3/2}\ll r\ll d^2$. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors $\mathbf{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.

41 pages, 1 figure

References in corpus (6)

• Understanding deep learning requires rethinking generalization
• Recovery Guarantees for One-hidden-layer Neural Networks
• Learning One-hidden-layer Neural Networks with Landscape Design
• Tensor principal component analysis via sum-of-squares proofs
• Distribution-Specific Hardness of Learning Neural Networks
• Polynomial-time Tensor Decompositions with Sum-of-Squares

Cited by in corpus (15)

• Optimization for deep learning: theory and algorithms
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• A Selective Overview of Deep Learning
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Decoupling Gating from Linearity
• Tensor Methods for Additive Index Models under Discordance and Heterogeneity
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• The Mismatch Principle: The Generalized Lasso Under Large Model Uncertainties
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• The Rate of Convergence of Variation-Constrained Deep Neural Networks
• Achieving Small Test Error in Mildly Overparameterized Neural Networks