Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This submission computes the asymptotic training and test error of linear estimators optimized by gradient flow on the least squares objective, under the student-teacher setting with Gaussian covariates studied in [Loureiro et al. 2021]. The analysis generalizes the earlier linear pencil calculation for random features model in [Bodin and Macris 2021], and recovers the performance of the ridge regression estimator when the time $t$ is large. The authors present a few examples of solvable models, and also demonstrate empirically that the Gaussian covariate predictions can be accurate for certain real-world datasets. 
strength_and_weaknesses: ## Strength

The studied problem is well motivated: most existing works on the precise asymptotics of training/test error only consider the empirical risk minimizer (instead of the entire gradient flow trajectory), and the time-evolution of the error reveals some interesting phenomena such as epoch-wise double descent. While the results are only derived for Gaussian features, we may expect wider applicability due to the Gaussian equivalence (universality) property. Moreover, the linear pencil construction and the Dyson Brownian motion derivation of the self-consistent equations could be useful in future random matrix-related research. 

## Weaknesses

My main concern is that many relevant prior results are not discussed.  

- Asymptotics of the least squares estimator in Section 3.2 (anisotropic features, isotropic teacher coefficients) was first rigorously studied in [Dobriban and Wager 2018]. This result was then extended to general teacher models using the Stieltjes transform approach in [Wu and Xu 2020] [Richards et al. 2020], where the authors already showed that the multiple descent risk curve can be engineered using eigenvalues of different scales. Also note that the self-consistent equations in these works are identical to the infinite time-limit in this submission. 

- The discussion of the Gaussian equivalence principle in Section 3.3 is insufficient and non-rigorous. The cited [Peche 2019] only implies the (weak) equivalence in the kernel spectrum, which does not guarantee the equivalence in the training and test error. The authors should look into [Hu and Lu 2020] and references therein. 

- Asymptotics of the gradient flow dynamics can also be analyzed using alternative approaches such as dynamical mean-field theory. In this submission, the squared loss gives a closed-form expression of the trajectory which simplifies the computation, but it would still be nice to briefly discuss and compare these different method. 

Dobriban and Wager 2018. High-dimensional asymptotics of prediction: ridge regression and classification.  
Wu and Xu 2020. On the optimal weighted $\ell_2$ regularization in overparameterized linear regression.  
Richards et al. 2020. Asymptotics of ridge (less) regression under general source condition.  
Hu and Lu 2020. Universality laws for high-dimensional learning with random features. 

In addition, it is not entirely clear of how ML theory researchers can benefit from knowing these asymptotic formulae. Currently, the application seems to be limited to plotting good-looking risk curves; this does not provide quantitative characterization of the reported phenomena. For example, to rigorously establish epoch-wise double descent, the authors need to check the time derivative of the error to show non-monotonicity. Such analysis would strengthen the theoretical contribution of this submission. 
clarity,_quality,_novelty_and_reproducibility: **Clarity \& Quality:** the writing is mostly clear. I have the following questions: 

- In the current manuscript there is no discussion around the assumptions, and it is not clear if they hold in the listed examples. For the random features example, I believe the activation function is zero-centered so that the spectral norm of the kernel matrix is asymptotically bounded. Can the authors confirm the conditions required for the activation? 

- In the Appendix, I would appreciate some explanations on how the large block matrices are constructed. Do we know if the linear pencil is minimal in terms of the size? 

- In Figure 4 (right), why are the experimental values only plotted until $t=10^2$? Does the test error start to deviate from the theoretical predictions after that? 

**Novelty:** see weaknesses above. 

**Reproducibility:** N/A. 
summary_of_the_review: My current evaluation is that this is a borderline submission: I believe the random matrix analysis is a solid contribution, but the authors need to thoroughly discuss prior works and present the results in a more accessible way for the ICLR community. I will consider updating my score if the authors can adequately address the above concerns.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper looks at the regularized linear regression where the data is generated using a Gaussian Covariate model and the regression targets are linear functions of the data. the paper starts by showing the that the setting is fairly general and captures many other set ups. In this set up, under some assumptions the paper then obtains a formula (albeit a complicated one) for the training and test error as time evolves. 

