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

We thank the reviewer for their appreciation of our work and for the suggestions which will help to improve it. The typos in the appendix raised in the review will be corrected in the revised version of the manuscript.

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.

Indeed, our paper uses the deterministic equivalents for the functionals listed in Theorem A.2 from [Misiakiewicz, Saeed, 2024]. However, we politely disagree that this is ``merely an extension with same techniques''. It requires a significant amount of work to ensure that we can indeed achieve multiplicative bounds that applies to the regime with optimal rates under source and capacity conditions. As noted by reviewer Gqjy, the proof is 28 pages despite not repeating previous results.

We further emphasize that it was not clear a priori that such a multiplicative bound---with optimal rates---for general $n$ and $p$ is achievable. Indeed, compared to the kernel case, the covariance over $z$ is a finite-rank random matrix $FF^T/p$, which does not concentrate (in particular, it has rank $p < n$ in the underparametrized case) and the model presents a double descent with a diverging peak at $n = p$ as $\lambda \to 0$.

[Misiakiewicz, Saeed, 2024] only considers kernel ridge regression, while we consider random feature ridge regression which involves many more terms. In particular, the following parts only appear in the RF case:

• Controlling the covariance matrix $\hat \Sigma_F$ of the feature $z$ (Lemma B.2).

• Showing concentration of the fixed points to the deterministic fixed point of Definition 1 (Proposition B.4, which requires a careful perturbation analysis and a uniform bound).

• While the deterministic equivalent over $z$ corresponds to the same computation as in the kernel ridge regression case with covariance $\hat \Sigma_F$ (with an added projection term), the deterministic equivalents over $F$ involves many more terms that are not covered by Theorem A.2. These terms need to be decomposed carefully in order to show that we can indeed obtain multiplicative bounds with optimal rates and control the dependencies on $\Sigma,\lambda,\gamma_+$.

Also, the result holds only under the strong concentration Assumption 3.1.

We refer the reviewer to the general rebuttal for a more detailed discussion.

Besides Theorem 3.3, our paper offers the following contributions: 1) the statement of the general non-asymptotic deterministic equivalents which unifies existing asymptotic predictions, 2) the complete and precise decay rates under source and capacity conditions, which improves over [Rudi, Rosasco, 2017], 3) numerical simulations in various settings that show that Theorem 3.3 apply beyond its formal assumptions.

As discussed above and in the response to reviewer b7dx, we consider Theorem 3.3 to be an interesting and challenging result to obtain even under Assumption 3.1. It is the first non-asymptotic (dimension-free) result with multiplicative approximation bounds for random feature regression. We acknowledge that Assumption 3.1 is restrictive, but such assumptions are common in the theoretical literature (e.g., it corresponds to the assumption in [Cheng, Montanari, 2022] for the infinite dimension case, or to [Bach, 2023] for linear asymptotics).

We consider relaxing this assumption to be an important direction, which we leave to future research. For instance, we believe that the approach in [Misiakiewicz, Saeed, 2024] could be applied here (see response below). However, this would significantly increase the complexity of the proof---which is already 28 pages---while marginally contributing to the main message of the paper (Definition 1 and Corollary 4.1).

• 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?

For the first question, [Misiakiewicz, Saeed, 2024] considers a relaxation of Assumption 3.1 by dividing the features into a low and a high-frequency components. The low-frequency features follow a Hanson-Wright type inequality similar to Assumption 3.1, while the high-frequency features are only assumed to be nearly orthogonal. Such a relaxation can be applied in the case of random feature ridge regression to both $(\psi_k)$ and $(\phi_k)$. However, note that the random feature matrix corresponds to the product $FG^T$ and therefore it is not straightforward to separate these two parts. Although we believe an analysis differentiating between the underparametrized and overparametrized regimes will work, we believe that it is beyond what can be expected from a conference paper.

See general rebuttal for a discussion of the second question.

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.

