# Memorization capacity of deep ReLU neural networks characterized by width and depth

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 32 references that are in the map.
- First posted on arXiv 10 Mar 2026.

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [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)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Deep Network Approximation Characterized by Number of Neurons](https://mlsanity.com/paper/1906.05497/) (2019)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Nonlinear Approximation via Compositions](https://mlsanity.com/paper/1902.10170/) (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)
- [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)
- [On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networks](https://mlsanity.com/paper/2409.00901/) (2024)
- [Approximation in shift-invariant spaces with deep ReLU neural networks](https://mlsanity.com/paper/2005.11949/) (2020)
- [Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Data](https://mlsanity.com/paper/2302.00834/) (2023)

## Abstract (arXiv)

This paper studies the memorization capacity of deep neural networks with ReLU activation. Specifically, we investigate the minimal size of such networks to memorize any N data points in the unit ball with pairwise separation distance δ and discrete labels. Most prior studies characterize the memorization capacity by the number of parameters or neurons. We generalize these results by constructing neural networks, whose width W and depth L satisfy W2L2= O(Nlog(δ-1)), that can memorize any N data samples. We also prove that any such networks should also satisfy the lower bound W2L2=Omega (N log(δ-1)), which implies that our construction is optimal up to logarithmic factors when δ-1 is polynomial in N. Hence, we explicitly characterize the trade-off between width and depth for the memorization capacity of deep neural networks in this regime.