# Hardness of Learning Fixed Parities with Neural Networks

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 17 references that are in the map.
- First posted on arXiv 1 Jan 2025.

## Builds on (most cited first, 10 of 10)

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Poly-time universality and limitations of deep learning](https://mlsanity.com/paper/2001.02992/) (2020)
- [Statistical Queries and Statistical Algorithms: Foundations and Applications](https://mlsanity.com/paper/2004.00557/) (2020)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [On Symmetry and Initialization for Neural Networks](https://mlsanity.com/paper/1907.00560/) (2019)

## Built on by (most cited first, 7 of 7)

- [On the creation of narrow AI: hierarchy and nonlocality of neural network skills](https://mlsanity.com/paper/2505.15811/) (2025)
- [Learning Fricke signs from Maass form Coefficients](https://mlsanity.com/paper/2501.02105/) (2025)
- [Differentiable Logic Synthesis: Spectral Coefficient Selection via Sinkhorn-Constrained Composition](https://mlsanity.com/paper/2601.13953/) (2026)
- [When Is Compositional Reasoning Learnable from Verifiable Rewards?](https://mlsanity.com/paper/2602.07992/) (2026)
- [The two clocks and the innovation window: When and how generative models learn rules](https://mlsanity.com/paper/2605.10019/) (2026)
- [Learning through Internalization](https://mlsanity.com/paper/2606.20937/) (2026)
- [Teacher Geometry Shapes Learnability in Teacher-Student Networks](https://mlsanity.com/paper/2609.09595/) (2026)

## Abstract (arXiv)

Learning parity functions is a canonical problem in learning theory, which although computationally tractable, is not amenable to standard learning algorithms such as gradient-based methods. This hardness is usually explained via statistical query lower bounds [Kearns, 1998]. However, these bounds only imply that for any given algorithm, there is some worst-case parity function that will be hard to learn. Thus, they do not explain why fixed parities - say, the full parity function over all coordinates - are difficult to learn in practice, at least with standard predictors and gradient-based methods [Abbe and Boix-Adsera, 2022]. In this paper, we address this open problem, by showing that for any fixed parity of some minimal size, using it as a target function to train one-hidden-layer ReLU networks with perturbed gradient descent will fail to produce anything meaningful. To establish this, we prove a new result about the decay of the Fourier coefficients of linear threshold (or weighted majority) functions, which may be of independent interest.