Noisy Interpolation Learning with Shallow Univariate ReLU Networks

We thank the reviewer for the positive feedback on the work! We will add a more detailed comparison with Kornowski et. al. [1] and a discussion on the topics raised by the reviewer. We address their primary questions in order:

• Intuition regarding catastrophic vs tempered overfitting for $p>2$: It’s best to see this through Figure 2. The value of the linear splines stays between the value of the observed labels, and so in a sense are not too “crazy” and their distance from the target is similar to the magnitude of the noise, hence the $L_p$ error (for any $p$) is proportional to that of $p$-th moment of the noise (the Bayes $L_p$ error), which corresponds to “tempered” overfitting (tempered here means excess error proportional to the Bayes error, or noise level). More technically, consider $f^* \equiv 0$ for simplicity. The fitted function in any interval $[x_i,x_{i+1}]$ linearly interpolates between $y_i$ and $y_{i+1}$ and does not exceed the label values. Moreover, these labels are just noise random variables $\varepsilon_i$ and $\varepsilon_{i+1}$ when $f^* \equiv 0$, thus, for linear splines the $L_p$ risk will be proportional to the $p$-th moment of noise random variables, which is the Bayes $L_p$ risk.

  However, as illustrated in Figure 2, min norm neural nets prefer solutions with fewer “kinks”, which leads to spikes that go well beyond the observed values. With more points, there will be some extreme spikes, but these extreme spikes will also be narrow. For higher $p$, the contribution of extreme spikes to the $L_p$ error is more significant (scaling as height$^p$), and $p=2$ is the tip-off point where the thin and extreme spikes dominate the error. At a technical level, the height of the spike in the interval $[x_i,x_{i+1}]$ of length $\ell_i$ depends on the relative ratio of $\ell_i$ and its neighboring intervals $\ell_{i-1}$ and $\ell_{i+1}$. Thus, if $\ell_{i-1}$ and $\ell_{i+1}$ are "very small” as compared to $\ell_{i}$ then the effect of spikes would be large. The precise dependence on $\ell_i$ s and $p$ in the risk comes up in eq 25, which is analyzed using the distributional properties of $\ell_i$ s. Note that when the input is on the grid and the points are equally spaced, the relative ratio of $\ell_{i}$ with $\ell_{i-1}$ and $\ell_{i+1}$ remains constant. Thus, the asymptotic risk is worsened but only by a constant factor from linear splines, and we get tempered overfitting for $L_p$ losses for any $p \geq 1$.

• Linear splines vs min-norm networks: The paper indeed establishes that if we insist on overfitting, then min-norm networks are more problematic than linear splines, and we are better off with linear splines. But even better would be to not overfit in the first place and balance norm with training error, in which case low-norm networks would be better (e.g. for Lipschitz functions + noise, balancing network norm with training error would converge to the Bayes optimal predictor, whereas linear splines would be “tempered” with population error larger than Bayes optimal). Disclaimer: the purpose of this paper is NOT to advocate for overfitting, but rather to study its effect, in line with recent interest in the topic.

• We are not aware of work looking at min-$\ell_1$-norm neural nets, and are not sure how they would behave, but this could be interesting to look at.

• “Mildly dependent”: It is an informal term used to give intuition, not in a formal context. It roughly means that although the random variables are not, strictly speaking, independent, the effect of the dependencies is small, and vanishes as $n→\infty$. This is again an informal statement—-in our analysis, this dependence is taken care of precisely.

• Note that $X$ is the sum of $(n+1)$ i.i.d. $\textnormal{Exponential}(1)$. Thus, by the strong law of large numbers, as $n→ \infty$, $X/(n+1) \rightarrow \mathbb{E}[\textnormal{Exponential}(1)]=1$ almost surely. By the laws of limits and the definition of almost surely convergence, this implies that $(n+1)/X \rightarrow 1$ almost surely.

[1] Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in relu neural networks. arXiv preprint arXiv:2305.15141, 2023.

We thank the reviewer for their thorough review and positive feedback on the work!

We want to first address some of the points mentioned as weaknesses, where we see things differently:

• Novelty relative to Boursier and Flammarion [1]: Indeed, we study the same model as in Boursier and Flammarion [1]. This is also the same model studied in several other papers (e.g. Severese et. al. [2], Ergen and Pilanci [4], Hanin [5], and many more). The main novelty is in the question we ask, which is completely different: none of the previous papers, including Boursier and Flammarion [1], asked how such a model overfits, i.e. how it behaves when interpolating noisy data. In particular, our main results do not appear in any way in previous papers. To answer this novel question we indeed build on a characterization given by Boursier and Flammarion [1], but this is just a component of our analysis.

