Noisy Interpolation Learning with Shallow Univariate ReLU Networks
Authors: Nirmit Joshi
Gal Vardi
Nathan Srebro
Venue: ICLR 2024 spotlight (2024)
Keywords: Interpolation Learning
Benign Overfitting
ReLU Networks
Primary area: learning theory
TL;DR: We study the overfitting behavior of min-norm networks in the noisy regression setting.

Abstract: Understanding how overparameterized neural networks generalize despite perfect interpolation of noisy training data is a fundamental question. Mallinar et. al. (2022) noted that neural networks seem to often exhibit ``tempered overfitting'', wherein the population risk does not converge to the Bayes optimal error, but neither does it approach infinity, yielding non-trivial generalization. However, this has not been studied rigorously.  We provide the first rigorous analysis of the overfiting behaviour of regression with minimum norm ($\ell_2$ of weights), focusing on univariate two-layer ReLU networks.  We show overfitting is tempered (with high probability) when measured with respect to the $L_1$ loss, but also show that the situation is more complex than suggested by Mallinar et. al., and overfitting is catastrophic with respect to the $L_2$ loss, or when taking an expectation over the training set.

Published as a conference paper at ICLR 2024
NOISY INTERPOLATION LEARNING WITH SHALLOW UNIVARIATE RELU NETWORKS
Nirmit Joshi TTI-Chicago ni rmi t@tti seettic... edu
Gal Vardi
Nathan Srebro TTI-Chicago nat @tt itticc.. edu
TTI-Chicago and Hebrew University ga vardi @ttic...... li....d edv
ABSTRACT
Understanding how overparameterized neural networks generalize despite perfect interpolation of noisy training data is a fundamental question. |Malinarr et al.) (2022) noted that neural networks seem often exhibit "tempered overfitting" wherein the population risk does not converge to the Bayes optimal error, but nei- ther does it approach infinity, yielding non-trivial generalization. However, this has not been studied rigorously. We provide the first rigorous analysis of the overfitting behavior of regression with minimum norm (&g of weights), focusing on univariate two-layer ReLU networks. We show overfitting is tempered (with high probability) when measured with respect the L, loss, but also show that the situation is more complex than suggested by Mallinar et al.] and overfitting is catastrophic with respect to the T.2 loss, or when taking an expectation over the training set.
INTRODUCTION
A recent realization is that, although sometimes overfitting can be catastrophic as suggested by our classic learning theory understanding, in other overfitting may not be catastrophic. In fact, even interpolation learning, which entails achieving zero training eπror with noisy data, can still allow for good generalization, and even consistency (Zhang et al. 2017 Belkin et al.) 2018). 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 neu- ral networks, theoretical study so far has been mostly limited to linear and kernel methods, or to classification settings where the data is already linearly separable, with very high data dimension (tending to infinity as the sample size grows] But what about noisy interpolation learning in low dimensions, using neural networks?
'Minimum & norm lincar prediction (aka ridgeless regression) with noisy labels and (sub-) GGuussian fea-
tures has been studied extensively (e.g. |Hastic et al. [2200] Belkin et al. [020 Bartlett et al. 2020
Muthuku-
mar et al. 2020, Negrea al. [2020] Chinot Lerasle [220]] Koehler et al. [202] Wu & Xu
2020
Tsigler &
Bartlen Zhou et al. [022 Wang el al. [202 [Chtterjii el al.] [202]] Bartlett Long 202 202T] Shamir 2022
Ghosh & Belkin [202 Chatterji & Long] 2021] [ Wang & Thrampoulidn, lidis) [021] Cao et al. [202 Muthukumar
al. 2021 Montanari et al. 2020 Liang & Recht [021 | ['hrampouiidis et al. 2020 Wang et al. [021 Don-
hauser et [2022] Frei
2023 and noisy minimum 2, linear prediction (aka Basis Persuit) has also been
considered (e.g.Ju al. 2020), Koehler et al. 2021 Wang al. 2022). Either way. these analyses are all in high dimensional setting. with dimension going to infinity, since to allow for interpolation the dimension must be high, higher than the number of samples. Keree methods amount to a minimum & norm lincar prediction, with very non-Gaussian features. But existing analyses of interpolation learning with kernel methods rely on "Gaussian Universality": either assuming an ansatz the behavior is as for Gaussian features (Mallinar et all 22022 or establishing this rigorously in certain high dimensional scalings (Hastic et al.) 2019: Misiakiewicz
2022
Mei & Montanari] (002). 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 moderate dimensions.
Frei et al. 2202 2023) Cao al. (2022 Kou al. (2023) study interpolation learning with neural networks, only with high input dimension and when the data is interpolatable also with a linear predictor these
cases, although non- mon-linear neural networks are used, the results show they behave similarly to linear predic- tors. Manoj & Srebro (2023) take the other extreme and study interpolation learning with "short programs". which are certainly non- non-linear, but this is abstract model that does not directly capture learning with neural networks.

---

Published as a conference paper at ICLR 2024
Mallinar et al. (2022) conducted simulations with neural networks and observed "tempered" over- fitting: 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 (Cover & Hart| 1967). and Mallinar et al. heuristically explain it also for some kernel methods. However, we do not have satisfying and rigorous understanding of such behavior in neural networks, nor a more quantitative 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 in the noisy regression setting, with neural networks in low dimensions, where the data is not linearly interpolatable. Specifically, we study interpolation learning of univariate data (i.e. in one dimension) using two-layer ReLU network (with a skip connection), which is a predictor fo
R -> RR given by:
m
fo. by (z) = Σ au(WE + bj)+ + ag + bu
(1)
where 0 Re3m denotes the weights (parameters) {aj, Wyy b3 )- To allow for interpolation do not limit the width m, and learn by minimizing the norm of the weights (Savarese et al. [2019] Ergen
& Pilanci 2021
Hanin 2021] Debarre al. 2022; Boursier Flammarion 2023):
fs = arg min |1012 s.t. Vi E [n], fo (xx) = yi where 5 = {(11, v1). (on, vn)) (2)
50
Following Boursier & Flammarion (202)) we allow an unregularized skip-connection in equation 1
where the weights ag bo of this skip connection are not included in the norm |[@]| in equation 2
This skip connection avoids some complications and allows better characterizing fs but does not meaningfully change the behavior (see Section 2
Why min norm? Using unbounded size minimum weight-norm networks is natural for interpo- lation learning. It parallels the study of minimum norm high (even infinite) dimension linear pre- dictors. 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 overparameterized neural networks (Neyshabur al. 2014). Seeking minimum l norm weights is natural, e.g. as a result of small weight decay. Even without explicit weight decay, optimizing using gradient descent also related to an implicit bias toward low lg norm: this can be made precise for linear models and for classification with ReLU networks (Chizat & Bach 2020 Safran et al., 2022). For regression with ReLU networks, as we study here, the implicit bias is not well understood (see Vardi (203)), ), and studying equation Z a good starting point for understanding the behavior of networks learned via gradient descent even without explicit weight decay. Interestingly, minimum-norm interpolation corresponds to the rich regime, and does not correspond to any kernel (Savarese et al. 2019). For the aforementioned reasons, understanding the properties of min-norm interpolators has attracted much interest in recent years (Savarese al.
|019] Ongie et al. 22019] Ergen & Pilanci
2021 Hanin
2021 Debarre et al.) 2022 Boursier &
Flammarion] 2023)
Noisy interpolation learning. x ~ Uniform([0, 1]) and y fx) + with e independent of x, where x is uniform for simplicity and concreteness The noise e follows some arbitrary (but non- zero) distribution, and learning is based on an i.i.d. training set S ~ D 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 ||0|]- Indeed, under mild assumptions, this balanced approach leads to asymptotic consistency, with fs ===,0 f and the asymptotic population risk of fs converging to the Bayes risk. But what happens when we overfit and use the interpolating learning rule equation
We consider a noisy distribution D over [0, 1] x R:
(3)
2 All our results should also hold for any absolutely continuous distribution with bounded density and sup- port. Roughly speaking, this can be achieved by dividing the support into disjoint intervals such that the distribution in each interval is well-approximated by uniform distribution.
2

---

