tcb@breakable

# Noisy Interpolation Learning with
Shallow Univariate ReLU Networks

David S. Hippocampus
Department of Computer Science
Cranberry-Lemon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>
Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies.

###### Abstract

We study the asymptotic overfitting behavior of interpolation with minimum
norm ($\ell_{2}$ of the weights) two-layer ReLU networks for noisy univariate
regression. We show that overfitting is tempered for the $L_{1}$ loss, and any
$L_{p}$ loss for $p<2$, but catastrophic for $p\geq 2$.

##  1 Introduction

A recent realization is that although sometimes overfitting can be
catastrophic, as suggested by our classic learning theory understanding, in
other models overfitting, and even interpolation learning, i.e. insisting on
zero training error of noisy data, might not be so catastrophic, allowing for
good generalization (low test error) and even consistency
[zhang2017rethinkinggeneralization, belkin2018overfittingperfectfitting]. This
has led to efforts towards understanding the nature of overfitting: how benign
or catastrophic it is, and what determines this behavior, in different
settings and using different models.

Although interest in benign overfitting stems from the empirical success of
interpolating large neural networks, theoretical study so far has been mostly
limited to linear and kernel methods, or at least to settings where the data
is linearly interpolatable, with very high (tending to infinity) data
dimension111Minimum $\ell_{2}$ norm linear prediction (aka ridgeless
regression) with noisy labels and (sub-)Gaussian features has been studied
extensively [e.g. hastie2020surprises, belkin2020two, bartlett2020benignpnas,
muthukumar2020harmless, negrea2020defense, chinot2020robustness,
koehler2021uniform, wu2020optimal, tsigler2020benign, zhou2022non,
wang2022tight, chatterji2021interplay, bartlett2021failures,
shamir2022implicit, ghosh2022universal, chatterji2020linearnoise,
wang2021binary, cao2021benign, muthukumar2021classification,
montanari2020maxmarginasymptotics, liang2021interpolating,
thrampoulidis2020theoretical, wang2021benignmulticlass,
donhauser2022fastrates, frei2023benign], and noisy minimum $\ell_{1}$ linear
prediction (aka Basis Persuit) has also been considered [e.g.
ju2020overfitting, koehler2021uniform, wang2022tight]. Either way, these
analyses are all in the high dimensional setting, with dimension going to
infinity, since to allow for interpolation the dimension must be high, higher
than the number of samples. Kernel method amount to a minimum $\ell_{2}$ norm
linear prediction, with very non-Gaussian features. But existing analyses of
interpolation learning with kernel methods rely on “Gaussian Universality”:
either assuming as an ansatz the behavior is as for Gaussian features
[mallinar2022benign] or establishing this rigorously in certain high
dimensional scalings [hastie2019surprises, misiakiewicz2022spectrum,
mei2022generalization]. In particular, such analyses are only valid when the
input dimension goes to infinity (though possibly slower than the number of
samples) and not for fixed low or moderate dimension. frei2022benign,
frei2023benign, cao2022benign, kou2023benign study interpolation learning with
neural networks, but only with high input dimension and when the data is
interpolatable also with a linear predictor—in these cases, although non-
linear neural networks are used, the results show they behave similarly to
linear predictors. manoj2023interpolation take the other extreme and study
interpolation learning with “short programs”, which are certainly non-linear,
but this is an abstract model that does not directly capture learning with
neural networks.. But what about noisy interpolation learning in low (or
moderate) dimensions, using neural networks?

mallinar2022benign conducted simulations with neural networks and observed
“tempered” overfitting: the asymptotic risk does not approach the Bayes-
optimal risk (there is no consistency), but neither does it diverge to
infinity catastrophically. Such “tempered” behavior is well understood for
$1$-nearest neighbor, where the asymptotic risk is roughly twice the Bayes
risk [cover1967nearest], and mallinar2022benign heuristically explain it also
for some kernel methods. However, we do not have a satisfying nor rigorous
understanding of such behavior in neural networks, nor a more quantitative or
precise understanding of just how bad the risk might be when interpolating
noisy data using a neural net.

In this paper, we begin rigorously studying the effect of overfitting with
neural networks in low dimensions, where the data is not linearly
interpolatable, but a large enough network can of course always interpolate.
Specifically, we study interpolation learning of univariate data (i.e. in one
dimension) using a two-layer ReLU network (with a skip connection), which is a
predictor $f_{\theta,a_{0},b_{0}}:\reals\rightarrow\reals$ given by:

$f_{\theta,a_{0},b_{0}}(x)=\sum_{j=1}^{m}a_{j}(w_{j}x+b_{j})_{+}+a_{0}x+b_{0}~{},$
(1)

where $\theta\in\reals^{3m}$ denotes the weights (parameters)
$\\{a_{j},w_{j},b_{j}\\}_{j=1}^{m}$. To allow for interpolation we do not
limit the width $m$, and learn by minimizing the norm of the weights
[savarese2019infinite, ergen2021convex, hanin2021ridgeless,
debarre2022sparsest, boursier2023penalising]:

$\hat{f}_{S}=\arg\min_{f_{\theta,a_{0},b_{0}}}\norm{\theta}^{2}\;\text{ s.t.
}\;\forall i\in[n],\;f_{\theta,a_{0},b_{0}}(x_{i})=y_{i}~{}\;\textrm{where
$S=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$}.$ (2)

Following boursier2023penalising we allow an unregularized skip-connection in
Eq. (1), where the weights $a_{0},b_{0}$ of this skip connection are not
included in the norm $\norm{\theta}$ in Eq. (6). This skip connection avoids
some complications and allows better characterizing $\hat{f}_{S}$ but should
not meaningfully change the behavior (see Section 2).

#### Why min norm?

Using unbounded size minimum weight-norm networks is natural for interpolation
learning. It parallels the study of minimum norm high (even infinite)
dimension linear predictors. For interpolation, we must allow the number of
parameters to increase as the sample size increases. But to have any hope of
generalization, we must choose among the infinitely many zero training error
networks somehow, and it seems that some sort of explicit or implicit low norm
bias is the driving force in learning with large overparametrized neural
networks [neyshabur2014search]. Seeking minimum $\ell_{2}$ norm weights is
natural, e.g. as a result of small weight decay. Even without explicit weight
decay, optimizing using gradient descent is also related to an implicit bias
toward low $\ell_{2}$ norm: this can be made precise for linear models and for
classification with ReLU networks [chizat2020implicit, safran2022effective].
For regression with ReLU networks, as we study here, gradient descent does not
exactly minimize the $\ell_{2}$ norm, but the implicit bias is probably still
related, and studying Eq. (6) is a good starting point also for understanding
the behavior of networks learned via gradient descent.

