Dimension-free deterministic equivalents and scaling laws for random feature regression

Summary

This paper provides a non-asymptotic bound (Theorem 3.3) on the test error of random feature ridge regression (RFRR) using dimension-free (in the sense of the feature space) deterministic equivalents, which are the solutions to some self-consistent equations, under a concentration assumption (Assumption 3.1) on the features. As a result, they recover (Corollary 3.5) the deterministic equivalents result on the test error of kernel ridge regression (KRR) from previous literature, and they prove the exact decay rate of the neural scaling law (Corollary 4.1), filling the gap from previous literature.

Strengths

This paper improves the results from previous literature in multiple ways: non-asymptotic over asymptotic bounds [Loureiro2022], RFRR over KRR [Misiakiewicz2024], more precise neural scaling law [Rudi2017, Cui2022]. The phase diagram (Figure 2) is novel, as far as I know, and it offers great insights for the test error in RFRR. Reference: - *Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with a teacher student model. Journal of Statistical Mechanics: Theory and Experiment, 2022(11):114001, nov 2022.* - *Theodor Misiakiewicz and Basil Saeed. A non-asymptotic theory of kernel ridge regression: deterministic equivalents, test error, and gcv estimator, 2024.* - *Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.* - *Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: the crossover from the noiseless to noisy regime. Journal of Statistical Mechanics: Theory and Experiment, 2022(11):114004, nov 2022.*

Weaknesses

My main concern, however, is the significance of the theoretical contribution of this paper. From the first sight, this paper is merely an extension of the paper [Misiakiewicz2024] with same techniques of deterministic equivalents. Also, the result holds only under the strong concentration Assumption 3.1. As mentioned in the paper (line 119-121), I think that this paper could have been more significant if Assumption 3.1 had been relaxed in this paper.

Questions

Regarding the above comments, 1. Could the authors explain more how different it is to implement the deterministic equivalents techniques in RFRR than in KRR? 2. How difficult it would be to relax Assumption 3.1 as in [Misiakiewicz2024]? And what datasets and random feature model could satisfy Assumption 3.1 empirically? 3. Despite not essential, but it could help the readers a lot if the authors could explain more on the quantities and their intuitions in the paper, like Eq (21-27). From my point of view, Theorem 3.3 is not the easiest to read. Besides the questions, I found some potential typos in the appendix: - A paragraph (line 536 - 540) seems misplaced: they should be directly after Eq (50). - The equation below line 587 should be $\mathbf{f}\_j = ((\xi\_k\phi\_k(\mathbf{w}\_j)))\_{j\geq1}$ instead of $\mathbf{f}\_j = ((\xi\_k\psi\_k(\mathbf{w}\_j)))\_{j\geq1}$. - a ``\rangle`` is missing in the equation under line 590: it should be $\sigma(\langle \mathbf{w}\_p,\mathbf{x}\_i \rangle)$ instead of $\sigma(\langle \mathbf{w}\_p,\mathbf{x}\_i )$.

Rating

6

Confidence

4

Soundness

4

Presentation

3

Contribution

2

Limitations

This paper is theoretical paper and the authors have addressed the assumptions and conditions explicitly in the paper.

Summary

EDIT: updated my score after rebuttal. The authors investigate the excess risk in random feature ridge regression. They give a deterministic expression that approximates the excess risk, with a controlled relative error. The dependence of the deterministic "equivalent" w.r.t. to key quantities in the problem is examined.

Strengths

* Understanding the generalization ability of simple models is important, especially as our intuition of generalization has been challenged by recent results on overparametrized neural networks. Therefore, the paper is potentially impactful. * The proposed result generalizes and refines a string of previous results in a single deterministic equivalent, and the dependence of this equivalent to problem parameters yields interesting conclusions, e.g. on the minimal number of features needed to achieve a statistically satisfying rate. * There is clearly a lot of work that has gone in obtaining such a general result.

Weaknesses

