mlsanityData to 7 Oct 2026

Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Data

arXiv 2302.00834 ↗First posted 2 Feb 2023cs.LG cs.NE stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

We study the interpolation power of deep ReLU neural networks. Specifically, we consider the question of how efficiently, in terms of the number of parameters, deep ReLU networks can interpolate values at N datapoints in the unit ball which are separated by a distance δ. We show that Omega(N) parameters are required in the regime where δ is exponentially small in N, which gives the sharp result in this regime since O(N) parameters are always sufficient. This also shows that the bit-extraction technique used to prove lower bounds on the VC dimension cannot be applied to irregularly spaced datapoints. Finally, as an application we give a lower bound on the approximation rates that deep ReLU neural networks can achieve for Sobolev spaces at the embedding endpoint.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 20 of its 47 references that are in the map. First posted on arXiv 2 Feb 2023.

Builds on

20 of 47 references.

References · 20

  1. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  2. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 667
  3. 2017The Deep Ritz method: A deep learning-based numerical algorithm for solving variational problemscited by 581
  4. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  5. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  6. 2016Benefits of depth in neural networkscited by 248
  7. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  8. 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 165
  9. 2020Deep Network Approximation for Smooth Functionscited by 163
  10. 2021Optimal Approximation Rate of ReLU Networks in terms of Width and Depthcited by 95
  11. 2021Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networkscited by 86
  12. 2016Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with ℓ1 and ℓ0 Controlscited by 84
8 more
  1. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 58
  2. 2022Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spacescited by 50
  3. 2017Depth Separation for Neural Networkscited by 46
  4. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  5. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  6. 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
  7. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  8. 2021An Exponential Improvement on the Memorization Capacity of Deep Threshold Networkscited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 0; 2026: 1.

3 papers.

  1. 2023On the Optimal Expressive Power of ReLU DNNs and Its Application in Approximation with Kolmogorov Superposition Theoremcited by 13
  2. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  3. 2026Memorization capacity of deep ReLU neural networks characterized by width and depthcited by 0