#### Noisy interpolation learning.

We consider a noisy distribution $\dist$ over $[0,1]\times\reals$:

$x\sim\unif([0,1])\;\;\;\;\text{ and }\;\;\;\;y=f^{*}(x)+\eps\;\text{ with
}\eps\textrm{ independent of }\,x,$ (3)

where $x$ is uniform for simplicity and concreteness, the noise $\eps$ follows
some arbitrary (non-zero) distribution, and learning is based on an i.i.d.
training set $S\sim\dist^{n}$. Since the noise is non-zero, the “ground truth”
predictor $f^{*}$ has non-zero training error, seeking a training error much
smaller than that of $f^{*}$ would be overfitting (fitting the noise) and
necessarily cause the complexity (e.g. norm) of the learned predictor to
explode. The “right” thing to do is to balance between the training error and
the complexity $\norm{\theta}$. Indeed, under mild assumptions, this balanced
approach leads to asymptotic consistency, with
$\hat{f}_{S}\xrightarrow{n\rightarrow\infty}f^{*}$ and the asymptotic
population risk of $\hat{f}_{S}$ converging to the Bayes risk. But what
happens when we overfit and use the interpolating learning rule Eq. (6)?

Figure 1: Comparison between linear-spline (purple) and min-norm (green)
interpolators.

#### Linear Splines.

At first glance, we might be tempted to think that two-layer ReLUs behave like
linear splines (see Figure 1). Indeed, if minimizing the norm of weights
$w_{i}$ and $a_{i}$ but not the biases $b_{i}$ in Eq. (6), linear splines are
always a valid minimizer [savarese2019infinite, ergen2021convex]. As the
number of noisy training points increases, linear splines “zig-zag” with
tighter “zigs” but non-vanishing “amplitude” around $f^{*}$, resulting in an
interpolator which roughly behaves like $f^{*}$ plus some added non-vanishing
“noise”. This does not lead to consistency, but is similar to a nearest-
neighbor predictor (each prediction is a weighted average of two neighbors).
Indeed, in Theorem 1 of Section 4, we show that linear splines exhibit
“tempered” behavior, with asymptotic risk proportional to the noise.

#### From Splines to Min-Norm ReLU Nets.

But it turns out minimum norm ReLU networks, although piecewise linear, are
not quite linear splines: roughly speaking, and as shown in Figure 1, they are
more conservative in the number of “pieces”. Because of this, in convex
(conversely, concave) regions of the linear spline, minimum norm ReLU nets
“overshoot” the linear spline in order to avoid breaking linear pieces. This
could create additional “spikes”, extending above and below the data points
(see Figures 1 and 2) and thus potentially increasing the error. How bad is
the effect of such spikes on the population risk?

#### Effect of Overfitting on $L_{p}$ Risk.

It turns out the answer is subtle and depends on how we measure the error.
Measuring population risk as $L_{p}(f):=\Exp_{(x,y)\sim\dist}[|f(x)-y|^{p}]$,
we show in Theorems 2 and 3 of Section 5.2 that for $1\leq p<2$,

$L_{p}(\hat{f}_{S})\xrightarrow{n\rightarrow\infty}\Theta\left(\frac{1}{(2-p)_{+}}\right)\,L_{p}(f^{*}).$
(4)

This is an upper bound for any Lipschitz target $f^{*}$ and any noise
distribution, and it is matched by a lower bound for Gaussian noise. That is,
for abs-loss ($L_{1}$ risk), as well as any $L_{p}$ risk for $1\leq p<2$,
overfitting is tempered. But this tempered behavior explodes as $p\rightarrow
2$, and we show in Theorem 4 of Section 5.3 that for any $p\geq 2$, including
for the square loss ($p=2$), as soon as there is some non-zero noise,
$L_{p}(\hat{f}_{S})\xrightarrow{n\rightarrow\infty}\infty$ and overfitting is
catastrophic.

#### Convergence vs Expectation.

The behavior is even more subtle, in that even for $1\leq p<2$, although the
risk $L_{p}(\hat{f}_{S})$ converges in probability to a tempered behavior as
in Eq. (4), its expectation is infinite:
$\Exp_{S}[L_{p}(\hat{f}_{S})]=\infty$. Note that in studying tempered
overfitting, mallinar2022benign focused on this expectation, and so would have
categorized the behavior as “catastrophic” even for $p=1$, emphasizing the
need for more careful consideration of the effect of overfitting. We would of
course not get such strange behavior with the traditional non-overfitting
approach of balancing training error and norm, which yields risk converging
almost surely, with finite expectation converging to the optimal risk and
vanishing variances.

#### I.I.D. Samples vs. Samples on a Grid.

The catastrophic effect of interpolation on the $L_{p}$ risk with $p\geq 2$ is
a result of the effect of fluctuations in the spacing of the training points.
Large, catastrophic, spikes are formed by training points extremely close to
their neighbors but with different labels (see Figures 2 and 5). To help
understand this, in Section 6 we study a “fixed design” variant of the
problem, where the training inputs lie on a uniform grid, $x_{i}=i/n$, and
responses follow the random model $y_{i}=f^{*}(x_{i})+\epsilon_{i}$. In this
case, interpolation is always tempered, with
$L_{p}(\hat{f}_{S})\xrightarrow{n\rightarrow\infty}\Theta(L_{p}(f^{*}))$ for
all constant $p\geq 1$ (Theorem 5 of Section 6).

#### Summary and Contribution.

Our work is the first step toward studying noisy interpolation learning on
non-linearly-interpolatable data in actual neural networks, where the capacity
of the model comes from the size of the network and not the dimension of the
data. We study the univariate case. Univariate regression with min-norm ReLU
networks is a rich model in its own right [e.g. savarese2019infinite,
ergen2021convex, hanin2021ridgeless, debarre2022sparsest,
boursier2023penalising, williams2019gradient, mulayoff2021implicit,
safran2022effective] and a starting point for further investigation. We see
that even for univariate data, the overfitting behavior is subtle and requires
careful and detailed analysis, and especially for the universally studied
squared loss, does not fit the “tempered overfitting” predictions of e.g.
mallinar2022benign.

