Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies random feature regression in high dimensional setting, when the data and model weights are assumed to be normal with anisotropic covariances. By an error decomposition argument, the exact formulas for the bias, variance and total error are provided. The results motivates the discussion on the multiple descent effect of the sample-wise test error curve, and the authors also prove that the error against overparametirazation only exhibits double descent. The phase transition is associated with the spectral structure of the approximated kernel matrix. Also, the error is improved when the data covariance aligns more with the model weight covariance.
main_review: In general, the paper is written clearly with enough technical details to understand the arguments. The motivation to study data with anisotropic covariances is good. The findings on the error curve structures and the correspondence between phase transition and induced kernel matrix spectrum are interesting. In all, I think the significance and contribution of this paper meet the bar of ICLR.

However, one thing that may weaken the significance of this work is that, as a theoretical paper, the proof techniques of the main results is almost the same as previous works studying the case of identity covariance. The only difference is the changing in the covariance, which only changes some calculations. Thus, from the technical perspective, the paper does not provide much new insight.

Questions and detailed comments:

1. What is the motivation to consider random model weights and what is a good practical implication of this setting and related results (e.g., the covariance alignment)? I notice that the analysis in Liao et. al NeurIPS 2020 also does not require that the data has identity covariance matrix, and do not assume random weights either. I think that setting could be more practical. How does the results in this paper compare with theirs?

2. The analytical figures are plotted using the data model described in Section 2.3. Does the observations hold for more general data distributions?

3. What is s in equation (12)? In Figure 3 c), what is the optimal regularization parameter lambda? Seems that it is not described.

4. In Figure 2 a), the multiple descent is more obvious for small \omega, which is the linear model. Is that correct? Then why is it stated as an observation for random feature regression?

Some plots in Figure 2 and 3 needs to be better clarified. I'm a little bit confused about some plots and find it hard to get what the curves represent. There is a typo in the caption of Figure 2, 3rd line. 
summary_of_the_review: In the sub-field of high-dimensional random feature regression, the paper present good contribution and results to consider the anisotropic data distribution, though the proof techniques mostly follow from previous works. Therefore, I think the paper has its pros and cons, depending on the "weight" of technical novelty. In all, I feel the paper is above the borderline of acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies nonlinear random feature regression of a linear response in the *anisotropic* setting where both the covariates and parameter have arbitrary covariance matrix. The training error and test error are computed explicitly as the dimension, sample size, and number of features jointly tend to infinity. The proof method relies on linearization and a technique from free probability involving the construction of linear pencils. The asymptotic formulas are used to theoretically describe (i) the beneficial effect of overparameterization on the bias and variance components of the test error and (ii) the number of critical points of the test error as a function of overparameterization. This paper graphs the asymptotic formulas for some specific models to demonstrate parameter-wise and sample-wise multiple descent phenomena. 
main_review: **Strengths**:
	
- To my knowledge this is a novel contribution that broadens the understanding of overparameterization, a topic of interest to the ICLR readership
	
- The asymptotic formulas are exact and relatively simple.
	
- This paper introduces an interesting notion of alignment between the covariance matrix of the covariates and that of the parameter, and it is shown how this alignment affects the test error
	
- The main paper is well-organized, clear, and has interesting, illustrative figures.
	
**Concerns**: 

- I am mainly concerned with the rigor and clarity of the derivation of the main theorem, Theorem 3.1. Please see the section "Proof of Theorem 3.1" below.

- To my understanding, Figures 1--3 are generated by plotting the asymptotic formulae from Theorem 3.1. It would strengthen the paper to confirm these plots with simulations on synthetic data.


**Proof of Theorem 3.1**

My points below mostly concern Section F to the end of Section F.4.1 in the Supplement. The proof happens in two steps: (i) linearization of random features and (ii) application of free-probability theory to compute the trace of some complicated matrices. 
	
(i) *Linearization*: This paper claims without proof that the test error is unchanged by an appropriate linearization of the non-linear random features. Of the given references on pg.13, I could only find a proof of the invariance of test error under linearization in Mei--Montanari '19, which only studies the case of random spherical (that is, isotropic) covariates. This requires justification in the anisotropic case.
	
Also a minor point: after linearization, the definition of $F$ changes I think. Please make this clear in the text 

(ii) *Free probability*:  Most of Section F relies on computations of various traces of matrix products involving covariance matrices and iid Gaussian matrices.

