Abstract
Theoretical understanding of deep learning often relies on "linearization" frameworks like the Neural Tangent Kernel (NTK), which approximate neural networks as linear models over fixed features. However, these theories fail to explain why neural networks significantly outperform traditional linear methods in practice. This paper addresses this gap by proving that two-layer neural networks can efficiently learn "sparse parities"—a class of functions where linear methods require exponential resources. We demonstrate that gradient descent enables neural networks to perform non-linear feature learning, creating an exponential separation in complexity between deep learning and fixed-feature linear models.
Introduction
A central question in machine learning theory is whether neural networks are fundamentally more powerful than linear methods acting on fixed, high-dimensional representations. While the NTK regime suggests networks behave like linear classifiers at initialization, this "lazy training" perspective ignores the adaptive feature learning that characterizes deep learning.
To investigate this, we focus on sparse parities: functions that compute the XOR of a small subset of input bits. Parities are notoriously difficult for most algorithms and serve as a rigorous test for non-linear learning capabilities. We show that while linear models are "blind" to these structures without an exponential number of features, neural networks can adaptively discover the relevant bits.
Methodology
We analyze a standard depth-two neural network utilizing the ReLU6 activation function ($\min(\max(x, 0), 6)$). The network is trained using standard gradient descent with a symmetric initialization, where weights are initialized in pairs with opposite signs to facilitate the learning of parity structures.
Our analysis compares:
- Linear Methods: Models that learn a linear classifier over a fixed, data-independent embedding (e.g., kernels, random features).
- Neural Networks: The depth-two model where both layers are updated via gradient descent, allowing for feature adaptation.
We introduce a family of distributions ($D_A$) over the $n$-dimensional hypercube $\{ \pm 1/\sqrt{n} \}^n$. These distributions are designed such that the first gradient step of a neural network can identify the relevant bits for a parity function, whereas linear methods remain at chance level.
Experimental Setup: MNIST-Parity
To validate our theoretical findings on more realistic data, we developed the MNIST-parity benchmark. In this task, the model is presented with a strip of $k$ random MNIST digits. The objective is to predict whether the sum of the digits in the strip is even or odd. This task requires the model to first recognize individual digits (feature learning) and then compute their parity (non-linear combination).
Key Results and Discussion
Our theoretical analysis yields two primary results:
- Exponential Separation: Theorem 1 proves that for any fixed embedding of dimension $N$, the error on sparse parities remains near random guessing unless $N$ or the weight norm $B$ grows exponentially with the number of relevant bits.
- Polynomial Success for NNs: Conversely, Theorem 2 proves that a two-layer ReLU6 network trained with gradient descent achieves small error in a polynomial number of iterations.
The experimental results on MNIST-parity confirm these findings. As shown in the figures below, when $k=1$ (a simple digit classification task), all models perform well. However, for $k=3$, a significant gap emerges.
In the $k=3$ case, linear models—including those in the NTK regime—perform at roughly 50% accuracy (random chance). In contrast, the ReLU neural network achieves nearly 80% accuracy. This demonstrates that the network is not merely acting as a fixed kernel but is actively learning the underlying features necessary to solve the parity problem.
Conclusion
This work provides a rigorous mathematical foundation for the superiority of neural networks over linear methods. By demonstrating an exponential gap in learning sparse parities, we highlight the critical role of adaptive feature learning. Future work will focus on extending these results to deeper architectures and identifying broader classes of "natural" distributions that exhibit similar separations between linear and non-linear learning regimes.
Summary updated