Figure 2: The min-norm interpolator for $30$ random points with $f^{*}\equiv
0$ and $\normal(0,1)$ label noise.

##  2 Review: Min-Norm ReLU Networks

Minimum-norm unbounded-width univariate two-layer ReLU networks have been
extensively studied in recent years, starting with savarese2019infinite, with
the exact formulation Eq. (6) incorporating a skip connection due to
boursier2023penalising. boursier2023penalising, following prior work,
establish that a minimum of Eq. (6) exists, with a finite number of units, and
that it is also unique.

The problem Eq. (6) is also equivalent to minimizing the “representational
cost”

$R(f)=\int_{\IR}\sqrt{1+x^{2}}|f^{\prime\prime}(x)|dx$

over all interpolators $f$, although we will not use this characterization in
our analysis. Compared to savarese2019infinite, the weighting $\sqrt{1+x^{2}}$
is due to penalizing the biases $b_{i}$. More significantly, the skip
connection in Eq. (1) avoids the “fallback” terms of
$|f^{\prime}(-\infty)+f^{\prime}(+\infty)|$, which only kicks-in in extreme
cases (very few points or an extreme slope). This simplified analysis and
presentation while rarely effecting the solution.

boursier2023penalising provide the following characterization of the
minimizer222 If the biases $b_{i}$ are not included in the norm
$\norm{\theta}$ in Eq. (6), and this norm is replaced with
$\sum_{i}(a_{i}^{2}+w_{i}^{2})$, the modified problem admits multiple non-
unique minimizers, including a linear spline (with modified behavior past the
extreme points) [savarese2019infinite]. This set of minimizers was
charactarized by hanin2021ridgeless. Interestingly, the minimizer
$\hat{f}_{S}$ of Eq. (6) (when the biases are included in the norm) is also a
minimizer of the modified problem (without including the biases). All our
results apply also to the setting without penalizing the biases in the
following sense: the upper bounds are valid for all minimizers, while some
minimizer, namely $\hat{f}_{S}$ that we study, exhibits the lower bound
behavior. $\hat{f}_{S}$ of Eq. (6), which we will rely on heavily:

######  Lemma 1 (boursier2023penalising).

For $0\leq x_{1}<x_{2}<\cdots<x_{n}$, the problem in Eq. (6) admits a unique
minimizer of the form:

$\hat{f}_{S}(x)=ax+b+\sum_{i=1}^{n-1}a_{i}(x-\tau_{i})_{+}~{},$ (5)

where $\tau_{i}\in[x_{i},x_{i+1})$ for every $i\in[n-1]$.

As in the above charactarization, it is very convenient to take the training
points to be sorted. Since the learned network $\hat{f}_{S}$ does not depend
on the order of the points, we can always “sort” the points without changing
anything. And so, throughout the paper, we will always take the points to be
sorted (formally, the results apply to i.i.d. points, and the analysis is done
after sorting these points).

##  3 Introduction

In recent years, there has been a growing interest in studying overfitting and
interpolation learning with noisy training data. Following initial experiments
by zhang2017rethinkinggeneralization, researchers observed that
overparameterized neural networks often achieve perfect fit to noisy training
data and still generalize well to unseen data. This phenomenon does not align
with the traditional belief from statistical learning theory that overfitting
to noise leads to poor out-of-sample prediction performance, and understanding
it has become a central question in the theory of deep learning.

This question motivated the study of _benign overfitting_ , where the learned
predictor perfectly fits (i.e., interpolates) noisy training data, but still
approaches _Bayes-optimal_ generalization when the training set is
sufficiently large. Despite a great deal of theoretical research, the settings
where benign overfitting is known to occur are limited (see the related work
section for details). Indeed, the existing results focus mostly on linear
predictors and kernel regression. Moreover, several works show benign
overfitting in nonlinear neural networks, but only in classification settings
where the data distribution is linearly separable and the input dimension is
larger than the number of training samples.

mallinar2022benign conducted experiments with neural networks on simple tasks
and observed that they do not exhibit either benign or catastrophic
overfitting. That is, in the limit where the training set size is large, the
learned predictor does not approach the Bayes-optimal risk, but also does not
diverge catastrophically. They termed this intermediate regime _tempered
overfitting_ , and studied it theoretically for kernel regression.

The aforementioned experimental results, as well as the limitations of the
existing theoretical results on benign overfitting suggest that understanding
tempered overfitting is crucial for explaining interpolation learning in
neural networks. Since all prior results on benign or tempered overfitting
either consider linear (or kernel) models, or consider linearly-separable
distributions with extremely high-dimensional inputs, a main challenge is to
understand tempered overfitting in settings that require nonlinear predictors
and where the input dimension is smaller than the number of samples.

In this work, we make a first step in this direction, by analyzing tempered
overfitting in two-layer univariate ReLU networks. We consider wide ReLU
networks that interpolate noisy training data of the form
$\\{(x_{i},y_{i})\\}_{i=1}^{n}\subseteq[0,1]\times\mathbb{R}$, such that
$x_{i}$ is distributed uniformly on $[0,1]$ and
$y_{i}=f^{*}(x_{i})+\epsilon_{i}$ where $\epsilon_{i}$ is a Gaussian random
noise. We aim to understand the performance of the interpolator on test data
from the same distribution at the limit where $n\to\infty$. Any finite
training dataset can be interpolated by infinitely many ReLU networks, and the
specific interpolator learned by gradient methods is determined either by
implicit or explicit regularization. We focus on the interpolator whose
parameters have a minimal norm, namely, on ridgeless regression. Such a min-
norm interpolator corresponds to an optimal solution when training the network
using an infinitesimally small explicit $L_{2}$ regularization (a.k.a. weight
decay). 333We note that characterization of the _implicit_ regularization of
gradient flow on ReLU networks with regression losses is currently unknown
(see vardi2022implicit).