*Major issues with (ii)*

-  pg 13: There is no explanation of the construction of the $Q^{K^{-1}}$, which I believe is the *linear pencil*. A short, precise description of the linear pencil methodology would improve the paper since it is crucial to the proof.

-  pg 17: "We aim to compute the asymptotic values..." I am concerned about the looseness in taking limits described here. How can the limit in $n_0, n_1, m$ be taken in two stages? Once these go to infinity, there should be no dependence of any expressions on $n_0, n_1, m$. It is also not clear at what point limits are taken in the computation in Section F.4.1. 

-  pg 18: Formula (S200) is crucial. Please give a reference to the precise section and theorem in Mingo--Speicher '17. 

-  pg 19: The R-transforms in (S202)--(S208) depend on indices of $G^{K^{-1}}$ that go out of range. For example there is a $(3, 15)$ entry in (S203).

-  pg 19: The details of R-transform computations are omitted. I find this acceptable, but please cite the specific chapter in Mingo--Speicher that describes the technique for computing them

-  pg 19: How is (S200) used to derive equations (S209)--(S228)? I would appreciate if in the discussion period the authors can explain how to derive (S209) from (S200) and the various R-transforms. In particular, I would like to understand the details of why the expectation over $\mu$ shows up and what happened to all of the random matrices.

-  pg 19: The appearance of $\mu$ in (S209)--(S228) suggests that limits with respect to $n_0, n_1, m$ have been taken. So how is it that the terms $n_1, n_0, m$ still appear in these expressions?

-  pg 22: The calculation in Section F.4.4 involves the system (S312)--(S364) consisting of ~50 equations that spans 3 pages. It is hard to verify the end result. Are all of these equations necessary for the derivation? If a simpler explanation isn't possible, I recommend giving a computer-assisted proof citing Mathematica or other algebra software. 

*Minor issues with (ii)*

-  pg 13: $K$ appears to be regularized in (S137), but later $\hat K$ is introduced that has the same formula. Should $K$ be non-regularized in Section F?

-  pg 13: $\theta$ is not defined and seems to sometimes be written as $\Theta$ or $\Theta_F$. 

-  pg 18: "Here the normalized trace... acts on the space of 18x18 matrices." Should it be 9x9 matrices?

-  For readability, I suggest re-organizing lists of equations with indices listed in lexicographic order ( for example in (S172)--(S194) )

-  pg 19: The terms in (S209, S210) have no expectation over $\mu$, but the remaining ones do. Is this a typo?

**Minor issues/typos in the main text**

- For consistency, use either "total error" throughout or "test error" throughout

- pg 2: "... in the relatively trivial case of isotropic covariates..." Please replace this with "... in the case of isotropic covariates..." It is clear that isotropy is a simpler case, but I think it's good to avoid referring to prior works as relatively trivial. 

- pg 3, Eq (5, 6): The expectation over $\beta$ appears and then disappears; for consistency please make a choice whether or not to include the expectation over $\beta$ in the error metric.

- pg 3: "...the test error of linear regression depends on the geometry of $(\Sigma, \beta)$." This is confusing since $\beta$ is random. Perhaps it should be the geometry of $(\Sigma, \Sigma_\beta)$

- pg 4, Eq (9): Usually the term "empirical spectral distribution" is reserved for the random measure given by the eigenvalues of a *random* matrix. Since $\Sigma, \Sigma_\beta, \mu_{n_0}$ are deterministic, perhaps just saying "joint spectral distribution" suffices?

- pg 5, Definition 2.1: "If the asymptotic coefficients are such that $\mathbb{E}^{\mu_1}[\lambda q| \lambda]/\mathbb{E}^{\mu_2}[\lambda q| \lambda]$..." I think it should be $\mathbb{E}^{\mu_1}[ q| \lambda]/\mathbb{E}^{\mu_2}[ q| \lambda]$ instead (otherwise the value is independent of $\lambda$)

- pg 5, Theorem 3.1: The main result is hard to parse because the definitions of parameters are scattered throughout pgs 1--5. A short recap or pointer to prior definitions could help with this.

- pg 5, Theorem 3.1: It took me a while to understand the meaning of  "the training error $E_{train}^{\Sigma} \to E_{train}^{\mu}$ where *insert Eq (14)*".  A clearer rephrasing is "the training error $E_{train}^{\Sigma}$ tends to the value $E_{train}^{\mu}$, where *insert Eq (14)*".