• Limiting to one dimension: This is indeed a limitation, which is shared also by many other papers studying low-norm ReLU networks (e.g. Boursier and Flammarion [1], Hanin [5], Severevse et. al. [2], Debarre et. al. [3] and others mentioned above) and in-fact also the Kornowski et. al. [6] paper mentioned. Kornowski et. al.’s treatment of higher dimensions is limited to simulations or the extreme case $d \gg n^2$ (in which case learning is essentially linear and the overfitting is benign—see paragraph 2 on page 1 and also the footnote)--they also do not have theoretical analysis for fixed dimensions beyond $d=1$. Going beyond one dimension is very interesting, and we believe it is possible, but has proven to be difficult not only for us but also for the entire community.

• Considering $f^* \equiv 0$ for catastrophic overfitting: As this is a lower bound, we find it strongest to show that overfitting is catastrophic even in the easiest case, i.e. $f^* \equiv 0$. Our result should be interpreted as: "Even for such a simple target function $f^* \equiv 0$, in the presence of noise, the interpolating predictor exhibits catastrophic behavior." Overfitting will also be catastrophic with any Lipschitz target and non-zero noise.

Below we answer their questions.

• Our constant $C_p$ (in Theorem 1) only depends on $p$ and $C$ (in Theorem 2) is a universal constant (the dependence on $p$ is explicit). These constants do not have any dependence on the Lipschitz constant. Our result should be interpreted as “as long as the Lipschitz constant is finite, the asymptotic $L_p$ risk is proportional to the Bayes $L_p$ risk, where the constant of proportionality only depends on $p$.” Note that the dependence in the Lipschitz constant will show up in the non-asymptotic rates, but at least for the asymptotic results as we show here, the terms associated with the Lipschitz constant vanish as $n→ \infty$, and we get no dependence.

• We believe our upper bounds of tempered overfitting continue to hold for any $(G,\alpha)$ Holder continuous functions with $0<\alpha \leq 1$. The same phenomenon of transition from tempered to catastrophic at $p=2$ would occur. The primary reason we consider Lipschitz continuity is because the Lipschitz functions can be exactly represented by ReLU nets with bounded weights (see Boursier and Flammarion [1], Theorem 1). If the function is not Lipschitz, then its representation cost (minimum norm to represent the function exactly) is infinite. However, we agree that even if one cannot represent the function exactly, it is possible to talk about approximation, and it seems like the same analysis generalizes to even Holder continuous functions. The only difference is that now the terms with dependence on $G$ vanish but at a slower rate.

[1] Etienne Boursier and Nicolas Flammarion. Penalizing the biases in norm regularisation enforces sparsity. arXiv preprint arXiv:2303.01353, 2023.

[2] 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.

[3] Thomas Debarre, Quentin Denoyelle, Michael Unser, and Julien Fageot. Sparsest piecewise-linear regression of one-dimensional data. Journal of Computational and Applied Mathematics, 406:114044, 2022.

[4] Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterized neural networks. Journal of Machine Learning Research, 2021.

[5] 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.12960, 2021.

[6] Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in relu neural networks. arXiv preprint arXiv:2305.15141, 2023.

We seriously thank the reviewer for their constructive feedback! Below we address the questions.

• In line with other papers on interpolation learning, we indeed provide an asymptotic characterization (benign/tempered/catastrophic). Obtaining a finite sample bound on the convergence (or divergence) would require additional assumptions (which we preferred not to get into in order to keep the paper focused—e.g. our results do not depend on the Lipschitz constant, only on it being finite) but should be possible using standard concentration inequalities and a more elaborate analysis.

• As we explain on page 2, the precise implicit bias of GD (and even Shevchenko et. al. [1]’s analysis) does not guarantee that min-norm interpolators are reached. However, we note that the main property of min-norm interpolators that determines the overfitting behavior in our analysis is the formation of “spikes”, and such spikes are empirically observed while interpolation with GD in Shevchenko et. al. [1]. Thus, studying min-norm interpolators with these properties is a good starting point. Moreover, considering the min-norm interpolator is natural when training with small weight decay.

• Indeed, for linear splines (warmup) and data on the grid (contrast analysis), we do not explicitly provide lower bounds showing that overfitting is tempered rather than benign. These are fairly straightforward and we will include them in the final version for completeness. Thanks for pointing this out! To be clear: we do provide lower bounds in the main analysis (min-norm neural nets on i.i.d. samples), just not for the warmup and the contrast analysis.

[1] Alexander Shevchenko, Vyacheslav Kungurtsev, and Marco Mondelli. Mean-field analysis of piecewise linear solutions for wide relu networks. The Journal of Machine Learning Research, 23(1): 5660–5714, 2022.