# Learning Parities with Neural Networks

arXiv: https://arxiv.org/abs/2002.07400 · HTML: https://mlsanity.com/paper/2002.07400/

## Key facts

- Cited by 78 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2020.

## Built on by (most cited first, 30 of 78)

- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Video Super-Resolution Transformer](https://mlsanity.com/paper/2106.06847/) (2021)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Why Larger Language Models Do In-context Learning Differently?](https://mlsanity.com/paper/2405.19592/) (2024)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [Limitations of the NTK for Understanding Generalization in Deep Learning](https://mlsanity.com/paper/2206.10012/) (2022)
- [Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networks](https://mlsanity.com/paper/2306.04073/) (2023)
- [How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?](https://mlsanity.com/paper/2402.15607/) (2024)
- [Feature emergence via margin maximization: case studies in algebraic tasks](https://mlsanity.com/paper/2311.07568/) (2023)
- [Spectral Evolution and Invariance in Linear-width Neural Networks](https://mlsanity.com/paper/2211.06506/) (2022)
- [From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency](https://mlsanity.com/paper/2410.05459/) (2024)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Properties of the After Kernel](https://mlsanity.com/paper/2105.10585/) (2021)
- [The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2110.03922/) (2021)
- [Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs](https://mlsanity.com/paper/2306.16921/) (2023)
- [Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks](https://mlsanity.com/paper/2104.03093/) (2021)
- [A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Experts](https://mlsanity.com/paper/2405.16646/) (2024)
- [Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classification](https://mlsanity.com/paper/2301.01597/) (2022)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [Towards Understanding Learning in Neural Networks with Linear Teachers](https://mlsanity.com/paper/2101.02533/) (2021)

## Abstract (arXiv)

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.