- pg 6, Figure 1: (f) is missing a legend

- pg 6, Figure 1: In (d, e), it took me a while to understand what the black solid and dashed lines correspond to in the plots. I recommend just making a slightly bigger legend of the form " Total error ($\theta$ = 1), Bias ($\theta$ = 1), Variance ($\theta$ = 1), Total error ($\theta$ = -1), Bias ($\theta$ = -1), Variance ($\theta$ = -1)" 

- pg 6, Figure 1: What do the blue dashed/solid lines indicate in (a)? What do the gold dashed/solid lines indicate in (b, c)? Are these necessary?

- pg 7, Figure 2: There is not much color variation in (b). Is this intentional?

- pg 7, Figure 2: Please add to the caption that (b) plots the limiting spectral density of the kernel matrix

- pg 8, Figure 3: The tick marks in (a) are very small and hard to read

- pg 8, Figure 3: In (b, c), it is hard to see the color gradient. Different textures for each curve would improve this. 


summary_of_the_review: The topic of this theoretical paper is of interest to the machine learning community, and the contributions given would extend understanding of the generalization behavior of high-dimensional, overparameterized models. My current recommendation to reject is because of the concerns mentioned above about the correctness, rigor, and clarity of the proof of the main theorem, Theorem 3.1. 

======================

Update on review (11/29)

Following the discussion and revision, my confidence has improved on the correctness of the results. Further the surrounding literature that was overlooked is now addressed, especially in Appendix A. 

This work does have some lack of novelty since versions of Theorem 3.1 were known and multiple descent phenomena and some effects of alignment had been recognized in anisotropic random feature regression. Still the main contribution of this paper is the new phenomenology that it identifies, which to my knowledge include the behavior of the bias and variance under overparameterization and (mis)alignment, steep cliffs in the learning curves and their relation to spectral gaps in the covariance matrix, and that parameter-wise descent is limited to double descent. This in itself is a noteworthy contribution. 

This paper would be further strengthened by establishing the equivalence of the formulas here with those of d'Ascoli et al '21 and Loureiro et al '21. This would help compensate for the loss in novelty. Also, while the relationship with d'Ascoli et al '21 seems well explained, not as many details are given about the connections with Loureiro et al '21. I also think that this paper needs to be careful regarding claims that it sets these prior works on rigorous footing because (i) the proof of the linearization invariance in Theorem 3.1 is not contained in this paper,  and (ii) to my understanding, the formulas of d'Ascoli et al '21 and Loureiro et al '21 are rigorous modulo linearization invariance. To summarize, the manuscript would benefit from further revision to clarify its contributions and their place in the literature.

All things considered, I am now slightly leaning toward acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper evaluates the training and generalization errors of the random feature (ridge) regression model, in the regime where the number of samples $m$, the input feature dimension $n_0$, and the hidden layer size $n_1$ tend to infinity at the same rate. More precisely, the authors consider
* Gaussian data with zero mean and general covariance $x_i \sim \mathcal{N}(0, \Sigma)$;
* label generated by $y(x_i) = \beta^\top x_i/\sqrt{n_0} + \epsilon_i$, for some additive noise $\epsilon_i \sim \mathcal{N}(0, \sigma_\epsilon^2 ) $ and coefficient vector $\beta \sim \mathcal{N} (0, \Sigma_\beta)$;
* (random feature) kernel regression on $K(x_i, x_j) = \frac1{n_1} \sigma(W x_i/\sqrt{n_0})^\top \sigma(W x_j/\sqrt{n_0})$;

and evaluate the training and test performance as a function of the dimensionality, the nonlinear function (via a few scalar parameters), as well as the spectral behavior of $\Sigma$ and $\Sigma_\beta$.

As a consequence of this theoretical evaluation, the authors characterize sample-wise multiple descents, steep cliffs, and how they relate to, e.g., the spectrum of the (random feature) kernel matrices and the structure of coefficient vector $\beta$. 
main_review: The major contribution of this work is to extend the high-dimensional characterization of random feature (kernel) regression model to the case of anisotropic data. This improves previous efforts of [Mel & Ganguli, 2021] by considering nonlinear random features models, and of [Mei & Montanari, 2021] by considering anisotropic data.

