mlsanityData to 14 Oct 2026

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

arXiv 1911.09873 ↗First posted 22 Nov 2019cs.LG stat.MLcited by 23

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 7; 2023: 5; 2024: 3; 2025: 1; 2026: 3.

23 papers.

Sort:

  1. 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
  2. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  3. 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
  4. 2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
  5. 2022Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysiscited by 15
  6. 2022Small Transformers Compute Universal Metric Embeddingscited by 12
  7. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  8. 2022Size and depth of monotone neural networks: interpolation and approximationcited by 10
  9. 2021A Recipe for Global Convergence Guarantee in Deep Neural Networkscited by 8
  10. 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
  11. 2022Randomly Initialized One-Layer Neural Networks Make Data Linearly Separablecited by 6
  12. 2023Analysis of the expected L2 error of an over-parametrized deep neural network estimate learned by gradient descent without regularizationcited by 4
11 more
  1. 2023Generator Born from Classifiercited by 4
  2. 2022A Combinatorial Perspective on the Optimization of Shallow ReLU Networkscited by 3
  3. 2023Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Datacited by 3
  4. 2023Memorization With Neural Nets: Going Beyond the Worst Casecited by 2
  5. 2026Deep Networks Learn Deep Hierarchical Modelscited by 2
  6. 2024RedEx: Beyond Fixed Representation Methods via Convex Optimizationcited by 1
  7. 2024Generalizability of Memorization Neural Networkscited by 1
  8. 2024Learned Random Label Predictions as a Neural Network Complexity Metriccited by 1
  9. 2025Approximation with SiLU Networks: Constant Depth and Exponential Rates for Basic Operationscited by 0
  10. 2026Random Label Prediction Heads for Studying Memorization in Deep Neural Networkscited by 0
  11. 2026Dimension-Free Rank Lifting from Random Hyperplane Arrangementscited by 0