At first glance, we might be tempted to think that two-layer univariate ReLU
networks behave like linear splines (see Figure 3), and thus exhibit tempered
overfitting, with the population loss not converging to its optimal value but
also not off by more than a constant factor (we provide a detailed analysis of
linear splines in Section 4). Indeed, prior works considered the relationship
between norm minimization in univariate ReLU networks and linear-spline
interpolation, as we discuss in the related work section. However, although
the min-norm interpolator is piecewise linear, it actually “spikes” beyond the
interpolated points (see Figure 5). Such spikes could be arbitrarily high when
the configuration of training points is particularly unfortunate, requiring
care in analyzing the typical behavior of min-norm interpolators. It turns out
that the qualitative effect of these spikes also depends on the loss function.

Below we summarize our main contribution:

  * •

For any $L_{p}$ loss with $p\in[1,2)$, we show that overfitting is tempered
(see Section 5.2). That is, the test performance of the min-norm interpolator
is worse than the predictor $f^{*}$ only by a constant factor.

  * •

For $L_{p}$ losses with $p\geq 2$ we show that overfitting is catastrophic
(Section 5.3). Namely, the population loss diverges as the training set’s size
tends to infinity.

  * •

When the training samples are equally spaced (e.g., in settings where the
learner can actively choose the training points, and then observe noisy
measurements at these points, and the query points are selected on an equally
spaced “grid”), we prove that overfitting is tempered w.r.t. $L_{p}$ for any
$p\geq 1$ (Section 6). Thus, the catastrophic behavior does not occur when the
samples are equally spaced, as it stems from the random variation in the
spacing between training points.

  * •

We show that tempered behavior is delicate, as in some cases we can have a
probability guarantee for tempered overfitting even if the expectation (over
the training samples) of the population loss is unbounded (see Section 5.2).
That is, although we have tempered behavior with high probability, the
expectation does not satisfy the definition of tempered overfitting given by
mallinar2022benign.

  * •

Experiments: TODO

The paper is structured as follows: Below we discuss some related work. We
introduce our setting in Section LABEL:sec:prelim. In Section 4 we analyze
tempered overfitting using the linear-spline interpolator. Our results on
interpolation learning with random data are provided in Section 5, as well as
an informal discussion on the proof ideas. The results on interpolation
learning with samples on the grid are given in Section 6. All formal proofs
are deferred to the appendix.

### Related work

#### Benign and tempered overfitting.

The benign overfitting phenomenon has been extensively studied in recent
years. Previous works analyzed the conditions in which benign overfitting
occurs in linear regression [hastie2020surprises, belkin2020two,
bartlett2020benignpnas, muthukumar2020harmless, negrea2020defense,
chinot2020robustness, koehler2021uniform, wu2020optimal, tsigler2020benign,
zhou2022non, wang2022tight, chatterji2021interplay, bartlett2021failures,
shamir2022implicit, ghosh2022universal], kernel regression [liang2020just,
mei2019generalization, liang2020multipledescent, mallinar2022benign,
rakhlin2019consistency, belkin2018overfittingperfectfitting,
mcrae2022harmless, beaglehole2022kernel, lai2023generalization], and linear
classification [chatterji2020linearnoise, wang2021binary, cao2021benign,
muthukumar2021classification, montanari2020maxmarginasymptotics,
shamir2022implicit, liang2021interpolating, thrampoulidis2020theoretical,
wang2021benignmulticlass, donhauser2022fastrates]. Moreover, several works
considered benign overfitting in classification using nonlinear neural
networks, in settings where the data distribution is linearly separable and
the input dimension is larger than the number of training samples
[frei2022benign, frei2023benign, cao2022benign, kou2023benign].

mallinar2022benign suggested the taxonomy of benign, tempered, and
catastrophic overfitting, which we use in this work. They demonstrated
empirically that nonlinear neural networks in classification tasks exhibit
tempered overfitting. Moreover, they studied tempered overfitting in kernel
regression. manoj2023interpolation studied tempered overfitting for a learning
rule returning short programs in some programming language.

We emphasize that the current work is the first to consider benign or tempered
overfitting in regression using nonlinear neural networks. Furthermore, we
note that all previous theoretical results on benign overfitting in linear
predictors and neural networks considered high-dimensional settings, where the
input dimension is larger than the number of samples in the training dataset.

#### Shallow univariate ReLU networks.

Several works studied ridgeless regression in univariate networks.
savarese2019infinite and ergen2021convex considered ridgeless regression with
two-layer univariate ReLU networks. In their setting, the solutions are
required to minimize the norm of the weights excluding the bias terms. That
is, the bias terms are not penalized. They showed that the linear-spline
interpolator is a solution to the ridgeless regression probelm, but this is
not a unique solution. Thus, in addition to the linear-spline interpolator
there are infinitely many other networks that fit the data and minimize the
norms. hanin2021ridgeless and debarre2022sparsest considered a similar
setting, and gave a geometric characterization of all minimal-norm
interpolators.

boursier2023penalising studied ridgeless regression with two-layer univariate
ReLU networks, where both the weights and the bias terms are penalized. They
showed that in this setting, there is a unique solution, i.e., a unique
interpolator that minimizes the parameters’ norms. Moreover, under certain
assumptions on the data, this solution is sparse, namely, has a small number
of kinks. We note that in this work we consider a similar setting, and we use
their characterization of the min-norm interpolator.

williams2019gradient studied regression in univariate two-layer ReLU networks
in the kernel regime. mulayoff2021implicit analyzed stable minima when
training shallow univariate ReLU networks using SGD. Finally,
safran2022effective studied the dynamics and implicit bias in training shallow
univariate ReLU networks in a classification setting. There, the implicit bias
of gradient flow leads to solutions that maximize the margin in parameter
space, namely, to networks with minimal parameter norms that attain a margin
of at least $1$. They showed that this bias toward norm minimization implies
minimization of the number of linear regions up to a constant factor, and
derived a generalization bound (in a noiseless setting).

#### Min-norm interpolation with univariate ReLU networks.

We consider neural networks $f_{\theta,a_{0},b_{0}}:\reals\to\reals$ defined
by

$f_{\theta,a_{0},b_{0}}(x)=a_{0}x+b_{0}+\sum_{j=1}^{m}a_{j}(w_{j}x+b_{j})_{+}~{},$

