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

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

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [The Deep Ritz method: A deep learning-based numerical algorithm for solving variational problems](https://mlsanity.com/paper/1710.00211/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [Deep Network Approximation for Smooth Functions](https://mlsanity.com/paper/2001.03040/) (2020)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networks](https://mlsanity.com/paper/2101.12365/) (2021)
- [Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with  ℓ1  and  ℓ0  Controls](https://mlsanity.com/paper/1607.07819/) (2016)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [Neural Networks Learning and Memorization with (almost) no Over-Parameterization](https://mlsanity.com/paper/1911.09873/) (2019)
- [An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks](https://mlsanity.com/paper/2106.07724/) (2021)

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

- [On the Optimal Expressive Power of ReLU DNNs and Its Application in Approximation with Kolmogorov Superposition Theorem](https://mlsanity.com/paper/2308.05509/) (2023)
- [On the Optimal Memorization Capacity of Transformers](https://mlsanity.com/paper/2409.17677/) (2024)
- [Memorization capacity of deep ReLU neural networks characterized by width and depth](https://mlsanity.com/paper/2603.09589/) (2026)

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