Published as a conference paper at ICLR 2024
4.0
Figure 1: Comparison between linear-spline (purple) and min-norm (green) interpolators.
Linear Splines. At first glance, we might be tempted think that two-layer ReLUU behave like linear splines (see Figure D Indeed, if minimizing the norm of weights w, and ag but not the biases 6, in equation 2 linear splines are valid minimizer (Savarese et al. 2019 Ergen Pilanci 2021]. 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 nearest-neighbor predictor (each prediction weighted average of two neighbors). Indeed, in Theorem T of Section 3 we show that linear splines exhibit "tempered" behavior, with asymptotic risk proportional to the noise level.
From Splines to Min-Norm ReLU Nets. It out minimum norm ReLU networks, although piecewise linear, are not quite linear splines: roughly speaking, and as shown in Figure they are more conservative in the number of linear "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 creates additional "spikes", extending above and below the data points (see Figures and 2 and thus potentially increasing the error. In fact, such spikes are also observed in interpolants reached by gradient descent (Shevchenko et al. 2022 Figure 1). How bad is the effect of such spikes on the population risk?
OUR CONTRIBUTION
Effect of Overfitting on I,p Risk. It turns out the answer is quite subtle and, despite considering the same interpolator, the nature of overlitting actually depends on how we measure the error. For function f IR R, measure its L, population error and the reconstruction error respectively as
(S)
E (x.n)~
[l((z) vlP)
and Rp(3) =
Uniiformm (0.1)) (1[(x) (x))))
E
We show in Theorems and B of Section 4.2 that for 1 1pp22
(f()s)
n-000 θ (2 -)=
1 (22-)))) Cp(5").
(4)
This is an upper bound for any Lipschitz target f and any noise distribution, and it is matched by lower bound for Gaussian noise. That is, for abs-loss (L1 risk), as well as any Lp risk for 1 & < 2, overfitting is tempered. But this tempered behavior explodes as p + 2, and we see sharp transition. We show in Theorem of Section 4.3 that for any p 2 2, including for the square loss (p = 2), in the presence of noise, (f(ss 12+00 oc and overfitting is catastrophic.
Convergence vs. Expectation. The behavior even more subtle, in that even for < 2, although the risk (f()s converges in probability to a tempered behavior in equation its expectation is infinite: Es [s(C,((s)] = oc. Note that in studying tempered overfitting, Mallinar et al. 2022) focused this expectation, and would have categorized the behavior "catastrophic" even for 1, emphasizing the need for more careful consideration of the effect of overfitting.
LLD.. Samples vs. Samples on a Grid. The catastrophic effect of interpolation on the Lp risk with p 2 2 is 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 study "fixed design" variant
(see Figures and 5). To help understand this, in Section
3

---

Published as a conference paper at ICLR 2024
0.0 32 5.4 0.6
2.8
2.0
Figure 2: The min-norm interpolator for 30 random points with f and N 1) label noise.
of the problem, where the training inputs lie on uniform grid, 2; = i/n, and responses follow Y: (x:) + G.- In this case, interpolation is always tempered, with (f(ss) n ((Lp(f)) for any constant 2 (Theorem Section
Discussion and Takeaways. Our work is the first to study noisy interpolation learning with min- norm ReLU networks for regression. It is also the first to study noisy interpolation learning in neural networks where the input dimension does not grow with the sample size, and to consider non-linearly-interpolaatll
data distributions (see below for comparison with concurrent work in a classification setting). The univariate case might seem simplistic, but is a rich and well-studied model in its own right (Shevchenko et al. [2022] [rgen & Pilanci 2021 Hanin 202 Debarre al., 2022 Boursier Flammarion 2023] Williams et al., 2019, Mulayoff et al. 2021; Safran et al, 2022 and
see, it already exhibits many complexities and subtleties that need to be resolved, and 18 thus a non-trivial necessary first step if we want to proceed to the multivariate case.
The main takeaway from work is that the transition from tempered to catastrophic overfitting can be much more subtle than previously discussed, both in terms of the details the setting (e.g., sampled data data grid) and in terms of the definition and notion of overfitting (the loss function used, and expectation vs. high probability). Understanding these subtleties is crucial before moving on more complex models.
More concretely, we see that for the square loss, the behavior does not fit the "tempered overfitting" predictions of Mallinar et al.] (2022), and for the L1 loss we get tempered behavior with high probability but not in expectation, which highlights that the definitions of (Mallinar et al. 2022) need be refined. We would of course not get such strange behavior with the traditional non-overfittin approach of balancing training error and norm; in this situation the risk converges almost surely to the optimal risk, with finite expectation and vanishing variances. Moreover, perhaps surprisingly, when the input data is the grid (equally spaced), the behavior is tempered for all losses even in the presence of label noise. This demonstrates that the catastrophic behavior for Lp losses for p 2 is not just due to the presence of label noise; it is the combination of label noise and sampling of points that hurts generalization. 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 (Beaglehole jet al., (2022] Lai et af.] (2023). Our results imply that this simplification might change the behavior of the interpolator significantly. In summary, the nature of overfitting delicate property of the combination of how we measure the loss and how training examples are chosen.
Comparison with concurrent work. In a concurrent and independent work, Kornowski et al. (2023) studied interpolation learning in univariate two-layer ReLUU networks in classification set- ting, and showed that they exhibit tempered overfitting. In contrast to our regression setting, in classification only the output's sign affects generalization, and hence the height of the spikes do not play significant role. As result, our regression setting exhibits a fundamentally different behavior, and the above discussion the delicateness of the overfitting behavior in regression does not apply to their classification setting.
2 REVIEW: MIN-NORM RELU NETWORKS
Minimum normm unbounded-win width univariate two-layer ReLU networks have been extensively stud- ied in recent years, starting with Savarese al. (019)) with the exact formulation equation 2 in-
4

---

Published as a conference paper at ICLR 2024
(s)
8x(x)
81
82(x)
Figure 3: An illustration of the linear spline interpolator 9s (left), and of the variant hy where linear pieces are extended beyond the endpoints (right).
corporating skip connection due to Boursier & Flammarion 2023 Boursier & Flammarion following prior work, establish that a minimum equation 2 exists, with a finite number of units, and that is also unique.
The problem in equation 2 is also equivalent to minimizing the "representation cost" R(f) I vI+x* (f" [=)]dda over all interpolators f. although we will not use this characterization ex- plicitly in our analysis. Compared to [Savarese al.] (2019), where the representation cost is given by max (x)),)) (5"(-o)) + f'(+))) the weighting v1+ x² is due penalizing the biases by. More significantly, the skip connection in equation avoids the "fallback" terms of extreme slope). This simplified the technical analysis and presentation, while rarely affecting the solution.
[-'(-00 (+)+ which only kick-in in extreme cases (very few points
Boursier & Flammarion provide the following characterization of the minimizer fs of equation which we will rely on heavily:
Lemma 2.1 (Boursier & Flammarion (203)), )) For 0 I x1 D2 < ... < En. the problem in
equation] admits a unique minimizer of the form:
fs(x) = ox + b
ag(x - Ti)+
(5)
where TÚ [11, for every i [n 1].
As in the above characterization, is very convenient to take the training points to be sorted. Since the learned network fs 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 WARM UP: TEMPERED OVERFITTING IN LINEAR- INTERPOLATION
We start by analyzing tempered overfitting for linear-spline interpolation. Namely, we consider the piecewise-lined function obtained by connecting each pair of consecutive points in the dataset ~ D" (see Figures| I and 3 left) and analyze its test performance.
Given dataset S [x,,, v1)) Y let gi E. + R be the affine function joining the points (z,, v1) and (#++1. 1.+1). Thus, 9: is the straight line joining the endpoints of the i-th interval. Then, the
linear spline interpolator ÿs [0, 1] + R is given by
n-1
Os(x) = U/ 1(x < x1) + Un 1fx 2 x
Σ
(x(z)) 1fx E [13,
(6)
'If' the biases b; are not included in the norm [[O]] in equation 2 and this norm is replaced with Σ : wu)
the modified problem admits multiple non-unique minimizers, including linear spline (with modified behavior past the extreme points) (Savarese et al. 2019). This set of minimizers was characterized by Hanin (202T) Interestingly, the minimizer fs of equation 2 (when the biases are included in the norm) is also minimizer of the modified problem (without including the biases). All our results apply also the setting without penalizing the biases the following sense: the upper bounds are valid for all minimizers, while some minimizer, namely fs that we study, exhibits the lower bound behavior.
5

---

Published as a conference paper at ICLR 2024
Note that in the intervals [0, æ1 and [at, 1] the linear-spline is defined to be constants that corre- spond to labels y1 and yn respectively. The following theorem characterizes the asymptotic behavior of (0s)) for every p 2
Theorem 1. Let f be any Lipschitz,function and 'D be the distribution from equation 3 Let S ~ D", and Ås be the linear-spline interpolator (equation 6 w.r.t the dataset Then, for any p 2 there is constant Cp such that
lim P. (Rp((s)) Cp =1 and Tim ((G =1 n--000 S
The theorem shows that the linear-spline interpolator exhibits tempered behavior, namely, w.h.p. over S the interpolator Îs performs like the predictor f", up a constant factor. To understand why Theorem T holds, note that for all i [n- 1] and E [xi, #5+1 the linear-spline interpolator satisfies (x(x) E min [3i. Ms+1 }, max (1,, yt+1 Moreover, we have for all E [n]] that [y: ff= (z;)) |cs]. where is the random noise. Using these facts, it is not hard to bound the expected population loss of ÿs each interval [x, 1.+1], and by using the law of large numbers
also possible to bound
the probability (over S) that the loss in the domain [0, 1] is large. Thus, we can bound the Lpp loss both in expectation and in probability.
Delicate behavior of linear splines. We now consider the following variant of the linear-spline interpolator:
hs(x) = (x) 1fx < x1 + 9n-1(z) 1(x > xn + 9s(x) 1f2 E (e1,,,)
(7)
In words, hg is exactly the same as os in the interval [211 vn). but extends the linear pieces g and 9h-1 beyond the endpoints I1 and In (respectively), illustrated in Figure 3 (right). The interpolator hg still exhibits tempered behavior in probability, similarly to Ås- However, perhaps surprisingly, hig is not tempered in expectation (see Appendix A for details). This delicate behavior of the linear-spline interpolator is important since in the next section we will show that the min-norm interpolator has similar behavior to iıg in the intervals [0, 211, [I,,, 1), and as consequence, it is tempered with high probability but not in expectation.
MIN-NORM INTERPOLATION WITH RANDOM DATA
In this section, study the performance of the min-norm interpolator with random data. We first present some important properties of the min-norm interpolator in Section 4.1 In Sections 4.2 and 4.3
we use this characterization study its performance.
4.1 CHARACTERIZING THE MIN-NORM INTERPOLATOR
Our goal is to give characterization of the min-norm interpolator fs( (equation 5). in terms of linear splines as defined equation 6 Recall the definition of affine functions gi (z),.... : -n- (r), which piece-wise affine functions joining consecutive points. Let ó, be the slope of the line (z)), i.c. ò, = (x). We denote 8, := ó1 and 6, := 6n-1. Then, we can define the sign of the curvature of the linear spline (x) at each point.
Definition 4.1. For any E [n].
+1 5, > 6:-1
curv(2;)
0
6, 6:41
-1
5, 6:-1
Based on the curvature, the following lemma geometrically characterizes fs any interval [xy, (441), in terms of the linear pieces Ji-1, Dis 9:-1-
Lemma 4.2. The function is can be characterized as follows:
(- fs(x) = 9i x (-o0,,
fs(x) = (x:) for (mn-1,00):

---

Published as a conference paper at ICLR 2024
y
min (gv( gx(s))
-11
8z64
congle
max(gs(+)gss(t)
Xg
X2
X3
X4
X5
%
Figure 4: An illustration of the characterization of fs from Lemma 4.2
In each interval (14, for {2.... 22.. !fcurv((s)) curv(2;41) = then
max 1 91+ (x)) & fs(x) - gx(x;;
If fcurv((a)) = curv(2;41) = -1 then
min(g:-1(x)) git1 (x)) fs(x) 2 g(();;
Else, ie. either curv(z;) = 0 or cu = or curv(z,) # curv(a;+1).
ss(x) 9 (xr).
The lemma implies that fs coincides with 9s except in an interval [a, 2441) where the curvature of the two points are both +1 or -1 (see Figure Intuitively, this property captures the worst- case effect of the spikes and will be crucial in showing the tempered behavior of fs w.r.t. Lp for p E [1, 2). However, this still does not imply that such spikes are necessarily formed.
To this end, Boursier & Flammarion 2023 Lemma 8) characterized the situation under which indeed these spikes are formed. Roughly speaking, if the sign of the curvature changes twice within three points, then get spike. Formally, we identify special points from left to right recursively where the sign the curvature changes.
Definition 4.3. We define n Having defined the location of the special points a1.... Ri-b we recursively define
n4 min > n4-1 : curv(z,) * curv(En.))+
If there is such n4-1 <j < n where curv(I;;) + curv(In,), then ni-1 is the location of the last special point.
Lemma 4.4 (Boursier & Flammarion 20023). For any k 2 if f & 8ns and Rk+1 7i + +2, then fg has exactly one kink between (Ing (Ing-1, Bnst.). Moreover, (f = curv(Ima+1) = -1
then fs(x) min Ira +1 (x)) in [T 11)
Lemma 8), which we reprove in the appendix for completeness. See Figure for an illustration of the above lemma. To show the catastrophic behavior of fs for p 2 2. we will consider events under which such configurations of points are formed. This will result in spikes giving catastrophic behavior.
This is a slight variation of (Boursier & Flammarion 2023
4.2 TEMPERED OVERFITTING FOR L, WITH E (1,2)
We now show the tempered behavior the minimal norm interpolator w.r.t. Lp losses for p E [1,2).
Theorem 2. Let f be a Lipsehitz function and D be the distribution from equation 3 Sample
D", and let fs be the min-norm interpolator (equation Then, for some universal constant
C> 0, for any E (1,2) we have
lim (Rp(ss) t00
C 2-p c,(5)] and lim P n S
cy(fs) S C_ c.(5)) =
2-

---

Published as a conference paper at ICLR 2024
(x)
Sou
14.40
Ry Ry
X
aumbed
5
An illustration of the spike formed by Lemma 4.4 Here, 22 and æ are two consecutive special points with exactly one point in between. There must be exactly one kink in (01, Thus, in (22, wa), the interpolator is must be min(gi (I:), (x))).
Figure 5:
The proof of Theorem 2 builds on Lemma 4.2, which implies that in interval [ra, 1441), a spike in the interpolator fs must be bounded within the triangle obtained from Ii-1, Iis 9i+ (see Figure 4 Analyzing the population loss of fs requires considering the distribution of the spacings between data points. Let fo...., fn be such that
...
Vi [n 1] l, Z++1 Ts. to = I1, ln In
(8)
Prior works (Alagar 1976 Pinelis 2019) established that
Xu X,
n Lid. Exp(1), and X = Σ where Xo. Xn
(Co....,er)
(9)
X
==0
The slopes of the affine functions 91-1.9-1 9++1 are roughly - 1. where lj are the lengths as defined in equation 8 Hence, the spike's 's height is proportional to max As result, the Lp loss in the interval [1,, 11+1] roughly
&
E,
gp+1
.4 (
Using the distribution of the Ej's given in equation g we can bound the expectation of this expres- sion. Then, similarly to our discussion linear splines in Section 3 in the range [z1. we can bound the Lp loss both in expectation and in probability. In the intervals [0, x1] and [zn, 1], the expected loss infinite (similarly to the interpolator hi in equation 7. and therefore we have
5 [C((fs) oo.
(10)
Still, we can get high probability upper bound for the L,p loss in the intervals [0, 21 and [x,, 1]. Thus, we get a bound on I., loss in the entire domain [0, 1] w.h.p. We note that the definition of tempered overfitting in Mallinar et al. (202)) considers only the expectation. Theorem 2 and equation] 10mmply that in our setting we have tempered behavior in probability but not in expectation, which demonstrates that tempered behavior delicate.
We also show lower bound for the population loss Lp which matches the upper bound from The- orem / (up to a constant factor independent of p). The lower bound holds already for f 0 and Gaussian label noise.
Theorem 3. Let f = O. consider label noise ~ No0 o²) for some constant a > 0, and let D be the corresponding distribution from equation 3 Let S Dn, and let is be the min-norm interpolator (equation) 5). Then, for some universal constant e > 0, for any p E [1, 2) we have
lim IP
Ro((s)
2-p c,(0)] and
lim PP (.((ss)
c,( - =1.
_ P
The proof of the above lower bound follows similar arguments to the proof of catastrophic overfitting for p > 2, which will discuss in the next section.
8

---

Published as a conference paper at ICLR 2024
4.3 CATASTROPHIC OVERFITTING FOR Lp WITH p 2
Next, we prove that for the Lp loss with 2 2, the min-norm interpolator exhibits catastrophic overfitting, We prove this result already for f and Gaussian label noise:
Theorem 4. Let f
consider label noise DD be the corresponding distribution from equation
NO0 o²) for some constant a > O. and let
3 Let S ~ D", and let fs be the min-norm
interpolator (equation 5). Then, for any p 2 2 and b 0.
lim 20000
(R((s)) > bl =1 and
lim PP ((((s)) > b) =1. n-000
To obtain some intuition this phenomenon, consider the first four samples (I1, 3/1 91)...., (2a. ya), and let & be the lengths of the intervals as defined in equation g We show that with constant probability, the configuration of the labels of these samples satisfies certain properties, which illustrated in Figure In this case, L.4 imppiees that in the interval [22, æg] the interpolator fs is equal to min(g1 (z) where (respectively, ga) is the affine function that connects æ 22 (respectively, 23, (44) Now, as can be seen in the figure, in this "unfortunate configuration" the interpolator Is spikes above f = 0 in the interval [22, 73], and the spike's s height proportional to
As a result, the Tp loss in the interval [222, 33) is roughly 253 Using equation 9.
max
can show that Es
max PP oo for any p 2 2.
We then divide divide the samples in S into (n)) disjoint subsets and consider the events that labels are such that the 4 middle points exhibit an "unfortunate configuration" as described above. Using the fact that have (n) such subsets and the losses in these subsets are only mildly corre- lated, we are able to prove that fs exhibits catastrophic behavior also in probability.
We note that the proof of Theorem 3 follows similar arguments, except that when < 2 the expec- tation of the Lp loss in each subset with an "unfortunate configuration" is finite, and hence we get finite lower bound.
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;, m.) E [n]]. where
T and y: = f=;;a + e, for i..d. noise E
(II)
Note that the randomness in S is only in the label noises 4; It can be interpreted as a non-adaptive 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 Lp loss:
Theorem 5. Let f be any Linschitz.uunctinn For the size-n dataset S given by equation 11 let fs be the min-norm interpolator (equation 5.
function.
Then for any p 1, there is a constant C such that
RR((s) S Cp Co() =1 and lim TP S
lim P n- S
(c(fs)) & CC Cppp))))
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 fs(r) 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. From Theorem 5 we conclude that the catastrophic behavior for Lp with p 2 shown in Theorem steems from the non-uniformity in the lengths of the intervals [x,, 2.41], which occurs when the 2; are drawn random.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This research was done as part of the NSF-Simons Sponsored Collaboration on the Theoretical Foundations of Deep Learning and the NSF Tripod Institute Data, Econometrics, Algorithms, and Learning (IDEAL). N. J. would like to thank Surya Pratap Singh for his generous time in helping resolve Python errors.
REFERENCES
Vangalur $ Alagar. The distribution of the distance between random points. Journal of Applied Probability, 13(3):558-56, 1976.
Peter L Bartlett and Philip M Long. Failures of model-dependent generalization bounds for least- norm interpolation. The Journal of Machine Learning Research, 22(1):927--9311 2021.
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Acudemy of Sciences, 117744):30063-300777 2020.
Daniel Beaglehole, Mikhail Belkin, and Parthe Pandit. Kernel ridgeless regression is inconsistent for low dimensions. arXiv preprini arXiv:2205.133: 13525, 2022.
Mikhail Belkin, Daniel Hsu, and Partha Mitra. Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM
Journal on Mathematics of Data Science, 264):1167-1180, 2020.
Etienne Boursier and Nicolas Flammarion. Penalising the biases norm regularisation enforces sparsity, arXiv preprint arXiv:2303.01355 2023.
Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for over- per-parameterized maximum mar- gin classification on sub-gaussian mixtures. In Advances in Neural Information Processing Sys- tems (NeurIPS), 2021.
Yuan Cao, Zixiang Chen, Mikhail Belkin, and Quanquan Gu. Benign overfitting in two-layer con- volutional neural networks. arXiv preprint arXiv:2202.06522 2022.
Niladri S. Chatterji and Philip M. Long. Finite-sample sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129);1-30, 2021.
Niladri S Chatterji, Philip M Long, and Peter L Bartlett. The interplay between implicit bias and benign overfitting in two-layer linear networks. arXiv preprint arXiv:2108. 11489, 2021.
Geoffrey Chinot and Matthieu Lerasle. On the robustness of the minimum Eg interpolator. arXiv preprint arXhv:2003.05838, 2020.
Lenaic Chizat and Francis Bach. Implicit bias gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference Learning Theory (COLT), 2020.
Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions on infor- mation theory, 13(1):21-27, 1967.
Thomas Debarre, Quentin Denoyelle, Michael Unser, and Julien Fageot. Sparsest piecewise-liness regression of one-dimensional data. Journal of Computational and Applied Mathematics, 406: 114044, 2022.
W Edwards Deming and Clarence G Colcord. The minimum in the gamma function. Nature, 135 (3422):917-917, 1935.
Konstantin Donhauser, Nicolo Ruggeri, Stefan Stojanovic, and Fanny Yang. Fast rates for noisy in- terpolation require rethinking the effect of inductive bias. In International Conference on Machine Learning (ICMI., 2022. 2022.
10

---

Published as a conference paper at ICLR 2024
Tolga Ergen and Mert Pilanci. Convex geometry and duality of wver-parameterized neural networks. Journal of machine learning research, 2021.
Spencer Frei, Niladri S. Chatterji, and Peter L. Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory (COLT), 2022.
Spencer Frei, Gal Vardi, Peter L Bartlett, and Nathan Srebro. Benign overfitting in linear clas- sifiers and leaky relu networks from kkt conditions for margin maximization. arXiv preprint arXiv:2303.01462, 2023.
Nikhil Ghosh and Mikhail Belkin. A universal trade-off between the model size, test loss, and training loss of linear predictors. arXiv preprint arXiv:2207.11621, 2022.
Boris Hanin. Ridgeless interpolation with shallow relu networks in 1d is nearest neighbor curvature extrapolation and provably generalizes on lipschitz functions. arXiv preprint arXiv:2109. /2960, 2021.
Trevor Hastic, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint
2019.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Preprint, arXiv: 085000 2020.
Peizhong Ju, Xiaojun Lin, and Jia Liu. Overfitting can be harmless for basis pursuit, but only to degree. Advances in Neural Information Processing Systems, 33:7956-7967, 2020.
Frederic Koehler, Lijia Zhou, Danica J Sutherland, and Nathan Srebro. Uniform conver- gence of interpolators: Gaussian width, norm bounds, and benign overfitting. arXiv preprint arXiv::/066.09276 2021.
Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in relu neural networks. arXiv preprint arXiv:2305. 15141, 2023.
Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting for two-layer relu networks. arXiv preprint arXiv:2303.04145. 2023.
Jianfa Lai, Manyun Xu, Rui Chen, and Qian Lin. Generalization ability of wide neural networks on R. arXiv preprint arX 2023.
Tengyuan Liang and Benjamin Recht. Interpolating classifiers make few mistakes. arXiv preprint 118. 2021.
Neil Mallinar, James B Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Pree- tum Nakkiran. Benign, tempered, or catastrophic: A taxonomy of overfitting. arXiv preprint arXiv:2207.06569, 2022.
Naren Sarayu Manoj and Nathan Srebro. Interpolation learning with minimum description length. arXiv preprint 20X.v:2302..7263. 2023.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
Theodor Misiakiewicz.
Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv preprint arXiv:2204.1042. 2022.
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max- margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. Preprint, 191 2020.
Rotem Mulayoff, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability: A view from function space. Advances in Neural Information Processing Systems, 14:17749-1776) 2021.
11

---

Published as a conference paper at ICLR 2024
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless inter- polation of noisy data in regression. IEEE Journal on Selected Areas Information Theory, 2020.
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparamettrizzed regimes: Does the loss function matter? Journal of Machine Learning Research, 22(222): 2021.
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform convergence: Generalization via derandomization with an application interpolating predictors. Interna- tional Conference on Machine Learning, pp. 7263-7272, 2020.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. Preprint, arXiv: arXiv:1412.00 1412.6612. 2014.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint arXiv:1910.01633 2019.
Iosif Pinelis. Order statistics on the spacings between order statistics for the uniform distribution. arXiv preprint 1909:099900666 2019.
Itay Safran, Gal Vardi, and Jason Lee. On the effective number of linear regions in shallow uni- variate relu networks: Convergence guarantees and implicit bias. Advances in Neural Information Processing Systems (NeurIPS), 2022.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pp. 2667-2690. PMLR, 2019.
Ohad Shamir. The implicit bias of benign overfitting. In Conference on Learning Theory, pp- 448-478. PMLR, 2022.
Alexander Shevchenko, Vyacheslav Kungurtsev, and Marco Mondelli. Mean-field analysis of piece- wise linear solutions for wide relu networks. The Journal of Machine Learning Research, 23(1): 3660-5714 14, 2022.
Christos Thrampoulidis, Samet Oymak, and Mahdi Soltanolkotabi. Theoretical insights into multi- class classification: A high-dimensional asymptotic view. Advances in Neural Information Pro- cessing Systems, 33:8907-8920, 2020.
A. Tsigler and P. L. Bartlett. Benign overfitting in ridge regression. Preprint, arXiv:2009.14286 2020.
Gal Vardi. On the implicit bias in deep-learning algorithms. Communications of the ACM, 66(6): 86-93, 2023.
Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum 11-norm interpolation of noisy data. In International Conference Artificial Intelligence and Statisties (AISTATS), 2022.
Ke Wang and Christos Thrampoulidis. Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting and regularization. Preprint, arXiv:2011.091/ 2021.
Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis. Benign overfitting in multiclass classi- fication: All roads lead to interpolation. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. In Advances in Neural Information Pro- cessing Systems, pp. 2378-83877 2019.
Denny Wu and Xu. On the optimal weighted & regularization in overparameterized linear regres- sion. Advances in Neural Information Processing Systems, 33:101 12-10123, 2020.
12

---

Published as a conference paper at ICLR 2024
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations (ICLR), 2017.
Lijia Zhou, Frederic Koehler, Pragya Sur, Danica Sutherland, and Nathan Srebro. A non- asymptotic moreau envelope theory for high-dimensional generalized linear models. arXiv preprint arXiv:2210. 2022.
13

---

Published as a conference paper at ICLR 2024
A DELICATE BEHAVIOR OF LINEAR SPLINES
Recall the definition of hg from equation 7
hs(x)) gn (I) 1f x1 + 9n-1(x) 1(x mn) + ûs(*) 1 [x))
For simplicity, assume that S = 0 and consider the Li loss. Since in the interval [0, 21 the interpolator hg is defined by extending the line connecting (I1,81) and (22, U2), then it has slope of θ and hence the L1 loss of hs in [0, is
(6) 2 - +
(2)-0
X X XX-1
as can be seen in Figure (right). Recall that (Xo...., Xn) and X are defined in equation 9 Since X1 Exp(1), then x oc, and as a consequence the expected L1 loss in [0, xi is
infinite. similar argument also holds for the interval [zn. 1]. Thus, we get that lRg (hs))) = oc. However, with high probability the lengths l and fn-1 will not be too short, and therefore the loss in the intervals [0, æ1] and [In, 1] will be bounded, which implies tempered overfitting with high probability.
B PROOF OF THEOREM 1
Proof of Theorem Let G < oo be the Lipschitz constant of f*. We sample S D and we number points (Ii; Mi) such that:
0 << 21 22 < ... In <.
We will also denote 20 = 0 and In+1 = for simplicity of exposition. Our goal is to analyze the population and reconstruction errors of linear splines ÿs (x), as defined in equation
(ās)
E
((0s(x)
(x. D
E Uniform(( 1),e
[()((z) (x) c|pl
2
E
[1ās(x)) f (x)) lc]
2--1
E
((ás(x) (')) +E
Uniformm (o.1])
2 (R, Cp(s)))
(12)
Therefore, it boils down analyzing Ry We define the risk in the interval [I,, 3241] as the random variable R,, In particular, for i E {0, ...
R4
lās(z) - (x) and Ro(ūs(r))
Σ R
(13)
1=0
The entire range from [0. 1] is divided into n + intervals. We denote their length by lo
Ln In
particular, = T++1 Tg.. Recall the joint distribution of (fo...., ln) in equation 9
We first show that the sum of the risks in the first and the last intervals is vanishing as n - 0o.
Lemma B.1. For any & 0, we have lim Ps Ro
R. S 7] =
All the helper lemmas, including the above, are proved at the end of the proof of the theorem. We now focus on bounding the remaining R, ss Define
R
R
(14)
14

---

Published as a conference paper at ICLR 2024
then are interested in bounding R. For any i E In 1] and x E [0,,
[os()) - (x) = (g) (x))
1/1 (Vit1 - V/l
(x (x- xz) - (x)
(fi+1 xi}
f" (2(++1) + c++1 - f (xx) - (x -x- fx(x)
(zx) +a+
31+1 24
G G| - -xa| { + E141 - Esl (x: -x;)
<1((()) mxxx) +||++
Ii-1 24
G( x;;) + |(tzl + lesl
<G(z 2;) + +|//+
(x xzi
I4+1 2í
SG.4 4 + 1ti| + G. + +|ii| Pi
=2G 8 + |it1| + 2/ez/-
Therefore, for i E [n- - 1]
1i11
R. = lās(z) - (x)) do s (22 4 + |e1+1l + 2/e:1)²
J44
< 3 ((2G) + |4+1|2 + 2P|e/
s 3r (2G) + 3 1 1 + 30 20--12p.1ee 12 Rg
Therefore, if define R := Σー R then it serves upper bound for R. i... R 5 R. Since the l are mildly dependent random variables; we will try to re-express ft as the sum of independent random variables. We now define random variables "g...., E, i..d Exp(1)/(n + 1). More specifi- cally, (fo....,En, En) = (x)) (n) Using these random variables, define random variables similar to Rn Rn-1, but replace & with &
R, 3 (2G)) + +3" -3 +3 3 22 and R
Σ R. 1=1
Then, the following lemma (whose proof we include after the proof of the theorem) establishes the almost convergence between R and R. Therefore, suffices to bound the latter.
Lemma B.2. As n - oc, we have ft - î 0s O.
Still on looking at R, any two consecutive R, and R441 are dependent since it shares 6;+1 in its definition. Due to this, we split A into two sums Russ (and Reven ) containing odd-numbered terms (and even-numbered terms respectively).
Rodd
Σ RA,
Roven
Σ R, and R. == -Rodd + Reven 1e|n-11,922-0
VEIR 11,822=1
Now, Ras is the sum of (n- 1)/2] i.i.d. random variables. Similarly, Reven is the sum of [(n 1)/2 i...d. random variables. Let calculate the expectation of these identically distributed random variables, which are R2 's. For any (n 1). Further simplifying:
3 (2G) 3e-
+ 38-1.2P. 10-1.2--e//P-. lel
Rodd
Σ
(15)
(n + 11p+1
(n+1)
(n + 1)
iE(n 2
By the strong law of large numbers (LLN), can say that - x0
1
Σ
xp+1 as B|Exp(1) T(p 2)
[nn 1
fe[n-1],:%2-1
15

---

Published as a conference paper at ICLR 2024
Therefore, as n oo, for 2 1 the first term of equation 13
(2G) a.s O.
Σ
(16)
(n 1)pt1
iE 1622-1
Similarly, using the strong LLN
Σ
3 G+1
+3 .2'GG/ 12.+a3-1.
-4, 3o-1 E [|ctt1 [X;]] + 3 22
2 BB[|c [x:]:
[(n - 1)/2]
16/m-11,.822-1
3 (p(f")+++++))))))))))))))) 3 22
(f
Therefore, as n + oo, the second and third terms of equation
15 converge almost surely as follows.
Σ 13--1 10-1 Px
3P-1, 2P |esle
a.s. 3 (p( + 3 (g(
2
(n + +
(n 1)
12fn-11,%%2-
(17)
Therefore, combining equation 16 and equation 17 and substituting in equation 15
00
3p-1Lp((")) + 3 ((")
Road
2
Exactly following a similar argument,
a.s. 3 Lp(5)) + 30 -2 (p(())
Reven
2
Therefore,
38- (p()*) 3P-1 3 (F'
Using R- R - 0 by Lemma B.2 as + co, we have R "h, 3p cp(f")+++ 3p-1 (ff")
Finally, using the fact that R < R, obtain the following:
lim n n-000
R S (3a-1 (2" + + +) =1.
(18)
Recall the definition of equation 14 and (ûs) equation 13 Having a probabilistic bound
on R gives us bound on (ās) when using Lemma B. In particular, we get
lim 1
(R)) < (3p-1 (2P + +11 +) +,)+)) 1.
(19)
Finally, combining this with equation 12
lim IP [C(())) S Cpf) =
where Cp 2 10000=13-11(
+ 1].
We now prove Lemmas B.I and B.2 in order.
Proof of Lemma B.I For any x E (1, we have 0s(xx) = y1- Therefore,
[gs(x) f*(x) = 191 fz (x1) + - fx)) s G|æ1 x + leil S Glo + lell.
The implies that
- Ro ( (Glo + 2- Gre + 2 - Similarly, for E [zn: 1]
- Pr.
x +cnl S Gl, + (cal- [ās(>) - ff'(x)l 1ym- - =f(()) - G|a,
Therefore
R, = -f lās(z) ( (2)) dx s (Gl, + P,,)) < Gppptt + +2p 22-21/6 Pln
16

---

Published as a conference paper at ICLR 2024
Combining the two we get
R + Rm] - 28 GP (E(e0 + B((xt)) + (B|a [n] + Bl| (m.)
2 (
=2 ((CT+
+ 2 (5") [[6]] 2
n +
X3
2 2Ff n n+1
SP' E
(X, + + x²)²
2P B[Exp(1)p] E
+ (1)
[(n, 1)2
=n1 _
2P+1GP 1 =n 2 dz + o (1)
= GPG 2. Jo 2²
dz + 0n(1)
[(n)
[(n)
50
2 GPl(n 2)
2p GG
+ On (1)
+ +n((1) = on (1)
[(n)
(n 1) -2) 2)
Therefore, applying Markov's inequality yields that for any > 0,
E|Ro + Ra] < (n))
PiRo
+ R
> 1
8
and the lemma follows.
Proof of Lemma B.2 By equation o we have (lo....,en)
(oo ....., Xx) ) where
Xu...., .......,..... L.d. Exp(1) and X == Ei X4, Also, we have E = n+1
X, for all i.
For every p 21 1 we have
xpt1
Xp+1
70+1 g++1
(n + 1)ptI
Xx+I
x
(1-
(1-
(n (n+ 1)pt1
(n + 1)p+1
Xp+1
Ens n- Xp+1
+ p+1
-
(n 1)
X
and by the strong law of large numbers we have 1. and thus
Σn-1 xpt1 n-1
as
E Exp+1 < oc and (nt1) as,
25, 0. (p411
Moreover, we have
1 Σ Ceee lslcsp)
Xcledp
+
X
Xeleil (1- n +1
n+1
x
n- X,le,|" (-- n
x
n
++1
n 1
and by the strong law of large numbers we have and thus
Σ X a-1
as, E EX,,,, < co and
n+1 as 1,
x
1
Σ
(baG - (Lla/--41c1P as, 0.
17

---

Published as a conference paper at ICLR 2024
Similarly, we also have
- as 0.
Overall, we get
R - R
3 (2G) --0 1/66111 3p-1. .2 lelee
-3- -
30- 1:le4411111 ---3 -33--1 10.1..0 lilesl)
n-1
+ 30-1 n-1 ( - (
n-1 Lsles Bsleal?)
(2G))
Σ
Σ
+ +30-1. 2
> 0.
C OMITTED PROOF FROM SECTION 4.1
Recall the definition of the affine functions 91...., 9n-1 in Section Also, recall the slope values 5p,-..,0 6n and the sign of the discrete curvature curv(x;) any point z;. As mentioned, Boursier & Flammarion (2023) showed Lemma which says that there is a unique minimizer of equation 2 which piecewise linear and has at most one kink in the range [zy, 11+1). Due this, we have only one degree of freedom between any two points; the solution can be completely characterized
by variables s* [s where sf is the slope of the line incoming to point (æ B:). Formally,
s =
lim,- Df(x,- - c).
Boursier & Flammarion (2023) (Lemma 3) proved the following lemma which upper and lower bounds the value of of in terms of 6;-1 and 6,.
Lemma C.1 (Boursier & Flammarion (003)). For any E [nl], sf E (min(6;-116)) 51), max( 0:)] where 5g- = 81 and on, 0,-1-
Having the above lemma at our disposal, we will now show Lemma 4.2 which characterizes the worst-case behavior of formation spikes.
Proof of Lemma 4.2 is easy to see that the function fs cannot have any kink on (-oc, x1). This just follows from Lemma 2.1 Moreover, the slope of this straight line incoming to (z1,21) is given by s1 E [min &n ), max 51 8n by Lemma C. Therefore, fs(x)) in the interval (-o0, 21) must be 91 (z)). Now, again by Lemma 2.1 we can have at most one kink between [x) x2).
Since 9i (x)) is unique line joining the points (z v1) and (I22, y2), having one kink and changing the line at some point x E (12) will not pass through the point (12,, But since fs(22) = y/.
we must have that fs(x) = 91 (x) in the entire (-)0,
Similarly, by Lemma 2.1 the point (In, Mn) is 8x 5n-1 since 8 E [min(5n-1, (n,),, max(5 6n]] and 8,-1 5n by Lemma C.1 Thus, it must be that fs(z) 9n-1(x) in [xn, oo). Moreover, fs( has at most one kink in -n-1, 2,)) This kink cannot belong to (Ix-1, In) since (x-1(x) is the unique line joining the points (In-1, 1n- and (In, yn). Combining, we can say that fs(c)) = 1 in [I oo).
don't have any kink from (0). Moreover, the slope incoming to
We now consider [x,, 2:41) for any i {2. (2...., 2}. We prove the lemma under three different cases.
1. Case 1: curv(z;) curv(x;+1)= =
First of all, since 6;-1 > o, and gi (zx) = 9.( = yis we have g. (x) 2 (x(2) in x (2rs (+))- Similarly, since 8,41 < 8n even ( 2 ge(x) for [ri, 2441)
18

---

Published as a conference paper at ICLR 2024
Using the same argument, since of E [6,, 0-1) and 8/41 E [ōs+1, by Lemma C.1 we say that fs lies above g:(x) in [14) Therefore, only remains to show that fs(x) & min(9i-1(at) (z)1
Let us assume that is not true. Let x² [ay, 2(41) be the intersection point of 9:-1 and (x)) If [s(x) 2 min(gi-1 (I), 9641 (2)) for some a E [xt (441), then it is easy to observe that it must be true at the location of the kink which is x', i.e. fs(x') 2 min (in(g:=1222) 9i 1 (2))).
Now we have two possibilities; the first one is x' < xx, in which case
fs(x') - Vi Ji Ii-1(x') - yi 6;-1,
x' 24
x'' Iz
contradicting Lemma C.I If x x² then
V/-1 fs(x')
Mi+1 - ge+ (x+)
de+1,
Zit1 x²'
Fi+1
again contradicting Lemma C.1 In either case, get contradiction and therefore, must have
(x) < fx() S (0)
2. Case 2: curv(z;) curv = +1
Using similar strategy, one can also show the desired result in this case. More formally, flip the label signs and apply exactly the same argument but on -ss: - 9s. - 9k-1, 99++1 instead. Then using the above argument, we achieve
(x)(x) -fs(x) S - g6+ (x)).
This implies
9:(2) 2 fs(x) max(gi-1(2), 0++1(=)}
3. Case 3: Otherwise, we may have several situations. We consider them one by one. curv(z;; O. Then 8;-1 = 6,. Then by Lemma C.1 we must have that of 6, Also, we have either one or no kink in (241) by Lemma 2.1 Since 9x(2) ) is the unique line joining the points (I,, Mi) and (Ii+1, (144), ), we cannot have any kink and fs = (x).. Similarly, if curv(x:+1) = 0 then 6, = 6:41 and 8/41 5;, which gives us that fs(x) gi(x)) using the uniqueness.
The only remaining possibilities are curv(x;) = +1 but curv(x;41) -1 but curv(x;+1) = +1. W.L.og., we consider the former situation. Then 6,-1 < and 6; > 8.41. Also, by Lemma 2.1 there is at most one kink in (1+)); Therefore, if we show that the kink is at 2; only, it is sufficient. Let us assume that it is not the case, namely, the kink is at x' E (Is, Fe41) If fs("') )²= > 9: (2), then the slope of the line incoming at J;;
1 or curv(z;) =
is(x')
ge(x') Vi dz. x' Zz x' Iz
contradicting Lemma C.1 incoming at #4+1:
On the other hand, if fs(x') gi (r)),, then the slope of the line
Vi-1 is(x')
Di+1 96(x')
8,.
x++1 x
T,+1 x!
contradicting Lemma
Therefore, the lemma is true in all the cases.
As corollary, we get the following lemma.
19

---

Published as a conference paper at ICLR 2024
Lemma C.2. Fix any E f2...., 2}, and consider E [+1)
lfs(2) - (x)) max f19)(2) f for E (0,
lfs(x) (x)) Ian (x))
and E [1
- = 1 f*)x
Proof. The above lemma is clearly true for x E (0,z2), since in that range, fs(x)
= 9l (a: by
Lemma 4.2 Similarly, for x E [mn-1, 1] we have fs(x) = 9n-1 by Lemma 4.2
This implies
that (fs(2) f" (x)) 19n-1 (x) (z))
Also, by applying Lemma 4.2 for any (2, (2...., 2) and for any E [at, 11+1), one can say that unless curv(z;) = curv(#i+1) = -1 or curv(ar)) curv(re+1) +1, we have
fs(x) (xx( [*(x)]
and the lemma holds. If curv(z;) curv(ai+1) = -1 Then by Lemma 4.2 we have g:(2) I (z) $ min( (+11 Let x- E [as, 2(41), where 9i-1(x) and ()+1(z) meet.
For x [æ,, (x))) - fx( S gg-1((1) (x) S gi+((()) (2). Therefore, -xx)- < fs(x) - (x) - -
- (x) S (411())-f((
If (1) is non-negative, then the claim is clearly true. Because even (2) and (3) are positive. (1) is negative then the only way the ffs(2) - (xx) can be greater than (9. fx)) is when
(x) (xx is positive, And thus 9:+1 (x) (x) is also positive. Therefore have
(l) - (z)) fs(x)
(x) f(()- S 1 - (x) & (0:t(()) - f-((x)
which immediately implies the desired result. Similarly, for x E (x", gc(x)) S fs(x) s (++1 S (z)) Therefore,
(x(x) (x) S -s(t)-
- (x) s (z)) ( S gi- (x)
(2)
=33
Again if (1) is non-negative, then the claim is clearly true. If (1) is negative then the only way the
(fs(z) - [x)) can be greater than (x) (x)] is when ())( f*((x) is positive. And thus (x-1 - fx) is also positive. Therefore we have
- -f < fs(x) f*) S (0)1(() f S 10:1((x) - fz))
and the lemma follows. The proof exactly symmetric for when curv(x;) = curv(x;;) = +1; the only difference is that we apply the same argument on -9;, 9i- - and - is and add the function (xr) instead of subtracting.
We now recall Definition 4.3 of special points. Boursier Flammarion (2023) proved that if two special points occur within two points. Then we get spike. Our Lemmal4.4 a mild generalization of the lemma.
Proof of Lemma 4.4 Boursier & Flammarion 2023 Lemma 8) already showed that if 76+11
ng 2 then fs has exactly one kink in (In--1, Tnes)). Consider four consecutive points (Iay Un,-1), (In, Mn.). (Fnu+1: 11)+ ). and (Ii,, +2, Fra +2). The first three are non-collinear curv(xnn+2)
and even the last three are non-colinear since curv(ann) way to interpolate them with 2 linear pieces is to extend Ing -1 and gos+1 until they intersect. This immediately implies that fs(x) min (gm, -1 11.
-I. Therefore, the only
20

---

Published as a conference paper at ICLR 2024
D PROOF OF THEOREM 2
Proof of Theorem Let f be G-Lipschitz. We sample D and number points (æz, y6) from left to right based on the z-coordinate. Again, we denote 2o := O and 2n++1 := 1 for notational convenience (they not used in determining fs). The domain [0, 1] is divided into + 1 intervals of length lo, ,1. where L; = Zi+1 Iz-- We want to analyze the population Lp loss of the min-norm interpolator Is as defined in equation 2 for E [1, 2). Exactly following the step for the derivation of equation 48
we get
cf(fs) S 22" (R, + ()())),
(20)
where (fs)) is defined and simplified as the following.
F++1=1 =1
Rp(ss)= =
[fs(x) (x)) dr
2i+1
lfs(z) - f (x)1 dz) dx
1=0
19 (xr) - 1 do f 2n-1
19n-1(x) - (x))1 dr
2 21+1
Σ
( (4 (z)) (1= (x)) de
max
1=
(by Lemma C.2
1g (x) - (x))p de S" 19n-1(x) (x)) dr
1m-1
n- 2
2i11
+
Σ
19((z) - (x)) min((g(-1(2)) ff ( - (x)1²) de
1=2
21
99 (x) (x))² de /' (-))) de Σ
19:(x) - 8 (z))
1=1
Ro
=
T1 2
min - 19+1 -f))()
R
< Ro R. + Rg) + R.
(21)
The following lemma, which we prove after the theorem, establishes that Ro + R. is vanishing with high probability.
Lemma D.1. For any > 0, we have lim Ps(Ro + R, I 7 =
Moreover, we have already bounded (r) in equation 19 in fact for any y 2 1. When p E 2), reduces to:
lim (ā)) S 174,())) n 200 S
(22)
We now focus bounding R. Intuitively, R is the risk term caused due spike formation. This is only bounded for p E [1,2) 2) and grows as p approaches 2. For é E {2...., n 2}. define:
1111
R =
min - ft (x)). - f((x)" de.
21

---

Published as a conference paper at ICLR 2024
Then R = R2 Moreover, each R; can be simplified as the following. For any i E n 2} and any x E Iaa 2s11/,
91-1(z) 1/4 + (yi yi-1) (x-x:) - --4)-f((0)) (x)
34 - 2
(1i)) Ei l (xi-1) - - (x -r)))) - r(()
(ax)) +G+
Ij 2i-1
GlIz Fi-1) 16 6 1(x 6--1| x;ii
(1f (x()) +|//+
3j - Ii-1
G( - G(
xi-1) + |el + 1(--1)
<G(r - (x:) + +111l +
(x xz)
3j - Ii-1
G G. - lea + |eg_1l el
+
<G-4+ +|e|+
li-1
b
-G 4 + lea + (les) + + Pi-1
(23)
Mi+1 + (y1+2 - y1+1l (x Iz+1) ((())
F442 Ii+l
(*(x+11) + (1(4422 G+2 - (Ii+1) - 641 (x - x-+1)
D1+2 T:+1
G(I142 - 2(+1) leit2 - E041l pr - r141l 8
< - +641l
-
1;-2 lit1
G(0i42 x++11 + |it2| 16--1) |x rrt1l
<G -1+11++ +1G411++
I++2 - fi+1
G. G- Jeit2 + |ei-1| li
SG-4 + le41l +
liti li
-2G b, 10t1 (1041) + ((0t2)) lit1
(24)
Fill
R
min (()) - (x+
- dx
< E142
4
L
p
min
2G e, + +1l + ( + (le|+
2G l, + les + (1e+1l + (6)21)
2
dx
4-1
L++1
(using equation
23 and equation
24
t, max (1-1111111 l
<
2GL, + +|// |c+1/ + (leal + |c-1l + le-11 ((+2l)
Es
<pp-1
ei (2GG))) + +le/ + |e411+ P+ (2/es) + 2/e4+1 |e-11 + (61+2)) max max li+13
( ))ee
gx+1
= -2002 + 4 + 48 104111 P4 + (1c]+ + le--1 l4422))
max foxx(li- l
R
(25)
Then R R= R₂ is upper bound on R. The random variables are mildly dependent. To achieve independence, denote lo, &. ii....,,, & ii.d
Exp(1)/(n 1); in particular, i X./n+1.
22

---

Published as a conference paper at ICLR 2024
We replace &, with é, and define random variables Rg.
2,5t1
R. Go + 1 + |ei+1 |e++11") + 4t (1eal |es+1| + |e--1l (e1+2))*
and
max (4-11 l
n-2 R
Σ
R
1=2
We claim that:
Lemma D.2. As + co, we have R R 82 200
The proof is similar Lemma B.2 Therefore, suffices give bound on R. Still, any four consccutive R is are dependent. Therefore, re-express R into four disjoint sums such that each individual of them is the sum of only i.i.d. random variables. We divide the indices into four sets Zj
for 0 S j S 3. Define Ij (1%4 = j I is (n 2)} for j S 3 and
RV)) =
Σ R4
Then n
Σ NC)
İE
j=0
Then for any 0 5 S 3, further simplifying
7o+1
RG) = Σ 2 2-p-2 G + 48 (1a/ + (((+1)))
+ 4p<1 + 16t1l + 19-1l + 1(+22))
max 1axx 1
IEI
2Bp
40- ((eal" + ((441"))x
(n + 1)p+1 iEL,
(n + 1)
iez
:=7
T2
Xp+1 max Xi-1, X }
Σ 48 ( 1G-1l + 14-1l 16422)
(26)
(n +
IEI
Now, each Ti, T2 and T3 is the average of i.i.d. random variables (up scaling). Thus, as by the strong LLN,
=200==2200000000 Σ 230-2 2 un, 23p-2 - + < oo. IE
Therefore, using the fact lim 00 1] + and since we considering that p 2 we get that the first term of equation 26 converges to 0 almost surely, i.e. as -> 0o
Ti (n 1)p+I
Σ V
2 2 GPX ns O.
(27)
Similarly, since E[X,] and |||+|"] random variables, with finite expectation. Using the strong law of large numbers, as n - oo the second term of equation 26
(f*)
< oo even T2 (up scaling) is the average i...d
1 4.- B[(GeP +1-- P)) 4
4P-1
T2 nn +
40 + (6)11))); 2s,
40
2 Cz(
(28)
Finally, Ta is also the average of i.i.d random variables (up to scaling). Before applying the strong
LLN, we must verify if each summand has a finite expectation. Since E[[c]]] = Lp(f" < cc and
1| = l'(+2) < oc, it easy to observe that it boils down to verifying if IE] max has finite expectation. The following claim verifies this.
Claim D.3. Let A, B lid.
11p(1), then E
<
2
max
BF
(2-p)
23

---

Published as a conference paper at ICLR 2024
Therefore, applying the strong LLN in exactly the same way:
1
X
T3
4' 4' ([e lest1l + 16-1l + (e++2)) max X 1 X }
0.5.
(n + 1)
iET
Xp-11
E
4 (les] + |et1|| + lee-1/ + (4+22)
max (X X(+13
[(p + 2) 48 -8 (Blleil + le + |ei-1 1P- (2)
1
max mmax(X;-11- x }o
2 ( 2)2"
(29)
(2 p2)
where in the last inequality, we use Claim D.3 Using equation 29 equation 27 and equation 28 we get a high probability bound on RG) (recall definition in equation 26 In particular, for S j S 3
lim P R00
4P-1
2 4, 2p l(p + 2)
+1) c,( =1.
2
2-p p
Using the fact that considering p [1, we get
384
lim P
RC) <
2 2 +1) Cp(P*)
=1,
R6) S (ft)
lim
=1.
000
2
Therefore, since R = >3 =3 RD0 we obtain
1548 (f**) Rs
lim 200
= =1
(2 - p)
Using this along with Lemma D.2 and the fact that R < Ri gives
1549 Cf
lim P
R
1.
(2 p)
Further substituting this in the bounds from equation 21 and using Lemma D.I and equation
1567C,(f*)
lim I Ro((s) < (2 - p)
1.
n-000
Finally, using equation 20 with the above
3136Lp(5*)
lim P n-000 S
colfs)
(2 p)
As such, by letting 3136, the theorem follows.
We now prove the lemmas and claims used in the above proof.
24

---

Published as a conference paper at ICLR 2024
Proof of Lemma D.1
For any
[0, 21]. we have
(V2 - yn)
(2) f (x)) = +
(x - -f(
22 #1
(f(0z) + - (2( fff((( -1
(x1) +a+
(x- (xx)
12 I1
G( - 21) + l22 - -1 x x- m1
(11)(1)) -f(( + +
22 21
G[ - x1) + |62l + |6il
<G - ltr + +
x x11
22 I1
G G- + |e2| + 111
SG 6o + 1a|+
-2G 4 + 1 (122) + |cal) Eg L
Therefore,
/
En 7
Ro
(x) (x)) de s to 2G lo + 1el + (1e2) + lcal)
g0l
1+1
< 4--- (2G)²
ttt + -p- E1 P0 + 40 162|
+ 14-11
|eilp
0
Ey
PP
Xpt
Xo (Xo + 1....... +.)
-p-1. (2G)².
+ 12
(Xo + ... + Xn p
X
+ (4p-1 (c2 + 40-1, 1a11))
(30)
XP (X, +... Xn)
We now provide probabilistic upper bounds on Xo. |2z/ and lell, and lower bounds on X1 and Xa Xn, which suffices to further upper bound Ro.
f E dz = 1- n3
P[X. < 3nm] = 1 P|Xo > 33mn]] =1n==1- 11
33mn]==1-
3lnn
Using Markov's inequality,
E Elle1 P2]
Pl < fp(l)) Inn]= =1 1 11n]=ap > (p(st) Inn] 21
(x( ((ff""nn Inn
Inn
Similarly.
P||e2|- R < (p(")) Inn] 2 Inn
e dz f
P
lnn'
where the last inequality follows from the Taylor expansion of e Finally, as n - co, by the strong Law of Large Numbers, Σx ==
X,
a.s.
1. This implies
n
P X
= =1 on (1).
2
1=0
Doing a union bound over these events, and substituting these probabilistic bounds in equation 30 get that with probability (1),
4 (2G)² In 40- (p-''p(( 3lm 2. Cp(T*) 2-4p-1c,(f") Inn (3 (3
Ro
on (1).
(x/2)x+1
(n/2)
(2/1nn) (1/2)
Following the exact same steps, one can say that with probability 1 - o, (1), we have Rr = (1). Therefore, doing the union bound and combining both, we get that with probability o,) we
have Rg + R,, = on (1). This implies, for any 7 > O,
lim RRo + R. S 7 1. 12+00
25

---

Published as a conference paper at ICLR 2024
Proof of Lemma D.2 By equation
we have (Lu....,Ex)
xx... . x)
where
X. Exp(1) and X = x Xx. Also, we have & = n+1 Xa....,2 X
Lid.
for all i.
Therefore,
n1 2
e
(leal + |es+1| lec-//-++++eaaee les+2))
mi LD
n-2
X,
4 (lad + 1644/ + l4--2/ (6--2))
X(+1)
X
n n+1
2=2
X,
n2 n X -11-)
4 (lel + 164411 + |4--1 + 2E
2=2
By the strong law of large numbers, n + co, n+1 ns, 1. Thus, ("x - م:, 0. Also, T X
converges almost surely to a finite quantity as n + oc. To see this, we split T into four disjoint sums, one each over indices in Zj- = {i: i% j} for 0 S S 3. And each of them converges almost surely to a finite quantity by equation 29 and hence also the overall sum T. Therefore, as + 00
7
Σ 4" (eel:///ellleee/eeeeeal11
0. (31)
max 1, 14
Next, we have
n- 2
n-2 2
3p 2 GP
(att--2t
(et) 70t1
23p 2 GP xt+
Xp+I
(n + 1)p+I
2=
2=2
Li=2 X Xp+1
n1 3
( 1) ((=+1)==-))
23
n -- 3
(n + 1 1)p+T
X
and by the strong law of large numbers we have 1, and thus
ンm xp+1
as E Xp+1 < oc and (u*1) (m+1) ns
n-3
Σ
3x
2 GD
10+1 - (00+1-2000 (00t1) as, 0.
(32)
1=2
Moreover,
n- 2
1
4
leip"
( - 1.) = 1-
X
n #+1
i=2
4--1
2
E4
P
PX;
n- ///nnnn (n++1_))
x-x
n
3
R n+ 1
and by the strong law of large numbers we have and thus
ンー Px 3-3
as E |es I X₁ < oc and (++1) nS 1,
n 2
Σ
4
(1 (6,)
2,)
as, 0.
(33)
By similar argument, also have
n-2 2
Σ
(6i
25,
(34)
26

---

Published as a conference paper at ICLR 2024
Combining equation 31
32
33
and
(4
we get
n-2
n-2
R R =
30 Gr (ettz - pgt1)
Σ 48
(4
(4-
+
Σ
4
let11l (e-
1=2
2=2
1=
n-2
40 40 (leil + lest1 1 |ti-1| (e142))
aut
max
(1-1, 11+110
max
L1t230
Proof of Claim D.3 We first show that max show that the CDF of max A, B} is the same the CDF of A Let maxx(A,B) (A.B) and FA+ (.) be their CDFs respectively. Then for any 0.
(A, B} A+ + B Both A, ~ Exp(1). We will
Li.d
2.
B
2(2 x)) de [ c (1---2(2-r)) dr
F 2 (2)
(2) PP
A + 2
=
"
2
00
30
C dx - e
22
c" dr = =1 - c 23 (e - -1) = 2 + -2
(1 (1- = P(A s B
(mxx ( A, B) 2)
(f)
Using this, we can further simplify the expectation as follows.
1
2"
1
E
E
S E
2" E
[ax B\P
(A
+ 2
(A+
B)P
r(2, 1)P
2D
dz
0
2"
Pe = dz
2 (2 - p)
2
2 2-p'
where the last inequality follows from Claim D.4 and the fact that S 2.
Claim D.4. For z E (0, 1], we have + - T(z) 5
Proof. For >>>> 0.
I(2) w w--1e-w dw w
00
w
dw =0+ 1 (o
c dw
00
J0
2
2
r(1 +)
(35)
2
Now for 0 < x 5 1, we have 1 < 1+ < 2. Therefore,
1 S [(1 + 11
2
The upper bound follows from the fact that T(-) is unimodal (with first decreasing and then increas- ing). Therefore, the maximum value of T()) in [1,2] is (ox) 1. The lower bound
follows from Deming & Colcord (1935); the minimum value is approximately 0.8856032, which is
least 1/2. Putting this back equation 35 for x <
< T(2) <
2z
27

---

Published as a conference paper at ICLR 2024
E LOWER BOUNDS
Our lower bounds (Theorem and follow from very similar situations under which spikes are formed. Therefore, we first present basic construction of such situation; later, we specialize to the case of p E 21 and 2 2 and obtain both theorems respectively.
Recall the noise model ~ NN 1). We first claim the following.
Lemma E.1. For any function f. we have Cp(f) 2 Rf(
The above lemma then allows solely focus lower bounding the reconstruction loss of the predictor.
Proof of Lemma E.1
By definition,
Cp(f)
E llf(z)
E (x) - c|a].
(a.x)~
Let q R- R. be the density of the folded standard Gaussian, i.e. [W 1)}. Then due the symmetry of the Gaussian,
Cf(
E
E (0,1)
-
E
2 f1(()) 5PP 31 -() ff()) 6PP) 5PP q()) d5
1
E
[f(z) - (x))
(by Claim E.2 below)
Uniiforomm [0.1])
E
[[((z) - (z) (f)
(by definition)
Z~Uniffem
Here the second last step follows from the following claim, which we prove below.
Claim E.2. For any p R, p 2 1, and 5 RR, we have { + 8|p
|1 51P) 2 |n|2.
Proof. The claim trivially holds for μ = 0. Now consider > 0, then if 2 then
((u + 8)p 1p 8lm) 2 2 (2 2 28 1p np.
But if < then since the function
|.12 is convex for 2 1 we have
1 6)
2 (p 60)= 3}>> 11 1 5 )= uP,
2 (Iu 8|p H 8lP) マ (" 6)p
Finally, if f < 0, then apply the same argument to 1 giving the desired result.
This concludes the proof of the lemma.
We now describe the situations under which spikes are formed. We will consider (*)(x) and the noise model (0, 1). Let S ~ D" be the data points. Again, we number them such that
To =: 21 <
In < 1 == En+1.
We have + 1 intervals with lengths lo. ..., ln from left to right. In particular, Zi+1 Fz.
We now consider N := |n/10] disjoint subsets Si...., SN C S such that S, n SSS; = 0 for i + j. Each S, is set of six consecutive points (ordered from left to right). For any i [N].
S (0,, vy) ; 10 1)
10( 1) 6).
It is clear by definition that these sets are disjoint.
28

---

Published as a conference paper at ICLR 2024
f fx())
111
61,6
1,
41
X1,2
X1,5
xi,1
X1,3
X;,6
X
612
61,5
S
Ci,
2
liA
Figure 6: An illustration of configuration of points the i-th subset St when the event A, happens.
We denote the noise random variables associated with j-th point of S by ei.- Also. re-denote the distance between any two consecutive points from the same subset by 4, i.c 4 is the distance between (j + 1)-th point and j-th point in S,. Consider the events , as below.
A (4,2 9,5 S -1 n fG,1, Ga3, G,6 [1,2]) n (4,s 2 4,22 n (4,3 2 (.,)
See Figure for an illustration. This considers the event that the bad configuration of points happens for points in S. Then we express (fs))) the risk of the predictor in [0, 1], in terms of the random variables & 8 when such bad configurations occur. Formally,
Lemma E.3.
For S 2:
#0+1 4,3
Ro((s) 2 Σ
1 [Ac]:
(Ls, + 1
For p 2 2:
Ro(fs) 2 Σ
1 [A4.
LL2 + l,
Proof. Without loss of generality, assume that A, holds and consider the following analysis under Ai. (One can choose any E [N] and the discussion follows in the same way). If A happens then curv(r2) +1, curv(xaa) curv(2:4)
+1. Therefore, 2y and are special points according to Definition 4.3; the curvature changes within the distance of 2 points. Therefore, by Lemma 4.4 there exactly one kink possible in (I22, æs). More importantly, in the interval (æz, 24), the function fs(x) = (z), Therefore, for any [z3, ma).
and again zy we will have curv(x;)
1/3 1/2
C3 C2 (a
32(x) = 1/3 +
(a x3) = +
x3))
2 1
(x x3).
83 T2
F3 D2
Eg
Similarly,
(a(x)= 1/4 + y5 y4
(x v3) ca
64
(x n.a
C4
(xa
x)
1+
(xs x)). eg
2
23 FA
23 F2
29

---

Published as a conference paper at ICLR 2024
Therefore, if A1 happened then writing the Lp reconstruction error in the interval [ay, xa]:
24
(x) = (s(
min (02(())9x(()) dx
2
2
min 1 + x 13), 1 +
(I4 - x}} dx
l2
1+ (x gz) dx +
(1+
- (x) - 2) dæ,
l2
x'
where x=' [13 is the x-coordinate of the point of intersection of the two lines. Thus, to find x
2
2
1
(x
1 +
(x4
x²
lg
1
1
(x*
F3)
(es
(x"
xss))
l2
ls
1
+
(x* 23)) lA
82
84
(x" x3)) = lg
l22s
E26s
8/ 84
82 + ls
844g
(x1
x²
ls
1/ LA
When 1 Sp < 2: Writing the reconstruction risk in [x3, v.] and substituting the above:
24
2
m3)) P
["d (1 I
2 (x1 - -a) p
fs(x) (z)
1+ (x
dx +
dx
2
pB
P
2
(x 233)
dr +
(xa - xx)
dr
l2
la
2n
1) 62p (x" - -13)p41 +
xx" 3
(p
(p + 1) la
b
4
(B2 + fa)otI + (12 (4)
(p 1)
2F
(p 1)
(l2 (22+la) l4)
g++1
2 (62 + 4,)P
(36)
where the last inequality follows from the fact that considering p E (1,2).
30

---

Published as a conference paper at ICLR 2024
When p 22 2
2
p
f
1
(xr m3)
dr
1 (x4 - σ)
dr
E2
4
2
2
1+
(xc
2z)
dx
1 1+
(x's x))
dr
L2
43
(hoth integrands are at least in the range)
2
na
2
xx 133)
dx
+
(x4 xx)
dx
l2
E1
x
4
4
(x
4a)
3
(T4 xt)s
36
34
=
3
(62 44)3
+
3
(l2 + ka)3
4
3 (42 4
(37)
(E2 44)
By the definition of risk, one can say that
Rs(fs) N
Σ NE
ffs())ff(()) dr
Then by doing the above analysis as in equation 36 and equation 37 for each i E N, along with the observation that the risk in any #4,1] is non-negative, we obtain the desired result. In particular, for 1 < p 2:
N
g0+1
Rf( 2
(li,2 l 1A,]:
And, for p 2
Rf(ss) 2
1 1[Ar).
(61 2
Lemma E.4. The events {A are independent. Moreover, P(A:) = co for some universal constant cg.
Proof. The events AI...., An are independent since the noises are i.i.d. Also, the event about the interval lengths (that are dependent random variables) the above {4,3 2 4,2) n (&r, 2 f,4) can be expressed in terms of the underlying exponential random variables (which are independent) as {X,,3 2 X n (X,,3 2 X.,). Finally, it is easy to observe that for any i E [N]. P (A,) is some universal constant co-
E.1 PROOF OF THEOREM 3
We have f* = 0 and the noise distribution is (O, Therefore, (p( is just constant (dependent on p). More precisely.
Proof of Theorem 3
Lp(S") Elle!"] σº 20/2
p +
2
r
(38)
V
2
V
where in the last incquality we use = 1 and 1 5 5 < 2. Also, for 1 S p < 2, by Lemma E.3
g+1
R₂ Rfs(s) 2
Σ
(Le, + b 1[A
= R
(39)
31

---

Published as a conference paper at ICLR 2024
Then, to create independence, we define (lo....,&r, Lid. Esp(1)/(n11) where 4, replace 4ss with Es's to define Ry.
X, We now
N
= Rp
1|4
(2,,2 + (
i=1
Lemma E.5. As n - oc we have R R - 0.
Moreover, expressing Rp in terms of X;'s
N
X
N
N
X (X12 + Xi,))
Rg - (n+
[[A]]
[A.]]
(40)
(X + X,a))
(n (++1) 1)
N 1=1
Therefore, Rp is the average of N i...d. random variables (up to scaling). Each random variables have the expectation
XP+1 1.3
X
E
[A.)]
< E
(X,,2 + 2
(Xi,2 + x
(Xi, + X2,4)²
(1Exp(1))++11
(sum of two i.id Exp(1)s is [(2, 1))
I(2, 1)
ztt - dz
dz
((2)
gP c dz
-1-Pc - de
[(p + 2) p) 00,
(41)
for 1 S < 2. Thus, by the strong law of large numbers, as (also N [L1/1]] + oo)
N
x
1[A.]
AS E
1.3
[Ad
N
(X12 + x,
(X1.2 + X
X
Xp+
= P E
14
P(A))
X2,2 S X,,,, S X1,3
(Xi,2 + Xi
(Xi,2 + X2.)p
(by definition of A,)
X
2 P
(since the function is non-increasing in terms X and Xz,4)
(X,,2 + X
c. E[Exp(L))Ptt) p+1
Co (n-r(2+p))) r(2 p) 2 2cp r(2 p)
[22 1)P
(since - p < 2)
(by Claim D.4p
(2 (2-p) p)
Moreover, lim x+1 1om tion 40 we obtain that for constant
[r/1|] n-1
Therefore, recalling the definition of R2 in equa-
10
lim P
R
2
co
7 1.
2-000
10(2 p)
Therefore, using Lemma E.5
lim P
R 2
Co
n S
20(2 p)
Recalling equation 39 that R is lower-bound on the risk, we obtain
lim (f{(s) 2 20(2 p)
Co
= 1.
n-000
S
32

---

Published as a conference paper at ICLR 2024
By equation 38 Cp(f")
7/v Choosing covF/a0 get the desired theorem, i.e.
lim P Rp((s) 2 (2-p)
Cp( =1.
Finally, using Lemma E.1 we obtain
c lim (p((s) 2 (2-p)
co(M)) =I
i N and j (1,2,3,4,5, 6), where Xi.j Exp(1) and X is the sum of (n 1) i.d Exp(1) random variables. Therefore, by definition of Rp and Rp
Proof of Lemma E.S
Recall equation that lújj Xx./x for S
g0+1
p (2,2 + 3
Rp Rs
2,3
1(Ai))
Σ
1,3
(b,2 + lg
(X.a/x)D
/u./nn) 1
(Xua/X + Xx. o/// [[A
(Xuz/n41 + Xea/n+1) 1 [(A,]
X (X,,2 X
n n+ -1
(42)
X
We already know that by equation More formally, by the strong LLN
41 T converges to finite quantity almost surely as co.
T
N 1 Σ N
X
Xz, [[A.]
a.s. 1 EE
X ) [(A.]]
1.3
< <0,
(X1,2
10
(X
where the last inequality follows from equation 41 random variables, by the strong law of large numbers, as n co, we have n+1 2s, Therefore, x
Since X is the sum of (n + 1) i..dd Exp(1)
m+1 2... 0. Combining this in equation 42 we obtain that fł, R2 -> 0.
X
E.2 PROOF OF THEOREM 4
Proof of Theorem 4
We have the same f" 0 and the noise distribution is A/ 1). By Lemma
for p 2
G
Rp(fs)
(L1,2 + l,,1) 1[A,).
i=1
Recall equation 9 that byg Xta/x, where X1,1 ~ Exp(1) and the sum of (n+ 1) i.i.d Exp(1) random variables, one of which is X.j. Thus,
(xra/x)3 (Xuz/x + Xia/x)² [[A,]
X
Ro((s)
1.3
1 1Ag
Rt.
(43)
X
X2,2 + X1,)²²
i [N], define
1
N
R = (X + X
Then R
Σ
R
(44)
X
i=1
33

---

Published as a conference paper at ICLR 2024
Each R₃ has infinite expectation, show in the following calculation.
X [A4]
X
[[ =E
-P(A))
A
(Xi,2 + x2
(X,,2 + xi,a)a
X 1.3
cu E
X1,2 S X1,3, Xx, S X1,3
(by Lemma E.4 and recall A,)
(Xi,2 + X2,a²
X 1.3
2 Co E
(Xi,2 + X;,)²
(the function inside expectation is non-increasing in terms of Xt,2, Xi,4)
cu E[
[(2, 1)3
/-00 c dz
600
22 ze=
dz 600
Therefore, define the truncated random variables (a) which the truncation of R2 any finite threshold a. Formally,
Ta))) == min min(f,, a).
Then (a) has finite expectation by its definition, which we denote by (a) h(a) for some non-decreasing function h(a). Also, it must be that lim h(a) because the expectation of (a) goes infinity does. We now define
N
f(a) == X
Σ T((a),
then T(a) for any fixed a, by its definition serves lower bound R (recall equation 44 We
rewriting T()) follows
((a) + 1 N
1
T())).
(45)
X
N
i=1
Then as n - oc, since X is the sum n + i.i.d. Exp(1), by the strong law of large numbers
n + 1 a>, E[Exp(1)] =
(46)
X
Similarly, by the strong LLN
N
Ti(a) as. E[T.(a)) = h(a).
(47)
N
=1
And, finally using lim T obtain
along with equation 47 and equation 46 in equation 45 we
To
T(a) h((a)
10
Therefore, for any b > 0 choose a" such that h(a") ) 2 216, then as + 0c, F(a)) - Maa))11
2.16 (note that it always possible choose such since lim h(a) oc). This implies
lim PTf((a) 2 25] 1.
Thus, using the fact that T(a*) is a lower bound on
lim P 2 26} 1. 12+00
Finally, recalling equation 43 that R is lower bound Ry (fs) we obtain the desired theorem.
lim P(R,((s) bj 1. n
Note that Lemma immediately also implies
lim P (fs)s > bj 1. 200 S
34

---

Published as a conference paper at ICLR 2024
F PROOF OF THEOREM 5
Proof of Thheormm 5 Let f be G-Lipschitz. First, we observe that the distance between two con- secutive x,'s is is 1/n. The domain [0, 1] divided into n intervals of length 1/n. We again denote To 0 for notational convenience. Our goal is to analyze the population Lp loss of min-norm interpolating solution fx( defined in equation 2
Cplfs)
E (r.
[fs((T)) w/r]
[[s((t) [ f (x) + cd]
E
u~-Unifomm (0,1)),c
20-1
E z~Uniform [0.11),
[If((E) -f'(")" +(
20-1
E
[fs((t) - (x)) +Bldd"))
U-mniomm (0.1])
2 (R + (p("))
(48)
Therefore, suffices to bound (fs).. It can expressed as the following.
n-1
Rf(ss) Σ
1f(x)-
- f())) dr
(49)
For [0, 22). fs(z)= 91 (I) by Lemma 4.2
Thus we have
[ss(z) - f (x) -1g1 (x) - (x))
91 + (y2 - 41)
(x - -xx))-
(x)) - +1 (x222) 62 - f* (x11 -6
(x-xx) - (x)
S <z)) - (x(x)) + +lo1+ + Glæz - 21 + E2 E1
x x
I2
G( 12) + |c2
|6
<G lta seal
1 xz
x2 - I1
G m
+ 102| 161
<G +leil +
1
2G + le2l + 2/el/
Using this we get,
/ [fs(z) (z)) dr < 2 22
22
2G
P
Ro + R1 <
+ 122l + 2/ea +2/
0
< 3D (( 2G P
((2G)
2
+ | + 20 p
(50)
n
Using exactly the same steps, can also bound the risk in the last interval [zn-1,
Rn-1 < 1 ===1
[2G ((2G)
1
ffs(z))f(())) de <0
+ |en-11= 2p
22|en pp)
(51)
In-1
7
n
Fix any i E 12,..., n 2}. and consider r E [11) By Lemma C.2 we get:
(fx) (x)) < max (1)((0) (in))) 1" (x)
35

---

Published as a conference paper at ICLR 2024
We can simplify each one by one.
(xx (x)) = y/4 (Ui+1 --i (z-);)- (x)
I++1 Dt
(x,) ta (1(4+1) + c1+ - (x;))) - Gi (x - xx.) (x)
I(+1 - 3/
G/n + lest1l + |cil
1 (x,) (x)) + +e/l +
1(x x1-1)
1/n
G +lal+ + GG/n ( lo411 +
+ (())
1
n
1/n
2G
+ 2/c/ + lettal-
Similarly,
(yi 11-
(x)) = 3/ +
(x - -x;)== - (x)
Tj -j-1
1r (x:) + +4 - 1' (xii-) 1) - 6i-1 (x 1 xz)) - f (x)
f (xx) + 1s +
84 2;-1
G/n++ + leil
+ |éi-1]]
- (1)) - f (xx) + |6/ +|/|+ +
1(x x;)l
1/n
+ 161 + G/n + led + |ei-nl +
1
1/n
n
2G
+ +2c + |G-1l-
n
Using a similar strategy, we also bound:
( = Uit1 + (Ji+2 Vi+1) (x -1+1))f"(m1
Zit2
Ii+1
(+s+11) + +.i41 (*(1142) + (x1+11 - Eitl -Ett
(x-1++1) - (x))
Rit2 Ii+1
G/n++ + 161+2l + lectal) 1(x - -x++1)
1 - ((0) +
-
1/n
G
G/n + lesu2l + lestal 1
< - + lecHll +
n
1/n
n
2G
+ 2lect1| + |est2l-
n
Therefore, combining the above three, for x in the intermediate intervals:
2G
2G
2G
- ((xr)l S max
2/e/| + [e041],
n + 2/eal +
+ez--l n + 2/e4t1/ + lestal
n
2G
2|ea| 2/e + |6042| + les-1-
n
Therefore, for any E f2..... n 2}. and x E [xy, 11-1
f=)) < 5 ((
2G
+ 2/cc + 2P|cii +
P lamal + k(
n
Therefore,
11
ff()- de 55 ((20)
(2G)
+ 12 1 2211 2 +|esl + +le-11)) 1
R
n
36

---

Published as a conference paper at ICLR 2024
We now over all i E (0, ...
1} and use equation 50 and equation 51
n-2
2G
Rolfs)=
Σ R
Σ
5P
c//// +
2 6+11 + 10+2| ? + 14-111
2=
m
n
((m))
[2G
( 2G
_ 33
2
n ((²))
1
+ 3
+ |e2/" + +2
+ -1- + 22 en 12
7
(5
3
3r) (2G)
2 22 +2
69 P + 3
En 6%
n2
n
(10% + 10 5/1642| + 11
122
(5 + 3 (2G)
2- 2-110 + 5P)
le P
(52)
np
n
The first term converges surely as n + 30. The second term proportional the average of i.dd. random variables |e,/", each having B||e||]| (f(f"). Therefore, by the strong LLN
c Lx(f))
1=1
Combining this with equation 52
lim
Rp((s) 1 (2 10" +2-5" +2-5"++1 +1) (zf") =1
Finally, substituting the bound from equation 48 in the above:
[f((s)) < (20 10P + 2P) Cp(s))] =1.
lim 2-+20
Letting Cp 20" + 10" + 2", we get the desired theorem.
37


Reviews:
[{"review_id": "JLZyg1HFBU", "reviewer": "Reviewer_bbgZ", "summary": "This paper tries to understand the generalization performance of overparametrized neural networks when interpolating noisy training data. Specifically, the authors consider the univariate 2-layer ReLU networks in regression setting and focus on the min $\\ell_2$ norm interpolator. This paper shows that the generalization performance is subtle and depends on the factors such as the choice of loss at evaluation time and whether one is considering high probability case or taking expectation over the training samples. The overfitting is tempered (test loss neither goes to Bayes optimal nor to infinity) when loss is $L_p$ for $1<p<2$ and considering the high probability outcomes. The overfitting is catastrophic (test loss goes to infinity) when loss is $L_2$ or considering expectations.", "questions": "-\tThe results in this paper seem to consider the asymptotic regime that sample size $n$ goes to infinity. I was wondering if there is a rate for this asymptotic convergence.\n-\tI was wondering if the min-norm interpolation considered in the paper can be naturally reached based on the implicit bias of some simple algorithms. For example, the authors mentioned that Shevchenko et al. showed similar spikes as the current paper. Does their algorithm exactly lead to the same implicit bias here?\n-\tI wonder if results like Theorem 1 and Theorem 5 are enough to say they are tempered overfitting, as they are only upper bound on the test loss. I feel there needs to also have a lower bound on the test loss?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tUnderstanding the generalization performance of interpolating solutions, especially non-linear interpolators such as ReLU networks, is an important and interesting question in deep learning theory.\n-\tThe paper gives a detailed characterization of the min $\\ell_2$ norm interpolating ReLU networks, compares it with the linear splines, and shows the subtle generalization performance depending on the loss function. I believe this is a good result and it seems to be novel in the literature of implicit bias and benign overfitting.\n-\tThe paper is overall well-written and easy-to-follow.", "weaknesses": "-\tThe paper focuses on the univariate ReLU networks which is relatively simple. (though it is understandable from technical point of view)\n-\tThe results are in the asymptotic regime that sample size $n$ goes to infinity. Thus, it does not give explicit rate of convergence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UszVpeIUWs", "reviewer": "Reviewer_9Vzu", "summary": "This paper delves into the nuanced behaviors of tempered overfitting and catastrophic overfitting within regression scenarios employing a min-norm two-layer ReLU network with skip connections. The key contribution lies in the establishment of significant results, notably demonstrating the occurrence of catastrophic overfitting when the $L_p$ loss is applied with $p\\geq2$. Furthermore, the paper uncovers the phenomenon of tempered overfitting, which surfaces when utilizing the $L_p$ loss with $1\\leq p<2$.\n\nIn a noteworthy extension of its findings, the paper also establishes that when working with samples distributed on a grid, tempered overfitting manifests for the $L_p$ loss with $p\\geq1$. These results shed valuable light on the interplay between loss functions, network architecture, and data distribution in the context of regression with min-norm ReLU networks.", "questions": "1. I have observed that in both your Theorem 1 and Theorem 2, you made the assumption that $f^*$ is a Lipschitz function. Assuming the Lipschitz constant is denoted as $c$, I am interested in understanding how the constants $C_p$ in Theorem 1 and the constant $C$ in Theorem 2 are related to this Lipschitz constant $c$.\n\n2. What would be the impact on the analysis if we were to assume that $f^*$ is Holder continuous instead of Lipschitz continuous in your main theorem? Could this alternative assumption be beneficial, given that you are dealing with $L_p$ loss in this context?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper is exceptionally well-crafted, boasting a highly organized structure that enhances its clarity and readability. The main paper is thoughtfully structured, and the presentation of the proof concept is remarkably accessible, thanks in part to the informative graphs provided.\n\nThe theoretical framework is excellent, as this paper conducts a comprehensive examination of the overfitting tendencies observed in min-norm ReLU networks within the context of regression. In doing so, it effectively bridges a critical gap, especially when contrasted with the closely related work by Kornowski et al. (2023), which primarily addressed overfitting within a classification setting.", "weaknesses": "It appears that this paper can be regarded as a subsequent work to Boursier & Flammarion (2023). The connection is evident as the pivotal lemma (Lemma 2.1) employed in this paper is directly drawn from Boursier & Flammarion (2023). Furthermore, the neural network model studied in this paper aligns with the one extensively examined in Boursier & Flammarion (2023). Consequently, the technical innovation in this paper seems somewhat limited in this regard.\n\nIt's important to note that this paper adopts a one-dimensional perspective, assuming $x$ to be a single dimension, confined within the range $x\\sim[0,1]$. In contrast, Kornowski et al. (2023) considered high-dimensional $x$. Another differentiating factor is that this paper primarily focuses on characterizing the asymptotic behavior of population error and reconstruction error, while Kornowski et al. (2023) delved into an analysis that extends beyond the asymptotic realm.\n\nIn Theorem 4, which addresses catastrophic overfitting for $L_p$ with $p\\geq 2$, it is essential to note that only a specific case with $f^*=0$ is considered. To enhance the depth and relevance of the analysis, it would be particularly intriguing to explore this phenomenon with a more general $f^*$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ntbYqJUfqV", "reviewer": "Reviewer_toQ6", "summary": "This paper studies the min-$\\ell_2$ norm interpolation learning of two-layer ReLU neural networks under the univariate data. The results start from linear splines, demonstrating that linear-spline interpolator exhibits tempered behavior. Then the min-norm interpolator is studied based on the relationship with the linear-spline. Then the results show that, tempered overfitting occurs in the Lp space with $1 \\leq p <2$ but catastrophic overfitting occurs for $p > 2$.", "questions": "- Could you please intuitively explain why catastrophic overfitting occurs for $p>2$ under the min-norm solution while linear spline does not?\n\n- Can Linear splines obtain better performance than the min-norm solution?\n- What is the result under the min-$l1$ norm solution? Intuitively, there is no significant difference for univariate data but I expect that some results from previous min-l1 norm literature can be discussed under the univariate setting.\n- What’s the meaning of “mildly dependent random variables” of $\\ell_i$?\n- How does $(n+1)/X -> 1$ hold with almost surely?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The generalization performance of linear splines and min-norm solution is studied in terms of tempered overfitting and catastrophic overfitting", "weaknesses": "There is no distinct drawback in my view. The proof is based on the nice statistical property of $\\ell_i$, which might be the key technical difficulty when extending to the $d$-dimensional data. For example, the two-dimensional data, we sort the data, split the space, define the risk in the two-dimensional interval. But the estimation based on $\\ell_i$ is unclear to me.\n\nBesides, comparison with (Kornowski et al. 2023) requires more discussion, especially in terms of the technical tools.\n\nApart from this, some references on the following topics in the related work are missing:\n-\tNeural networks, the representer theorem, splines, Banach spaces\n-\tBenign overfitting papers", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)