# An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 14 Jun 2021.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Bad Global Minima Exist and SGD Can Reach Them](https://mlsanity.com/paper/1906.02613/) (2019)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Network size and weights size for memorization with two-layers neural networks](https://mlsanity.com/paper/2006.02855/) (2020)

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

- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [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)
- [Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power](https://mlsanity.com/paper/2205.13863/) (2022)
- [Size and depth of monotone neural networks: interpolation and approximation](https://mlsanity.com/paper/2207.05275/) (2022)
- [How Does a Deep Learning Model Architecture Impact Its Privacy? A Comprehensive Study of Privacy Attacks on CNNs and Transformers](https://mlsanity.com/paper/2210.11049/) (2022)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Data](https://mlsanity.com/paper/2302.00834/) (2023)
- [Memorization Capacity of Neural Networks with Conditional Computation](https://mlsanity.com/paper/2303.11247/) (2023)
- [Memorization With Neural Nets: Going Beyond the Worst Case](https://mlsanity.com/paper/2310.00327/) (2023)
- [Interpolation with deep neural networks with non-polynomial activations: necessary and sufficient numbers of neurons](https://mlsanity.com/paper/2405.13738/) (2024)
- [VC dimension of partially quantized neural networks in the overparametrized regime](https://mlsanity.com/paper/2110.02456/) (2021)
- [Memorization Capacity for Additive Fine-Tuning with Small ReLU Networks](https://mlsanity.com/paper/2408.00359/) (2024)
- [Memorization capacity of deep ReLU neural networks characterized by width and depth](https://mlsanity.com/paper/2603.09589/) (2026)

## Abstract (arXiv)

It is well known that modern deep neural networks are powerful enough to memorize datasets even when the labels have been randomized. Recently, Vershynin (2020) settled a long standing question by Baum (1988), proving that deep threshold networks can memorize n points in d dimensions using widetildeO(e1/δ2+√n) neurons and widetildeO(e1/δ2(d+√n)+n) weights, where δ is the minimum distance between the points. In this work, we improve the dependence on δ from exponential to almost linear, proving that widetildeO(frac1δ+√n) neurons and widetildeO(fracdδ+n) weights are sufficient. Our construction uses Gaussian random weights only in the first layer, while all the subsequent layers use binary or integer weights. We also prove new lower bounds by connecting memorization in neural networks to the purely geometric problem of separating n points on a sphere using hyperplanes.