I think this paper makes a solid contribution to the understanding of high-dimensional random feature models.  Many insights (multiple descents due to data and model structure, steep cliffs, etc.) offered by the proposed analysis are valuable in the future (and improved) design of large-scale machine learning models more generally.


summary_of_the_review: Some detailed typos and remarks:
* page 3 on the model: I do not understand why one needs to consider the setting of random coefficient vector $\beta \sim \mathcal{N}(0, \Sigma_\beta)$ instead of, e.g., considering deterministic $\beta$, as in previous efforts. I find it somewhat confusing since the authors say after Equation (6) that "the outer expectation over $\beta$ has been suppressed since ..." Could the authors comment on this?
* page 3 "namely $\beta \sim \mathcal{N} (0, \Sigma_\beta)$.." 
* page 5: after (11) there should be more discussions and intuitions to help the readers understand the definition of $d$-scale LJSDs introduced here, which turns out to be of crucial significance in this paper.
* page 5 Equation (14): perhaps add a few words to define the (partial) derivative.
* page 7 Figure 2 covariance model with $\alpha = 10^3$: a typo here? Also, we see the sample-wise multiple descents appear for relatively small values of $\omega$, which, I imagine, implies a close-to-linear regime, could the authors comment on this?
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work studies random features regression on a setting where data $(x_{i}, y_{i})\in\mathbb{R}^{n_{0}+1}$, $i=1, \cdots,n$ is generated from a noisy linear model $y_{i}=\beta^{\top}x_{i}+\epsilon_{i}$ with correlated covariates $x_{i}\sim\mathcal{N}(0, \Sigma)$, planted weights $\beta\sim\mathcal{N}(0,\Sigma_{\beta})$ and independent Gaussian noise $\epsilon_{i}\sim\mathcal{N}(0,\sigma_{\epsilon}^2)$. Estimation is given by $\hat{y}(x) = \hat{\beta}^{\top}\sigma\left(Wx\right)$ with $\sigma$ a real-valued activation function and $W\in\mathbb{R}^{n_{1}\times n_{0}}$ a Gaussian matrix with iid $\mathcal{N}(0, 1/n_{0})$ entries, and $\hat{\beta}\in\mathbb{R}^{n_{1}}$ minimising the ridge regression risk on the features $f = \sigma\left(Wx\right)\in\mathbb{R}^{n_{1}}$.

Its main theoretical contribution is to provide an asymptotic characterisation of the test MSE, the bias and the variance on the proportional regime $m,n_{0}, n_{1}\to\infty$ with fixed ratios $\phi=n_{1}/m, \psi=n_{0}/n_{1}$, as a function of the asymptotic spectral statistics of $(\Sigma, \Sigma_{\beta})$, the ratios $(\phi,\psi)$, the $\ell_2$ penalty strength $\gamma>0$, the noise variance $\sigma_{\epsilon}^2$ and the constants $\rho = \mathbb{E}\left[z\sigma(z)\right]$, $\eta = \rm{Var}\left[\sigma(z)\right]$, $z\sim\mathcal{N}(0,1)$, characterising the activation $\sigma$. 

It provides numerical experiments confirming the validity of their formulas for finite but large dimension, and discusses the implications of the anisotropies $(\Sigma, \Sigma_{\beta})$  on the bias, variance and test error in different regimes. In particular, it shows that alignment between $\beta$ and the leading eigenvectors of $\Sigma$ reduces the test MSE, and that anisotropy can induce double-descent like behaviour in the learning curves. 
 
main_review: My main concern with this work is the total disconnection with the relevant literature in the topic. Different flavours of anisotropic random features have been previously studied in the literature: on the first layer weights [1], on the input features $x_{i}$ [2, 3], on both the target function weights $\beta$ and on the input features $x_{i}$ [4, 5], with **NONE** of these works cited in this manuscript. 

Moreover, in the isotropic case it has been proven that the asymptotic generalisation and training errors of RF in the proportional regime studied in this manuscript are equivalent to the error of an equivalent Gaussian model with correlated inputs [3, 6, 7, 8, 9]. This Gaussian equivalence was conjectured to hold also in the the anisotropic case of correlated inputs and target function weights, with extensive numerical evidence supporting it [3, 5]. Under this conjecture, the asymptotic formulas in this manuscript follow from previous works studying anisotropic ridge regression [10], and were generalised to generic convex losses and penalties in [5]. Therefore, it is no surprise that the effects of anisotropy in this work are similar to the ones reported in [11]. 

