Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: null
review_content: As a reviewer of this article, I have read the authors' response and again looked at the article as well as some publicly available material. I still like the article but have come to be even less happy than before about the credit given to prior work using linear pencils to understand random feature regression (I mentioned this point in my original review).

Specifically, it seems to me that the seminal paper that brought the idea of using linear pencils and operator valued free probability (OVFP) to studying random features was the work [32] of Adlam and Pennington. I understand that this paper didn't invent linear pencils and OVFP but it both pointed out the non-trivial fact that they are useful in the context of high dimensional random feature models and some did extremely precise and complicated computations to understand the generalization error (among other things). I believe that this article  should be highlighted much more prominently. 

I feel this way in part because I saw that obtaining a Cauchy integral representation for the time-varying training/test loss appears in several talks by the authors of [32] (one example is around 15:50 in this video: https://www.youtube.com/watch?v=kujyufpr9ys&list=PLWQvhvMdDChzsThHFe4lYAff3pu2m0v2H&index=8 see also around 40:00 in that video for plot of loss vs. time). Of course I don't expect the authors of the article under review to have watched all possible videos on the subject. But since what I view as the key new idea in the article under review (namely the time-varying expression for the training/test error) was already discussed in a well-attended public forum, I think it should be explicitly mentioned. From my point of view, giving accurate attribution for where both ideas and techniques come from is important for the integrity of our field. 

I hope the authors will consider making this emendation, as I feel it is both fair to do so and helpful for giving prospective readers more context. 
review_title: Good paper, but I feel prior work is not appropriately credited

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, authors proposed an analytical model to understand the multiple-descent curves in generalization errors of over-parameterized models (random feature models optimized over gradient flow). More specifically, they provided exact solutions to interpret the model-wise, epoch-wise and sample-wise double descent phenomenon. 

In Section 2., authors define the learning problem of over-parameterized models with random features as a regression problem of Ridge-alike, then define the optimization procedure as an ODE. In Section 2.2., authors represent  training and testing errors with  Cauchy integral representations with assumptions prespecified. They report the result as the solution of ODE under assumptions while providing some simulation results to backup their theoretical results. The sketched proofs are attached. 
main_review: The work provides asymptotic results on the generalization performance I might be wrong, the main results of this work looks the combination of existing results on gradient flows (to run OLS or Ridge) with some results on random matrix theories (to model the sample covariance established by random features) via Cauchy integral. Authors are encouraged to discuss their results with "Just Interpolate: Kernel ''Ridgeless'' Regression Can Generalize" at Annals of Stats 2020. Of-course, in Ridgeless paper, they did not cover the optimization issue. With gradient flow for OLS and Cauchy integral, it seems possible to obtain the exact solution of or tight approximation to the gradient flow for OLS at continuous-time t. It looks authors obtained their results through combination. Some simulations could be improved using real-world datasets.
limitations_and_societal_impact: It helps us understand why over-parameterized models work and interpret their generalization performance.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors analytically study model, sample, and epochwise descents of the random feature model. Model descent meaning how the test error changes as the model complexity is varied; sample descent meaning how the test error changes as the number of samples are varied; and epochwise descent meaning how the test error changes as the model trains. They derive analytic expressions for the test and train errors and study what happens when the number of neurons $N$, the number of samples $n$, and the sample dimensionality $d$ all tend to infinity. Since this can be done in varying ways, they study when $\frac{N}{d} \rightarrow \psi$ and $\frac{n}{d} \rightarrow \phi$ for fixed values of $\psi$ and $\phi$. They observe double descent which is beneficial (lower test error when $\psi \gg \phi$) if training is performed for a long time. On the other hand, if training is cut short (early stopping) the test error is low and even has a dip where later there develops a peak. The authors also observe triple descent if the training time tends to $\infty$.
main_review: Originality:

The idea of studying the analytic expressions for test and train error as training evolves is not particularly novel. However, the authors use some very sophisticated mathematical techniques which bring novelty to the work in a way that is not typical. Good job.

Quality:

This paper is extremely well written and flushed out. The authors did a great job.

Clarity:

The paper is mostly clear. It is hard to read because of the notation; however, that is to be expected for such a theoretical paper.

Significance:

This work is very interesting and important for the continued understanding of more complex models such as deeper neural networks.
limitations_and_societal_impact: Limitations:
As the authors mention on line 88, the work is not completely rigorous because of their concentration hypothesis. However, this is not an issue for me as they provide supporting empirical evidence to support their work.

Potential negative societal impacts:
None
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This article provides, modulo some important technical assumptions, computationally tractable formulas for the test and train error of a random features model trained by gradient flow on \ell_2-regularized MSE during the entire course of training. The features are those computed by the first layer of a randomly initialized neural network and the regime of interest for this article is a triple scaling limit in which the input dimension, dataset size, and hidden layer width tend to infinity but their ratios remain order 1. Unlike prior work this article provides formulas for the evolution in time of both the training and test error, instead only of only their behaviors are t = \infty. While the results are not completely rigorous (they assume concentration for spectral statistics of certain random matrices), I found them intriguing and am fairly convinced by plots in which the predictions fit empirics quite well. The main weakness for me is a lack of further formulation of takeaways from the theoretical results (see weakness #2). Overall, I thought this was a solid paper. 
main_review: Strengths:

1. Understanding the regime where input dimension, dataset size and the number of model parameters are all large is clearly relevant to modern ML. 

2. The techniques in this article give what is, at least to me, a nice approach to understanding the behavior in time for train and test error in random feature models. While these models are linear in the trainable parameters, they are not linear in the inputs and understanding the resulting training curves seems hard and interesting. 

3. If I understood correctly, the plots in Figure 3,4,5 were generated by analytically computing the test and train error from the formulas in Result 3.1. Assuming these match empirics, this is very useful indeed. I particularly liked “seeing” the epoch-wise, model-wise, and sample-wise descents appear and the phase transitions between double descent, triple descent, and other behaviors. 

4. I thought the main body of the article was well-written and was able to follow the logic. 

Weaknesses:
1. The formulas in Result 3.1, while seemingly analytically computable, are sort of horrendous at first glance. It would be nice if some intuition could be provided for what is going on. 

2. An amplification of #1: I feel that the techniques in this article are sophisticated but the interpretation of the results is a bit lackluster. Concretely, since the formulas themselves are hard to grok, it would have been very useful to me as a reader if the discussion in section 3.2 were amplified. (I understand that space is an issue, but I am not sure anyone really needs to see the exact structure of the linear pencil on page 9?) For example:

2a. When exactly do we expect that early stopping is useful? Are any of these situations surprising? 
2b. I am intrigued by the double plateau. Can you explain it intuitively? When should one expect it to occur?
2c. Can you explain more about the interaction of the non-linearity via its first few Hermite coefficients and the simultaneous appearance of the linear and non-linear spike?


Minor:
1. “passed an interpolation” should probably be “past an interpolation”

2. For equation (1) in the definition of H^{train} either H^{train} should be evaluated at a instead of a_t or the right hand side should contain ||a_t||^2 instead of ||a||^2. 

3. Line 179 page 5 “time” should probably be “times”

4. It might be useful for the reader if the extra empirical validation of the results in Figures 13-15 were highlighted in the main body.

5. I am not an expert in the developments of this kind of high-dimensional RMT for random feature generalization, but I have the feeling that the article of Adlam-Pennington “The neural tangent kernel … “ is kind of given short shrift. Maybe I’m missing the point, but it seems that the use of linear pencils is key for doing the computations related to spectral curves and the algebraic relations in Result 3.1. And if I am not mistaken these techniques were used for first time in this context in that article. More broadly, as a non-expert, it would have been very useful to have a bit more context comparing the present work to the various different strands of work on double and triple descent in high dimensional models.
limitations_and_societal_impact: The limitations were discussed. Societal impact was not addressed, but it is not clear to me that this kind of article has any serious potential societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an analytical derivation of the train and test loss curves of the random feature model. The main novelty lies in the fact that the authors not only capture the behavior at final times, but also the dynamics. This leads to various interesting observations, since such models have been shown to exhibit epoch-wise double descent.

main_review: Overall, I recommend the acceptance of this paper to NeurIPS.

Strengths: 
- First analysis of epoch-wise double descent I know of for RF models
- Paper is well organised, results are presented clearly
- The authors clearly state the non-rigorous hypothesis used
- The phase space plots are informative and reveal new phenomena such as the exponentially elongated bump in the epoch-wise phase space as we regularise too little (this is particularly interesting in my opinion)
- The authors do a good job to provide a sketch of proof, and even include an alternative proof using a different technique from statistical physics
- The derivations in the SM are thorough and detailed

Weaknesses: 
- Could be viewed as slightly incremental to the non-initiated community, but the complexity of the analytical derivations justify the novelty of the paper
- Fig. 2, which overlays the theoretical and experimental results, is plotted at final time as a function of phi/psi, but the late-time error was already derived in previous works; it would be better to have the numerical confirmation as a function of time, since time-dependency which is the key novelty of this paper.
- I think more space should be devoted to the phenomenology observed, as the analytical results are nearly impossible to parse for the reader.

Nits:
- Fig 1: a bit confusing that the t axis are inverted in the two panels
- Line 114: Hermite polynomials should be indexed by n
- “we notice that the linear-spike seems to appear earlier than the non-linear one” : this was observed already in reference 21.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper presents an asymptotically exact formula for the time-dependence of the training and test error of random feature regression in high dimensions. The reviewers all maintain a favorable view of the results, but there was some concern about the credit afforded to prior work.

Indeed, operator-valued free probability and linear pencils (and the linearizations required to utilize them in the context of nonlinear random feature models) were introduced to the machine learning community in prior work with the express purpose of facilitating the kind of analysis undertaken here. Furthermore, it appears that the main results and methods of this paper, namely those derived via the Cauchy integral formula, have been obtained and advertised elsewhere (though apparently only in talks and never published). As such, it seems there is limited technical novelty in the current paper, and it is imperative that the discussion is modified to more properly reflect this prior work and to emphasize that the contributions of this paper are not the techniques themselves, but rather the results.

On the other hand, there is of course significant value in actually carrying through the calculations in detail, presenting concrete results, and analyzing their implications. As such, this paper will be of value to the community, irrespective of related prior work. Therefore I believe this paper is a good addition to NeurIPS and recommend acceptance.
Decision: Accept (Poster)