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

arXiv: https://arxiv.org/abs/2205.10217 · HTML: https://mlsanity.com/paper/2205.10217/

## Key facts

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

## Builds on (most cited first, 30 of 54)

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Deep Pyramidal Residual Networks](https://mlsanity.com/paper/1610.02915/) (2016)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization](https://mlsanity.com/paper/2008.06786/) (2020)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks](https://mlsanity.com/paper/2012.11654/) (2020)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training](https://mlsanity.com/paper/2007.12826/) (2020)
- [A Random Matrix Approach to Neural Networks](https://mlsanity.com/paper/1702.05419/) (2017)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)

## Built on by (most cited first, 30 of 36)

- [Memorization Capacity of Multi-Head Attention in Transformers](https://mlsanity.com/paper/2306.02010/) (2023)
- [Reparameterization invariance in approximate Bayesian inference](https://mlsanity.com/paper/2406.03334/) (2024)
- [Wide Neural Networks Trained with Weight Decay Provably Exhibit Neural Collapse](https://mlsanity.com/paper/2410.04887/) (2024)
- [Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernels](https://mlsanity.com/paper/2302.01629/) (2023)
- [On the Convergence of Encoder-only Shallow Transformers](https://mlsanity.com/paper/2311.01575/) (2023)
- [The Positivity of the Neural Tangent Kernel](https://mlsanity.com/paper/2404.12928/) (2024)
- [Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension](https://mlsanity.com/paper/2405.14630/) (2024)
- [How Spurious Features Are Memorized: Precise Analysis for Random and NTK Features](https://mlsanity.com/paper/2305.12100/) (2023)
- [Benign Overfitting in Deep Neural Networks under Lazy Training](https://mlsanity.com/paper/2305.19377/) (2023)
- [Theoretical Analysis of Robust Overfitting for Wide DNNs: An NTK Approach](https://mlsanity.com/paper/2310.06112/) (2023)
- [Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterization](https://mlsanity.com/paper/2502.01347/) (2025)
- [Ditto: Quantization-aware Secure Inference of Transformers upon MPC](https://mlsanity.com/paper/2405.05525/) (2024)
- [On skip connections and normalisation layers in deep optimisation](https://mlsanity.com/paper/2210.05371/) (2022)
- [On progressive sharpening, flat minima and generalisation](https://mlsanity.com/paper/2305.14683/) (2023)
- [Most ReLU Networks Admit Identifiable Parameters](https://mlsanity.com/paper/2605.03601/) (2026)
- [Finite Sample Identification of Wide Shallow Neural Networks with Biases](https://mlsanity.com/paper/2211.04589/) (2022)
- [Towards Understanding the Word Sensitivity of Attention Layers: A Study via Random Features](https://mlsanity.com/paper/2402.02969/) (2024)
- [Explaining Grokking and Information Bottleneck through Neural Collapse Emergence](https://mlsanity.com/paper/2509.20829/) (2025)
- [Convergence Rates for Gradient Descent on the Edge of Stability in Overparametrised Least Squares](https://mlsanity.com/paper/2510.17506/) (2025)
- [Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence](https://mlsanity.com/paper/2210.06819/) (2022)
- [Train Faster, Perform Better: Modular Adaptive Training in Over-Parameterized Models](https://mlsanity.com/paper/2405.07527/) (2024)
- [Bayes without Underfitting: Fully Correlated Deep Learning Posteriors via Alternating Projections](https://mlsanity.com/paper/2410.16901/) (2024)
- [Constraining the outputs of ReLU neural networks](https://mlsanity.com/paper/2508.03867/) (2025)
- [A Law of Data Reconstruction for Random Features (and Beyond)](https://mlsanity.com/paper/2509.22214/) (2025)
- [A Framework for Overparameterized Learning](https://mlsanity.com/paper/2205.13507/) (2022)
- [Interpolation with deep neural networks with non-polynomial activations: necessary and sufficient numbers of neurons](https://mlsanity.com/paper/2405.13738/) (2024)
- [Improved Convergence Guarantees for Shallow Neural Networks](https://mlsanity.com/paper/2212.02323/) (2022)
- [Memorization in Graph Neural Networks](https://mlsanity.com/paper/2508.19352/) (2025)
- [Quantitative convergence of trained single layer neural networks to Gaussian processes](https://mlsanity.com/paper/2509.24544/) (2025)
- [Curvature-Guided LoRA: Matching Full Fine-Tuning in Function Space](https://mlsanity.com/paper/2603.29824/) (2026)

## 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.