I don't think this completely voids the interest of the discussion in this manuscript: even though the formulas might not be new, it unveils some interesting phenomenology. However, I do believe it would be much more interesting if it was put in perspective with the aforementioned related literature. For instance, how does the phenomenology induced by anisotropy compare with the results reported in [1,2,4]? What insights the RMT proof provide on the extent the Gaussian equivalence holds? etc. 

[1] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari, *Limitations of Lazy Training of Two-layers Neural Networks*, arXiv: arXiv:1906.08899 [stat.ML].

[2] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari, *When do neural networks outperform kernel methods?*, arXiv:2006.13409 [stat.ML].

[3] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mézard, Lenka Zdeborová, *The Gaussian equivalence of generative models for learning with shallow neural networks*, arXiv:2006.14709 [stat.ML].

[4] Stéphane d'Ascoli, Marylou Gabrié, Levent Sagun, Giulio Biroli, *On the interplay between data structure and loss function in classification problems*, arXiv:2103.05524 [cs.LG]

[5] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mézard, Lenka Zdeborová, *Learning curves of generic features maps for realistic datasets with a teacher-student model*, arXiv:2102.08127 [stat.ML]

[6] Song Mei, Andrea Montanari, *The generalization error of random features regression: Precise asymptotics and double descent curve*, arXiv:1908.05355 [math.ST]

[7] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, Lenka Zdeborová, *Generalisation error in learning with random features and the hidden manifold model*, arXiv:2002.09339 [math.ST].

[8] Hong Hu, Yue M. Lu, *Universality Laws for High-Dimensional Learning with Random Features*, arXiv:2009.07669 [cs.IT].

[9] Pennington and P. Worah, *Nonlinear random matrix theory for deep learning*, in Advances in Neural Information Processing Systems, 2017, pp. 2637-2646.

[10] Denny Wu and Ji Xu. *On the optimal weighted $\ell_2$ regularization in overparameterized linear regression*. arXiv:2006.05800 [stat.ML]

[11] Gabriel Mel, Surya Ganguli, *A theory of high dimensional regression with arbitrary correlations between input features and target functions: sample complexity, multiple descent curves and a hierarchy of phase transitions*, Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7578-7587, 2021. 
summary_of_the_review: This work provides some interesting insights on the effects of anisotropy in the RF ridge regression setting, but would strongly benefit from a major rewriting to account for a discussion of the relevant literature in this topic.

---------------------------------------------
**Update after the discussion period**

My main concern with this work was the disconnection with the existing literature dealing with anisotropic features on the asymptotic proportional regime. At first, I was surprised the authors had missed a long line of works based on a different approach than RMT to treat the same regime (Gordon inequalities), and the corresponding Gaussian equivalence discussion in a subset of these works. However, given their engament during the discussion period and their willingness to acknowledge this gap, I believe they have acted in good faith.

The revised manuscript from 23.11.2021 (including the revised appendix A) goes in the right direction. However, I join reviewer *ot31* in the opinion that it could be further improved by:

- Including the explicit connection with [5] in the case of the square loss with $\ell_2$ penalty (which the authors said they are already working on). This would be an interesting result in itself, bridging a gap between the two approaches in the existing literature and opening a possible direction of future research consisting of exploring whether the alignment discussion in this work hold for other losses. 
- Being more explicit about the linearisation assumption (c.f. *ot31* updated review). 

Assuming these suggestions will be incorporated in the final manuscript, I am changing my recommendation to an accept.
review_title: null

Meta-review: This paper extends recent and very active literature on analyzing learning algorithms in the simplified setting of Gaussian data and model weights, with the main generalization being to allow for non-isotropic covariance matrices.  The main technical results seem to be correct and slightly novel, though reviewers feel they are not innovative or unexpected enough to stand on their own.  However, the main contributions of the paper are then to interpret these results to give phenomenological results (regarding double descent, etc.), and reviewers were unanimously happy with these. In the end, all reviewers were positive about the paper.

The largest reviewer criticisms of the paper were technical issues (ot31) and lack of context of recent literature (3RfG). Both of these concerns were mostly addressed by the revision/rebuttal. The reviewers still had specific comments on improvement, but found no major faults.
Decision: Accept (Poster)