We will add a longer discussion on these terms in the revised version of the paper.

We thank the reviewer for their appreciation of our work and for the suggestions which will help to improve it. The issues (9, 10) and the typos raised in the minor comment section will be addressed and/or corrected in the revised version. Due to the space constraint in the rebuttals, will answer your questions in the "Minor" in a comment.

Below, we address the "General" and "Major" comments and questions.

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.

Random feature is a major research topic for the theory community at NeurIPS, with many papers about it every year. Our work is in direct dialogue with previous NeurIPS works, e.g. [Rahimi and Recht 2007, 2008; Rudi and Rosasco 2017; Cui et al. 2021; Xiao et al., 2022], and therefore our choice of venue simply reflects the interest we believe our results can rouse in this community.

Moreover, the main message of this work is simple, and we believe is well conveyed in 9 pages: we derive a deterministic, non-asymptotic characterization of the test error which generalizes previous results and can be used to derive new insights, such as the different power-law scalings of interest to both the kernel and neural scaling law communities. Indeed, due to the generality of the results the proof involve long and technical arguments with are left in the Appendix, but we politely disagree that this stands out from the NeurIPS practice, see e.g. proofs in the Appendices of [Rudi and Rosasco 2017; Loureiro et al., 2021; Xiao et al., 2022].

Eqn 4: don't you want $\epsilon$ to be zero-mean as well?

Indeed, the noise is intended to be zero-mean. We will explicitly state this assumption in the revised version of the paper

p3 L104; "we define wlog $\mathcal{V} = {\rm Im}(\mathbb{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 $\mathbb{T}$ being the whole of $\mathcal{V}$, we need to define $\mathcal{V}$ beforehand.

Indeed, we will remove ``wlog'' here, as we simply define $mathcal{V} = {\rm Im}(\mathbb{T})$.

Eqn 13 is only true in $L^2(\mu_x)$

Following the reviewer's suggestion, we will avoid any ambiguity by rewriting $f_\star = \sum_{k\geq 1}\beta_{\star,k}\psi_k$ in the revised version.

*Assumption 3.1. I am unsure what is meant by an infinite matrix $A$.

The matrix notation $A\in\mathbb{R}^{\infty\times\infty}$ is here used to represent a linear operator $A$ acting on an infinite-dimensional Hilbert space $\mathcal{H}$. In particular, given a basis ($\psi_k$) of $\mathcal{H}$, we define the $kk'-$th element of $A$ as $\langle \psi_k, A \psi_{k'}\rangle_{\mathcal{H}}$. The expression $Tr(\Sigma A)<\infty$ ensures that $\Sigma A$ is trace-class, as correctly stated by the reviewer. More generally, the infinite dimensional matrices that appears in the paper (e.g., $\Sigma$, $F^T F$, or $ff^T$) are understood to be linear operators $\mathcal{H} \to \mathcal{H}$.

Following the reviewer's suggestion, we will rephrase Assumption 3.1 in order to improve its clarity and add a remark on our notations in terms of linear operator for completeness.

"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?"

Assumption 3.1 is a slight relaxation of Hanson-Wright inequality, which is satisfied by 1) and 2), see [Adamczak, 2014] (note that the inequality is stated in finite dimension, however it also holds for $d = \infty$, as noted in Remark 2.1 in [Cheng, Montanari, 2022]).

Concerning the second part of the question, we consider the power decays $\xi_k^2 \asymp k^{-\alpha}$ and $\beta_{\star,k}\asymp k^{-\beta}$. Since we are considering square-integrable target function and feature map, we have that $2\beta, \alpha > 1$.

We notice that:

and the inequality in (16) holds if

The inequalities in (17) may be written as

Therefore, by applying the integral test for convergence, it is easy to show that all the series involved in the inequalities are bounded by a positive constant term dependent on $\alpha, \beta, \nu_2$ (where the latter depends itself on $\alpha, \beta$ and $n, p, \lambda$). For instance 

