# On the Optimal Memorization Power of ReLU Neural Networks

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 39 references that are in the map.
- First posted on arXiv 7 Oct 2021.

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

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Why Deep Neural Networks for Function Approximation?](https://mlsanity.com/paper/1610.04161/) (2016)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [Neural Networks Learning and Memorization with (almost) no Over-Parameterization](https://mlsanity.com/paper/1911.09873/) (2019)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [Neural Networks with Small Weights and Depth-Separation Barriers](https://mlsanity.com/paper/2006.00625/) (2020)
- [Network size and weights size for memorization with two-layers neural networks](https://mlsanity.com/paper/2006.02855/) (2020)
- [Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem](https://mlsanity.com/paper/1912.04378/) (2019)
- [An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks](https://mlsanity.com/paper/2106.07724/) (2021)
- [Memory capacity of neural networks with threshold and ReLU activations](https://mlsanity.com/paper/2001.06938/) (2020)
- [Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth](https://mlsanity.com/paper/2006.04048/) (2020)
- [Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks](https://mlsanity.com/paper/2003.12895/) (2020)

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

- [One Fits All:Power General Time Series Analysis by Pretrained LM](https://mlsanity.com/paper/2302.11939/) (2023)
- [Understanding Factual Recall in Transformers via Associative Memories](https://mlsanity.com/paper/2412.06538/) (2024)
- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [Memorization Capacity of Multi-Head Attention in Transformers](https://mlsanity.com/paper/2306.02010/) (2023)
- [On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encoding](https://mlsanity.com/paper/2410.01405/) (2024)
- [On the training and generalization of deep operator networks](https://mlsanity.com/paper/2309.01020/) (2023)
- [Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power](https://mlsanity.com/paper/2205.13863/) (2022)
- [On the Complexity of Neural Computation in Superposition](https://mlsanity.com/paper/2409.15318/) (2024)
- [Minimum width for universal approximation using ReLU networks on compact domain](https://mlsanity.com/paper/2309.10402/) (2023)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Small Transformers Compute Universal Metric Embeddings](https://mlsanity.com/paper/2209.06788/) (2022)
- [Width is Less Important than Depth in ReLU Neural Networks](https://mlsanity.com/paper/2202.03841/) (2022)
- [On the Optimal Memorization Capacity of Transformers](https://mlsanity.com/paper/2409.17677/) (2024)
- [Expressive Power of ReLU and Step Networks under Floating-Point Operations](https://mlsanity.com/paper/2401.15121/) (2024)
- [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)
- [Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size](https://mlsanity.com/paper/2502.11467/) (2025)
- [Minimum width for universal approximation using squashable activation functions](https://mlsanity.com/paper/2504.07371/) (2025)
- [A Law of Data Reconstruction for Random Features (and Beyond)](https://mlsanity.com/paper/2509.22214/) (2025)
- [Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension](https://mlsanity.com/paper/2111.14486/) (2021)
- [Memorization With Neural Nets: Going Beyond the Worst Case](https://mlsanity.com/paper/2310.00327/) (2023)
- [Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networks](https://mlsanity.com/paper/2409.06555/) (2024)
- [Memorization in Attention-only Transformers](https://mlsanity.com/paper/2411.10115/) (2024)
- [Exact Sequence Interpolation with Transformers](https://mlsanity.com/paper/2502.02270/) (2025)
- [Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Data](https://mlsanity.com/paper/2509.00924/) (2025)
- [Minimum Width of Deep Narrow Networks for Universal Approximation](https://mlsanity.com/paper/2511.06837/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [From Alexnet to Transformers: Measuring the Non-linearity of Deep Neural Networks with Affine Optimal Transport](https://mlsanity.com/paper/2310.11439/) (2023)
- [Empirical Capacity Model for Self-Attention Neural Networks](https://mlsanity.com/paper/2407.15425/) (2024)

## Abstract (arXiv)

We study the memorization power of feedforward ReLU neural networks. We show that such networks can memorize any N points that satisfy a mild separability assumption using tildeOleft(√Nright) parameters. Known VC-dimension upper bounds imply that memorizing N samples requires Omega(√N) parameters, and hence our construction is optimal up to logarithmic factors. We also give a generalized construction for networks with depth bounded by 1 ≤ L ≤ √N, for memorizing N samples using tildeO(N/L) parameters. This bound is also optimal up to logarithmic factors. Our construction uses weights with large bit complexity. We prove that having such a large bit complexity is both necessary and sufficient for memorization with a sub-linear number of parameters.