where $\theta\in\reals^{3m}$ denotes the vector of parameters
$\\{a_{j},w_{j},b_{j}\\}_{j=1}^{m}$, and $(\cdot)_{+}$ is the ReLU operation
$z\mapsto\max\\{0,z\\}$. The network $f_{\theta,a_{0},b_{0}}$ is a two-layer
ReLU network with an affine term. Let
$\mathcal{F}=\\{f_{\theta,a_{0},b_{0}}:m\in\nat,\theta\in\reals^{3m},a_{0},b_{0}\in\reals\\}$
be the class of all such neural networks (of any finite width).

Let $S=\\{(x_{i},y_{i})\\}_{i=1}^{n}\subseteq[0,1]\times\reals$ be a dataset
with $n\geq 2$. Throughout this work, we assume w.l.o.g. that
$x_{1}<\ldots<x_{n}$. Consider the following optimization problem:

$\inf_{f_{\theta,a_{0},b_{0}}\in\mathcal{F}}\norm{\theta}^{2}\;\text{ s.t.
}\;\forall i\in[n],\;f_{\theta,a_{0},b_{0}}(x_{i})=y_{i}~{}.$ (6)

The above problem considers interpolating the dataset $S$ using a min-norm
network. Note that $\theta$ includes all the parameters except for the affine
term, and specifically it includes the bias terms. We remark that our results
also apply to networks of infinite width, but Eq. (6) considers ReLU networks
of (arbitrarily large) finite width for ease of notation. Moreover, we note
that boursier2023penalising showed that the problem given in Eq. (6) is
equivalent to minimizing the implied regularizer
$R(f)=\int_{\IR}\sqrt{1+x^{2}}|f^{\prime\prime}(x)|dx$ over all interpolating
functions $f$.

We should discuss the skip connection and possibly explain why we believe
intuitively that it shouldn’t matter too much.

boursier2023penalising showed the following lemma about the min-norm
interpolator where all the $x_{i}$’s in $S$ are non-negative:

######  Lemma 2 (boursier2023penalising).

The problem in Eq. (6) admits a minimizer. Moreover, the minimizer is unique
(in function space) and has the following form:

$\hat{f}_{S}(x)=ax+b+\sum_{i=1}^{n-1}a_{i}(x-\tau_{i})_{+}~{},$ (7)

where $\tau_{i}\in[x_{i},x_{i+1})$ for every $i\in[n-1]$.

The above lemma implies that given a size-$n$ dataset $S$, there is a unique
min-norm interpolator $\hat{f}_{S}$, and it has at most one kink in the
interval $[x_{i},x_{i+1})$ for every $i\in[n]$. Note that even though the
problem in Eq. (6) allows arbitrarily wide networks, the min-norm interpolator
$\hat{f}_{S}$ can be computed by a network of width at most $n-1$.

#### Noisy interpolation learning.

Let $f^{*}:[0,1]\to\reals$ be a Lipschitz function. Let $\dist$ be a
distribution on $[0,1]\times\reals$, such that $(x,y)\sim\dist$ satisfies

$x\sim\unif([0,1])\;\;\;\;\text{ and }\;\;\;\;y=f^{*}(x)+\eps\;\text{ where
}\;\eps\sim\normal(0,\sigma^{2})~{},$ (8)

for a fixed constant $\sigma>0$. We note that we focus on the uniform
distribution on $[0,1]$ and on Gaussian noise for convenience, and our results
can be extended to more general input and noise distributions. For a function
$f:[0,1]\to\reals$ and $p\geq 1$, we define the population loss
$L_{p}(f):=\Exp_{(x,y)\sim\dist}[|f(x)-y|^{p}]$.

Let $S=\\{(x_{i},y_{i})\\}_{i=1}^{n}$ be a dataset drawn i.i.d. from $\dist$.
In this work, we study the test performance of the min-norm interpolator
$\hat{f}_{S}$, i.e., the population loss $L_{p}(\hat{f}_{S})$. By focusing on
the min-norm interpolator, we can study tempered overfitting without analyzing
the optimization question of whether gradient methods trained with weight
decay reach a global minimum or a sub-optimal local minimum. Thus, it allows
us to separate between two challenging problems, the first considers the
performance of ridgeless regression, and the second considers convergence
analysis for a non-convex problem.

##  4 Warm up: tempered overfitting in linear-spline interpolation

We start by analyzing tempered overfitting for linear-spline interpolation.
Namely, we consider the piecewise-linear function obtained by connecting each
pair of consecutive points in the dataset $S\sim\dist^{n}$ (see Figure 3
left), and analyze its test performance. As discussed, the linear-spline
interpolator is a minimizer of the network’s norms (albeit not a unique
minimizer) in a setting where the bias terms are not penalized
[savarese2019infinite, ergen2021convex]. In our setting, the linear-spline
interpolator does not minimize the network’s norms, but analyzing its test
performance is a useful first step toward understanding min-norm
interpolation.

Figure 3: An illustration of linear spline interpolation $\hat{g}_{S}(x)$ on a
dataset.

Given a dataset $S=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, let
$g_{i}:\IR\rightarrow\IR$ be the affine function joining the points
$(x_{i},y_{i})$ and $(x_{i+1},y_{i+1})$. Thus, $g_{i}$ is the straight line
joining the endpoints of the $i$-th interval. Then, the linear spline
interpolator $\hat{g}_{S}:\IR\rightarrow\IR$ is given by

$\hat{g}_{S}(x):=g_{1}(x)\cdot\mathbf{1}\\{x<x_{1}\\}+g_{n-1}(x)\cdot\mathbf{1}\\{x\geq
x_{n}\\}+\sum_{i=1}^{n-1}g_{i}(x)\cdot\mathbf{1}\\{x\in[x_{i},x_{i+1})\\}.$
(9)

Note that in the ranges $[0,x_{1}]$ and $[x_{n},1]$ the linear-spline
$\hat{g}_{S}$ is defined by extending the lines connecting $x_{1},x_{2}$ and
$x_{n-1},x_{n}$ respectively. The following theorem characterizes the
asymptotic bebavior of $L_{p}(\hat{g}_{S})$ for every $p\geq 1$:

######  Theorem 1.

Let $f^{*}$ be any Lipschitz function and $\dist$ be the distribution from Eq.
(8). Let $S\sim\dist^{n}$, and $\hat{g}_{S}$ be the linear-spline interpolator
(Eq. (9)) w.r.t. the dataset $S$. Then, for any $p\geq 1$ there is a constant
$C_{p}$ such that

