# Ridgeless Interpolation with Shallow ReLU Networks in 1D is Nearest Neighbor Curvature Extrapolation and Provably Generalizes on Lipschitz Functions

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 30 references that are in the map.
- First posted on arXiv 27 Sep 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Dynamical Isometry and a Mean Field Theory of CNNs: How to Train 10,000-Layer Vanilla Convolutional Neural Networks](https://mlsanity.com/paper/1806.05393/) (2018)
- [All you need is a good init](https://mlsanity.com/paper/1511.06422/) (2015)
- [Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process](https://mlsanity.com/paper/1904.09080/) (2019)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors](https://mlsanity.com/paper/1712.09376/) (2017)
- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience](https://mlsanity.com/paper/1905.13344/) (2019)
- [Banach Space Representer Theorems for Neural Networks and Ridge Splines](https://mlsanity.com/paper/2006.05626/) (2020)

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

- [On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias](https://mlsanity.com/paper/2205.09072/) (2022)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [How do Minimum-Norm Shallow Denoisers Look in Function Space?](https://mlsanity.com/paper/2311.06748/) (2023)
- [Intrinsic dimensionality and generalization properties of the R-norm inductive bias](https://mlsanity.com/paper/2206.05317/) (2022)
- [Optimal bump functions for shallow ReLU networks: Weight decay, depth separation and the curse of dimensionality](https://mlsanity.com/paper/2209.01173/) (2022)
- [Minimum norm interpolation by perceptra: Explicit regularization and implicit bias](https://mlsanity.com/paper/2311.06138/) (2023)
- [On damage of interpolation to adversarial robustness in regression](https://mlsanity.com/paper/2601.16070/) (2026)
- [The Effects of Multi-Task Learning on ReLU Neural Network Functions](https://mlsanity.com/paper/2410.21696/) (2024)
- [Minimal-Norm Univariate Two-Layer ReLU Classification: Exact Solutions and Global Optimality with Skip Connections](https://mlsanity.com/paper/2609.28438/) (2026)

## Abstract (arXiv)

We prove a precise geometric description of all one layer ReLU networks z(x;θ) with a single linear unit and input/output dimensions equal to one that interpolate a given dataset mathcal D=(xi,f(xi)) and, among all such interpolants, minimize the ℓ2-norm of the neuron weights. Such networks can intuitively be thought of as those that minimize the mean-squared error over mathcal D plus an infinitesimal weight decay penalty. We therefore refer to them as ridgeless ReLU interpolants. Our description proves that, to extrapolate values z(x;θ) for inputs x∈ (xi,xi+1) lying between two consecutive datapoints, a ridgeless ReLU interpolant simply compares the signs of the discrete estimates for the curvature of f at xi and xi+1 derived from the dataset mathcal D. If the curvature estimates at xi and xi+1 have different signs, then z(x;θ) must be linear on (xi,xi+1). If in contrast the curvature estimates at xi and xi+1 are both positive (resp. negative), then z(x;θ) is convex (resp. concave) on (xi,xi+1). Our results show that ridgeless ReLU interpolants achieve the best possible generalization for learning 1d Lipschitz functions, up to universal constants.