More is Better: when Infinite Overparameterization is Optimal and Overfitting is Obligatory

We thank the reviewer for their evaluation, noting in particular the clear writing and effort to crystallize common wisdom. To the first weakness: we opted for a streamlined, nonrigorous approach for our derivation of the RF eigenframework, adopting the philosophy typical in statistical physics where one makes justified approximations and then checks against numerics at the end of the calculation. As we discuss at various points, we expect our RF eigenframework to become exact in a proportional limit (e.g. precisely the limit taken by Bach et al (2023)). Extracting approximation errors for finite $n, k$ is not a trivial task, but we know of other work in progress that intends to do this.

To the second weakness: thank you for flagging this. We have added a few helpful phrases to help the reader understand that by “interpolation” we mean “zero training error.”

To the question about significance: we find that [the limiting KRR] is better than [finite RF regression]. However, this does not mean that KRR is arbitrarily good! Some other model type (e.g., a neural network) can certainly be better, and we make no claims about performance relative to any model outside of RF regression. To further clarify the relationship between these model classes: RF regression trains only the last layer, does not learn features, and becomes KRR in the limit of infinitely-many features. Infinite-width NNs are a special case of KRR and do not learn features, so long as one scales init + lr in the NTK fashion. Finite-width NNs learn features and are not simply related to RF regression or KRR. Heuristically speaking, we show that infinite-width NNs are better than RF regression, but whether infinite-width NNs are better than finite-width NNs remains an open problem.

To the enumerated questions:

1. We hope we have addressed your concerns. We are happy to offer additional clarifications.
2. We refer the reviewer to Appendix E discussing the motivation for scaling down noise with test error. Ultimately, this is just a theoretical convenience: in practice, $\sigma^2$ will indeed be whatever finite quantity it actually is, and $n$ will be finite. For the purposes of theoretical calculation, we want to take $n$ to infinity, and so we’re left with the question of what to do with $\sigma^2$ to preserve behavior similar to what we started with. We argue that keeping $\sigma^2$ unchanged as $n \rightarrow \infty$ actually changes the behavior in undesirable ways, and one instead ought to scale it down in the manner described. This is just a trick for writing down a better model for our learning task and does not actually amount to an assumption that the noise is really $n$-dependent.
3. Ah, there is no conflict: in Figure 1, the test error decreases continuously, and it also approaches an asymptote. Consider, for example, the function $x^{-1} + 1$ as $x$ grows: it always decreases, yet never decreases below its asymptote of $1$. Theorem 1 only promises that the gains from increasing $k$ are positive, but they will become smaller and smaller as $k$ grows.
4. Like us, Bowman and Montufár (2022) compare the learning of models with finite sample size and width to those of infinite sample size and width. They focus on training dynamics: their claim is of the flavor that “even at finite sample size and width, the evolution of the learned function looks like the infinite case early in training.” This is a similar message to the (empirical) message of the “deep bootstrap.” By contrast, we study generalization rather than the training trajectory, focus on the learned function at the end of training rather than early in training.

We thank the reviewer again for their review. If they feel we have addressed some of their concerns, we ask that they consider adjusting their score accordingly.

We thank the reviewer for their favorable evaluation! To the first comment re: rigor, while we are fully rigorous in all conclusions proven starting from eigenframeworks (i.e. Theorems, Lemmas, etc.), we opted for a streamlined, nonrigorous approach for our derivation of the RF eigenframework, adopting the philosophy typical in statistical physics where one makes justified approximations and then checks against numerics at the end of the calculation. As we discuss at various points, we expect our RF eigenframework to become exact in a proportional limit (e.g., precisely the limit taken by Bach et al (2023)). The analysis of Bach (2023) is rigorous under the Gaussian ansatz, and one can likely use the same techniques to obtain a rigorous proof for our RF eigenframework.

Regarding the noise, our analysis applies even at high noise. Indeed, Figure 2 includes traces with relative noise variance as large as 50! We focus most of the exposition on the case of small noise because this is an interesting and realistic case.

Thank you again for the review!

We thank the reviewer for their favorable evaluation, noting in particular the unifying nature of our results. We will respond to the two stated weaknesses.

(i) We understand the reviewer’s comments to mean that, while they find our study of overfitting for powerlaw tasks (Section 5) solid and concrete, they find the RF eigenframework in Section 4 to be less surprising. This is fair: we are generally less interested in the RF eigenframework itself than in what new things we can conclude from it (namely the “more is better” result of Theorem 1). If some prior work had given a simple derivation and statement of this general result, we would have been happy just citing it. As nobody had done that to the best of our knowledge and it seems generally useful, we decided to. We also note that the simplicity with which a result may be derived is not necessarily indicative of the result’s importance, and the result reached here is indeed fairly general :)

(ii) We understand that the reviewer finds unclear the relation of our “fitting-ratio-based” notion of overfitting to the simpler, more common approach of simply studying the ridgeless case (and perhaps comparing to the optimally-regularized case). To clear this up: the model is ridgeless ($\delta = 0$) precisely when the fitting ratio is zero ($\mathcal{R}\_{tr/te} = 0$). When we find that $\mathcal{R}_{tr/te} = 0$ is optimal, we are precisely finding that zero ridge is optimal. We realize that we missed saying this explicitly, and so we have added some appropriate text where we introduce the fitting ratio. The reviewer’s interpretation of Corollary 1 is correct (and indeed answers the reviewer’s concern regarding Theorem 2), and the text will say so.

To the reviewer’s questions:

(Qi): All the cited works derive the same eigenframework. Right now, the best (i.e. most general while still rigorous) source for this eigenframework is probably Cheng and Montanari (2022), and this could be taken as the canonical starting point if one is required. We have edited the text to say this.

(Qii): Yes, this is the intended claim. The most important curve is the one with zero noise, because this is the true, unmodified task. The point of adding noise is that Corollary 1 predicts that adding noise should make overfitting no longer obligatory, and we are testing that. Comparing to noisy curves is also a way of stressing that the unmodified tasks seem to not have significant noise.

(Qiii): This is a good question. The finite-k case is algebraically harder to handle: from the start, one has the two coupled equations (2) defining implicit constants instead of just one. To undertake a similar powerlaw analysis, one might write test error in terms of $\gamma$, then write $\gamma$ in terms of the train-test ratio, and finally optimize over the train-test ratio. The test error in the finite-k case would be significantly more complicated than in the infinite-k case (Lemmas 4 and 10), but this might work. It may be a doable thing for a future paper.

(Qiv): Thanks for catching this. We’ve fixed it.

We thank the reviewer again for their review. If they feel we have addressed some of their concerns, we ask that they consider adjusting their score accordingly.