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 show that in certain overcomplete regimes, where the number of hidden units is large relative to the input dimension, learning becomes computationally equivalent to the hard problem of tensor decomposition.
Introduction
In deep learning theory, there is a significant gap between the empirical success of neural networks and our theoretical understanding of their learnability. While massive networks are trained daily, proving why and when they can be learned efficiently remains a challenge. Most existing hardness proofs focus on worst-case scenarios with artificial datasets. Mondelli and Montanari address this by investigating the average-case complexity of learning a simple two-layer neural network on "natural" data distributions, such as Gaussian inputs. They aim to identify regimes where learning is computationally impossible for any efficient algorithm, despite being information-theoretically possible.
Methods
The authors employ a reduction technique to link neural network learning with tensor decomposition. Specifically, they demonstrate that efficiently learning the weights of a two-layer network would imply an efficient solution for decomposing a 3rd-order tensor into rank-1 components.
The study relies on several key theoretical components:
- Complexity-Theoretic Assumptions: The results are based on the conjecture that no polynomial-time algorithm can solve tensor decomposition when the number of components $r$ significantly exceeds $d^{1.5}$, where $d$ is the input dimension.
- Activation Functions: The analysis primarily focuses on low-degree polynomial activations, such as $\sigma(x) = a_0 + a_1x + a_3x^3$.
- Synthetic Generative Models: To validate their theory, the authors use synthetic datasets where feature vectors $x$ are standard Gaussians in $\mathbb{R}^d$, and weights $w$ are random isotropic vectors. Labels $y$ are generated by a ground-truth two-layer network.
Numerical experiments were conducted with $n = 5 \times 10^6$ samples, input dimension $d=50$, and varying hidden units $r \in \{50, 350, 2500\}$.
Results
A central finding is the existence of a "weight estimation bottleneck": for these networks, generalization is fundamentally tied to accurate weight recovery. If an algorithm cannot recover the underlying weight vectors, its prediction error remains as high as a trivial baseline that simply outputs the average label.
The paper identifies a "hard regime" when the number of hidden units $r$ satisfies $d^{3/2} \ll r \ll d^2$. In this regime, the problem transitions from being computationally easy to average-case hard. This difficulty is intrinsically linked to the geometry of high-dimensional tensors, where the network's weight information is encoded in a manner mirroring tensor decomposition.
Numerical results using Stochastic Gradient Descent (SGD) confirm these theoretical predictions. As shown in the figures above, for $r=50$, the generalization error decreases significantly. However, as $r$ increases to 2500 (with $d=50$), SGD fails to learn anything useful, matching the predicted $d^{3/2}$ barrier.
Discussion
While the core proofs rely on polynomial activation functions and Gaussian inputs, the authors argue that these results highlight fundamental computational barriers. Common activations like ReLU can be approximated by polynomials, suggesting the robustness of this connection. Future work may explore whether different data generative models or extreme over-parameterization could bypass these tensor-based bottlenecks. The study underscores that even "simple" neural network architectures can present profound computational challenges when the number of hidden units is large.
Summary updated