Random Features Outperform Linear Models: Effect of Strong Input-Label Correlation in Spiked Covariance Data

Authors: Samet Demir, Zafer Dogan
Primary area: learning theory
Keywords: Random feature model, Gaussian equivalence, universality

Abstract:
Random Feature Model (RFM) with a nonlinear activation function is instrumental in understanding training and generalization performance in high-dimensional learning. While existing research has established an asymptotic equivalence in performance between the RFM and noisy linear models under isotropic data assumptions, empirical observations indicate that the RFM frequently surpasses linear models in practical applications. To address this gap, we ask, _"When and how does the RFM outperform linear models?"_ In practice, inputs often have additional structures that significantly influence learning. Therefore, we explore the RFM under anisotropic input data characterized by spiked covariance in the proportional asymptotic limit, where dimensions diverge jointly while maintaining finite ratios. Our analysis reveals that a high correlation between inputs and labels is a critical factor enabling the RFM to outperform linear models. Moreover, we show that the RFM performs equivalent to noisy polynomial models, where the polynomial degree depends on the strength of the correlation between inputs and labels. Our numerical simulations validate these theoretical insights, confirming the performance-wise superiority of RFM in scenarios characterized by strong input-label correlation.

Decision: reject
Reviewer scores: 3, 3, 6, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1729790996981

thread_type:
official_review

<thread_object>
creator: reviewer_vcz1

<content>
summary:
This paper examines the performance of random feature models (RFMs) with anisotropic input data, characterised by spiked covariance. Whilst RFMs and linear models are asymptotically equivalent for isotropic data, RFMs tend to perform better in practical applications – an observation that the authors put down to the structured, anisotropic nature of real world data. They establish a ‘universality theorem’, extending the work of Hu and Lu (2023) to prove that there exists two different activation functions with equivalent performances if the first two statistical moments of $\sigma(\mathbf{F} \mathbf{x},y)$ match. They use this result to show that higher-order polynomial models are equivalent to RFMs for spiked covariance data, and show that in particular limits for this data linear models become sufficient (roughly, when input correlations and covariance spiking becomes small). Input-label correlation is found to be crucial in determining whether RFMs outperform linear models. The authors provide detailed theoretical guarantees and experimental validation on synthetic data.

strengths:
The paper makes solid technical contributions, making a careful detailed case that, for spiked covariance data (Eq. 6), RFMs will perform better except when the spike magnitude, alignment parameter, or cosine similarity between the rows of $\mathbf{F}$ and $\gamma$ are sufficiently small (how should I interpret the last condition?). It provides a nice extension to the work of Hu (2023) beyond the linear regime, and it seems possible that this type of data structure/anisotropy might be responsible for the superior performance of RFMs in the wild. The experiments (especially, measuring generalisation error vs. number of samples, alignment and spike magnitude for different models in Fig. 3) appear to back up the authors’ central claims.

