# Memorization With Neural Nets: Going Beyond the Worst Case

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 39 references that are in the map.
- First posted on arXiv 30 Sep 2023.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [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)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Neural Networks Learning and Memorization with (almost) no Over-Parameterization](https://mlsanity.com/paper/1911.09873/) (2019)
- [Network size and weights size for memorization with two-layers neural networks](https://mlsanity.com/paper/2006.02855/) (2020)
- [An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks](https://mlsanity.com/paper/2106.07724/) (2021)
- [The Separation Capacity of Random Neural Networks](https://mlsanity.com/paper/2108.00207/) (2021)
- [Memory capacity of neural networks with threshold and ReLU activations](https://mlsanity.com/paper/2001.06938/) (2020)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently](https://mlsanity.com/paper/1909.11837/) (2019)
- [Randomly Initialized One-Layer Neural Networks Make Data Linearly Separable](https://mlsanity.com/paper/2205.11716/) (2022)
- [Memory capacity of two layer neural networks with smooth activations](https://mlsanity.com/paper/2308.02001/) (2023)

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

- [Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Data](https://mlsanity.com/paper/2509.00924/) (2025)
- [Memorization in image classification: test set behavior and scaling laws](https://mlsanity.com/paper/2610.16090/) (2026)

## Abstract (arXiv)

In practice, deep neural networks are often able to easily interpolate their training data. To understand this phenomenon, many works have aimed to quantify the memorization capacity of a neural network architecture: the largest number of points such that the architecture can interpolate any placement of these points with any assignment of labels. For real-world data, however, one intuitively expects the presence of a benign structure so that interpolation already occurs at a smaller network size than suggested by memorization capacity. In this paper, we investigate interpolation by adopting an instance-specific viewpoint. We introduce a simple randomized algorithm that, given a fixed finite data set with two classes, with high probability constructs an interpolating three-layer neural network in polynomial time. The required number of parameters is linked to geometric properties of the two classes and their mutual arrangement. As a result, we obtain guarantees that are independent of the number of samples and hence move beyond worst-case memorization capacity bounds. We verify our theoretical result with numerical experiments and additionally investigate the effectiveness of the algorithm on MNIST and CIFAR-10.