$\sum_{k\geq 1} \frac{k^{-\alpha}}{(k^{-\alpha} + \nu_2)^{-1}} < \int_{0}^\infty \frac{x^{-\alpha}}{(x^{-\alpha} + \nu_2)^{-1}}{\rm d}x = \nu_2^{-1/\alpha}\frac{\pi}{\alpha}\csc\left(\frac{\pi}{\alpha}\right) =: C_{\alpha,\nu_2}.$

[Adamczak, 2014] A note on the Hanson-Wright inequality for random vectors with dependencies.

Definition 1: For easier reading, I would define $\nu_1,\nu_2$ first, then $\Upsilon$, and then only $B$ and $R$.

We thank the reviewer for raising this issue, which will be addressed in the revised version of the paper.

p5 L156 is there an implicit dependence on the feature map dimension?

Indeed, this remark is confusing and we will rephrase it. There is no dependency on the feature map dimension. The covariance $\Sigma$ might depend indirectly on the feature map dimension (however the key quantity is the intrinsic dimension $r_\Sigma$ and our results hold for infinite dimensional feature maps).

Thanks for the clarifications! I am still in two minds: one the one hand, I agree that the 9-pager already conveys an interesting technical contribution, with clarity, provided the authors implement the minor changes recommended by the reviewers. On the other hand, I would have preferred having had the time to proofread the proof carefully, in a journal submission like JMLR. But, after having read the other reviews, and anticipating over the reviewer discussion period, I am willing to increase my score and not argue for rejection.

We thank the reviewer for their appreciation of our work and for the suggestion which will help improving it.

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

We will expand the discussion around Assumption 3.1 (see the general rebuttal for a discussion).

We thank the reviewer for their appreciation of our work and for the suggestions which will help improving it. The typos raised (2, 5, 6, 7, 8, 11, 14) will be corrected in the revised version of the manuscript.

Below, we address the other specific comments and questions.

"One concern is how we can check Assumptions 3.1 and 3.2"

Please see general rebuttal.

"[... ] the bound of $\mathcal{E}(n,p)$ seems to be loose and cannot get $\tilde{O}(n^{-1/2}+p^{-1/2})$"

The bounds in (28-29) are technical conditions used in intermediate steps of the proof to ensure the multiplicative bounds. If conditions (28-29) are verified, then the approximation guarantee (30) is satisfied with $\mathcal{E} (n,p)$ rate given in (32). Conditions (28-29) are not meant to ensure that $\mathcal{E}(n,p)$ is small, but that the bound (30) holds (and indeed, $\mathcal{E}(n,p)$ might not be vanishing).

The conditions (28-29) and rate $\mathcal{E}(n,p)$ depend explicitly on $n,p,\lambda,\Sigma$ and should be applied to specific settings. We will add the details of how to compute these bounds in the case of source and capacity conditions in Corollary 4.1., to illustrate the use of this theorem (and provide a full proof of Remark 4.1).

Some dependency in $\Sigma$ and $\lambda$ in the multiplicative bounds are unavoidable, and therefore are not technical. However, in most relevant examples (e.g. regularly varying spectrum), $\rho_\kappa (p)$ and $\tilde \rho_\kappa (n,p)$ will be of order $\log (\max (n,p))^C/\kappa$, and $\mathcal{E} (n,p)$ will indeed be of order $p^{-1/2} + n^{-1/2}$ up to log factors. We further believe that the dependency on $\lambda$ could be improved, at the cost of a worst dependency $p^{-c} + n^{-c}$, $c <1/2$, and further assumptions (see for example [Cheng, Montanari, 2022]). We will add this discussion to the revised version.

"Is there any theoretical guarantee for this approximation?"

