# Provable Memorization via Deep Neural Networks using Sub-linear Parameters

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

## Key facts

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

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

- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [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)
- [On the training and generalization of deep operator networks](https://mlsanity.com/paper/2309.01020/) (2023)
- [Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformer](https://mlsanity.com/paper/2201.13094/) (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)
- [An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks](https://mlsanity.com/paper/2106.07724/) (2021)
- [Small Transformers Compute Universal Metric Embeddings](https://mlsanity.com/paper/2209.06788/) (2022)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (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)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [Expressive Power of ReLU and Step Networks under Floating-Point Operations](https://mlsanity.com/paper/2401.15121/) (2024)
- [Label-noise-tolerant medical image classification via self-attention and self-supervised learning](https://mlsanity.com/paper/2306.09718/) (2023)
- [Capacity Bounds for Hyperbolic Neural Network Representations of Latent Tree Structures](https://mlsanity.com/paper/2308.09250/) (2023)
- [Transformers Can Solve Non-Linear and Non-Markovian Filtering Problems in Continuous Time For Conditionally Gaussian Signals](https://mlsanity.com/paper/2310.19603/) (2023)
- [Approximation Bounds for Transformer Networks with Application to Regression](https://mlsanity.com/paper/2504.12175/) (2025)
- [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)
- [Bayesian Statistics Guided Label Refurbishment Mechanism: Mitigating Label Noise in Medical Image Classification](https://mlsanity.com/paper/2106.12284/) (2021)
- [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)
- [Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networks](https://mlsanity.com/paper/2409.06555/) (2024)
- [Exact Sequence Interpolation with Transformers](https://mlsanity.com/paper/2502.02270/) (2025)
- [Minimum Width of Deep Narrow Networks for Universal Approximation](https://mlsanity.com/paper/2511.06837/) (2025)
- [Generalizability of Memorization Neural Networks](https://mlsanity.com/paper/2411.00372/) (2024)

## Abstract (arXiv)

It is known that O(N) parameters are sufficient for neural networks to memorize arbitrary N input-label pairs. By exploiting depth, we show that O(N2/3) parameters suffice to memorize N pairs, under a mild condition on the separation of input points. In particular, deeper networks (even with width 3) are shown to memorize more pairs than shallow networks, which also agrees with the recent line of works on the benefits of depth for function approximation. We also provide empirical results that support our theoretical findings.