mlsanityData to 7 Oct 2026

Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization

arXiv 2205.10217 ↗First posted 20 May 2022stat.ML cs.IT cs.LGcited by 36

Not on the map. Why?

Abstract (arXiv)

The Neural Tangent Kernel (NTK) has emerged as a powerful tool to provide memorization, optimization and generalization guarantees in deep neural networks. A line of work has studied the NTK spectrum for two-layer and deep networks with at least a layer with Omega(N) neurons, N being the number of training samples. Furthermore, there is increasing evidence suggesting that deep networks with sub-linear layer widths are powerful memorizers and optimizers, as long as the number of parameters exceeds the number of samples. Thus, a natural open question is whether the NTK is well conditioned in such a challenging sub-linear setup. In this paper, we answer this question in the affirmative. Our key technical contribution is a lower bound on the smallest NTK eigenvalue for deep networks with the minimum possible over-parameterization: the number of parameters is roughly Omega(N) and, hence, the number of neurons is as little as Omega(√N). To showcase the applicability of our NTK bounds, we provide two results concerning memorization capacity and optimization guarantees for gradient descent training.

Key facts. Cited by 36 papers in the map (data through 7 Oct 2026). Builds on 54 of its 75 references that are in the map. First posted on arXiv 20 May 2022.

Builds on

54 of 75 references.

References · 54

  1. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,267
  2. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  4. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  6. 2018On Lazy Training in Differentiable Programmingcited by 671
  7. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  8. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  9. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  10. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  11. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  12. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
38 more
  1. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  2. 2021Deep learning: a statistical viewpointcited by 239
  3. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  4. 2016Deep Pyramidal Residual Networkscited by 163
  5. 2019Linearized two-layers neural networks in high dimensioncited by 155
  6. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  7. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  8. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
  9. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  10. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  11. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  12. 2020The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalizationcited by 101
  13. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
  14. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  15. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  16. 2020The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Trainingcited by 84
  17. 2017A Random Matrix Approach to Neural Networkscited by 80
  18. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
  19. 2020Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networkscited by 76
  20. 2017The loss surface of deep and wide neural networkscited by 74
  21. 2018The Emergence of Spectral Universality in Deep Networkscited by 74
  22. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
  23. 2020A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descentcited by 69
  24. 2020Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topologycited by 66
  25. 2019Quadratic Suffices for Over-parametrization via Matrix Chernoff Boundcited by 58
  26. 2020The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networkscited by 58
  27. 2020Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixturescited by 47
  28. 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
  29. 2020Deep Networks and the Multiple Manifold Problemcited by 35
  30. 2018Small nonlinearities in activation functions create bad local minima in neural networkscited by 28
  31. 2018On the Spectrum of Random Features Maps of High Dimensional Datacited by 27
  32. 2019Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Networkcited by 27
  33. 2019Eigenvalue distribution of nonlinear models of random matricescited by 27
  34. 2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
  35. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  36. 2021Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networkscited by 21
  37. 2020A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Networkcited by 18
  38. 2020Network size and weights size for memorization with two-layers neural networkscited by 16

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 7; 2024: 11; 2025: 8; 2026: 5.

36 papers.

Sort:

  1. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 39
  2. 2024Reparameterization invariance in approximate Bayesian inferencecited by 17
  3. 2024Wide Neural Networks Trained with Weight Decay Provably Exhibit Neural Collapsecited by 14
  4. 2023Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernelscited by 13
  5. 2023On the Convergence of Encoder-only Shallow Transformerscited by 13
  6. 2024Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimensioncited by 13
  7. 2024The Positivity of the Neural Tangent Kernelcited by 12
  8. 2023How Spurious Features Are Memorized: Precise Analysis for Random and NTK Featurescited by 11
  9. 2023Benign Overfitting in Deep Neural Networks under Lazy Trainingcited by 10
  10. 2025Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterizationcited by 9
  11. 2023Theoretical Analysis of Robust Overfitting for Wide DNNs: An NTK Approachcited by 8
  12. 2022On skip connections and normalisation layers in deep optimisationcited by 7
24 more
  1. 2024Ditto: Quantization-aware Secure Inference of Transformers upon MPCcited by 7
  2. 2023On progressive sharpening, flat minima and generalisationcited by 6
  3. 2022Finite Sample Identification of Wide Shallow Neural Networks with Biasescited by 5
  4. 2024Towards Understanding the Word Sensitivity of Attention Layers: A Study via Random Featurescited by 5
  5. 2026Most ReLU Networks Admit Identifiable Parameterscited by 5
  6. 2025Explaining Grokking and Information Bottleneck through Neural Collapse Emergencecited by 4
  7. 2022Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergencecited by 3
  8. 2024Train Faster, Perform Better: Modular Adaptive Training in Over-Parameterized Modelscited by 3
  9. 2024Bayes without Underfitting: Fully Correlated Deep Learning Posteriors via Alternating Projectionscited by 3
  10. 2025Constraining the outputs of ReLU neural networkscited by 3
  11. 2025A Law of Data Reconstruction for Random Features (and Beyond)cited by 3
  12. 2025Convergence Rates for Gradient Descent on the Edge of Stability in Overparametrised Least Squarescited by 3
  13. 2022A Framework for Overparameterized Learningcited by 2
  14. 2022Improved Convergence Guarantees for Shallow Neural Networkscited by 1
  15. 2024Interpolation with deep neural networks with non-polynomial activations: necessary and sufficient numbers of neuronscited by 1
  16. 2025Quantitative convergence of trained single layer neural networks to Gaussian processescited by 1
  17. 2026Curvature-Guided LoRA: Matching Full Fine-Tuning in Function Spacecited by 1
  18. 2026Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minimacited by 1
  19. 2024Architectural Strategies for the optimization of Physics-Informed Neural Networkscited by 0
  20. 2024Hybrid Coordinate Descent for Efficient Neural Network Learning Using Line Search and Gradient Descentcited by 0
  21. 2025Memorization in Graph Neural Networkscited by 0
  22. 2025TPV: Parameter Perturbations Through the Lens of Test Prediction Variancecited by 0
  23. 2026On McDiarmid's Inequality under Dependence via Approximate Tensorization of Entropycited by 0
  24. 2026The Differential Neural Tangent Kernel and Its Positivitycited by 0