# Neural Networks Learning and Memorization with (almost) no Over-Parameterization

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2019.

## Built on by (most cited first, 23 of 23)

- [On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths](https://mlsanity.com/paper/2101.09612/) (2021)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis](https://mlsanity.com/paper/2206.12802/) (2022)
- [Small Transformers Compute Universal Metric Embeddings](https://mlsanity.com/paper/2209.06788/) (2022)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Size and depth of monotone neural networks: interpolation and approximation](https://mlsanity.com/paper/2207.05275/) (2022)
- [A Recipe for Global Convergence Guarantee in Deep Neural Networks](https://mlsanity.com/paper/2104.05785/) (2021)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [Randomly Initialized One-Layer Neural Networks Make Data Linearly Separable](https://mlsanity.com/paper/2205.11716/) (2022)
- [Analysis of the expected L2 error of an over-parametrized deep neural network estimate learned by gradient descent without regularization](https://mlsanity.com/paper/2311.14609/) (2023)
- [Generator Born from Classifier](https://mlsanity.com/paper/2312.02470/) (2023)
- [A Combinatorial Perspective on the Optimization of Shallow ReLU Networks](https://mlsanity.com/paper/2210.00176/) (2022)
- [Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Data](https://mlsanity.com/paper/2302.00834/) (2023)
- [Memorization With Neural Nets: Going Beyond the Worst Case](https://mlsanity.com/paper/2310.00327/) (2023)
- [Deep Networks Learn Deep Hierarchical Models](https://mlsanity.com/paper/2601.00455/) (2026)
- [RedEx: Beyond Fixed Representation Methods via Convex Optimization](https://mlsanity.com/paper/2401.07606/) (2024)
- [Generalizability of Memorization Neural Networks](https://mlsanity.com/paper/2411.00372/) (2024)
- [Learned Random Label Predictions as a Neural Network Complexity Metric](https://mlsanity.com/paper/2411.19640/) (2024)
- [Approximation with SiLU Networks: Constant Depth and Exponential Rates for Basic Operations](https://mlsanity.com/paper/2512.12132/) (2025)
- [Random Label Prediction Heads for Studying Memorization in Deep Neural Networks](https://mlsanity.com/paper/2607.11541/) (2026)
- [Dimension-Free Rank Lifting from Random Hyperplane Arrangements](https://mlsanity.com/paper/2609.39855/) (2026)

## Abstract (arXiv)

Many results in recent years established polynomial time learnability of various models via neural networks algorithms. However, unless the model is linear separable, or the activation is a polynomial, these results require very large networks -- much more than what is needed for the mere existence of a good predictor. In this paper we prove that SGD on depth two neural networks can memorize samples, learn polynomials with bounded weights, and learn certain kernel spaces, with near optimal network size, sample complexity, and runtime. In particular, we show that SGD on depth two network with tildeOleft(fracmdright) hidden neurons (and hence tildeO(m) parameters) can memorize m random labeled points in mathbbSd-1.