$\lim_{n\rightarrow\infty}\Pr_{S}\left[L_{p}(\hat{g}_{S})\leq
C_{p}\,L_{p}(f^{*})\right]=1.$

The theorem shows that the linear-spline interpolator exhibits tempered
behavior, namely, w.h.p. over $S$ the interpolator $\hat{g}_{S}$ performs like
the predictor $f^{*}$, up to a constant factor.

To understand why Theorem 1 holds, Note that for all $i\in[n-1]$ and
$x\in[x_{i},x_{i+1}]$ the linear-spline interpolator satisfies
$\hat{g}_{S}(x)\in[\min\\{y_{i},y_{i+1}\\},\max\\{y_{i},y_{i+1}\\}]$.
Moreover, we have for all $i\in[n]$ that
$|y_{i}-f^{*}(x_{i})|=|\epsilon_{i}|$, where $\epsilon_{i}$ is the random
noise. Using these facts, it is not hard to bound the expected population loss
of $\hat{g}_{S}$ in each interval $[x_{i},x_{i+1}]$, and by using the law of
large numbers it is also possible to bound the probability that the loss in
the range $[x_{1},x_{n}]$ is large. Thus, in the range $[x_{1},x_{n}]$ we can
bound the $L_{p}$ loss both in probability and in expectation.

The less intuitive part is the behavior of $\hat{g}_{S}$ in the intervals
$[0,x_{1}]$ and $[x_{n},1]$. Analyzing the population loss in these intervals
requires considering the distribution of the spacings between data points. Let
$\ell_{0},\ldots,\ell_{n}$ be such that

$\forall
i\in[n-1]\;\;\ell_{i}=x_{i+1}-x_{i},\;\;\;\;\ell_{0}=x_{1},\;\;\;\;\ell_{n}=1-x_{n}~{}.$
(10)

Prior works [alagar1976distribution, pinelis2019order] established that

$\left(\ell_{0},\dots,\ell_{n}\right)\sim\left(\frac{X_{0}}{X},\dots,\frac{X_{n}}{X}\right),\text{
where }X_{0},\dots,X_{n}\iid\text{Exp}(1),\text{ and
}X:=\sum_{i=0}^{n}X_{i}~{}.$ (11)

For simplicity, assume that $f^{*}\equiv 0$ and consider the $L_{1}$ loss.
Since in the interval $[0,x_{1}]$ the linear-spline $\hat{g}_{S}$ is defined
by extending the line connecting $x_{1},x_{2}$, then it has slope of
$O\left(\frac{1}{\ell_{1}}\right)$, and hence the $L_{1}$ loss of
$\hat{g}_{S}$ in $[0,x_{1}]$ is

$O\left(\frac{\ell_{0}^{2}}{\ell_{1}}\right)=O\left(\frac{X_{0}^{2}}{X\cdot
X_{1}}\right)~{},$

as can be seen in Figure 3 (right). Since $X_{1}\sim\text{Exp}(1)$, then
$\Exp\left[\frac{1}{X_{1}}\right]=\infty$, and as a consequence we show that
the expected $L_{1}$ loss in $[0,x_{1}]$ is infinite. A similar argument also
holds for the interval $[x_{n},1]$. Hence, we get that

$\Exp_{S}\left[L_{p}(\hat{g}_{S})\right]=\infty~{}.$

However, with high probability the lengths $\ell_{1}$ and $\ell_{n-1}$ will
not be too short, and therefore the loss in the intervals $[0,x_{1}]$ and
$[x_{n},1]$ will be bounded, which allows us to obtain tempered overfitting
with high probability.

We remark that the undesirable performance of the linear-spline interpolator
$\hat{g}_{S}$ in the intervals $[0,x_{1}]$ and $[x_{n},1]$ can be avoided by
changing the definition of $\hat{g}_{S}$, such that it will return a constant
value in these intervals (as in Figure 1). In this case, we will get tempered
overfitting also in expectation. However, we preferred to analyze linear
splines as defined in Eq. (9), since a similar behavior in $[0,x_{1}]$ and
$[x_{n},1]$ also occurs in the min-norm interpolator, as we will show in the
next section.

##  5 Min-norm interpolation with random data

In this section, we study the performance of the min-norm interpolator with
random data. We first present some important properties of the minimal norm
interpolator in Section 5.1. In Sections 5.2 and 5.3 we use this
characterization to study its performance.

###  5.1 Characterizing the min-norm interpolator

Our goal is to give a characterization of the min-norm interpolator
$\hat{f}_{S}(x)$ (Eq. (7)), in terms of linear splines as defined in Eq. (9).
Recall the definition of affine functions $g_{1}(x),\dots,g_{n-1}(x)$, which
are piece-wise affine functions joining consecutive points. Let $\delta_{i}$
be the slope of the line $g_{i}(x)$, i.e. $\delta_{i}=g_{i}^{\prime}(x)$. We
denote $\delta_{0}:=\delta_{1}$ and $\delta_{n}:=\delta_{n-1}$. Then, we can
define the sign of the curvature of the linear spline $\hat{g}_{S}(x)$ at each
point.

######  Definition 3.

For any $i\in[n]$,

$\curv(x_{i})=\begin{cases}+1&\delta_{i}>\delta_{i-1}\\\
0&\delta_{i}=\delta_{i+1}\\\ -1&\delta_{i}<\delta_{i-1}\end{cases}$

Figure 4: An illustration of the characterization of $\hat{f}_{S}$ from Lemma
4.

Based on the curvature, the following lemma geometrically characterizes
$\hat{f}_{S}$ in any interval $[x_{i},x_{i+1})$, in terms of the linear pieces
$g_{i-1},g_{i},g_{i+1}$.

######  Lemma 4.

The function $\hat{f}_{S}$ can be characterized as follows:

  * •

$\hat{f}_{S}(x)=g_{1}(x)$ for $x\in(-\infty,x_{2})$;

  * •

$\hat{f}_{S}(x)=g_{n-1}(x)$ for $x\in[x_{n-1},\infty)$;

  * •

In each interval $[x_{i},x_{i+1})$ for $i\in\\{2,\dots n-2\\}$,

    1. 1.

If $\curv(x_{i})=\curv(x_{i+1})=+1$ then

$\max\\{g_{i-1}(x),g_{i+1}(x)\\}\leq\hat{f}_{S}(x)\leq g_{i}(x);$

    2. 2.