Then they specialize to specific instances and re-discover known results from prior work. 


strength_and_weaknesses: **Strengths**
---

1) The set up is fairly general and captures many existing models that have been analyzed. 
2) The method provides the whole training curve and not just the limiting distribution. 
3) The paper re-captures known results/
4) The idea of evolutions of the eigenvalues and the ``bulk'' in section 3.2 is interesting. 

**Weaknesses**
---

1) I think the results are very hard to parse specially Result 2.1 and result 2.4. Further in result 2.1 the terms depend on equations $\tilde{f}$ which is very complicated term which itself terms on equation (8) which is a complicated implicit equation (both sides depend on the quantity). Hence while the formulas might be true, it is not clear how informative they are. **That is, do they actually tell us much more than $\beta^\lambda = (\hat{X}^T\hat{X} + \lambda I )^{−1} \hat{X}^T Y$ and then just writing down the test error.**


clarity,_quality,_novelty_and_reproducibility: **Clarity**
---

While the writing of the paper is clear, the equations and the results are fairly opaque. 

**Novelty and Significance**
---

The analysis techniques are not the most novel. However, the generality of the setting and then derivation of known results in this unified setting is significant. 

**Reproducibility**
---

The paper should be reproducible. 

**Questions**
---

1) Can the authors provide some insight into the formulas in Result 2.1?
summary_of_the_review: In summary the paper is a nice theoretical contribution however, the insights that can be readily obtained seem lacking. I think significant work would be required to simply the formulas or some work should be done to help understand the formulas (at heuristically) would go a long way to improving the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies gradient descent for linear regression under the high dimensional framework. Under certain conditions, the authors study the generalization error in such gradient descent, and show that there exists multiple descent in the generalization error of the linear model during training. The authors also conduct experiments on the random feature models and realistic data sets.
strength_and_weaknesses: Strengths:

1.  Multiple descent and learning in high dimensions is an important and interesting topic. This paper proposes some timely and interesting results.

2. The paper provides rigorous proof of the generalization error in the gradient descent flow, and also provides some simulations and experiments.

Weaknesses: 

My major concern is that there seem to be some confusing/vague statements. Below are some examples: 

1. Given existing analyses on double/multiple descent in linear models and the regularization effect of early stopping, the technical contribution of the paper may be limited. 

2. Recently, there are some papers related to multiple descent (arXiv:2204.10425, arXiv:2205.14846, arXiv:2208.09897). The connection between this paper and existing works is not discussed very thoroughly.

3. The theory applies to the high dimensional setting, so setting $p=3$ in the experiments may not be very reasonable. The authors should provide simulation results with larger $p$.
clarity,_quality,_novelty_and_reproducibility: I think the clarity of this paper can be improved if the authors give more discussion on the problem setting, intuition, and comparison to recent works. The novelty of this paper mainly lies in the observation of multiple descent with respect to the training epochs.
summary_of_the_review: In summary, this paper gives solid and interesting results. However, as discussed above, several parts of the paper can still be improved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study the evolution under gradient flow of the training and test errors in the setting of Gaussian covariate models, which encompasses several other well studied settings. Using tools from random matrix theory, in particular the linear pencil, they calculate the exact asymptotic behavior of several quantities in the high-dimensional limit. The authors show how multiple descent phenomena can arise as a function of both number of parameters and training time. The paper also includes results on real datasets and shows good agreement between simulations and theoretical predictions.
strength_and_weaknesses: **Strengths**

- The setting of Gaussian covariates is nice and generalizes many other models.
- Early stopping is important in practice. This theory gives some results on how to choose the stopping to avoid multiple-descent peaks.
- The analysis connecting the peaks in Fig 2 to the spectrum in Fig 3 is nice.
- The use of Dyson’s Brownian motion to derive the self-consistent equation (276) is cool.


**Weaknesses**