## General comments My main concern is the format of the paper, which I think is more suited to a mathematical-minded ML/stats journal than a conference. The main paper is very dense but misses key details such as proofs or proof outlines, while the full proof of the main result is 28 pages long, which makes the full paper 50 pages long (i.e., appendices included). It is not reasonable to expect reviewers to go through such a long technical proof in the context (short time span and heavy workload) of NeurIPS reviews. As a journal submission, I would have the time required to go through the proofs and get to the heart of the proposed (interesting) result. ## Major 1. Eqn 4: don't you want $\epsilon$ to be zero-mean as well? 2. p3 L104; "we define wlog $\mathcal{V} = Im(T)$": if this is indeed a definition, I don't see why we need to add "wlog". If this is a statement about the image of $T$ being the whole of $\mathcal{V}$, we need to define $\mathcal{V}$ beforehand. 3. Eqn 13 is only true in $L^2(\mu_x)$ so I would avoid involving $\mathbf{x}$ in the statement of the equation, which suggests you mean a pointwise equality and requires a quantifier. If you actually meant a pointwise equality, then this should be explained, and further assumptions should likely be made on $\varphi$. 4. Assumption 3.1. I am unsure what is meant by an infinite matrix $A$. Especially when one needs to talk about the trace of $\Sigma A$, so that I assume we want to guarantee that $\Sigma A$ is a trace-class operator. Can you rephrase the assumption in terms of operators? Similarly, the Frobenius norm for operators should be defined. 5. p4 L117: can you give more details on why cases 1) and 2) are covered by your assumption? Same for p4 L128: can you detail why these power decays satisfy Assumption 3.2? 6. Definition 1: For easier reading, I would define $\nu_1, \nu_2$ first, then $\Upsilon$, and then only $B$ and $R$. Otherwise, the reader has to wait until Eqn (24) to understand Eqn (18), which requires a lot of buffer memory from the reader's brain. 7. p5 L156 is there an implicit dependence on the feature map dimension? Can you explain where? 8. Figure 1: I would keep the caption short and descriptive, and move the definition of the data generating process to the main text. This would allow to explain more, for instance, what you mean by $v$ has a fixed overlap with the teacher vector". 9. The bibliography needs to be harmonized. There are many missing journal/conference names (if it's an arxiv preprint, say so and give the arxiv number), and a few initials mixed with full first names. 10. p9 A short discussion section summarizing the main points and limitations of the paper would be a good addition. ## Minor * p1 L23: here and in the rest of the paper, you use the notation $\mu_w(\mathcal{W})$ to indicate that $\mu_w$ is a probability measure on $\mathcal{W}$. I would say that is not standard notation, and I would rather keep $\mu_w(\mathcal{W})$ for the measure of the whole space $\mathcal{W}$, i.e. 1. * p1 L25: I think $\sigma$ has not been defined yet. * p2 L46 "demystifying phenomena such as double descent and benign overfitting". I would give a reference for each concept. * p2 L55 no need to boldface "our main contributions". * Eqn 9: I would write $\mathrm{Var}$ instead of $\mathrm{Cov}$. * p4 L127: settings * p4 L135: what is a "self-consistent" equation? * p5 L142 "we use $a_i = '*'$ to denote [...]": I don't understand the exact meaning of this statement. * Eqn 30: I would remind the reader that $R_{n,p}$ has been defined in Definition 1. * p5 L151 "in place" reads strangely. "In order", maybe? * p5 L152 what does "fully" mean in "fully non-asymptotic"? * p6 L171 what do you mean by "single-index"? * p6 L183 span, not spam! * p6 L183 infinite-dimensional * p7 L216 understanding * p8 L255 decays * Figure 3 is too small to read.

Questions

* Item 4 in my major comments.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

This is fundamental work and does not have any immediate potentially harmful impact.

Summary

Prior work on random feature (ridge) regression study the test error in the high-dimensional asymptotic. However, ideally one would hope for a non-asymptotic deterministic characterization of the test error. In this paper, the authors tackle this problem and show that under a concentration assumption, the test error is well approximated by a closed-form expression that only depends on the feature map eigenvalues. They use this result to study various problem in random features regression.

Strengths

- This paper rigorously solves an important problem in the analysis of random features regression. I think Theorem 3.3 will be of independent interest as well. - The main result of the paper does not require the random regression coefficient assumption and hold for deterministic beta_star. - Theorem 3.3 has a very clean form. The bounds in Theorem 3.3 are multiplicative. Thus, they scale correctly with the risk. Taking particular limits (e.g., p \to \infty or \lambda \to zero), we easily recover already known phenomenon. - The authors derive sharp excess error rates under power-law assumptions and provide a tight result on the smallest number of features needed to achieve optimal minimax rate. - The proofs seem correct and rigorous. All in all, I really enjoyed reading this paper and I recommend acceptance.

Weaknesses