First, we would like to clarify that Figures 1 and 2, 5, 6 are intended as an illustration of the scope of the theory to settings that might go beyond the technical assumptions. The ``empirical diagonalization'' procedure is therefore only a tool to obtain the spectrum in cases which it is not available analytically (e.g. real data), and has been inspired from other works in the literature, e.g. [Bordelon et al., 2020; Loureiro et al., 2020; Simon et al., 2023a].

Indeed, when estimating the spectrum empirically the quality of the theoretical predictions will depend on the choice $N,P$. The convergence rates for the empirical estimation of the spectrum were studied in [Koltchinskii and Giné, 2000; Braun, 2006], and in the worst-case are given by the usual CLT rates. In practice (e.g. Figs. 1 and 2), we observe that $N,P = 10^{4}$ was enough for a very good agreement with finite size simulations in the range of $n,p$ considered.

However, it is important to stress that this is unrelated to the proportional asymptotics (after estimating $\Sigma,\beta_*$, we use the deterministic equivalents in Definition 1). It just implies that to go to larger $n,p$ (e.g. a polynomial scaling) ones requires a finer estimation of the spectrum.

-[Koltchinskii and Giné, 2000] Random matrix approximation of spectra of integral operators.

-[Braun, 2006] Accurate error bounds for the eigenvalues of the kernel matrix.

"In (10), do you need to assume the subsets $\mathcal{X}$ and $\mathcal{W}$ in $\mathbb{R}^{d}$ are compactly supported?"

We introduce an abstract random feature model $\varphi : \mathcal{X} \times \mathcal{W} \to \mathbb{R}$, but we only require that it is diagonalizable. It is sufficient for $\mathcal{X}$ and $\mathcal{W}$ to be Polish probability spaces and $\varphi$ to be square integrable, so that $\varphi$ is diagonalizable (by the spectral theorem of compact operators). For Theorem 3.3, we only use Assumption 3.1 that is an assumption directly on the eigenfunctions of the activation.

What is $\nu_{2}$ in (17) in Assumption 3.2? You did not introduce this notation until Definition 1.

Indeed, the parameter $\nu_2$ is the solution of (23) in Definition 1. Following the reviewer's remark, we will move Assumption 3.2 after Definition 1 in the revised version.

"In line 147, why do you assume assumption 3.2 again?"

This is a typo. Thank you for pointing it out!

"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."

For most cases of interest, $\rho_{\lambda}(n)$ will be of order $\log (n)^C/\lambda$ (see response above). We further insist that these bounds are non-asymptotic (they depend explicitly on finite $n$) and do not need to be vanishing: if they are equal to $1/2$, it is enough to pinpoint the scale of the functionals.

"How do you prove the last equation on page 16? How do you apply the matrix Bernstein inequality for infinite dimension $\tilde{S}$?"

$||S_i|| = ||x_{+,i}||^{2}= x_{+,i}^T I x_{+,i}$. We can therefore apply Assumption A.1 with $A= I$ and do an union bound on $i \in [n]$, which results in the $\log(n)$ factor.

$S_i$ can be seen as a trace class operator, and many tools from matrix theory extend to this setting. The matrix Bernstein inequality only depends on the operator norm and the intrinsic dimension of the matrix, and not on the size of the matrix, and its proof extends to infinite dimensional operators. See for example [Rudi, Rosasco, 2017] and references therein.

"In Line 634, you consider $\eta\in(0,1/4)$ but in the main results, you have $\eta\in(0,1/2)$?"

This is a typo. Thank you for pointing it out!

"How do you prove $||\hat{\Sigma}||_{op}\geq 1/2$"

In the proof in section B.7.1, we have $|| \hat{\Sigma} || \geq || F_1 F_1^T /p ||$ and by equation (124), we proved that the top eigenvalue of $F_1 F_1^T /p$ (i.e., $k_1 = 1$) is lower bounded by $\hat \xi_1^2/2$, where $\hat\xi_1^2 = || \Sigma || = 1$ by assumption.