mlsanityData to 7 Oct 2026

Generalizability of Memorization Neural Networks

arXiv 2411.00372 ↗First posted 1 Nov 2024cs.LG cs.AIcited by 1

Not on the map. Why?

Abstract (arXiv)

The neural network memorization problem is to study the expressive power of neural networks to interpolate a finite dataset. Although memorization is widely believed to have a close relationship with the strong generalizability of deep learning when using over-parameterized models, to the best of our knowledge, there exists no theoretical study on the generalizability of memorization neural networks. In this paper, we give the first theoretical analysis of this topic. Since using i.i.d. training data is a necessary condition for a learning algorithm to be generalizable, memorization and its generalization theory for i.i.d. datasets are developed under mild conditions on the data distribution. First, algorithms are given to construct memorization networks for an i.i.d. dataset, which have the smallest number of parameters and even a constant number of parameters. Second, we show that, in order for the memorization networks to be generalizable, the width of the network must be at least equal to the dimension of the data, which implies that the existing memorization networks with an optimal number of parameters are not generalizable. Third, a lower bound for the sample complexity of general memorization algorithms and the exact sample complexity for memorization algorithms with constant number of parameters are given. It is also shown that there exist data distributions such that, to be generalizable for them, the memorization network must have an exponential number of parameters in the data dimension. Finally, an efficient and generalizable memorization algorithm is given when the number of training samples is greater than the efficient memorization sample complexity of the data distribution.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 40 of its 72 references that are in the map. First posted on arXiv 1 Nov 2024.

Builds on

40 of 72 references.

References · 40

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Deep Learning with Differential Privacycited by 2,682
  3. 2017A Closer Look at Memorization in Deep Networkscited by 936
  4. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  6. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 667
  7. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  8. 2017Exploring Generalization in Deep Learningcited by 595
  9. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  10. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  11. 2020What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimationcited by 492
  12. 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 452
28 more
  1. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  2. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  3. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  4. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  5. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  6. 2021Deep learning: a statistical viewpointcited by 239
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  8. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  9. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  10. 2016Identity Matters in Deep Learningcited by 107
  11. 2020Minimum Width for Universal Approximationcited by 92
  12. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  13. 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
  14. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  15. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
  16. 2014On the Computational Efficiency of Training Neural Networkscited by 71
  17. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  18. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  19. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  20. 2022Stability Analysis and Generalization Bounds of Adversarial Trainingcited by 30
  21. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  22. 2022Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Powercited by 23
  23. 2021Interpolating Classifiers Make Few Mistakescited by 22
  24. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  25. 2021Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regressioncited by 17
  26. 2024Generalization Bound and New Algorithm for Clean-Label Backdoor Attackcited by 11
  27. 2020Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networkscited by 7
  28. 2024Data-Dependent Stability Analysis of Adversarial Trainingcited by 4

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Curse of Dimensionality in Neural Network Optimizationcited by 1