If $\curv(x_{i})=\curv(x_{i+1})=-1$ then

$\min\\{g_{i-1}(x),g_{i+1}(x)\\}\geq\hat{f}_{S}(x)\geq g_{i}(x);$

    3. 3.

Else, i.e. either $\curv(x_{i})=0$ or $\curv(x_{i+1})=0$ or
$\curv(x_{i})\neq\curv(x_{i+1})$,

$\hat{f}_{S}(x)=g_{i}(x).$

The lemma implies that $\hat{f}_{S}$ coincides with $\hat{g}_{S}$ except in an
interval $[x_{i},x_{i+1})$ where the curvature of the two points are both $+1$
or $-1$ (see Figure 4). Intuitively, this property captures the worst-case
effect of the spikes and will be crucial in showing the tempered behavior of
$\hat{f}_{S}$ w.r.t. $L_{p}$ for $p\in[1,2)$. However, this still does not
imply that such spikes are necessarily formed.

To this end, boursier2023penalising characterized the situation under which
indeed these spikes are formed. Roughly speaking, if the sign of the curvature
changes twice within three points, then we get a spike. Formally, we identify
special points from left to right recursively where the sign of the curvature
changes.

######  Definition 5.

We define $n_{1}:=1$. Having defined the location of the special points
$n_{1},\dots,n_{i-1}$, we recursively define

$n_{i}=\min\\{j>n_{i-1}:\curv(x_{j})\neq\curv(x_{n_{i}})\\}.$

If there is no such $n_{i-1}<j\leq n$ where
$\curv(x_{j})\neq\curv(x_{n_{i}})$, then $n_{i-1}$ is the location of the last
special point.

######  Lemma 6 (boursier2023penalising).

For any $k\geq 1$, if $\delta_{n_{k}-1}\neq\delta_{n_{k}}$ and
$n_{k+1}=n_{k}+2$, then $\hat{f}_{S}$ has exactly one kink between
$(x_{{n_{k}}-1},x_{n_{k+1}})$. Moreover, if
$\curv(x_{n_{k}})=\curv(x_{n_{k}+1})=-1$ then
$\hat{f}_{S}(x)=\min\\{g_{n_{k}-1}(x),g_{n_{k}+1}(x)\\}$ in
$[x_{n_{k}},x_{n_{k}+1})$.

Figure 5: An illustration of the spike formed by Lemma 6. Here, $x_{2}$ and
$x_{4}$ are two consecutive special points with exactly one point in between.
There must be exactly one kink in $(x_{1},x_{4})$. Thus, in $[x_{2},x_{3})$,
the interpolator $\hat{f}_{S}$ must be $\min\\{g_{1}(x),g_{3}(x)\\}$.

This is a slight variation of [boursier2023penalising, Lemma 8], which we
reprove in the appendix for completeness. See Figure 5 for an illustration of
the above lemma. To show the catastrophic behavior of $\hat{f}_{S}$ for $p\geq
2$, we will consider events under which such configurations of points are
formed. This will result in spikes giving catastrophic behavior.

###  5.2 Tempered overfitting for $L_{p}$ with $p\in[1,2)$

We now show the tempered behavior of the minimal norm interpolator w.r.t.
$L_{p}$ losses for $p\in[1,2)$.

######  Theorem 2.

Let $f^{*}$ be a Lipschitz function and $\dist$ be the distribution from Eq.
(8). Sample $S\sim\dist^{n}$, and let $\hat{f}_{S}$ be the min-norm
interpolator (Eq. (7)). Then, for some universal constant $C>0$, for any
$p\in[1,2)$ we have

$\lim_{n\rightarrow\infty}\Pr_{S}\left[L_{p}(\hat{f}_{S})\leq\frac{C}{2-p}\cdot\,L_{p}(f^{*})\right]=1~{}.$

The proof of Theorem 2 builds on Lemma 4, which implies that in an interval
$[x_{i},x_{i+1})$, a spike in the interpolator $\hat{f}_{S}$ must be bounded
within the triangle obtained from $g_{i-1},g_{i},g_{i+1}$ (see Figure 4). The
slopes of the affine functions $g_{i-1},g_{i+1}$ are roughly
$\frac{1}{\ell_{i-1}},\frac{1}{\ell_{i+1}}$, where $\ell_{j}$ are the lengths
as defined in Eq. (10). Hence, the spike’s height is proportional to
$\frac{\ell_{i}}{\max\\{\ell_{i-1},\ell_{i+1}\\}}$. As a result, the $L_{p}$
loss in the interval $[x_{i},x_{i+1}]$ is roughly

$\left(\frac{\ell_{i}}{\max\\{\ell_{i-1},\ell_{i+1}\\}}\right)^{p}\cdot\ell_{i}=\frac{\ell_{i}^{p+1}}{\max\\{\ell_{i-1},\ell_{i+1}\\}^{p}}~{}.$

Using the distribution of the $\ell_{j}$’s given in Eq. (11), we can bound the
expectation of this expression. Then, similarly to our discussion on linear
splines in Section 4, in the range $[x_{1},x_{n}]$ we can bound the $L_{p}$
loss both in expectation and in probability. In the intervals $[0,x_{1}]$ and
$[x_{n},1]$ the expected loss is infinite, and therefore we have

$\Exp_{S}\left[L_{p}(\hat{f}_{S})\right]=\infty~{}.$ (12)

Still, we can get a high probability upper bound for the $L_{p}$ loss in the
intervals $[0,x_{1}]$ and $[x_{n},1]$, as we did in the case of linear
splines. Thus, we get a bound on $L_{p}$ loss in the entire domain $[0,1]$
w.h.p.

We note that the definition of tempered overfitting in mallinar2022benign
considers only the expectation. Theorem 2 and Eq. (12) imply that in our
setting we have tempered behavior in probability but not in expectation, which
demonstrates that tempered behavior is delicate.

We also show a lower bound for the population loss $L_{p}$ which matches the
upper bound from Theorem 2 (up to a constant factor independent of $p$). The
lower bound holds already for $f^{*}\equiv 0$ and Gaussian label noise:

######  Theorem 3.

