Learning curves for deep structured Gaussian feature models

Summary

This work focuses on the generalization performance of models utilizing multi-layered Gaussian random features. The study evaluates the impact of feature anisotropy, which is often overlooked due to common assumptions that features are generated using independent, identically distributed Gaussian weights. The findings demonstrate that correlations within the first layer of features can enhance generalization, but any structure beyond the initial layer proves generally detrimental. These insights provide valuable perspective on how weight structure affects generalization in random feature models with linear activations.

Strengths

1. The paper is well-written and the theorems are constructed with a solid use of mathematical rigor. 2. The idea is interesting, where how correlation between the rows of the first layer of features can improve generalization is a new theoretical result, which could be very interesting to the community. 3. Visualization and numerical experiments are conducted along with the theoretical results. For instance, the experiments in Figure 2 nicely summarize the theoretical finding, implying the bounds are generally non-vacuous.

Weaknesses

1. The discussion to previous works are limited. There are many RFM works recently. Although they may focus on a different perspective, such as inductive biases or behavior under SGD, but it would still be valuable to briefly discuss the relationship to these works. 2. At the first glimpse, it is hard to parse how the structure can improve the generalization in some of the theorem or corollary. In particular, there are many constants and it is non-trivial to interpret their numerical property. Adding a simple sentence after the theorem to briefly summarize it could help reader better parse the results.

Questions

1. Would figure 2 vary a lot if we modified the number of data points? In particular, would the theory behaves differently under over-parameterized or under-parameterized regime? 2. The theorems analyze the asymptotic learning curve, where the numerical experiments are conducted under a relatively small number of datapoints. Will this cause a gap between the theory and the experimental results? 3. The constraint on the norm of the teacher vector (line 142) is not very intuitive. Can you briefly explain this? 4. Does the result approximately hold for setting without closed form such as Lasso-regression?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors did discuss the limitation and there is no obvious negative societal impact.

Summary

The authors investigate the exact asymptotics characterization of deep Gaussian feature models. They analyze depth-L linear Random Feature Models where the feature matrix is built as a product of L factors, each drawn from a matrix Gaussian distribution. Thanks to the replica method, they compute the generalization error learning curves for the ridge regression estimator. They study the influence of the weight structure on the test performance, presenting numerical experiments backing up the theoretical claims.

Strengths

The authors consider the interesting case of deep RFMs with weight anisotropy. They compute the performance for both ERM and Bayes estimators in the high-dimensional proportional regime. They present numerical simulation and release the code to reproduce the main experiments.

Weaknesses

The primary weakness of this paper is the clarity of the presentation, more precisely I believe more effort should be put into guiding a non-expert reader with a more detailed introduction, and by creating connections between the different main results presented. See below for a more detailed discussion.

Questions

1) The abstract is very concise. I would expand this section to help guide the reader, e.g., mention that you focus on interpolators, describe what exactly solvable model for anisotropic spectra you considered (power law), briefly explain that the proposed formalism allows as well to cover analysis of Bayesian setting. 2) On a similar note to the first point, the introduction section is too short. There is little explanation of why RFMs are interesting, e.g., it is not mentioned explicitly their relation with the limiting kernel. The analysis of power-law spectrum decay is standard in the kernel literature and goes under the name of source-capacity conditions [1]. There is no mention of the technique which is going to be used for the computation (the replica trick). Please mention why the interpolating (ridgeless) regime is interesting, with associated reference, e.g. ref [5] in the main text. There is no citation to previous work on the Bayesian settings, the reference [42] mentioned in the conclusion could be introduced as well there. A justification should be given for the Gaussian data assumption, e.g., by referring to the extensive line of work on the Gaussian Universality property, see [2]. 3) Please before introducing the preliminaries and the setting on page 2, include a summary of your main contributions. 4) Why is it untractable to study the $\lambda > 0$ case? A numerical investigation of the behavior at finite regularization I believe would enhance the manuscript, if the problem is not untractable. If this is the case, please mention why in the main text. 5) The results are nice but I believe some work is needed to glue them together. The authors may think to move in the appendix some proof and substitute them with explanations in plain words to help the reader build intuition, as the notation is quite heavy. 6) In Sec. 4 remind the reader in which theorem are defined $(\alpha_{min},\mu)$. 7) Can the authors explain in more detail why the exponents $(\omega_1,\dots,\omega_L)$ do not affect the scaling laws if they enter only with the sum (Sec. 5)? [1] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm, 2007. [2] Montanari, A. and Saeed, B. N. Universality of empirical risk minimization, 2022.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

1 poor

Contribution

3 good

Limitations

The limitations are addressed in the manuscript.

Summary

The authors introduce correlations to weights of linear RFMs and study the generalization error. This is done under the assumption data follows Gaussian distribution and linear model. The authors provide a general expression for the limiting generalization error that recovers results from previous works as special cases.

Strengths

The present results present appear to be very general and well linked to previous research. The introduction and preliminaries section are relatively clear.

Weaknesses

The proofs could be included in the supplementary material which would allow for more text interpreting the results and providing the intuition for their importance. The authors should explain the solutions (15) and (16). The authors should explain in more detail their result, i.e. (18). The authors should be more explicit about the notation, e.g. carefully check the use of /tilde or $\kappa_0$. In my opinion, the clarity of the paper could be improved.

Questions

Do solutions (15) and (16) always exist? Can you elaborate on their form? Do you have any intuition how quickly convergence to (13) happen? Do you have any intuition about the limits when p is fixed?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A

Summary

