Learning Parities with Neural Networks

Amit Daniely, Eran Malach

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:

  1. Linear Methods: Models that learn a linear classifier over a fixed, data-independent embedding (e.g., kernels, random features).
  2. 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.

Accuracy comparison on MNIST-parity for k=1 and k=3. While all models succeed at k=1, only the ReLU neural network learns the parity structure for k=3, while linear methods (NTK, Gaussian features) fail to exceed random chance.

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

Abstract

In recent years we see a rapidly growing line of research which shows learnability of various models via common neural network algorithms. Yet, besides a very few outliers, these results show learnability of models that can be learned using linear methods. Namely, such results show that learning neural-networks with gradient-descent is competitive with learning a linear classifier on top of a data-independent representation of the examples. This leaves much to be desired, as neural networks are far more successful than linear methods. Furthermore, on the more conceptual level, linear models don't seem to capture the "deepness" of deep networks. In this paper we make a step towards showing leanability of models that are inherently non-linear. We show that under certain distributions, sparse parities are learnable via gradient decent on depth-two network. On the other hand, under the same distributions, these parities cannot be learned efficiently by linear methods.
BibTeX
@inproceedings{daniely2020learning,
  author = {Amit Daniely and Eran Malach},
  title = {{Learning Parities with Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=cXZVZI1bAYW},
}
Figure