mlsanityData to 14 Oct 2026

On the Optimal Memorization Power of ReLU Neural Networks

arXiv 2110.03187 ↗First posted 7 Oct 2021cs.LG cs.NE stat.MLcited by 40

Not on the map. Why?

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.

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

24 of 39 references.

References · 24

  1. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  2. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 672
  3. 2016Error bounds for approximations with deep ReLU networkscited by 574
  4. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 311
  5. 2016Benefits of depth in neural networkscited by 250
  6. 2015The Power of Depth for Feedforward Neural Networkscited by 183
  7. 2021A Universal Law of Robustness via Isoperimetrycited by 151
  8. 2016Identity Matters in Deep Learningcited by 109
  9. 2016Why Deep Neural Networks for Function Approximation?cited by 82
  10. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 78
  11. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 59
  12. 2020A law of robustness for two-layers neural networkscited by 55
12 more
  1. 2017Depth Separation for Neural Networkscited by 46
  2. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  3. 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
  4. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  5. 2021Depth separation beyond radial functionscited by 18
  6. 2020Neural Networks with Small Weights and Depth-Separation Barrierscited by 17
  7. 2020Network size and weights size for memorization with two-layers neural networkscited by 17
  8. 2019Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theoremcited by 15
  9. 2021An Exponential Improvement on the Memorization Capacity of Deep Threshold Networkscited by 14
  10. 2020Memory capacity of neural networks with threshold and ReLU activationscited by 13
  11. 2020Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depthcited by 13
  12. 2020Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networkscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 10; 2024: 11; 2025: 7; 2026: 7.

40 papers.

Sort:

By area:

  1. 2023One Fits All:Power General Time Series Analysis by Pretrained LMcited by 632
  2. 2024Understanding Factual Recall in Transformers via Associative Memoriescited by 51
  3. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
  4. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 40
  5. 2024On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encodingcited by 36
  6. 2023On the training and generalization of deep operator networkscited by 31
  7. 2022Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Powercited by 23
  8. 2024On the Complexity of Neural Computation in Superpositioncited by 21
  9. 2023Minimum width for universal approximation using ReLU networks on compact domaincited by 18
  10. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  11. 2022Small Transformers Compute Universal Metric Embeddingscited by 12
  12. 2022Width is Less Important than Depth in ReLU Neural Networkscited by 10
28 more
  1. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  2. 2024Expressive Power of ReLU and Step Networks under Floating-Point Operationscited by 5
  3. 2024Provable Tempered Overfitting of Minimal Nets and Typical Netscited by 5
  4. 2023Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Datacited by 3
  5. 2023Memorization Capacity of Neural Networks with Conditional Computationcited by 3
  6. 2025Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Sizecited by 3
  7. 2025Minimum width for universal approximation using squashable activation functionscited by 3
  8. 2025A Law of Data Reconstruction for Random Features (and Beyond)cited by 3
  9. 2021Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimensioncited by 2
  10. 2023Memorization With Neural Nets: Going Beyond the Worst Casecited by 2
  11. 2024Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networkscited by 2
  12. 2024Memorization in Attention-only Transformerscited by 2
  13. 2025Exact Sequence Interpolation with Transformerscited by 2
  14. 2025Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Datacited by 2
  15. 2025Minimum Width of Deep Narrow Networks for Universal Approximationcited by 2
  16. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 2
  17. 2023From Alexnet to Transformers: Measuring the Non-linearity of Deep Neural Networks with Affine Optimal Transportcited by 1
  18. 2024Empirical Capacity Model for Self-Attention Neural Networkscited by 1
  19. 2024Generalizability of Memorization Neural Networkscited by 1
  20. 2025Analyzing the Power of Chain of Thought through Memorization Capabilitiescited by 1
  21. 2026Quantitative Approximation Rates for Group Equivariant Learningcited by 1
  22. 2026Geometric Factual Recall in Transformerscited by 1
  23. 2023On the Query Complexity of Training Data Reconstruction in Private Learningcited by 0
  24. 2024Memorization Capacity for Additive Fine-Tuning with Small ReLU Networkscited by 0
  25. 2026Memorization capacity of deep ReLU neural networks characterized by width and depthcited by 0
  26. 2026Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examplescited by 0
  27. 2026Approximation Error Upper and Lower Bounds for H"older Class with Transformerscited by 0
  28. 2026Finite Probes Suffice: Identifiability and Universality for Weight-Space Learningcited by 0