I suggest the authors expand the discussion around Assumption 3.1 and provide more detailed examples for which this assumption holds.

Questions

The paper is very well written and I have no particular question.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

The authors have adequately addressed the limitations.

Summary

The paper studied the non-asymptotic generalization error for random feature ridge regression (RFRR) models. By considering the eigendecomposition of random features with respect to data distribution and weight distribution, the authors proved a feature-dimension-free deterministic equivalence for the generalization error of RFRR, where the sample size and number of features bound the approximation error. From this deterministic equivalence, fixing the number of data points, this paper presented the minimal number of features for the optimal decay rate of the excess risk of RFRR when considering power law assumptions for data covariance and target. This analysis provides a clear picture of the generalization error scaling law for source and capacity conditions of RFRR.

Strengths

1. The paper is well-motivated, and the mathematics appears correct to me. The writing is clear, and the authors do a good job of presenting results with many discussions and comparisons of related works. 2. The authors provide various empirical simulations to justify the theorems, including random synthetic data, real-world data, random weights, and weights trained by gradient descents. This offers more insights into theoretic results and the generality of the results in this paper.

Weaknesses

1. One concern is how we can check Assumptions 3.1 and 3.2 for specific nonlinear feature models with some concrete data and weight distributions. The results of this paper rely on the eigen decomposition in (11) but can we get some specific examples of eigenvectors $\psi_k$ and $\phi_k$? For instance, in a classical high-dim statistics setting, if we consider a nonlinear RFRR model with i.i.d. sub-Gaussian dataset and weight matrix and a certain nonlinear teacher model, can we justify Assumptions 3.1 and 3.2 in this case? 2. There should be more clarification for the notations and conditions of the main results, Theorem 3.3. For instance, what would be the meaning of (25-27) and (28-29)? Are these bounds and approximation rates necessary or due to some technical reasons? If we apply the bounds in (28-29) to (32) for the error bound of the deterministic equivalence, the bound of $\mathcal{E}(n,p)$ seems to be loose and cannot get $\tilde O(n^{-1/2}+p^{-1/2})$.

Questions

1. In the simulation, the authors provide an empirical diagonalization method for estimating $\Sigma$ and $\beta$ by considering $N=P\gg n,p$ and computing the eigendecomposition of the empirical feature covariance. Is there any theoretical guarantee for this approximation? This approximation seems to indicate that we can still apply the asymptotic results for empirical feature covariance under the proportional or polynomial scaling regime for $n, p$, e.g. [Mei and Montanari, 2022, Gerace et al., 2021, Dhifallah and Lu, 2020, Hu and Lu, 2023, Hu et al., 2024], to analyze the deterministic equivalence and the generalization errors. 2. In (10), do you need to assume the subsets $\mathcal{X}$ and $\mathcal{W}$ in $\mathbb{R}^d$ are compactly supported? 3. Typo (7): $h_*\to f_*$ 4. What is $\nu_2$ in (17) in Assumption 3.2? You did not introduce this notation until Definition 1. 5. You did not introduce intrinsic dimension around (25). 6. In line 147, why do you assume assumption 3.2 again? 7. Line 183, typo: spam; Line 230: (37) $\to$ (38)? 8. In Definition 3, typo in the definition $r_\Gamma(k)$: $p \to q$. Line 546, $\Sigma\to \Gamma$. 9. In Theorem A.2, what is the typical order of $\rho_\lambda (n)$? From (53), we cannot claim the error term in (54) will be vanishing. 10. How do you prove the last equation on page 16, for the upper bound the $||S_i||_{op}$? Can you explain it? And in the same proof, how do you apply the matrix Bernstein inequality for infinite dimension $\tilde S$? 11. Below Line 587, typo in $f_j$: $j\ge 1\to k\ge 1$; typo in (60): $A\to B$. 12. In Line 634, you consider $\eta_*\in (0,1/4)$ but in the main results, you have $\eta_*\in (0,1/2)$. Can you clarify it? 13. How do you prove $||\hat \Sigma_F||_{op}\ge 1/2$? 14. Below Line 800 and in Line 1033, you use $G$ to denote the resolvent which has been used as the data feature matrix as well.

Rating

6

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

N/A

Official Comment by Reviewer b7dx

Many thanks for the authors' response and explanations. The rebuttal has resolved most of my questions. I tend to accept this paper and expect the authors to include more discussions in the revision, especially for Assumption 3.1 and Remark 4.1.