mlsanityData to 7 Oct 2026

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

arXiv 1810.07770 ↗First posted 17 Oct 2018cs.LG stat.MLcited by 76

Not on the map. Why?

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.

Key facts. Cited by 76 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 14; 2023: 16; 2024: 15; 2025: 8; 2026: 8.

76 papers.

Sort:

By area:

  1. 2021Equivariant Subgraph Aggregation Networkscited by 154
  2. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  3. 2021Dash: Semi-Supervised Learning with Dynamic Thresholdingcited by 147
  4. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  5. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  6. 2023Knowledge-Augmented Reasoning Distillation for Small Language Models in Knowledge-Intensive Taskscited by 62
  7. 2025How much do language models memorize?cited by 53
  8. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 46
  9. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  10. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 39
  11. 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
  12. 2022Improving Self-Supervised Learning by Characterizing Idealized Representationscited by 33
38 more
  1. 2022Selective Network Linearization for Efficient Private Inferencecited by 31
  2. 2023Graph Positional Encoding via Random Feature Propagationcited by 30
  3. 2023Universality and Limitations of Prompt Tuningcited by 30
  4. 2022Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Powercited by 23
  5. 2022Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformercited by 22
  6. 2024On the Complexity of Neural Computation in Superpositioncited by 21
  7. 2023Minimum width for universal approximation using ReLU networks on compact domaincited by 17
  8. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  9. 2023Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscapecited by 16
  10. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  11. 2021An Exponential Improvement on the Memorization Capacity of Deep Threshold Networkscited by 14
  12. 2021The Separation Capacity of Random Neural Networkscited by 14
  13. 2024Next-token prediction capacity: general upper bounds and a lower bound for transformerscited by 11
  14. 2021When Are Solutions Connected in Deep Networks?cited by 10
  15. 2026Contextual Rollout Bandits for Reinforcement Learning with Verifiable Rewardscited by 10
  16. 2022Task Discovery: Finding the Tasks that Neural Networks Generalize oncited by 9
  17. 2021Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samplescited by 8
  18. 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
  19. 2024Interplay between depth and width for interpolation in neural ODEscited by 8
  20. 2024Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Productscited by 8
  21. 2024A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarseningcited by 8
  22. 2024GRANOLA: Adaptive Normalization for Graph Neural Networkscited by 7
  23. 2022Randomly Initialized One-Layer Neural Networks Make Data Linearly Separablecited by 5
  24. 2022Finite Sample Identification of Wide Shallow Neural Networks with Biasescited by 5
  25. 2023Memory capacity of two layer neural networks with smooth activationscited by 5
  26. 2024Expressive Power of ReLU and Step Networks under Floating-Point Operationscited by 5
  27. 2025Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centralitycited by 5
  28. 2021A Convergence Theory Towards Practical Over-parameterized Deep Neural Networkscited by 4
  29. 2023Cluster-based classification with neural ODEs via controlcited by 4
  30. 2024Fixed width treelike neural networks capacity analysis -- generic activationscited by 4
  31. 2025Machine Unlearning under Overparameterizationcited by 4
  32. 2023Memorization Capacity of Neural Networks with Conditional Computationcited by 3
  33. 2023State space models can express n-gram languagescited by 3
  34. 2023Capacity of the treelike sign perceptrons neural networks with one hidden layer -- RDT based upper boundscited by 3
  35. 2023Lifted RDT based capacity analysis of the 1-hidden layer treelike sign perceptrons neural networkscited by 3
  36. 2025Comparison of generalised additive models and neural networks in applications: A systematic reviewcited by 3
  37. 2021A Law of Robustness for Weight-bounded Neural Networkscited by 2
  38. 2021Capacity of Group-invariant Linear Readouts from Equivariant Representations: How Many Objects can be Linearly Classified Under All Possible Views?cited by 2

50 most cited of 76 All 76 (JSON)