Learning Parities with Neural Networks

Amit Daniely, Eran Malach

TL;DR

This paper provides a rigorous mathematical proof that neural networks are strictly more powerful than linear methods (like kernel methods or random features). By focusing on "sparse parities," the authors demonstrate an exponential separation: while linear models require exponential resources to solve these problems, a simple two-layer neural network trained with gradient descent can solve them in polynomial time.

The "Deepness" Gap

In recent years, much of the theoretical progress in understanding neural networks has relied on "linearization." Frameworks like the Neural Tangent Kernel (NTK) suggest that training a very wide neural network is essentially equivalent to training a linear classifier on a fixed, high-dimensional set of features.

While mathematically elegant, this perspective is unsatisfying. If neural networks were just "glorified kernel machines," they shouldn't be performing so much better than traditional linear methods in practice. This paper addresses this "deepness" gap by asking: Can we prove there are problems that neural networks can solve, but linear methods fundamentally cannot?

To answer this, the authors study sparse parities—a notoriously difficult family of functions where the output depends on whether the sum of a small subset of input bits is even or odd (essentially a multi-bit XOR).

Methods

The authors analyze a depth-two neural network using the ReLU6 activation function ($\min(\max(x, 0), 6)$). They train this network using standard gradient descent on both layers simultaneously.

To make the problem tractable for gradient-based optimization, they introduce a specific (though non-uniform) distribution of data. Under the standard uniform distribution, learning parities is known to be "hard" for almost all algorithms. By carefully constructing an "easier" distribution, they create an environment where:

  1. The gradient signal is strong enough for a neural network to "pick up" the relevant bits.
  2. The problem remains impossible for any linear method to solve without an exponential number of features or exponentially large weights.

The proof involves showing that the first gradient step is transformative: it moves the weights of the first layer toward a state where they represent "good" features that correlate with the parity function.

Datasets

The paper uses two primary evaluations:

  1. Synthetic Parity Data: Mathematically generated bit-strings where the label is the parity of a subset of $k$ bits.
  2. MNIST-Parity: A novel benchmark introduced to test the theory in a "vision-like" setting. In this task, the model is given a strip of $k$ random MNIST digits and must predict if the sum of those digits is even or odd.
  3. For $k=1$, this is just identifying if a single digit is even/odd (an easy task).
  4. For $k=3$, the model must recognize three distinct digits and compute their collective parity (a much harder task).

Key Insights and Ideas

  • Representation Learning vs. Fixed Features: The core insight is the proof of exponential separation. Linear methods (including NNs restricted to the NTK regime) are stuck with whatever features they start with. Standard NNs, however, use the first few steps of gradient descent to learn a representation that makes the parity problem easy.
  • The Power of the First Step: The authors show that even a single gradient step can move a neuron from a random state to one that approximately implements a piece of the parity logic.
  • Failure of Linearization: The results highlight that the "linearization" or "lazy training" view of neural networks misses the most important part of deep learning: the ability to adaptively find non-linear structures in data.

Key Results

  • Theoretical Separation: The authors prove that for a parity of $k$ bits, any linear method requires an embedding dimension $N$ or weight norm $B$ that grows as $2^{\Omega(k)}$. In contrast, a neural network solves it with $\text{poly}(k)$ neurons and iterations.
  • MNIST-Parity Performance:
    • When $k=1$, all models (NNs, NTK, Random Features) perform well, achieving ~90-95% accuracy.
  • When $k=3$, the ReLU network achieves ~80% accuracy, while all linear-equivalent models (including the NTK-regime network) fail completely, hovering around 50% (random guessing).
Accuracy on MNIST-Parity for k=1 and k=3, showing the failure of linear methods on the harder task.
  • Strict Superiority: This confirms that the success of NNs isn't just due to having "more parameters," but due to a qualitatively different optimization process that learns useful representations.

Limitations and Future Work

  • Distributional Assumptions: The proof relies on a specific data distribution. While this is a standard theoretical technique to show separation, learning parities under a truly uniform distribution remains a challenge for gradient descent.
  • Depth: The paper focuses on depth-two networks. The authors suggest that the next frontier is finding similar separations between "shallow" (depth-two) and "deep" (depth-three or more) networks.
  • Generalization: While parities are a great "stress test" for non-linearity, they are highly structured. Future work could explore if these insights apply to more natural, hierarchical data structures found in real-world images or text.

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