# Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity

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

## Key facts

- Cited by 78 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2018.

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

- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Dash: Semi-Supervised Learning with Dynamic Thresholding](https://mlsanity.com/paper/2109.00650/) (2021)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Knowledge-Augmented Reasoning Distillation for Small Language Models in Knowledge-Intensive Tasks](https://mlsanity.com/paper/2305.18395/) (2023)
- [How much do language models memorize?](https://mlsanity.com/paper/2505.24832/) (2025)
- [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)
- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [Improving Self-Supervised Learning by Characterizing Idealized Representations](https://mlsanity.com/paper/2209.06235/) (2022)
- [Selective Network Linearization for Efficient Private Inference](https://mlsanity.com/paper/2202.02340/) (2022)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Universality and Limitations of Prompt Tuning](https://mlsanity.com/paper/2305.18787/) (2023)
- [Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power](https://mlsanity.com/paper/2205.13863/) (2022)
- [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)
- [Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscape](https://mlsanity.com/paper/2305.19510/) (2023)
- [Efficient Subgraph GNNs by Learning Effective Selection Policies](https://mlsanity.com/paper/2310.20082/) (2023)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [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)
- [When Are Solutions Connected in Deep Networks?](https://mlsanity.com/paper/2102.09671/) (2021)
- [Next-token prediction capacity: general upper bounds and a lower bound for transformers](https://mlsanity.com/paper/2405.13718/) (2024)
- [Contextual Rollout Bandits for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2602.08499/) (2026)
- [Task Discovery: Finding the Tasks that Neural Networks Generalize on](https://mlsanity.com/paper/2212.00261/) (2022)
- [Interplay between depth and width for interpolation in neural ODEs](https://mlsanity.com/paper/2401.09902/) (2024)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)

## Abstract (arXiv)

We study finite sample expressivity, i.e., memorization power of ReLU networks. Recent results require N hidden nodes to memorize/interpolate arbitrary N data points. In contrast, by exploiting depth, we show that 3-layer ReLU networks with Omega(√N) hidden nodes can perfectly memorize most datasets with N points. We also prove that width Theta(√N) is necessary and sufficient for memorizing N data points, proving tight bounds on memorization capacity. The sufficiency result can be extended to deeper networks; we show that an L-layer network with W parameters in the hidden layers can memorize N data points if W = Omega(N). Combined with a recent upper bound O(WLlog W) on VC dimension, our construction is nearly tight for any fixed L. Subsequently, we analyze memorization capacity of residual networks under a general position assumption; we prove results that substantially reduce the known requirement of N hidden nodes. Finally, we study the dynamics of stochastic gradient descent (SGD), and show that when initialized near a memorizing global minimum of the empirical risk, SGD quickly finds a nearby point with much smaller empirical risk.