Let $f^{*}\equiv 0$, consider label noise $\epsilon\sim\normal(0,\sigma^{2})$
for some constant $\sigma>0$, and let $\dist$ be the corresponding
distribution from Eq. (8). Sample $S\sim\dist^{n}$, and let $\hat{f}_{S}$ be
the min-norm interpolator (Eq. (7)). Then, for some universal constant $c>0$,
for any $p\in[1,2)$ we have

$\lim_{n\rightarrow\infty}\Pr_{S}\left[L_{p}(\hat{f}_{S})\geq\frac{c}{2-p}\cdot
L_{p}(f^{*})\right]=1~{}.$

The proof of the above lower bound follows similar arguments to the proof of
catastrophic overfitting for $p\geq 2$, which we will discuss in the next
section.

###  5.3 Catastrophic overfitting for $L_{p}$ with $p\geq 2$

Next, we prove that for the $L_{p}$ loss with $p\geq 2$, the min-norm
interpolator exhibits catastrophic overfitting. We prove this result already
for $f^{*}\equiv 0$ and Gaussian label noise:

######  Theorem 4.

Let $f^{*}\equiv 0$, consider label noise $\epsilon\sim\normal(0,\sigma^{2})$
for some constant $\sigma>0$, and let $\dist$ be the corresponding
distribution from Eq. (8). Let $S\sim\dist^{n}$, and let $\hat{f}_{S}$ be the
min-norm interpolator (Eq. (7)). Then, for any $p\geq 2$ and $b>0$,

$\lim_{n\to\infty}\Pr_{S}\left[{L_{p}(\hat{f}_{S})>b}\right]=1~{}.$

To obtain some intuition on this phenomenon, consider the first four samples
$(x_{1},y_{1}),\ldots,(x_{4},y_{4})$, and let $\ell_{i}$ be the lengths of the
intervals as defined in Eq. (10). We show that with constant probability, the
configuration of the labels of these samples satisfies certain properties,
which are illustrated in Figure 5. In this case, Lemma 6 implies that in the
interval $[x_{2},x_{3}]$ the interpolator $\hat{f}_{S}$ is equal to
$\min\\{g_{1}(x),g_{3}(x)\\}$, where $g_{1}$ (respectively, $g_{3}$) is the
affine function that connects $x_{1},x_{2}$ (respectively, $x_{3},x_{4}$).
Now, as can be seen in the figure, in this “unfortunate configuration” the
interpolator $\hat{f}_{S}$ spikes above $f^{*}\equiv 0$ in the interval
$[x_{2},x_{3}]$, and the spike’s height is proportional to
$\frac{\ell_{2}}{\max\\{\ell_{1},\ell_{3}\\}}$. As a result, the $L_{p}$ loss
in the interval $[x_{2},x_{3}]$ is roughly
$\frac{\ell_{2}^{p+1}}{\max\\{\ell_{1},\ell_{3}\\}^{p}}$. Using Eq. (11), we
can show that
$\Exp_{S}\left[\frac{\ell_{2}^{p+1}}{\max\\{\ell_{1},\ell_{3}\\}^{p}}\right]=\infty$
for any $p\geq 2$.

Now, we divide the $n$ samples in $S$ into $\Theta(n)$ disjoint subsets of $6$
consecutive points. For each subset we consider the event that the labels are
such that the $4$ middle points exhibit an “unfortunate configuration” as
described above. These events are independent and occur with constant
probability. Therefore, there will be $\Theta(n)$ subsets with such
unfortunate configurations of labels with high probability. The expectation of
the population loss $L_{p}$ in each of these subsets is infinite. Using the
fact that we have $\Theta(n)$ such subsets and the losses in these subsets are
only mildly correlated, we are able to prove that $\hat{f}_{S}$ exhibits a
catastrophic behavior also in probability.

We note that the proof of the Theorem 3 follows similar arguments, except that
when $p<2$ the expectation of the $L_{p}$ loss in each subset with an
“unfortunate configuration” is finite, and hence we get a finite lower bound.

##  6 Min-norm interpolation with samples on the grid

In this section, we analyze the population loss of the min-norm interpolator,
when the $n$ data-points in $S$ are uniformly spaced, instead of i.i.d.
uniform sampling considered in the previous sections. Namely, consider the
training set $S=\\{(x_{i},y_{i}):i\in[n]\\}$, where

$x_{i}=\frac{i}{n}\hskip 5.69054pt\text{and}\hskip
5.69054pty_{i}=f^{*}(x_{i})+\eps_{i}\;\text{ for i.i.d. noise }\;\eps_{i}~{}.$
(13)

Note that the randomness in $S$ is only in the label noises $\epsilon_{i}$. It
can be interpreted as a _nonadaptive active learning_ setting, where the
learner can actively choose the training points, and then observe noisy
measurements at these points, and the query points are selected on an equally
spaced grid.

We show that in this situation the min-norm interpolator exhibits tempered
overfitting with respect to any $L_{p}$ loss:

######  Theorem 5.

Let $f^{*}$ be any Lipschitz function. For the size-$n$ dataset $S$ given by
Eq. (13), let $\hat{f}_{S}$ be the min-norm interpolator (Eq. (7)). Then for
any $p\geq 1$, there is a constant $C_{p}$ such that

$\lim_{n\rightarrow\infty}\Pr_{S}\left[L_{p}(\hat{f}_{S})\leq
C_{p}\,L_{p}(f^{*})\right]=1~{}.$

An intuitive explanation is as follows. Since the points are uniformly spaced,
whenever spikes are formed, they can at most reach double the height without
the spikes. Thus, the population loss of $\hat{f}_{S}(x)$ becomes worse but
only by a constant factor. We remark that in this setting the min-norm
interpolator exhibits tempered overfitting both in probability (as stated in
Theorem 5) and in expectation. We emphasize that the polynomial regression
(minimum degree polynomial interpolating the data) will continue to be
catastrophic even under the grid setting.

From Theorem 5 we conclude that the catastrophic behavior for $L_{p}$ with
$p\geq 2$ shown in Theorem 4 stems from the non-uniformity in the lengths of
the intervals $[x_{i},x_{i+1}]$, which occurs when the $x_{i}$’s are drawn at
random.

Finally, we note that previous works considered benign overfitting with data
on the grid as a simplified setting, which may help in understanding more
general situations [beaglehole2022kernel, lai2023generalization]. Our results
imply that this simplification might change the behavior of the interpolator
significantly.

## Acknowledgments and Disclosure of Funding

TODO