mlsanityData to 7 Oct 2026

Provable Memorization via Deep Neural Networks using Sub-linear Parameters

arXiv 2010.13363 ↗First posted 26 Oct 2020cs.LGcited by 34

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 5; 2023: 10; 2024: 6; 2025: 7; 2026: 2.

34 papers.

Sort:

By area:

  1. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  2. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 46
  3. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  4. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 39
  5. 2023On the training and generalization of deep operator networkscited by 31
  6. 2022Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformercited by 22
  7. 2024On the Complexity of Neural Computation in Superpositioncited by 21
  8. 2023Minimum width for universal approximation using ReLU networks on compact domaincited by 17
  9. 2021An Exponential Improvement on the Memorization Capacity of Deep Threshold Networkscited by 14
  10. 2022Small Transformers Compute Universal Metric Embeddingscited by 12
  11. 2022Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Coverscited by 11
  12. 2022Width is Less Important than Depth in ReLU Neural Networkscited by 10
22 more
  1. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  2. 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
  3. 2024Expressive Power of ReLU and Step Networks under Floating-Point Operationscited by 5
  4. 2023Label-noise-tolerant medical image classification via self-attention and self-supervised learningcited by 4
  5. 2023Capacity Bounds for Hyperbolic Neural Network Representations of Latent Tree Structurescited by 4
  6. 2025Approximation Bounds for Transformer Networks with Application to Regressioncited by 4
  7. 2023Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Datacited by 3
  8. 2023Memorization Capacity of Neural Networks with Conditional Computationcited by 3
  9. 2023Transformers Can Solve Non-Linear and Non-Markovian Filtering Problems in Continuous Time For Conditionally Gaussian Signalscited by 3
  10. 2025Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Sizecited by 3
  11. 2021Bayesian Statistics Guided Label Refurbishment Mechanism: Mitigating Label Noise in Medical Image Classificationcited by 2
  12. 2024Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networkscited by 2
  13. 2025Exact Sequence Interpolation with Transformerscited by 2
  14. 2025Minimum width for universal approximation using squashable activation functionscited by 2
  15. 2025Minimum Width of Deep Narrow Networks for Universal Approximationcited by 2
  16. 2023Memorization With Neural Nets: Going Beyond the Worst Casecited by 1
  17. 2024Interpolation with deep neural networks with non-polynomial activations: necessary and sufficient numbers of neuronscited by 1
  18. 2024Generalizability of Memorization Neural Networkscited by 1
  19. 2025Analyzing the Power of Chain of Thought through Memorization Capabilitiescited by 1
  20. 2025Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Abilitycited by 0
  21. 2026Memorization capacity of deep ReLU neural networks characterized by width and depthcited by 0
  22. 2026Approximation Error Upper and Lower Bounds for H"older Class with Transformerscited by 0