This work studies the asymptotic risk of deep linear random features models (RFMs), with a high dimensional analysis based on the replica method. It extends previous work on this topic by relaxing the standard i.i.d assumption for the Gaussian weights in each layer. Several consequences of their anaysis are discussed: (i) several known results in linear regression, isotropic models, infinite width RFM, are recovered as special cases ; (ii) it is shown that feature anisotropy is detrimental, in the sense that the risk of the isotropic model lowerbounds the risk of the general model ; (iii) it is shown that feature anisotropy does not affect the scaling laws of the risk ; (iv) going beyond ridge regression, the analysis allows for the derivation of the risk of the Gibbs estimator, where feature anisotropy is shown to be generally beneficial (resp detrimental) for large (resp small) prior variance.

Strengths

* Sound piece of theoretical work. * Relaxing the standard feature isotropy assumption seems to be a natural extension of the recent line of work on deep RFMs. Since the learned features of deep learning models often exhibit complex correlations, it could also provide insights on the effects of feature learning of deep networks in a controlled setting. * The paper is very clearly written and enjoyable to read.

Weaknesses

My main reservation regarding this paper is related to its scope -- and the significance of the results. * While the analysis presented in the paper is novel and fills a gap in the literature by relaxing a standard assumption, the technical innovations appear to be somewhat limited and incremental compared to previous work, such as References [28]. I believe some related references were missed, see e.g., Mel & Pennington (ICLR 2022) -- which also investigates the effect of feature anisotropy in random feature regression. I understand the main technical difference is that they work with shallow models with a Gaussian feature matrix, whereas the current paper work with Gaussian products (one may argue that the first setting is sufficient to capture the effects of anisotropy in RFMs). * The insights gained from this analysis also seem to have certain limitations. For instance, considering that in setting (13), the risk is studied in expectation over rotation invariant Gaussian matrices $Z_\ell$ at each layer, the result of Section 4 on the optimality of the isotropic case appears rather unsurprising to me. Moreover I believe that the studied setting may not allow for significant insights into representation learning (not that the authors claim otherwise, but this is one of the motivations for the work i.m.o). For example , the assumption of Gaussians requires layerwise independence, while in feature learning scenarios, one would expect learned features in different layers to be correlated with each other -- and with the underlying data structure. So from that poinf of view, I feel the assumptions underlying this work are still quite restrictive. On a minor related note, the general-sounding statement found in Section 1, "these results are consistent with the intuition that representation learning at only the first layer of a deep linear model is sufficient to achieve optimal performance" is a bit puzzing, as it seems to contradict known results in the topic, e.g. those on the implicit sparsity bias in deep linear networks (which requires representation learning in multiple layers, see e g., Woodworth et al, 2020). **References** Mel & Pennington (ICLR 2022). Anisotropic Random Feature Regression in High Dimensions. https://openreview.net/forum?id=JfaWawZ8BmX. Woodworth et al, 2020. Kernel and rich regimes in overparametrized models, https://arxiv.org/abs/2002.09277.

Questions

* As the authors mention in the conclusion, Gaussian equivalence theorems could potentially extend these results to more general activations (and losses). Including this extension would considerably increase the paper's scope. Could the authors provide a bit more details about the extent of the technical gaps to be filled to achieve this ? * Could the authors comment on the comparisons with the results of Gerace et al, which seem to address the case of general RFMs with any (fixed) feature matrix F satisfying the balance condition (1.7)? **References** Gerace et al, 2020. Generalisation error in learning with random features and the hidden manifold model. https://arxiv.org/pdf/2002.09339.pdf

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Adequately acknowledged.

Summary

The paper derives the learning curves (generalization error vs number of samples) for random linear deep networks with Gaussian weights with non-trivial correlations. The correlations at the first layer control the performance of those networks, while all other layers (possibly of different widths) are equivalent to a single layer of minimal width among them.

Strengths

* Quality: the main result that in the noiseless case, correlations at the first layer improve performance, while correlations in the other layers degrade it (Lemmas 4.1 and 4.2) is interesting (and is not fully captured by the summary “representation learning at only the first layer of a deep linear model is sufficient to achieve optimal performance”). The additional result for generalization error of scale-free correlations, which converge with previously known results for uncorrelated weights, is very nice.

Weaknesses

* Quality: it is not justified why the authors focus on the “ridgeless limit”; can’t the minimal generalization error be achieved at a finite value of lambda? Why not? The model studied seems to collapse for large alpha0 (figure 1 a vs b), but the phenomena is not explained. * Clarity: as a theory-heavy paper, the authors could have done a better job in keeping the notation clear. p was not properly defined; I assumed it was the number of samples. The spectral moments generating function from eq 15,17 is introduced only at eq 19. The functions (or scalars) phi and phi bar (evaluated at k0) are not introduced. The important “expectation with respect to the limiting spectral distribution” is not properly defined (“is defined in eq X of the SM” would have been fine as well). * Significance: the results of sections 4 and 5 seem to suggest the depth of the network does not contribute anything, as only alpha_min enters the results. This is probably a limitation of the linear model, and thus the discussion on the behaviour of deep networks seems empty. Also, the focus on the noiseless case makes it hard to extrapolate what (if any) of the results hold under noise at an optimal finite lambda.

Questions

* Can the minimal generalization error be achieved at a finite lambda value? * Is there any effect of depth when alpha_min is kept fixed?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors are clear about the limitations of their work, where only the behaviour for the ridgeless case is studied (and hence the behaviour under noise is not well understood), and only linear networks are studied (and hence the depth does not play an effect), with random initialization (and hence there is no training).

Response

Thank you for your explanation which partially addresses the raised concerns. Overall, I think the proposed ideas are interesting, and I will keep my score.

Thank you for the rebuttal

I sincerely thank the authors for the rebuttal. I think that the main weakness is the clarity in the presentation and that the promised changes will strongly help the readability of the text. I would like to keep my score as in the original review.