mlsanityData to 7 Oct 2026

Memorization capacity of deep ReLU neural networks characterized by width and depth

arXiv 2603.09589 ↗First posted 10 Mar 2026cs.LG cs.NA math.NAcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper studies the memorization capacity of deep neural networks with ReLU activation. Specifically, we investigate the minimal size of such networks to memorize any N data points in the unit ball with pairwise separation distance δ and discrete labels. Most prior studies characterize the memorization capacity by the number of parameters or neurons. We generalize these results by constructing neural networks, whose width W and depth L satisfy W2L2= O(Nlog(δ-1)), that can memorize any N data samples. We also prove that any such networks should also satisfy the lower bound W2L2=Omega (N log(δ-1)), which implies that our construction is optimal up to logarithmic factors when δ-1 is polynomial in N. Hence, we explicitly characterize the trade-off between width and depth for the memorization capacity of deep neural networks in this regime.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 19 of its 32 references that are in the map. First posted on arXiv 10 Mar 2026.

Builds on

19 of 32 references.

References · 19

  1. 2016Error bounds for approximations with deep ReLU networkscited by 567
  2. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  3. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  4. 2016Benefits of depth in neural networkscited by 248
  5. 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 165
  6. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  7. 2019Deep Network Approximation Characterized by Number of Neuronscited by 120
  8. 2021Optimal Approximation Rate of ReLU Networks in terms of Width and Depthcited by 95
  9. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
  10. 2022Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spacescited by 50
  11. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  12. 2019Nonlinear Approximation via Compositionscited by 37
7 more
  1. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  2. 2020Network size and weights size for memorization with two-layers neural networkscited by 16
  3. 2019Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theoremcited by 15
  4. 2021An Exponential Improvement on the Memorization Capacity of Deep Threshold Networkscited by 14
  5. 2024On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networkscited by 13
  6. 2020Approximation in shift-invariant spaces with deep ReLU neural networkscited by 12
  7. 2023Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Datacited by 3

Built on by

Not cited yet.