# Memory capacity of neural networks with threshold and ReLU activations

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2020.

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

- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Memorization Capacity of Multi-Head Attention in Transformers](https://mlsanity.com/paper/2306.02010/) (2023)
- [Task Discovery: Finding the Tasks that Neural Networks Generalize on](https://mlsanity.com/paper/2212.00261/) (2022)
- [Globally Optimal Training of Neural Networks with Threshold Activation Functions](https://mlsanity.com/paper/2303.03382/) (2023)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [Fixed width treelike neural networks capacity analysis -- generic activations](https://mlsanity.com/paper/2402.05696/) (2024)
- [Capacity of the treelike sign perceptrons neural networks with one hidden layer -- RDT based upper bounds](https://mlsanity.com/paper/2312.08244/) (2023)
- [Lifted RDT based capacity analysis of the 1-hidden layer treelike sign perceptrons neural networks](https://mlsanity.com/paper/2312.08257/) (2023)
- [Memorization With Neural Nets: Going Beyond the Worst Case](https://mlsanity.com/paper/2310.00327/) (2023)
- [Effective Frontiers: A Unification of Neural Scaling Laws](https://mlsanity.com/paper/2602.02593/) (2026)
- [Memorization Capacity for Additive Fine-Tuning with Small ReLU Networks](https://mlsanity.com/paper/2408.00359/) (2024)
- [Information Theoretic Perspective on Representation Learning](https://mlsanity.com/paper/2601.11334/) (2026)

## Abstract (arXiv)

Overwhelming theoretical and empirical evidence shows that mildly overparametrized neural networks -- those with more connections than the size of the training data -- are often able to memorize the training data with 100% accuracy. This was rigorously proved for networks with sigmoid activation functions and, very recently, for ReLU activations. Addressing a 1988 open question of Baum, we prove that this phenomenon holds for general multilayered perceptrons, i.e. neural networks with threshold activation functions, or with any mix of threshold and ReLU activations. Our construction is probabilistic and exploits sparsity.