- No significant new machine learning implications from the results are derived in the paper. This might limit the paper’s interest to the wider ICLR community.
- I couldn’t find any details of how numerical predictions are generated from the equations of Result 2.1. In particular, how are the contour integrals calculated? Which contour is used? How do you avoid spurious solutions to the self-consistent equation?
clarity,_quality,_novelty_and_reproducibility: - It would help my review if the authors could comment on what is completely novel in this work. My current sense is that the main contribution is to generalize previous work, including Bodin and Macris, to the full Gaussian covariates setting.
- Just after Eq (8), the assumption that U and V* commute is mentioned to provide a limiting self-consistent equation. Can this be avoided by introducing a joint spectral density like Assumption 1 in [1]?
- In Sec. 1.1, the authors should consider citing [2] and [3] in relation to the analytic calculation of double-descent curves. Similarly [4] is a relevant citation from triple or even multiple descents for the generalization error.
- I think Eq (9) has a typo since there is the matrix I in the denominator.

[1] Tripuraneni, Nilesh, Ben Adlam, and Jeffrey Pennington. "Overparameterization improves robustness to covariate shift in high dimensions." Advances in Neural Information Processing Systems 34 (2021): 13883-13897.

[2] Lin, Licong, and Edgar Dobriban. "What Causes the Test Error? Going Beyond Bias-Variance via ANOVA." J. Mach. Learn. Res. 22 (2021): 155-1.

[3] Adlam, Ben, and Jeffrey Pennington. "Understanding double descent requires a fine-grained bias-variance decomposition." Advances in neural information processing systems 33 (2020): 11022-11032.

[4] Adlam, Ben, and Jeffrey Pennington. "The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization." International Conference on Machine Learning. PMLR, 2020.
summary_of_the_review: The paper contains nice results that unify and extend previous work. The paper's main claims are supported by proofs and illustrative experiments. Overall the paper is clearly written and covers a lot of material.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents and analyzes formulas for the high-dimensional asymptotic trajectory of gradient flow for least-squares regression in the Gaussian covariate model. The results generalize those of Loureiro et al. (2021) to finite time and of Bodin & Macris (2021) to a broader class of models.

The reviewers appreciate the relatively general setup, the practical importance of studying early stopping, and the interesting phenomenology revealed through numerical investigation of the equations. The discussion highlighted several reviewer concerns, including insufficient discussion of prior work, lack of rigor in parts of the analysis, limited machine learning takeaways, and challenges with reproducibility.

The reviewers pointed out that the scope of the analysis becomes relatively limited without invoking universality/Gaussian equivalence, which has yet to be proven rigorously. The authors' response contends that it is a common tool which has been used in prior works without proof as well. Given that the consequence of forgoing the universality claims is merely a reduction in generality (rather than in invalidation of the results as a whole), I would agree with the authors that this limitation is not a significant weakness of the paper.

On the other hand, the reviewers also point out that the observed phenomenology and interpretation of the results is based entirely on numerical evaluation of the formulas, rather than an analytical investigation of the properties of the equations. This significantly reduces the value delivered by presenting the formulas in the first place, as it would be simpler and equally illuminating to perform a numerical evaluation of finite-sized models, which could be done without any theoretical analysis whatsoever.

Furthermore, the numerical evaluation of the equations is itself extremely non-trivial. One reviewer asked for clarification regarding the choice of contour for the numerical integration, but the response does little to address potential concerns about convergence or the accuracy of the obtained results, particularly for large values of t, for which the integrand can become highly oscillatory. Because the main takeaways of the paper rely on these numerics, more details about the method and its convergence would be important additions.
justification_for_why_not_higher_score: This paper presents non-trivial formulas that characterize the trajectory of gradient flow in the Gaussian covariate model. While these expressions have independent merit and may be interesting to parts of the theory community, the paper does little to draw scientific conclusions out of those formulas, and instead relies on their numerical evaluation to demonstrate relevant phenomenology. Given that the numerical evaluation is non-trivial, that insufficient details were provided about how to extract accurate numerical results, and that limited analytical conclusions were obtained without resorting to numerics, the contributions of this paper mainly rest on the presentation of the equations themselves, which is in itself insufficient for publication at ICLR.
justification_for_why_not_lower_score: N/A.
Decision: Reject