weaknesses:
1. *Applicability to real-world data.* I appreciate that the specific parameterisation of Eq. 6 is needed for analytic tractability, but can the authors provide evidence that this kind of anisotropy in real-world datasets is responsible for the performance gap between RFMs and linear models? I think that the detailed analysis on this toy model is valuable in its own right, and would be of especial interest for readers of e.g. IEEE transactions on information theory (where Hu 2023, which this work builds on, was published). But to be suitable for ICLR, I think it would be helpful to provide some evidence that similar behaviour holds on real-world data. As a straightforward example, the authors could show performance on a real dataset with the polynomial kernel, ablating over different $l$ and inspecting when performance approaches RFM. Do any properties of real-world distributions roughly corresponds to $\theta$ and $\alpha$, spike magnitude and alignment? Can we see a difference in the gap for datasets where these properties differ? Another way to better orient the work in existing ML literature would be to go further explaining the relationship to double descent, beyond the brief empirical observations around line 490, or the relationship (if any) to feature learning in neural networks. 
2. *Other points.*
- *Thm 1*. An activation function $\sigma$ and its Hermite expansion $\widehat{\sigma}$ will perform identically if we include every term since the Hermite basis is complete (line 280). Under suitable asymptotic conditions (needed to bound the contribution from higher order terms), it’s not too surprising that it becomes sufficient to consider just the first two terms. This appears to be the central conclusion of Thm. 1. I don’t doubt that the authors’ derivations are correct and can see that this is an essential corollary for the arguments that follow, but I wonder whether emphasising this as a `key advancement of this work’ (line 263) is overstated/misplaces emphasis.
- *Assumption 7*. A.7, which is required to keep the perturbed objective convex (line 742), seems to be essential to Thm. 1. Is there any evidence that this will hold in practice? This seems like an important and nontrivial assumption, needed to make claims about the generalisation error, so I wonder why it is deferred to the appendix. Perhaps it would be better to include it in the main text, and probe whether it holds in practice in the experiments.  
- *Odd activation functions*. Assumption A.6. requires that activation functions are odd. The authors empirically show that their arguments hold even when this is relaxed, e.g. for ReLU. Can the authors give some idea of where their arguments break down for non-odd activation functions (I guess around line 1006)? And why doesn’t Fig. 3 include any odd activations, e.g. tanh, given that the proof only holds in this case?

As a stylistic comment, Fig. 2a is difficult to read since the noisy linear and random feature models for $\tanh$ are overlaid. Perhaps this could be presented a little differently to make things clearer.

questions:
1. To what extent would these findings generalise to other anisotropic data settings, and to what extent are they expected to be particular to the spiked covariance model?
2. Are there any practical implications from this work for model selection, given access to a labelled dataset? 
3. Given the odd activation function assumption (A.6), do the authors see any empirical difference in results depending on the parity of $\sigma$? As mentioned above, including $\tanh$ in Fig. 3 might help answer this question.

I sincerely thank the authors for their time and efforts. It’s great to see such detailed, careful mathematical work, which is sometimes lacking in the field! If they can convince me of the broader applicability of their findings (especially, relating to real-world datasets) and clarify assumption A.7 I will be happy to raise my score.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730383190563

thread_type:
official_review

<thread_object>
creator: reviewer_qg5y

<content>
summary:
This paper explores the conditions when and how random feature models (RFM) outperform linear models, focusing on the anisotropic conditions with spiked covariance data with strong input-label correlations. Specifically, they prove that RFM performs equivalent to noisy polynomial models with polynomial degrees influenced by input-label correlation. Numerical simulations are conducted to validate the theoretical results.

strengths:
1. This paper looks good and well-written. Random features model and its connection to neural networks is of interest in machine learning theory.
2. The main contribution is its theoretical aspect, which extends the previous work in [1] to the anisotropic data structure. The universality theorem extends the understanding of RFMs, demonstrating their performance across different activation functions.
3.  Authors suggest that exploiting the non-linearities of RFMs could lead to significant performance gains in high correlation scenarios, which is interesting and confirms practitioners’ intuition.

weaknesses:
1. **Assumptions**: The author only discusses these assumptions from a technical or the math proof aspect, the practical aspects and their limitations should be clarified. And it seems hard to verify these assumptions in practice.
2. **Comparisons with previous work**:  The comparison with previous work is not enough, the proof technique in this paper is based on [1], and more comparisons and detailed differences should be remarked in the paper.
3.  **Limited experiments**:  While the focus of this paper is theory, the experiments in this paper are not adequate, only evaluated in some simulated data, while the real data application with unknown data structure is missing. The detailed setup of the experiment is not clearly presented in this paper, which should be put in a separate section.
3.  **Scope of Application**: While detailed, the focus is specifically on spiked covariance data, which may not generalize to all data structures and might not hold in all real-world scenarios.

questions:
1. While the authors say *"it is noteworthy that while ReLU (9) does not conform to the odd function assumptions stipulated in(A.6)"* in line 208, the simulation uses ReLU as an activation function and gets good results, can you explain it more intuitively?
2. The alignment parameter $\alpha$ seems to be a simple multiplication of two parameters in the structure of x and y, what is the real meaning of the input-label correlation in practice?
3. The main theorem in this paper is only an asymptotic results, i.e., equation (56), can you provide some non-asymptotic results such as the converge speed between the corresponding generalization errors $G_{\sigma}$ and $G_{\hat{\sigma}}$? 
4. While this paper is the extension to [1], and [1] considers a general loss function, can the framework from square loss extend to a general loss?

[1]  *Universality Laws for High-Dimensional Learning with Random Features*. (2023), Hu and Lu, TIT.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730681464647

thread_type:
official_review

<thread_object>
creator: reviewer_xjdd

<content>
summary:
This paper targets to address the question of "When and how does the RFM outperform linear models?". To this end, the paper considers the setting where the data are distributed according to a spike covariance model, which is more general than the isotropic setting existing analyses based on. The author(s) show that RFM can outperform linear models when there is a high correlation between inputs and labels. They also show that RFM is equivalent to noisy polynomial models, where the polynomial degree depends on the input-output correlations.

strengths:
- The paper is clearly written and motivated
- The topic of study is important, since RFMs are closely related to other machine learning models like neural networks. 
- The work extents existing studies by performing analysis on a more general data distribution, which is a step toward more general analysis.
- The theoretical analysis is derived in detail.
- The theoretical analysis is verified with numerical experiments

weaknesses:
- Is it unclear how realistic the assumptions in p.4 are. It would be helpful to verify them using real data and compare the assumptions with the ones used in related analyses
- It seems that every single equation in the paper is numbered. It would be more readable to remove the numbers of the unreferenced equations.

questions:
- How realistic is the spike covariance model? Are there any datasets that (approximately) follow such distribution?
- For the assumptions (equation 10) and (equation 11), do existing datasets satisfy them? If so, is there any references or empirical plots? Also, how does these assumptions compared to those of Hu and Lu (2023)'s?
- In (10), is the equation independent of y?
- It is stated in the literature review that RFMs are used in explaining the double descent phenomenon. Can this study on generalization performance provide information about the double descent phenomenon for data drawn from the spike covariance model?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730711177046

thread_type:
official_review

<thread_object>
creator: reviewer_rz3a

<content>
summary:
This paper studied whether, and if so under what conditions, the performance of the random feature method (RFM) is better than that of a 
 simpler linear model. The authors considered the spiked covariance data model, where the anisotropic characteristics of $x$ relax the previous work based on a more restrictive isotropic data assumption, thereby broadening the applicability of their established results. One important discovery in this paper is that in the case of a strong correlation between inputs and labels, the RFM outperforms the linear model in the sense that the latter has worse generalization performance.

strengths:
This paper solidly verified an interesting phenomenon within the framework of the random feature model that the performance of a learning algorithm has essential dependence on the input or the input-label correlation.  I find it interesting that in the case of a strong correlation between inputs and labels, the RFM outperforms the linear model.

weaknesses:
**Writing:**

 I strongly suggest that the authors include some definitions, symbols, and notations (e.g. the training and generalization errors) in the main text so that the paper can be easily followed. I think that there is significant room for improvement in the paper's arrangement.

**Typographical remarks:**

The first expectation in Eq.(10) should not be taken over $(x,y)$ since the quantity involved does not contain $y$.  Some similar concerns also appear elsewhere.

questions:
I am a bit confused about why the RFM outperforms the linear model in mathematical expression. Could the authors provide a clear comparison of their learning rates in the presence of strong input-label correlation?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730817956601

thread_type:
official_review

<thread_object>
creator: reviewer_w9rg

<content>
summary:
The paper studies a random features (RF) model trained using ridge regression on a data with a spiked covariance matrix where the covariance is aligned to the target function. Conditions under which such alignment break the gaussian university  (and hence, RF outperforms linear models) is studied.

strengths:
- The paper is well written and well organized.

- Theorem 1 is something new and interesting. Although the proof technique is not novel, and is similar to the approach of Hu and Lu, the such universality across models is not something explicitly studied before (to the best of my knowledge). It can be of independent interest.

weaknesses:
1- Although the analysis of RF models with a spiked covariance assumption for the covariates is new, unlike what is stated in line 143-144, it can still be seen as "feature-learning": One can think of spiked covariance as a model for feature learning in the first layers of a deep neural network where the second-to-last layer is random (i.e., the matrix F) and the last layer is trained with ridge regression (i.e., the vector \omega). In particular, the connections to the following papers should be discussed. These papers study layer-wise updates for a three-layer neural network.

- [R1] Eshaan Nichani, Alex Damian, Jason D. Lee, Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks.
 
- [R2] Zihao Wang, Eshaan Nichani, Jason D Lee, Learning hierarchical polynomials with three-layer neural networks

2- Ba et al, (2023); Mousavi-Hosseini et al. (2023) study a problem similar to the one studied here, but for kernel ridge regression instead of random features regression. There needs to be a detailed comparison of the results presented here to the results of these two papers

3- What happens when we set \beta = 1/2 in Assumption A.2? Also, as the paper studies squared losses, there is probably no need to make the odd activation function assumption (A.6); there can be a easier direct proof of universality using Lindeberg exchange without the need to use the results of Hu & Lu.

4- A precise characterization of the training/test errors will improve the quality of this work significantly.

questions:
Please see the weakness section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730888247278

thread_type:
official_review

<thread_object>
creator: reviewer_ormf

<content>
summary:
This work examines Random Feature Models (RFMs) under the assumption of spiked covariance for the input data. The authors establish a Gaussian Equivalence (GE) principle for the errors achieved by RFMs in this setting by revealing an equivalence with noisy polynomial equivalent models. When the alignment between the spike and the target is small, the classical GE principle holds, but for larger alignments, an extended version is required. The analysis is supported by numerical simulations that validate the theoretical findings.

strengths:
The paper is nicely written and the authors provide a nice introduction to the related literature.

weaknesses:
The main weakness for this work is the strong relationship with already publsihed works, namely [Moniri et al. 2024, Cui et al. 2024]. The authors overclaim the depth of their contribution in different parts of the manuscript.

questions:
My main concern for the present submission is the lack of clear elements of novelty that do not meet the high ICLR standards. 

As the auhtors correctly report, (Moniri et al. 2024) have already provided the rigorous Random Matrix Theory characterization when the spike appears in the weights of the Random Feature map. These results have been extended up to the maximal learning rate scaling regime by (Cui et al. 2024) which describes the emergence of a fully non-polynomial equivalent feature map in this regime. 

I fail to see notable differences between the setting of the present submission and the one in the above-mentioned works. 

In different parts of the manuscript, the authors significantly overclaim their contribution. For example, on page 5 "new universality theorem", "this result is notably more general than previous findings". Could the authors clarify what are the novel aspect in their contribution and distinguish them clearly from the results in (Moniri et al. 2024)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732457352479

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Area Chairs and Reviewers,

Thank you for your detailed feedback on our work. In response to reviewers' feedback, we conducted new experiments on the CIFAR-10 dataset to evaluate the practical relevance of our findings. The new experimental results confirm our claims about the equivalence to the noisy polynomial model and the impact of input-label correlation. 

Note that we revised our paper during the rebuttal period and highlighted the revisions in blue.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733312461518

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Discussion

comment:
Dear Reviewers, AC, and SAC,

We thank you for your thorough evaluation and insightful comments on our manuscript. Below, we summarize the discussion and our responses:

### Key Concerns Raised:
1. **Applicability to Real-World Data**: 
   - Most of the reviewers expressed concerns about the practical relevance of our theoretical assumptions, particularly the spiked covariance model.
   - To address this, we conducted additional experiments on CIFAR-10 (binary classification: automobiles vs. airplanes) during the discussion period. These experiments demonstrated that our theoretical findings (e.g., equivalence of RFMs to noisy polynomial models) hold in real-world settings with structured data. These results were included in the revised manuscript.

2. **Novelty Compared to Existing Literature**:
   - Reviewers ormf and w9RG highlighted the need to better differentiate our work from prior studies (e.g., Moniri et al., 2024; Ba et al., 2023).
   - We clarified that our work goes beyond prior studies by focusing on the role of **input-label correlation** and its effect on model performance. We showed that RFMs outperform linear models under conditions of strong input-label correlation, a perspective not covered by the cited studies.
   - We also addressed the mathematical novelty of our approach, particularly the use of Lindeberg’s method to extend Gaussian equivalence results to anisotropic data.

3. **Clarity and Readability**:
   - Reviewers RZ3A and vcz1 suggested improving the presentation, such as including Assumption A.7 in the main text, revising figure layouts, and simplifying notation. 
   - In response, we updated figures (e.g., improved visibility in Fig. 2a) and clarified notations. Also, we will discuss Assumption A.7 in the main text in the final version of the paper.

### Remaining Concerns:
- **Reviewer ormf**: Maintained their score due to perceived limited novelty despite detailed clarifications on the distinctions from prior work.
- **Reviewer w9RG**: Argued that the connections to prior kernel regression work reduce the novelty. We respectfully disagreed, emphasizing that our focus on random feature models and input-label correlation is distinct.

### Outcomes:
- Reviewers RZ3A, xJdD, and vcz1 raised their scores after reviewing our responses and additional experiments.
- Despite maintaining their score, Reviewer QG5Y acknowledged the theoretical and practical insights of the work as strengths in their review.
- Reviewers ormf, and w9RG maintained their scores, citing limited novelty despite acknowledging our detailed responses. 

### Conclusion:
The discussion reflects recognition of the technical rigor, novel insights, and practical relevance of our work. We believe the revisions and responses have significantly addressed key points. 

Thank you for your time and consideration.

Best regards.
</content>
</thread_object>

</thread>


Metareview:
metareview:
(a) Summary:

The paper explores the conditions under which Random Feature Models (RFMs) outperform linear models in scenarios with spiked covariance data and strong input-label correlation. The authors demonstrate that RFMs can exceed linear models by leveraging this correlation and establish an equivalence between RFMs and noisy polynomial models, with polynomial degree determined by the input-label correlation. They present a universality theorem to support their claims and validate their results with numerical experiments.

(b) Strengths:

The paper addresses an important and timely topic in machine learning theory, providing insights into the advantages of RFMs under structured data conditions.
It introduces a new perspective on how input-label correlation influences model performance, which is a valuable addition to the existing literature.
The use of spiked covariance as a model enriches the theoretical analysis and broadens applicability to realistic datasets.
Numerical simulations are consistent with the theoretical findings.

(c) Weaknesses:

Novelty: Despite the efforts to differentiate the work, the contribution feels incremental relative to prior studies, such as those by Ba et al. (2023) and Mousavi-Hosseini et al. (2023), which addressed similar phenomena in kernel regression contexts. The parallels to existing studies raise questions about the novelty of the results.
Practical Relevance: While theoretical results are well-grounded, the assumptions about spiked covariance data and strong alignment between input and target seem restrictive and may limit real-world applicability.
Empirical Evaluation: The experimental validation lacks breadth, relying heavily on synthetic data and a single dataset (CIFAR-10 binary classification). This undermines the claim of practical relevance.
Clarity and Scope: Reviewers noted room for improvement in presentation, especially in defining key assumptions and notations, and explaining connections to related works.

(d) Decision:

The decision is to reject the paper. While the paper contributes to understanding RFMs, the incremental nature of the contribution and the limited empirical validation weigh against its acceptance. I encourage the authors to address these issues in a future submission by expanding empirical validation to real-world datasets, providing stronger distinctions from related works, and improving the clarity of assumptions and their practical implications.