# Dimension-free deterministic equivalents
for random feature regression

Leonardo Defilippis  Département d’Informatique, École Normale Supérieure -
PSL & CNRS, France Bruno Loureiro  Département d’Informatique, École Normale
Supérieure - PSL & CNRS, France Theodor Misiakiewicz  Toyota Technological
Institute at Chicago, United States.

###### Abstract

In this work we investigate the generalization performance of random feature
ridge regression (RFRR). Our main contribution is a general deterministic
equivalent for the test error of RFRR. Specifically, under a certain
concentration property, we show that the test error is well approximated by a
closed-form expression that only depends on the feature map eigenvalues.
Notably, our approximation guarantee is non-asymptotic, multiplicative, and
independent of the feature map dimension—allowing for infinite-dimensional
features. We expect this deterministic equivalent to hold broadly beyond our
theoretical analysis, and we empirically validate its predictions on various
real and synthetic datasets. As an application, we derive sharp excess error
rates under standard power-law assumptions of the spectrum and target decay.
In particular, we provide a tight result for the smallest number of features
achieving optimal minimax error rate.

###### Contents

  1. 1 Introduction
  2. 2 Setting
  3. 3 Deterministic equivalents
  4. 4 Scaling laws
  5. A Background on deterministic equivalents
  6. B Proof of the deterministic equivalent for RFRR
    1. B.1 Preliminaries
    2. B.2 Fixed points, feature covariance matrix, and tail rank
    3. B.3 Deterministic equivalents for functionals of $\mathbb{Z}$ conditional on $\mathbb{F}$
    4. B.4 Deterministic equivalents for functionals of $\mathbb{F}$
    5. B.5 Approximation guarantee for the variance term
    6. B.6 Approximation guarantee for the bias term
    7. B.7 Technical results
      1. B.7.1 Feature covariance matrix
      2. B.7.2 Concentration of the fixed points
      3. B.7.3 Proof of deterministic equivalents for functionals on $\mathbb{Z}$
      4. B.7.4 Proof of Lemma B.11
      5. B.7.5 Proof of Lemma B.13
  7. C Details of the numerical illustration
    1. C.1 Gaussian design
    2. C.2 Empirical diagonalization
    3. C.3 Real data
    4. C.4 Trained network
  8. D Derivation of the rates
    1. D.1 Variance term
    2. D.2 Bias term
  9. E Comparison with neural scaling laws

##  1 Introduction

At odds with classical statistical intuition, overparametrized neural networks
are able to generalize while perfectly interpolating the training data. This
observation, which defies the canonical mathematical understanding of
generalization based on complexity measures and uniform convergence, appears
surprising at first (Zhang et al., 2017). However, recent progress in our
mathematical understanding of generalization has taught us that this _benign
overfitting_ property of overparametrized neural networks is shared by a
plethora of simpler learning tasks (Bartlett et al., 2021; Belkin, 2021).
Among them, the investigation of the following class of _random feature
models_ has been at the forefront of this progress:

$\displaystyle{\mathcal{F}}_{\text{RF}}=\Big{\\{}\hat{f}({\boldsymbol{x}};{\boldsymbol{a}})=\frac{1}{\sqrt{p}}\sum_{j\in[p]}a_{j}\varphi({\boldsymbol{x}},{\boldsymbol{w}}_{j})\;:\;{\boldsymbol{a}}=(a_{j})_{j\in[p]}\in\mathbb{R}^{p}\Big{\\}}.$
(1)

Here ${\boldsymbol{x}}\in{\mathcal{X}}$ denotes the inputs and
${\boldsymbol{W}}=({\boldsymbol{w}}_{j})_{j\in[p]}$ a set of weight vectors
which are taken to be random
${\boldsymbol{w}}_{j}\in{\mathcal{W}}\subseteq\mathbb{R}^{d}\sim_{\text{iid}}\mu_{w}({\mathcal{W}})$.
Hence, as the name suggests the feature map
$\varphi:{\mathcal{X}}\times{\mathcal{W}}\to\mathbb{R}$ defines a random
function. A few examples of random feature maps include the fully connected
neural network features
$\varphi({\boldsymbol{x}},{\boldsymbol{w}})=\sigma(\langle{\boldsymbol{w}},{\boldsymbol{x}}\rangle)$,
and the convolutional features with global average pooling
$\varphi({\boldsymbol{x}},{\boldsymbol{w}})=\nicefrac{{1}}{{d}}\sum_{\ell=1}^{d}\sigma(\langle{\boldsymbol{w}},g_{\ell}\cdot{\boldsymbol{x}}\rangle)$
where
$g_{\ell}\cdot{\boldsymbol{x}}=(x_{\ell+1},\dots,x_{d},x_{1},\dots,x_{\ell})$
is the $\ell$-shift operator with cyclic boundary conditions (both with
$\mathcal{X}=\mathbb{R}^{d}$).

Random features were originally introduced by Rahimi and Recht (2007) as a
computationally efficient approximation for the limiting kernel:

$\displaystyle
K({\boldsymbol{x}},{\boldsymbol{x}}^{\prime})=\mathbb{E}_{{\boldsymbol{w}}\sim\mu_{w}}\left[\varphi({\boldsymbol{x}},{\boldsymbol{w}})\varphi({\boldsymbol{x}}^{\prime},{\boldsymbol{w}})\right].$
(2)

Although this can reduce the computational cost of kernel methods, it
introduces an approximation error. Rahimi and Recht (2008) showed that in a
supervised setting with $n$ samples, $p=O(n)$ features are sufficient to
achieve an excess risk $O(n^{-\nicefrac{{1}}{{2}}})$. Rudi and Rosasco (2017)
improved this result under standard power-law assumptions on the asymptotic
kernel spectrum, showing that for fast decays, less features are needed to
achieve the minimax rate. In Section 4 we will revisit this question, where we
will derive a tight result for the minimum number of features.

More recently, the random feature model has gained in popularity as a proxy
model for studying the generalization properties of two-layer neural networks
in the lazy regime of training (Jacot et al., 2018; Chizat et al., 2019).
Indeed, for particular choices of feature maps such as
$\varphi({\boldsymbol{x}},{\boldsymbol{w}})=\sigma(\langle{\boldsymbol{w}},{\boldsymbol{x}}\rangle)$,
it can also be seen as a two-layer neural network with fixed first-layer
weights. Exact asymptotic results for the generalization error of eq. 1 were
derived for different supervised learning tasks under the proportional scaling
regime $n,p=\Theta(d)$ in (Mei and Montanari, 2022; Gerace et al., 2021;
Dhifallah and Lu, 2020; Hu and Lu, 2023; Goldt et al., 2022; Loureiro et al.,
2022; Bosch et al., 2023b, a; Schröder et al., 2023, 2024) and under more
general polynomial scaling $n,p=\Theta(d^{\kappa})$ in (Simon et al., 2023b;
Aguirre-López et al., 2024; Hu et al., 2024). As discussed above, these works
played a fundamental role in our current mathematical understanding of the
relationship between overparametrization and generalization, demystifying
different phenomena such as double descent and benign overfitting. It also led
to fundamental separation results between lazy and trained networks (Ghorbani
et al., 2019, 2020; Mei et al., 2022), recently motivating the investigation
of corrections to the random limit (Ba et al., 2022; Dandi et al., 2023;
Moniri et al., 2024; Cui et al., 2024).

With the exception of (Simon et al., 2023b), which is based on non-rigorous
arguments, the results in all the works cited above are derived in the
asymptotic limit of large data dimension. However, the relative scaling of the
$n,p,d$ is fundamentally artificial, and in practice it is hard to
unambiguously define the regime of interest. Our main goal in this manuscript
is to provide a dimension-free characterization of the generalization error
allowing us to give tight answers to questions which cannot be addressed
asymptotically. More precisely, our main contributions are:

  * (i)

Under a concentration assumption on the feature map eigenfunctions, we prove a
non-asymptotic deterministic approximation for the RFRR risk
$\mathcal{R}_{{\rm test}}\approx\mathsf{R}_{n,p}$ which is independent of the
feature map dimension. More precisely, with high-probability over the input
data and random weights:

$\displaystyle|\mathcal{R}_{{\rm
test}}-\mathsf{R}_{n,p}|\leq\tilde{O}(p^{-1/2}+n^{-1/2})\cdot\mathsf{R}_{n,p}.$
(3)

where the _deterministic equivalent_ $\mathsf{R}_{n,p}$ can be computed by
solving a set of self-consistent equations. This result unifies the long list
of asymptotic formulas in the RFRR literature, and proves a conjecture by
Simon et al. (2023b). We numerically validate the results on various real and
synthetic datasets. The precise statement of the theorem and the assumptions
are discussed in Section 3.

  * (ii)

Leveraging our formula, we investigate the error scaling laws in a setting
where the target function and feature spectrum decay as a power-law, also
known as _source and capacity_ conditions. We provide a full picture of the
different scaling regimes and the cross-overs between them, summarized in
Figure 2. Our result is closely related to the neural scaling laws literature
(Kaplan et al., 2020), therefore providing the first rigorous, non-linear
extension of (Bahri et al., 2021; Maloney et al., 2022).

  * (iii)

We provide a sharp expression for the minimum number of features required to
achieve the minimax optimal decay rate of Caponnetto and De Vito (2007),
closing the gap of previous lower-bounds in the literature (Rudi and Rosasco,
2017).

##### Further related works —

Deterministic equivalents have been derived for a wide range of learning
problems, such as ridge regression (Dobriban and Wager, 2018; Hastie et al.,
2022; Cheng and Montanari, 2022; Wei et al., 2022), kernel ridge regression
(Misiakiewicz and Saeed, 2024), shallow (Liao and Couillet, 2018; Mei and
Montanari, 2022; Chouard, 2022; Bach, 2024; Atanasov et al., 2024) and deep
random feature regression (Fan and Wang, 2020; Schröder et al., 2023, 2024;
Chouard, 2023) and spiked random features (Wang et al., 2024). Scaling laws
under source and capacity conditions were studied by several authors in the
context of kernel ridge regression (Bordelon et al., 2020; Spigler et al.,
2020; Cui et al., 2022; Simon et al., 2023a; Li et al., 2023; Misiakiewicz and
Mei, 2022; Favero et al., 2021; Cagnetta et al., 2023; Dohmatob et al., 2024)
and classification (Cui et al., 2023).

##  2 Setting

In this work, we focus on the generalization properties of the random feature
class ${\mathcal{F}}_{\text{RF}}$ defined in eq. 1 in a supervised regression
setting. More precisely, consider a data set
${\mathcal{D}}=\\{({\boldsymbol{x}}_{i},y_{i})_{i\in[n]}\\}$ composed of $n$
independent and identically distributed samples from a joint distribution
$\mu_{x,y}(\mathcal{X}\times\mathbb{R})$. Let
$f_{\star}({\boldsymbol{x}})=\mathbb{E}[y|{\boldsymbol{x}}]$ denote the target
function. We assume $f_{\star}\in L_{2}(\mu_{x})$, where
$\mu_{x}(\mathcal{X})$ is the marginal distribution over $\mathcal{X}$.
Moreover, we assume the noise $\varepsilon\coloneqq
y-f_{\star}({\boldsymbol{x}})$ has finite variance
$\mathbb{E}[\varepsilon^{2}]=\sigma_{\varepsilon}^{2}<\infty$. Note this is
equivalent to:

$\displaystyle
y_{i}=f_{\star}({\boldsymbol{x}}_{i})+\varepsilon_{i},\qquad\quad f_{\star}\in
L_{2}(\mu_{x}).$ (4)

Given the training data, we are interested in the properties of the minimiser:

$\displaystyle\hat{{\boldsymbol{a}}}_{\lambda}({\boldsymbol{Z}},{\boldsymbol{y}})\coloneqq\operatorname*{arg\,min}_{{\boldsymbol{a}}\in\mathbb{R}^{p}}\Big{\\{}\sum_{i\in[n]}\left(y_{i}-\hat{f}({\boldsymbol{x}}_{i};{\boldsymbol{a}})\right)^{2}+\lambda\|{\boldsymbol{a}}\|_{2}^{2}\Big{\\}}=({\boldsymbol{Z}}^{\top}{\boldsymbol{Z}}+\lambda\boldsymbol{I}_{p}){\boldsymbol{Z}}^{\top}{\boldsymbol{y}},$
(5)

where we have defined the feature matrix
${\boldsymbol{Z}}_{ij}=p^{-\nicefrac{{1}}{{2}}}\varphi({\boldsymbol{x}}_{i};{\boldsymbol{w}}_{j})$
and the label vectors ${\boldsymbol{y}}=(y_{i})_{i\in[n]}$. In particular, we
are interested in its capacity of generalising to unseen data, as quantified
by the _excess population risk_ :

$\displaystyle\mathcal{R}(f_{\star},{\boldsymbol{X}},{\boldsymbol{W}},{\boldsymbol{\varepsilon}},\lambda)\coloneqq\mathbb{E}_{{\boldsymbol{x}}\sim\mu_{x}}\Big{[}\Big{(}f_{\star}({\boldsymbol{x}})-\hat{f}({\boldsymbol{x}};{\hat{\boldsymbol{a}}}_{\lambda})\Big{)}^{2}\Big{]}.$
(6)

It will be convenient to decompose the excess risk above in terms of the
standard bias and variance:

$\displaystyle\mathcal{R}(f_{\star};{\boldsymbol{X}},{\boldsymbol{W}},\lambda):=\mathbb{E}_{\boldsymbol{\varepsilon}}\left[\mathcal{R}(f_{\star};{\boldsymbol{X}},{\boldsymbol{W}},{\boldsymbol{\varepsilon}},\lambda)\right]=\mathcal{B}(h_{*};{\boldsymbol{X}},{\boldsymbol{W}},\lambda)+{\mathcal{V}}({\boldsymbol{X}},{\boldsymbol{W}},\lambda),$
(7)

where:

$\displaystyle\mathcal{B}(f_{\star};{\boldsymbol{X}},{\boldsymbol{W}},\lambda)$
$\displaystyle\coloneqq\mathbb{E}_{{\boldsymbol{x}}\sim\mu_{x}}\left[\left(f_{\star}({\boldsymbol{x}})-\mathbb{E}_{\boldsymbol{\varepsilon}}[\hat{f}({\boldsymbol{x}};{\hat{\boldsymbol{a}}}_{\lambda})]\right)^{2}\right],$
(8) $\displaystyle{\mathcal{V}}({\boldsymbol{X}},{\boldsymbol{W}},\lambda)$
$\displaystyle\coloneqq\mathbb{E}_{{\boldsymbol{x}}\sim\mu_{x}}\left[\text{Cov}_{{\boldsymbol{\varepsilon}}}(\hat{f}({\boldsymbol{x}};{\hat{\boldsymbol{a}}}_{\lambda}))\right].$
(9)

Note that to simplify the exposition, we have explicitly taken an expectation
over the training data noise
${\boldsymbol{\varepsilon}}=(\varepsilon_{i})_{i\in[n]}$. Indeed, it can be
shown that the excess risk eq. 6 concentrates on its expectation over
${\boldsymbol{\varepsilon}}$ under mild assumptions (see for example
(Misiakiewicz and Saeed, 2024)).

##  3 Deterministic equivalents

The excess risk eq. 6 is a function of the covariates ${\boldsymbol{X}}$ and
the weights ${\boldsymbol{W}}$, and therefore it is a random quantity. Our
main result in what follows is a sharp characterization of the bias and
variance in terms of a _deterministic equivalent_ depending only on the model
parameters and spectral properties of the features. Consider a square-
integrable $\varphi\in L_{2}(\mathcal{X}\times\mathcal{W})$, and define the
Fredholm integral operator
${\mathbb{T}}:L_{2}({\mathcal{X}})\to{\mathcal{V}}\subseteq
L_{2}({\mathcal{W}})$:

$\displaystyle{\mathbb{T}}h({\boldsymbol{w}})\coloneqq\int_{{\mathcal{X}}}\varphi({\boldsymbol{x}};{\boldsymbol{w}})h({\boldsymbol{x}})\mu_{x}({\rm
d}{\boldsymbol{x}}),\qquad\quad\forall h\in L_{2}({\mathcal{X}}),$ (10)

where we define without loss of generality that ${\mathcal{V}}={\rm
Im}({\mathbb{T}})$. This is a compact operator, and therefore can be
diagonalized:

${\mathbb{T}}=\sum_{k=1}^{\infty}\xi_{k}\psi_{k}\phi_{k}^{*},$ (11)

where $(\xi_{k})_{k\geq 1}\subseteq\mathbb{R}$ are the eigenvalues and
$(\psi_{k})_{k\geq 1}$ and $(\phi_{k})_{k\geq 1}$ are orthonormal bases of
$L_{2}({\mathcal{X}})$ and ${\mathcal{V}}$ respectively:

$\displaystyle\langle\psi_{k},\psi_{k^{\prime}}\rangle_{L_{2}({\mathcal{X}})}=\delta_{kk^{\prime}},\qquad\quad\langle\phi_{k},\phi_{k^{\prime}}\rangle_{L_{2}({\mathcal{W}})}=\delta_{kk^{\prime}}.$
(12)

Without loss of generality, we assume the eigenvalues are ordered in non-
increasing absolute values $|\xi_{1}|\geq|\xi_{2}|\geq\dots$, and for
simplicity of presentation we assume that all eigenvalues are non-zero, i.e.,
$\ker({\mathbb{T}})=\\{0\\}$. Denote ${\boldsymbol{\Sigma}}={\rm
diag}(\xi_{1}^{2},\xi_{2}^{2},\ldots)\in\mathbb{R}^{\infty\times\infty}$ the
diagonal matrix of the squared eigenvalues. Similarly, since $f_{\star}\in
L_{2}(\mu_{x})$, it admits the following decomposition in $(\psi)_{k\geq 1}$:

$\displaystyle f_{\star}({\boldsymbol{x}})=\sum\limits_{k\geq
1}{{\boldsymbol{\beta}}_{\star}}_{,k}\psi_{k}({\boldsymbol{x}})$ (13)

Our formal results will assume the following concentration property over the
eigenfunctions.

######  Assumption 3.1 (Concentration of the eigenfunctions).

Denote the (infinite-dimensional) random vectors111Note that we can consider
both ${\boldsymbol{\psi}}$ and ${\boldsymbol{\phi}}$ random elements of the
Hilbert space $\ell_{2}$ with distribution induced by
${\boldsymbol{x}}\sim\mu_{x}$ and ${\boldsymbol{w}}\sim\mu_{w}$, where
$\mathbb{E}[{\boldsymbol{\psi}}{\boldsymbol{\psi}}^{\mathsf{T}}]=\mathbb{E}[{\boldsymbol{\phi}}{\boldsymbol{\phi}}^{\mathsf{T}}]={\boldsymbol{\Sigma}}$
and ${\rm Tr}({\boldsymbol{\Sigma}})<\infty$.
${\boldsymbol{\psi}}:=(\xi_{k}\psi_{k}({\boldsymbol{x}}))_{k\geq 1}$ and
${\boldsymbol{\phi}}:=(\xi_{k}\phi_{k}({\boldsymbol{w}}))_{k\geq 1}$. There
exists a constant ${\sf C}_{x}>0$ such that for any deterministic p.s.d.
matrix ${\boldsymbol{A}}\in\mathbb{R}^{\infty\times\infty}$ with ${\rm
Tr}({\boldsymbol{\Sigma}}{\boldsymbol{A}})<\infty$, we have

$\displaystyle\mathbb{P}\left(\left|{\boldsymbol{\psi}}^{\mathsf{T}}{\boldsymbol{A}}{\boldsymbol{\psi}}-{\rm
Tr}({\boldsymbol{\Sigma}}{\boldsymbol{A}})\right|\geq
t\cdot\|{\boldsymbol{\Sigma}}^{1/2}{\boldsymbol{A}}{\boldsymbol{\Sigma}}^{1/2}\|_{F}\right)\leq$
$\displaystyle~{}{\sf C}_{x}\exp\left\\{-t/{\sf C}_{x}\right\\},$ (14)
$\displaystyle\mathbb{P}\left(\left|{\boldsymbol{\phi}}^{\mathsf{T}}{\boldsymbol{A}}{\boldsymbol{\phi}}-{\rm
Tr}({\boldsymbol{\Sigma}}{\boldsymbol{A}})\right|\geq
t\cdot\|{\boldsymbol{\Sigma}}^{1/2}{\boldsymbol{A}}{\boldsymbol{\Sigma}}^{1/2}\|_{F}\right)\leq$
$\displaystyle~{}{\sf C}_{x}\exp\left\\{-t/{\sf C}_{x}\right\\}.$ (15)

While Assumption 3.1 is restrictive and will not be satisfied by many non-
linear settings, it covers a number of popular theoretical models studied in
the literature: 1) independent sub-Gaussian entries, 2) verifying a log-
Sobolev inequality or convex Lipschitz concentration (see Cheng and Montanari
(2022)). We expect that Assumption 3.1 can be relaxed using the same procedure
as in Misiakiewicz and Saeed (2024) to cover classical examples such as data
and weights uniformly distributed on the sphere or hypercube. Such a
relaxation is involved and we leave it to future work. We will further assume
that:

######  Assumption 3.2.

There exists ${\mathsf{m}}\in\mathbb{N}$ such that

$\displaystyle
p^{2}\xi_{{\mathsf{m}}+1}^{2}\leq\frac{p\lambda}{n}\sum_{k={\mathsf{m}}+1}^{\infty}\xi_{k}^{2}.$
(16)

Furthermore, we will assume that for some ${\sf C}_{*}>0$ that we have

$\frac{{\rm
Tr}({\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1})}{{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}\leq{\sf
C}_{*},\qquad\quad\frac{\langle{{\boldsymbol{\beta}}_{\star}},({\boldsymbol{\Sigma}}+\nu_{2})^{-1}{{\boldsymbol{\beta}}_{\star}}\rangle}{\nu_{2}\langle{{\boldsymbol{\beta}}_{\star}},({\boldsymbol{\Sigma}}+\nu_{2})^{-2}{{\boldsymbol{\beta}}_{\star}}\rangle}\leq{\sf
C}_{*}.$ (17)

Assumption 3.2 is technical, and we believe it can be removed at the cost of a
more involved analysis. For instance, eq. 16 is always satisfied for
$\xi_{k}^{2}\propto k^{-\alpha}$ if we take ${\mathsf{m}}=O(p^{2})$. Condition
(17) was also considered in (Cheng and Montanari, 2022), and is satisfied in
many setting of interest, for example under source and capacity conditions
$\beta_{k}\asymp k^{-\beta}$ and $\xi_{k}^{2}\asymp k^{-\alpha}$ considered in
Section 4.

##### Main result —

Our main result concerns a dimension-free characterization of the risk eq. 6
in terms of deterministic equivalents. We start by defining them.

######  Definition 1 (Deterministic equivalents).

Given integers $n,p$, covariance matrix ${\boldsymbol{\Sigma}}$ and
regularization parameter $\lambda\geq 0$. Then, the deterministic equivalents
for the bias, variance and test error are defined as:

$\displaystyle\mathsf{B}_{n,p}({\boldsymbol{\beta}}_{*},\lambda)$
$\displaystyle\coloneqq\frac{\nu_{2}^{2}}{1-\Upsilon(\nu_{1},\nu_{2})}\Big{[}\langle{\boldsymbol{\beta}}_{*},({\boldsymbol{\Sigma}}+\nu_{2})^{-2}{\boldsymbol{\beta}}_{*}\rangle+\chi(\nu_{2})\langle{\boldsymbol{\beta}}_{*},{\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-2}{\boldsymbol{\beta}}_{*}\rangle\Big{]},$
(18) $\displaystyle\mathsf{V}_{n,p}(\lambda)$
$\displaystyle\coloneqq\sigma_{\varepsilon}^{2}\frac{\Upsilon(\nu_{1},\nu_{2})}{1-\Upsilon(\nu_{1},\nu_{2})}.$
(19) $\displaystyle\mathsf{R}_{n,p}({\boldsymbol{\beta}}_{*},\lambda)$
$\displaystyle\coloneqq\mathsf{B}_{n,p}({\boldsymbol{\beta}}_{*},\lambda)+\mathsf{V}_{n,p}(\lambda).$
(20)

where we have introduced the short-hand:

$\displaystyle\Upsilon(\nu_{1},\nu_{2})$
$\displaystyle\coloneqq\frac{p}{n}\left[\left(1-\frac{\nu_{1}}{\nu_{2}}\right)^{2}+\left(\frac{\nu_{1}}{\nu_{2}}\right)^{2}\frac{{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}{p-{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}\right],$
(21) $\displaystyle\chi(\nu_{2})$ $\displaystyle\coloneqq\frac{{\rm
Tr}({\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}{p-{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}.$ (22)

The parameter $\nu_{2}\in\mathbb{R}_{>0}$ is defined as the unique solution of
the self-consistent equation:

$\displaystyle
1+\frac{n}{p}-\sqrt{\left(1-\frac{n}{p}\right)^{2}+4\frac{\lambda}{p\nu_{2}}}=\frac{2}{p}{\rm
Tr}\left({\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\right),$
(23)

and $\nu_{1}\in\mathbb{R}_{>0}$ is given by:

$\nu_{1}:=\frac{\nu_{2}}{2}\left[1-\frac{n}{p}+\sqrt{\left(1-\frac{n}{p}\right)^{2}+4\frac{\lambda}{p\nu_{2}}}\right].$
(24)

Our main result provides precise conditions for when the deterministic
equivalents defined in definition 1 are a good approximation for the test
error eq. 6, as a function of the dimensions $n,p$, feature covariance
${\boldsymbol{\Sigma}}$, and regularization $\lambda>0$. More precisely, the
approximation rates will depend on them through the following quantities:

$\displaystyle M_{\boldsymbol{\Sigma}}(k)$ $\displaystyle\coloneqq
1+\frac{r_{{\boldsymbol{\Sigma}}}(\lfloor\eta_{*}\cdot k\rfloor)\vee
k}{k}\log\left(r_{{\boldsymbol{\Sigma}}}(\lfloor\eta_{*}\cdot k\rfloor)\vee
k\right),$ (25) $\displaystyle\rho_{\kappa}(p)$ $\displaystyle\coloneqq
1+\frac{p\cdot\xi^{2}_{\lfloor\eta_{*}\cdot
p\rfloor}}{\kappa}M_{\boldsymbol{\Sigma}}(p),$ (26)
$\displaystyle\widetilde{\rho}_{\kappa}(n,p)$ $\displaystyle\coloneqq
1+\mathbbm{1}[n\leq p/\eta_{*}]\cdot\left\\{\frac{n\xi_{\lfloor\eta_{*}\cdot
n\rfloor}^{2}}{\kappa}+\frac{n}{p}\cdot\rho_{\kappa}(p)\right\\}M_{\boldsymbol{\Sigma}}(n),$
(27)

We will have typically $\rho_{\kappa}(p)\asymp\log(p)^{C}/\kappa$ and
$\widetilde{\rho}_{\kappa}(n,p)\asymp\log(n\wedge p)^{C}/\kappa$. Below we
denote $C_{a_{1},\ldots,a_{k}}$ constants that only depend on the values of
$\\{a_{i}\\}_{i\in[k]}$. We use $a_{i}=`*$’ to denote the dependency on the
constants in Assumptions 3.1 and 3.2.

We have now everything we need in order to state our main result.

######  Theorem 3.3 (Test error of RFRR).

Under Assumptions 3.1, 3.2 and for any $D,K>0$, there exist constants
$\eta_{*}\in(0,1/2)$ and $C_{*,D,K}>0$ such that the following holds. For any
$n,p\geq C_{*,D,K}$, regularization $\lambda>0$, and target function
$f_{\star}\in L_{2}(\mu_{x})$, if Assumption 3.2 holds and

$\displaystyle\lambda\geq n^{-K},\qquad\gamma_{\lambda}\geq
p^{-K},\qquad\qquad\quad\widetilde{\rho}_{\lambda}(n,p)^{5/2}\cdot\log^{3/2}(n)\leq$
$\displaystyle~{}K\sqrt{n},$ (28)
$\displaystyle\widetilde{\rho}_{\lambda}(n,p)^{2}\cdot\rho_{\gamma_{+}}(p)^{8}\cdot\log^{4}(p)\leq$
$\displaystyle~{}K\sqrt{p},$ (29)

then with probability at least $1-n^{-D}-p^{-D}$, we have

$\displaystyle\left|\mathcal{R}(f_{\star};{\boldsymbol{X}},{\boldsymbol{W}},\lambda)-\mathsf{R}_{n,p}({\boldsymbol{\beta}}_{*},\lambda)\right|\leq
C_{*,D,K}\cdot{\mathcal{E}}(n,p)\cdot\mathsf{R}_{n,p}({\boldsymbol{\beta}}_{*},\lambda),$
(30)

where:

$\displaystyle\gamma_{\lambda}=\frac{p\lambda}{n}+\sum_{k={\mathsf{m}}+1}^{\infty}\xi_{k}^{2},\qquad\qquad\gamma_{+}=p\nu_{1}+\sum_{k={\mathsf{m}}+1}^{\infty}\xi_{k}^{2}.$
(31)

and the approximation rate is given by

${\mathcal{E}}(n,p):=\frac{\widetilde{\rho}_{\lambda}(n,p)^{6}\log^{7/2}(n)}{\sqrt{n}}+\frac{\widetilde{\rho}_{\lambda}(n,p)^{2}\cdot\rho_{\gamma_{+}}(p)^{8}\log^{7/2}(p)}{\sqrt{p}}.$
(32)

A few remarks on this result are in place:

  1. (a)

Theorem 3.3 provides fully non-asymptotic approximation bounds for the
population risk and its deterministic equivalent. They hold pointwise and for
a large class of functions. In particular, they do not require probabilistic
assumptions over the target function coefficients
${{\boldsymbol{\beta}}_{\star}}$, as for instance in (Dobriban and Wager,
2018; Richards et al., 2021; Wu and Xu, 2020).

  2. (b)

They are not explicitly dependent on the feature map dimension.

  3. (c)

They are multiplicative, and therefore relative to the scale of the risk. In
particular, they hold even if $\mathcal{R}\asymp n^{-\gamma}$, which will be
crucial to the discussion in section 4.

  4. (d)

Theorem 3.3 is considerably more general than previous results. First, it
extends the dimension-free results of Cheng and Montanari (2022) for well-
specified ridge regression and Misiakiewicz and Saeed (2024) for KRR (see
$p\to\infty$ discussion below) to the case of feature maps
$\varphi:{\mathcal{X}}\times{\mathcal{W}}\to\mathbb{R}$, which, as discussed
in Section 2, comprises several cases of interest in machine learning.
Moreover, the deterministic equivalent recovers as particular cases the
asymptotic results derived under proportional $n,p=\Theta(d)$ (Mei and
Montanari, 2022; Loureiro et al., 2022; Schröder et al., 2023) and polynomial
$n,p=\Theta(d^{\kappa})$ (Xiao et al., 2022; Hu et al., 2024; Aguirre-López et
al., 2024) scaling.

  5. (e)

The bounds depend on $\lambda^{-1}$ and $\lambda_{>{\mathsf{m}}}^{-1}$.
Following similar arguments as in Cheng and Montanari (2022); Misiakiewicz and
Saeed (2024), this assumption could be removed at the cost of a lengthier
analysis and worse rates $n^{-C}+p^{-C}$ with $C<1/2$.

Figure 1: Excess risk eq. 6 of RFRR as a function of the number of features
$p$ for a fixed number of samples $n$. Solid lines are obtained from the
deterministic equivalent in Theorem 3.3, and points are numerical simulations,
with the different curves denoting different regularization strengths
$\lambda\geq 0$. (Left) Training data
$({\boldsymbol{x}}_{i},y_{i})_{i\in[n]}$, $n=500$, sampled from a teacher-
student model
$y_{i}=\erf(\langle{\boldsymbol{\beta}},{\boldsymbol{x}}_{i}\rangle)+\varepsilon_{i}$,
$\sigma_{\varepsilon}^{2}=0.1$,
${\boldsymbol{x}}_{i}\sim_{\text{i.i.d.}}\mathcal{N}(0,{\boldsymbol{I}}_{d})$,
with a spiked random feature map
$\varphi({\boldsymbol{x}},{\boldsymbol{w}})=\operatorname{tanh}(\langle{\boldsymbol{w}}+u{\boldsymbol{v}},{\boldsymbol{x}}\rangle)$
where ${\boldsymbol{v}}\in\mathbb{R}^{d}$ has a fixed overlap
$\gamma=\langle{\boldsymbol{v}},{\boldsymbol{\beta}}\rangle$ with the teacher
vector, ${\boldsymbol{w}}\sim\mathcal{N}(0,d^{-1}{\boldsymbol{I}}_{d})$,
$u\sim\mathcal{N}(0,1)$. (Right) Training data
$({\boldsymbol{x}}_{i},y_{i})_{i\in[n]}$, $n=300$, sub-sampled from the
FashionMNIST data set (Xiao et al., 2017), with feature map given by
$\varphi({\boldsymbol{x}};{\boldsymbol{w}})=\erf(\langle{\boldsymbol{w}},{\boldsymbol{x}}\rangle)$
and $\mu_{w}=\mathcal{N}(0,d^{-1}{\boldsymbol{I}}_{d})$.

Figure 1 illustrates Theorem 3.3 in two different settings with real and
synthetic data. On the left, we show the population risk of learning a single-
index target function with a spiked random features model. This model was
recently shown to be equivalent to the first-step of training in a fully-
connected two-layer network (Ba et al., 2022), and it was recently studied by
several authors (Moniri et al., 2024; Cui et al., 2024; Wang et al., 2024). On
the right, we apply our formulas directly to a real data set. In both cases,
the theoretical curves show excellent agreement with the numerical
simulations. In Appendix C we present additional plots, together with a
discussion of how these plots were generated.

##### Particular limits —

We now discuss some particular limits of interest of the deterministic
equivalent eq. 20. First, note that at the interpolation threshold $n=p$, we
have $1-\Upsilon(\nu_{1},\nu_{2})\sim\sqrt{\lambda}$. Therefore, the risk
$\mathsf{R}_{n,p}\sim\lambda^{-1/2}$ diverges as $\lambda\to 0^{+}$, a well-
known behaviour known as the _interpolation peak_ in the random feature
literature (Hastie et al., 2022; Mei and Montanari, 2022; Gerace et al., 2021)
and observed in neural networks (Spigler et al., 2019; Nakkiran et al., 2021).

Another limit of interest is $p\to\infty$ where, in the generic case, the
features spam an infinite dimensional RKHS. Typically, the resulting kernel
will be universal, implying it can approximate any function in
$L_{2}(\mu_{x})$. In this limit, the risk bottleneck is given by the finite
amount of data $n$.

######  Corollary 3.4 (Kernel limit).

In the $p\to\infty$ limit both $\nu_{1}$ and $\nu_{2}$ converge to a single
$\nu_{\sf K}$ which is the unique positive solution to the following self-
consistent equation

$\displaystyle n-\frac{\lambda}{\nu_{\sf K}}={\rm
Tr}\big{(}{\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{\sf
K})^{-1}\big{)}.$ (33)

Moreover, the bias eq. 18 and variance eq. 19 terms simplify to:

$\displaystyle\mathsf{B}_{{\sf
K},n}({\boldsymbol{\beta}}_{*},\lambda)=\frac{\nu_{{\sf
K}}^{2}\langle{\boldsymbol{\beta}}_{*},({\boldsymbol{\Sigma}}+\nu_{\sf
K})^{-2}{\boldsymbol{\beta}}_{*}\rangle}{1-\frac{1}{n}{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{{\sf K}})^{-2})},$
$\displaystyle\mathsf{V}_{{\sf
K},n}(\lambda)=\sigma_{\varepsilon}^{2}\frac{{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{{\sf
K}})^{-2})}{n-{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{{\sf K}})^{-2})}.$
(34)

We denote the corresponding test error $\mathsf{R}_{{\sf
K},n}({\boldsymbol{\beta}}_{*},\lambda)=\mathsf{B}_{{\sf
K},n}({\boldsymbol{\beta}}_{*},\lambda)+\mathsf{V}_{{\sf K},n}(\lambda)$.

Note that eq. 19 exactly agrees with the dimension-free deterministic
equivalents for kernel methods in Cheng and Montanari (2022); Misiakiewicz and
Saeed (2024). Finally, the third limit of interest is the $n\to\infty$ where
data is abundant. In this case, the empirical risk eq. 5 converge to the
population risk, and therefore the bottleneck in the risk is given by the
capacity of the random feature class ${\mathcal{F}}_{\text{RF}}$ eq. 1 to
approximate the target $f_{\star}$.

######  Corollary 3.5 (Approximation limit).

In the $n\to\infty$ limit, we have $\nu_{1}\to 0$ and $\nu_{2}\to\nu_{{\sf
A}}$ satisfying the following simplified self-consistent equation:

$\displaystyle p={\rm
Tr}\big{(}{\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{{\sf
A}})^{-1}\big{)}.$ (35)

Moreover, the bias eq. 18 and variance eq. 19 terms simplify to:

$\displaystyle\mathsf{B}_{{\sf A},p}({\boldsymbol{\beta}}_{*})=\nu_{{\sf
A}}\langle{\boldsymbol{\beta}}_{*},({\boldsymbol{\Sigma}}+\nu_{\sf
A})^{-1}{\boldsymbol{\beta}}_{*}\rangle,$ $\displaystyle\mathsf{V}_{{\sf
A},n}=0.$ (36)

We denote the risk in this case $\mathsf{R}_{{\sf
A},p}({\boldsymbol{\beta}}_{*})=\mathsf{B}_{{\sf
A},p}({\boldsymbol{\beta}}_{*})$, which as expected does not depend on
$\lambda$.

##  4 Scaling laws

Our exact characterization of the excess risk in Theorem 3.3 shows that the
bottleneck in the model performance stems either from its approximation
capacity (as measured by the “width” $p$) and the availability of data (as
measured by the number of samples $n$). In other words, for a fixed data
budget $n$, increasing $p$ might not improve the error besides a certain
point, yielding a waste of computational resources. This raises an important
question: _given a fixed data budged $n$, what is the optimal choice of model
size $p_{\star}$?_

##### Context —

This is a fundamental question in the random feature literature, and was
investigated already in the pioneering works of Rahimi and Recht (2007, 2008),
who showed that to achieve an excess risk of $O(n^{-1/2})$ requires at most
$p=O(n)$ features. This upper bound was considerably refined by Rudi and
Rosasco (2017) under classical power law scaling assumptions, also known as
_source_ and _capacity_ conditions in the kernel literature:

$\displaystyle{\rm
Tr}{\boldsymbol{\Sigma}}^{\nicefrac{{1}}{{\alpha}}}<\infty,$
$\displaystyle||{\boldsymbol{\Sigma}}^{-r}{{\boldsymbol{\beta}}_{\star}}||_{2}<\infty.$
(37)

where $\alpha\in(1,\infty)$ and $r\in(0,\infty)$, with the case
$r=\nicefrac{{1}}{{2}}$ corresponding to $f_{\star}$ belonging to the RKHS of
the asymptotic random feature kernel eq. 2. The optimal minmax rate
$O\left(n^{-\frac{2\alpha r}{2\alpha r+1}}\right)$ for ridge regression under
source and capacity conditions were obtained by Caponnetto and De Vito (2007).
Rudi and Rosasco (2017) showed that this optimal rate can be attained by the
random feature hypothesis eq. 1 with
$p>p_{0}=O\left(n^{\frac{\alpha-1+2r}{1+2\alpha r}}\right)$ features. However,
this is only an upper bound, and understand how tight it is, as well as the
full picture in the hard regime $r\in(0,\nicefrac{{1}}{{2}})$, remains an open
question. In this section, we leverage our tight characterization of the
excess risk theorem 3.3 to provide a sharp answer to this question.

##### Results —

Without loss of generality, we can assume the covariance is a diagonal matrix
${\boldsymbol{\Sigma}}={\rm diag}(\xi_{k}^{2})_{k\geq 1}$, and we consider the
case where the exponents exactly saturate the source and capacity conditions
eq. 37:

$\displaystyle\xi_{k}^{2}=k^{-\alpha},$
$\displaystyle\beta_{*,k}=k^{-\frac{1+2\alpha r}{2}}.$ (38)

Further, we assume a relative scaling of the number of features $p$ and the
regularization $\lambda$ with the number of samples $n$:

$\displaystyle p=n^{q},$ $\displaystyle\lambda=n^{-(\ell-1)}.$ (39)

with $q\geq 0$ and $\ell\geq 1$.

######  Corollary 4.1 (Excess risk rates).

Under source and capacity conditions eq. 38 and scaling assumptions eq. 39,
the deterministic equivalent eq. 20 rate is given by:

$\displaystyle\mathsf{R}_{n,p}({\boldsymbol{\beta}}_{*},\lambda)=\Theta\left(n^{-\gamma_{\mathcal{B}}(\ell,q)}+\sigma_{\varepsilon}^{2}n^{-\gamma_{{\mathcal{V}}}(\ell,q)}\right)=\Theta\left(n^{-\gamma(\ell,q)}\right),$
(40)

where
$\gamma(\ell,q)\coloneqq\gamma_{\mathcal{B}}(\ell,q)\wedge\gamma_{{\mathcal{V}}}(\ell,q)$
for non-zero noise variance $\sigma_{\varepsilon}^{2}\neq 0$, otherwise
$\gamma(\ell,q)=\gamma_{\mathcal{B}}(\ell,q)$. The exponents
$\gamma_{\mathcal{B}}$ and $\gamma_{{\mathcal{V}}}$ are respectively the decay
rates of the bias and variance terms eqs. 18 and 19, and are explicitly given
by

$\displaystyle\gamma_{\mathcal{B}}$
$\displaystyle\coloneqq\left[2\alpha\left(\frac{\ell}{\alpha}\wedge q\wedge
1\right)(r\wedge
1)\right]\wedge\left[\left(2\alpha\left(r\wedge\frac{1}{2}\right)-1\right)\left(\frac{\ell}{\alpha}\wedge
q\wedge 1\right)+q\right],$ (41) $\displaystyle\gamma_{{\mathcal{V}}}$
$\displaystyle\coloneqq 1-\left(\frac{\ell}{\alpha}\wedge q\wedge 1\right).$
(42)

######  Remark 4.1.

Under the scaling in eqs. 37 and 39, one can check that the approximation
rates ${\mathcal{E}}(n,p)$ in Theorem 3.3 are vanishing for
$\ell\leq\alpha+(\nicefrac{{1}}{{5}}\wedge\nicefrac{{q}}{{4}})$ if $q\geq 1$,
and for $\ell\leq
q((\alpha+\nicefrac{{1}}{{16}})\vee\nicefrac{{1}}{{16(\alpha-1)}})$ if $q<1$,
which includes the optimal vertical line $\ell=\ell_{*}$. Hence, for these
regions of scaling, Theorem 3.3 readily implies that the excess risk eq. 6
indeed has the decay rates described in Corollary 4.1. As discussed in the
previous section, we expect that these approximation guarantees can be
improved to include a larger region of decay rates, but we leave it to future
work.

A detailed derivation of the result above from the deterministic equivalent
characterization from theorem 3.3 is discussed in Appendix D. The expressions
in eq. 41 are easier to visualise in a diagram. Figure 2 shows the excess risk
exponent $\gamma(\ell,q)$ as a function of the parameters $\ell$ and $q$, in
the case where $\sigma_{\varepsilon}^{2}\neq 0$ for $r\geq\nicefrac{{1}}{{2}}$
(left) and $r<\nicefrac{{1}}{{2}}$ (right). Note that the key difference
between the diagrams is the presence of an additional region for
$r\geq\nicefrac{{1}}{{2}}$.222Recall that these two cases correspond to the
target function $f_{\star}$ belonging ($r\geq\nicefrac{{1}}{{2}}$) or not
($r<\nicefrac{{1}}{{2}}$) to the RKHS spanned by the asymptotic kernel
Defining the following shorthand:

$\displaystyle\ell_{\star}\coloneqq\frac{\alpha}{2\alpha(r\wedge 1)+1},\qquad
q_{\star}\coloneqq 1-\ell_{\star}(2r\wedge
1),\qquad\hat{q}\coloneqq\frac{1}{\alpha(2r\wedge
1)+1}=q_{\star}\vee\frac{1}{\alpha+1}$ (43)

$\ell$$q$$0$$1-\frac{\ell}{\alpha}$$2\ell(r\wedge
1)$$\frac{\alpha-1}{\alpha}\ell+q$$1-q$$\alpha
q$$\alpha$$\ell_{*}$1$q_{*}$$\hat{q}$

$\ell$$q$0$1-q$$1-\frac{\ell}{\alpha}$$2\alpha qr$$2\ell
r$$\alpha$$\ell_{*}$1$q_{*}$

Figure 2: Excess error rate $\gamma$ in the regime
$n\gg\sigma_{\varepsilon}^{-\nicefrac{{1}}{{(\gamma_{\mathcal{B}}(\ell,q)-\gamma_{{\mathcal{V}}}(\ell,q))}}}$
as a function of $(\ell,q)$, defined in eq. 40 and eq. 39 for
$r\geq\nicefrac{{1}}{{2}}$ (Left) and $r\in[0,\nicefrac{{1}}{{2}})$ (Right).
The explicit crossover points $\ell_{\star},q_{\star},\hat{q}$ are defined in
eq. 43 as a function of the source $r$ and capacity $\alpha$ exponents.

we can identify two main regions in the $(\ell,q)$ plane, corresponding to a
trade-off between the bias $\gamma_{\mathcal{B}}$ and variance
$\gamma_{{\mathcal{V}}}$ terms:

  1. (a)

Variance dominated region ($\gamma_{{\mathcal{V}}}<\gamma_{\mathcal{B}}$): if
$\ell>\ell_{\star}$, $q>\hat{q}$ and $p>\lambda$, the excess risk is dominated
by the variance term, provided the number of samples is large enough
$n\gg\sigma_{\varepsilon}^{-\nicefrac{{1}}{{(\gamma_{\mathcal{B}}(\ell,q)-\gamma_{{\mathcal{V}}}(\ell,q))}}}$.333The
noise dominated regime where
$n<\sigma_{\varepsilon}^{-\nicefrac{{1}}{{(\gamma_{\mathcal{B}}(\ell,q)-\gamma_{{\mathcal{V}}}(\ell,q))}}}$
and the corresponding cross-over was studied by Cui et al. (2022). A similar
phenomenology hold here, but for simplicity we focus the discussion on the
data dominated regime. Inside this region it is possible to further
distinguish between two regimes:

     * •

slow decay regime (orange and brown): for $\ell<\alpha$ and $q<1$ ($p\ll n$),
$\gamma_{{\mathcal{V}}}=1-(\nicefrac{{\ell}}{{\alpha}}\wedge q)$, hence the
decay depends on the interplay between regularization strength and number of
random features and it is slower as $(\nicefrac{{\ell}}{{\alpha}}\wedge q)$
increases;

     * •

plateau regime (red): for $\ell\geq\alpha$ and $q\geq 1$ ($p\geq n$) the
excess risk converges to a constant value and does not decay as $n$ increases.

  2. (b)

Bias dominated region ($\gamma_{{\mathcal{V}}}>\gamma_{\mathcal{B}}$): if
$\ell<\ell_{\star}$, $q<\hat{q}$ and $p<\lambda$, the excess risk is dominated
by the bias term, whose decay is faster as $(\nicefrac{{\ell}}{{\alpha}}\wedge
q)$ increases (cyan, emerald and teal).

Note that in the limit of large number of random features $p\to\infty$, we
recover the same rates found by Cui et al. (2022) for kernel ridge regression.
Of particular interest is the rate for which the excess risk decay the fastest
with the number of samples $n$, and what is the minimum number of random
features $p_{\star}$ required to achieve this rate.

######  Corollary 4.2 (Optimal rates).

The optimal excess risk rate achieved by the random features hypothesis eq. 1
under source and capacity conditions eq. 38 and scaling assumptions eq. 39:

$\displaystyle\gamma_{\star}=\max_{\ell,q}\gamma(\ell,q)=\frac{2\alpha(r\wedge
1)}{2\alpha(r\wedge 1)+1},$ (44)

and it is attained for:

$\displaystyle\begin{cases}\lambda=\lambda_{\star}\coloneqq
n^{-(\ell_{\star}-1)}\\\ p\geq p_{\star}\coloneqq
n^{q_{*}}=\lambda_{\star}\end{cases}$ $\displaystyle\text{for
}r\geq\nicefrac{{1}}{{2}},$ (45)
$\displaystyle\begin{cases}\lambda=\lambda_{\star}\\\ p\geq
p_{\star}=\left(\lambda_{\star}^{-1}n\right)^{\nicefrac{{1}}{{\alpha}}}\end{cases}\text{or
}\begin{cases}\lambda\leq\lambda_{\star}\\\
p=p_{\star}=\left(\lambda_{\star}^{-1}n\right)^{\nicefrac{{1}}{{\alpha}}}\end{cases}$
$\displaystyle\text{for }r<\nicefrac{{1}}{{2}}$ (46)

corresponding to the bold red line (—) in fig. 2. In particular, the minimal
number of random features $p_{\star}=n^{q_{\star}}$ required to achieve the
optimal rate $\gamma_{\star}$ is given by:

$\displaystyle q_{\star}=1-\frac{\alpha(2r\wedge 1)}{2\alpha(r\wedge 1)+1}$
(47)

and corresponds to the bold red dot ($\bullet$) in fig. 2.

A few comments on Corollary 4.2 are in place. 1) The optimal excess error rate
eq. 44 is consistent with the minimax optimal rates for ridge regression from
Caponnetto and De Vito (2007), as also discussed by Rudi and Rosasco (2017).
2) The minimal number of random features $p_{\star}=n^{q_{\star}}$ in eq. 47
achieving the optimal rate eq. 44 in the $r\geq\nicefrac{{1}}{{2}}$ regime is
strictly smaller than the lower bound $p>p_{0}$ of Rudi and Rosasco (2017).
More precisely, letting $p_{0}=n^{q_{0}}$, for $r\in[\nicefrac{{1}}{{2}},1)$:

$\displaystyle q_{0}-q_{\star}=\frac{2(1-r)(\alpha-1)}{2\alpha
r+1}>0,\qquad\text{for all $\alpha>1$.}$ (48)

Figure 3: Excess risk eq. 6 of RFRR as a function of the number of samples $n$
under source and capacity conditions eq. 37 and power-law assumptions
$\lambda=n^{-(\ell-1)}$, $p=n^{q}$, with noise variance
$\sigma_{\varepsilon}^{2}=0.1$. Solid lines are obtained from the
deterministic equivalent Theorem 3.3. In the figure on the left, points are
finite size numerical experiments. Dashed and dotted lines are the analytical
rates from Corollary 4.1, stated in the legend. The colour scheme corresponds
to the regions of Fig. 2.

##### Relationship to scaling laws —

The empirical observation that the performance of large scale neural networks
decreases as a power law with respect to the number of samples, parameter and
computing time (Kaplan et al., 2020) has sparked a renewed wave of interest in
the theoretical investigation of power laws. In particular, despite being a
mature topic in the statistical learning literature, different recent works
have turned to the study of linear models under source and capacity conditions
as a playground to understand the emergence of different bottlenecks in the
excess error rates (Bahri et al., 2021; Maloney et al., 2022; Bordelon et al.,
2024; Atanasov et al., 2024; Nam et al., 2024). The approximation limit from
Corollary 3.5 and the kernel limit from Corollary 3.4 are known in this
literature as _Variance_ and _Resolution limited regimes_ , respectively
(Bahri et al., 2021). They correspond precisely to the bottlenecks in the
excess risk arising from the limited approximation capacity of the random
feature model or the limited availability of training data. In particular, the
rates in the variance limited regime in these works follow from Corollary 4.1,
and correspond to particular cases in fig. 2. A detailed connection to this
line of work, including the rates in the resolution limited regime, are
discussed in Appendix E.

#### Acknowledgements

We would like to thank Yasaman Bahri, Hugo Cui and Florent Krzakala for
stimulating discussions. BL acknowledges funding from the Choose France - CNRS
AI Rising Talents program.

## References

  * Aguirre-López et al. [2024] Fabián Aguirre-López, Silvio Franz, and Mauro Pastore.  Random features and polynomial rules, 2024.
  * Atanasov et al. [2024] Alexander B. Atanasov, Jacob A. Zavatone-Veth, and Cengiz Pehlevan.  Scaling and renormalization in high-dimensional regression, 2024.
  * Ba et al. [2022] Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang.  High-dimensional asymptotics of feature learning: How one gradient step improves the representation.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 37932–37946. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/f7e7fabd73b3df96c54a320862afcb78-Paper-Conference.pdf.
  * Bach [2024] Francis Bach.  High-dimensional analysis of double descent for linear regression with random projections.  _SIAM Journal on Mathematics of Data Science_ , 6(1):26–50, 2024.  doi: 10.1137/23M1558781.  URL https://doi.org/10.1137/23M1558781.
  * Bahri et al. [2021] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma.  Explaining neural scaling laws, 2021.
  * Bartlett et al. [2021] Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin.  Deep learning: a statistical viewpoint.  _Acta Numerica_ , 30:87–201, 2021.  doi: 10.1017/S0962492921000027.
  * Belkin [2021] Mikhail Belkin.  Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation.  _Acta Numerica_ , 30:203–248, 2021.  doi: 10.1017/S0962492921000039.
  * Bordelon et al. [2020] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan.  Spectrum dependent learning curves in kernel regression and wide neural networks.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 1024–1034. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/bordelon20a.html.
  * Bordelon et al. [2024] Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan.  A dynamical model of neural scaling laws, 2024.
  * Bosch et al. [2023a] David Bosch, Ashkan Panahi, and Babak Hassibi.  Precise asymptotic analysis of deep random feature models.  In Gergely Neu and Lorenzo Rosasco, editors, _Proceedings of Thirty Sixth Conference on Learning Theory_ , volume 195 of _Proceedings of Machine Learning Research_ , pages 4132–4179. PMLR, 12–15 Jul 2023a.  URL https://proceedings.mlr.press/v195/bosch23a.html.
  * Bosch et al. [2023b] David Bosch, Ashkan Panahi, Ayca Ozcelikkale, and Devdatt Dubhashi.  Random features model with general convex regularization: A fine grained analysis with precise asymptotic learning curves.  In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ , volume 206 of _Proceedings of Machine Learning Research_ , pages 11371–11414. PMLR, 25–27 Apr 2023b.  URL https://proceedings.mlr.press/v206/bosch23a.html.
  * Cagnetta et al. [2023] Francesco Cagnetta, Alessandro Favero, and Matthieu Wyart.  What can be learnt with wide convolutional neural networks?  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 3347–3379. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/cagnetta23a.html.
  * Caponnetto and De Vito [2007] Andrea Caponnetto and Ernesto De Vito.  Optimal rates for the regularized least-squares algorithm.  _Foundations of Computational Mathematics_ , 7(3):331–368, 2007.
  * Cheng and Montanari [2022] Chen Cheng and Andrea Montanari.  Dimension free ridge regression, 2022.
  * Chizat et al. [2019] Lénaïc Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/ae614c557843b1df326cb29c57225459-Paper.pdf.
  * Chouard [2022] Clément Chouard.  Quantitative deterministic equivalent of sample covariance matrices with a general dependence structure, 2022.
  * Chouard [2023] Clément Chouard.  Deterministic equivalent of the conjugate kernel matrix associated to artificial neural networks, 2023.
  * Cui et al. [2022] 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.  doi: 10.1088/1742-5468/ac9829.  URL https://dx.doi.org/10.1088/1742-5468/ac9829.
  * Cui et al. [2023] Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová.  Error scaling laws for kernel classification under source and capacity conditions.  _Machine Learning: Science and Technology_ , 4(3):035033, aug 2023.  doi: 10.1088/2632-2153/acf041.  URL https://dx.doi.org/10.1088/2632-2153/acf041.
  * Cui et al. [2024] Hugo Cui, Luca Pesce, Yatin Dandi, Florent Krzakala, Yue M. Lu, Lenka Zdeborová, and Bruno Loureiro.  Asymptotics of feature learning in two-layer networks after one gradient-step, 2024.
  * Dandi et al. [2023] Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan.  How two-layer neural networks learn, one (giant) step at a time, 2023.
  * Dhifallah and Lu [2020] Oussama Dhifallah and Yue M. Lu.  A precise performance analysis of learning with random features, 2020.
  * Dobriban and Wager [2018] Edgar Dobriban and Stefan Wager.  High-dimensional asymptotics of prediction: Ridge regression and classification.  _The Annals of Statistics_ , 46(1):247–279, 2018.  ISSN 00905364, 21688966.  URL https://www.jstor.org/stable/26542784.
  * Dohmatob et al. [2024] Elvis Dohmatob, Yunzhen Feng, and Julia Kempe.  Model collapse demystified: The case of regression, 2024.
  * Fan and Wang [2020] Zhou Fan and Zhichao Wang.  Spectra of the conjugate kernel and neural tangent kernel for linear-width neural networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 7710–7721. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/572201a4497b0b9f02d4f279b09ec30d-Paper.pdf.
  * Favero et al. [2021] Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart.  Locality defeats the curse of dimensionality in convolutional teacher-student scenarios.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 9456–9467. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper_files/paper/2021/file/4e8eaf897c638d519710b1691121f8cb-Paper.pdf.
  * Gerace et al. [2021] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová.  Generalisation error in learning with random features and the hidden manifold model.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2021(12):124013, dec 2021.  doi: 10.1088/1742-5468/ac3ae6.  URL https://dx.doi.org/10.1088/1742-5468/ac3ae6.
  * Ghorbani et al. [2019] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Limitations of lazy training of two-layers neural network.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/c133fb1bb634af68c5088f3438848bfd-Paper.pdf.
  * Ghorbani et al. [2020] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  When do neural networks outperform kernel methods?  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 14820–14830. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/a9df2255ad642b923d95503b9a7958d8-Paper.pdf.
  * Goldt et al. [2022] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mezard, and Lenka Zdeborova.  The gaussian equivalence of generative models for learning with shallow neural networks.  In Joan Bruna, Jan Hesthaven, and Lenka Zdeborova, editors, _Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference_ , volume 145 of _Proceedings of Machine Learning Research_ , pages 426–471. PMLR, 16–19 Aug 2022.  URL https://proceedings.mlr.press/v145/goldt22a.html.
  * Hastie et al. [2022] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani.  Surprises in high-dimensional ridgeless least squares interpolation.  _The Annals of Statistics_ , 50(2):949 – 986, 2022.  doi: 10.1214/21-AOS2133.  URL https://doi.org/10.1214/21-AOS2133.
  * Hu and Lu [2023] Hong Hu and Yue M. Lu.  Universality laws for high-dimensional learning with random features.  _IEEE Transactions on Information Theory_ , 69(3):1932–1964, 2023.  doi: 10.1109/TIT.2022.3217698.
  * Hu et al. [2024] Hong Hu, Yue M. Lu, and Theodor Misiakiewicz.  Asymptotics of random feature regression beyond the linear scaling regime, 2024.
  * Jacot et al. [2018] Arthur Jacot, Franck Gabriel, and Clement Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf.
  * Kaplan et al. [2020] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models, 2020.
  * Lecun et al. [1998] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.  doi: 10.1109/5.726791.
  * Li et al. [2023] Yicheng Li, haobo Zhang, and Qian Lin.  On the asymptotic learning curves of kernel ridge regression under power-law decay.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 49341–49364. Curran Associates, Inc., 2023.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/9adc8ada9183f4b9a007a02773fd8114-Paper-Conference.pdf.
  * Liao and Couillet [2018] Zhenyu Liao and Romain Couillet.  On the spectrum of random features maps of high dimensional data.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 3063–3071. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/liao18a.html.
  * Loureiro et al. [2022] 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.  doi: 10.1088/1742-5468/ac9825.  URL https://dx.doi.org/10.1088/1742-5468/ac9825.
  * Maloney et al. [2022] Alexander Maloney, Daniel A. Roberts, and James Sully.  A solvable model of neural scaling laws, 2022.
  * Mei and Montanari [2022] Song Mei and Andrea Montanari.  The generalization error of random features regression: Precise asymptotics and the double descent curve.  _Communications on Pure and Applied Mathematics_ , 75(4):667–766, 2022.  doi: https://doi.org/10.1002/cpa.22008.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.22008.
  * Mei et al. [2022] Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration.  _Applied and Computational Harmonic Analysis_ , 59:3–84, 2022.  ISSN 1063-5203.  doi: https://doi.org/10.1016/j.acha.2021.12.003.  URL https://www.sciencedirect.com/science/article/pii/S1063520321001044.  Special Issue on Harmonic Analysis and Machine Learning.
  * Misiakiewicz and Mei [2022] Theodor Misiakiewicz and Song Mei.  Learning with convolution and pooling operations in kernel methods.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 29014–29025. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/ba8aee784ffe0813890288b334444eda-Paper-Conference.pdf.
  * Misiakiewicz and Saeed [2024] Theodor Misiakiewicz and Basil Saeed.  A non-asymptotic theory of kernel ridge regression: deterministic equivalents, test error, and gcv estimator, 2024.
  * Moniri et al. [2024] Behrad Moniri, Donghwan Lee, Hamed Hassani, and Edgar Dobriban.  A theory of non-linear feature learning with one gradient step in two-layer neural networks, 2024.
  * Nakkiran et al. [2021] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever.  Deep double descent: where bigger models and more data hurt.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2021(12):124003, dec 2021.  doi: 10.1088/1742-5468/ac3a74.  URL https://dx.doi.org/10.1088/1742-5468/ac3a74.
  * Nam et al. [2024] Yoonsoo Nam, Nayara Fonseca, Seok Hyeong Lee, and Ard Louis.  An exactly solvable model for emergence and scaling laws, 2024.
  * Rahimi and Recht [2007] Ali Rahimi and Benjamin Recht.  Random features for large-scale kernel machines.  In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, _Advances in Neural Information Processing Systems_ , volume 20. Curran Associates, Inc., 2007.  URL https://proceedings.neurips.cc/paper_files/paper/2007/file/013a006f03dbc5392effeb8f18fda755-Paper.pdf.
  * Rahimi and Recht [2008] Ali Rahimi and Benjamin Recht.  Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning.  In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, _Advances in Neural Information Processing Systems_ , volume 21. Curran Associates, Inc., 2008.  URL https://proceedings.neurips.cc/paper_files/paper/2008/file/0efe32849d230d7f53049ddc4a4b0c60-Paper.pdf.
  * Richards et al. [2021] Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco.  Asymptotics of ridge(less) regression under general source condition.  In Arindam Banerjee and Kenji Fukumizu, editors, _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 3889–3897. PMLR, 13–15 Apr 2021.  URL https://proceedings.mlr.press/v130/richards21b.html.
  * Rudi and Rosasco [2017] 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.  URL https://proceedings.neurips.cc/paper_files/paper/2017/file/61b1fb3f59e28c67f3925f3c79be81a1-Paper.pdf.
  * Schröder et al. [2023] Dominik Schröder, Hugo Cui, Daniil Dmitriev, and Bruno Loureiro.  Deterministic equivalent and error universality of deep random features learning.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 30285–30320. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/schroder23a.html.
  * Schröder et al. [2024] Dominik Schröder, Daniil Dmitriev, Hugo Cui, and Bruno Loureiro.  Asymptotics of learning with deep structured (random) features, 2024.
  * Simon et al. [2023a] James B. Simon, Madeline Dickens, Dhruva Karkada, and Michael R. DeWeese.  The eigenlearning framework: A conservation law perspective on kernel regression and wide neural networks, 2023a.
  * Simon et al. [2023b] James B. Simon, Dhruva Karkada, Nikhil Ghosh, and Mikhail Belkin.  More is better in modern machine learning: when infinite overparameterization is optimal and overfitting is obligatory, 2023b.
  * Spigler et al. [2019] S Spigler, M Geiger, S d’Ascoli, L Sagun, G Biroli, and M Wyart.  A jamming transition from under- to over-parametrization affects generalization in deep learning.  _Journal of Physics A: Mathematical and Theoretical_ , 52(47):474001, oct 2019.  doi: 10.1088/1751-8121/ab4c8b.  URL https://dx.doi.org/10.1088/1751-8121/ab4c8b.
  * Spigler et al. [2020] Stefano Spigler, Mario Geiger, and Matthieu Wyart.  Asymptotic learning curves of kernel methods: empirical data versus teacher–student paradigm.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2020(12):124001, dec 2020.  doi: 10.1088/1742-5468/abc61d.  URL https://dx.doi.org/10.1088/1742-5468/abc61d.
  * Tropp et al. [2015] Joel A Tropp et al.  An introduction to matrix concentration inequalities.  _Foundations and Trends® in Machine Learning_ , 8(1-2):1–230, 2015.
  * Vershynin [2010] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  _arXiv preprint arXiv:1011.3027_ , 2010.
  * Wang et al. [2024] Zhichao Wang, Denny Wu, and Zhou Fan.  Nonlinear spiked covariance matrices and signal propagation in deep neural networks, 2024.
  * Wei et al. [2022] Alexander Wei, Wei Hu, and Jacob Steinhardt.  More than a toy: Random matrix models predict how real-world neural representations generalize.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 23549–23588. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/wei22a.html.
  * Wu and Xu [2020] Denny Wu and Ji Xu.  On the optimal weighted \ell_2 regularization in overparameterized linear regression.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 10112–10123. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/72e6d3238361fe70f22fb0ac624a7072-Paper.pdf.
  * Xiao et al. [2017] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
  * Xiao et al. [2022] Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington.  Precise learning curves and higher-order scalings for dot-product kernel regression.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 4558–4570. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/1d3591b6746204b332acb464b775d38d-Paper-Conference.pdf.
  * Zhang et al. [2017] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization, 2017.

## Appendix

##  Appendix A Background on deterministic equivalents

We consider a feature vector ${\boldsymbol{x}}\in\mathbb{R}^{q}$,
$q\in{\mathbb{N}}\cup\\{\infty\\}$, with covariance matrix
${\boldsymbol{\Gamma}}=\mathbb{E}[{\boldsymbol{x}}{\boldsymbol{x}}^{\mathsf{T}}]$.
We denote $\gamma_{1}^{2}\geq\gamma_{2}^{2}\geq\gamma_{3}^{2}\geq\cdots$ the
eigenvalues of ${\boldsymbol{\Gamma}}$ in non-increasing order. In the case of
infinite-dimensional features $q=\infty$, we will further assume that ${\rm
Tr}({\boldsymbol{\Gamma}})<\infty$, i.e., we consider ${\boldsymbol{\Gamma}}$
to be a trace-class self-adjoint operator.

We assume that the feature ${\boldsymbol{x}}$ satisfies the following
assumption.

######  Assumption A.1 (Feature concentration).

There exist ${\sf c}_{*},{\sf C}_{*}>0$ such that for any p.s.d. matrix
${\boldsymbol{A}}\in\mathbb{R}^{q\times q}$ with ${\rm
Tr}({\boldsymbol{\Gamma}}{\boldsymbol{A}})<\infty$, we have

$\mathbb{P}\left(\left|{\boldsymbol{x}}^{\mathsf{T}}{\boldsymbol{A}}{\boldsymbol{x}}-{\rm
Tr}({\boldsymbol{\Gamma}}{\boldsymbol{A}})\right|\geq
t\cdot\|{\boldsymbol{\Gamma}}^{1/2}{\boldsymbol{A}}{\boldsymbol{\Gamma}}^{1/2}\|_{F}\right)\leq{\sf
C}_{*}\exp\left\\{-{\sf c}_{*}t\right\\}.$ (49)

Recall that we denote $C_{a_{1},\dots,a_{k}}$ constants that only depend on
the values of $\\{a_{i}\\}_{i\in[k]}$. We use $a_{i}=`*$’ to denote the
dependency on the constants ${\sf c}_{*},{\sf C}_{*}$ from Assumption A.1.

We will further define the following two quantities.

######  Definition 2 (Effective regularization).

For an integer $n$, covariance ${\boldsymbol{\Gamma}}$, and regularization
$\lambda\geq 0$, we define the _effective regularization_ $\lambda_{*}$
associated to model $(n,{\boldsymbol{\Gamma}},\lambda)$ to be the unique non-
negative solution to the equation

$n-\frac{\lambda}{\lambda_{*}}={\rm
Tr}\big{(}{\boldsymbol{\Gamma}}({\boldsymbol{\Gamma}}+\lambda_{*})^{-1}\big{)}.$
(50)

######  Definition 3 (Intrinsic dimension).

For a covariance matrix ${\boldsymbol{\Gamma}}\in\mathbb{R}^{q\times q}$ with
eigenvalues in nonincreasing order
$\gamma_{1}^{2}\geq\gamma_{2}^{2}\geq\gamma_{3}^{2}\geq\cdots$, we define the
_intrinsic dimension_ $r_{{\boldsymbol{\Gamma}}}(k)$ at level
$k\in{\mathbb{N}}$ of ${\boldsymbol{\Gamma}}$ to be the intrinsic dimension of
the covariance matrix ${\boldsymbol{\Gamma}}_{\geq k}={\rm
diag}(\gamma_{k}^{2},\gamma_{k+1}^{2},\ldots)$, i.e., the covariance matrix
projected orthogonally to the top $k-1$ eigenspaces, which is given by

$r_{{\boldsymbol{\Gamma}}}(k):=\frac{{\rm Tr}({\boldsymbol{\Gamma}}_{\geq
k})}{\|{\boldsymbol{\Gamma}}_{\geq k}\|_{\rm
op}}=\frac{\sum_{j=k}^{p}\gamma^{2}_{j}}{\gamma^{2}_{k}}.$

The intrinsic dimension of ${\boldsymbol{\Gamma}}_{\geq k}$ captures the
number of dimensions of ${\boldsymbol{\Gamma}}_{\geq k}$ that have significant
spectral content, i.e., $\gamma_{j}^{2}\approx\|{\boldsymbol{\Gamma}}_{\geq
k}\|_{\rm op}$ (see [Tropp et al., 2015, Chapter 7] for further background).

We are given $n$ i.i.d. features $({\boldsymbol{x}}_{i})_{i\in[n]}$, and we
denote
${\boldsymbol{X}}=[{\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{n}]^{\mathsf{T}}\in\mathbb{R}^{n\times
q}$ the feature matrix. We introduce
${\boldsymbol{z}}_{i}={\boldsymbol{\Gamma}}^{-1/2}{\boldsymbol{x}}_{i}$ the
whitened features, and
${\boldsymbol{Z}}={\boldsymbol{X}}{\boldsymbol{\Gamma}}^{-1/2}$ the whitened
feature matrix. The train and test errors are functionals of the feature
matrix ${\boldsymbol{X}}$. In particular, they depend on the following
resolvent matrix

${\boldsymbol{R}}=({\boldsymbol{X}}^{\mathsf{T}}{\boldsymbol{X}}+\lambda{\mathbf{I}}_{q})^{-1}.$

In this section we consider functionals that depend on products of
${\boldsymbol{X}}$, ${\boldsymbol{R}}$ and deterministic matrices.

Throughout this appendix, we assume that $\lambda>0$. The existence and
uniqueness follow from noticing that the left-hand side is monotonically
increasing in $\lambda_{*}$ while the right-hand side is monotonically
decreasing. We consider the change of variable
$\mu_{*}:=\mu_{*}(\lambda)=\lambda/\lambda_{*}$, such that $\mu_{*}$ is the
unique non-negative solution of

$\displaystyle\mu_{*}=\frac{n}{1+{\rm
Tr}({\boldsymbol{\Gamma}}(\mu_{*}{\boldsymbol{\Gamma}}+\lambda)^{-1})}.$ (51)

Both $\mu_{*}$ and $\lambda_{*}$ are increasing functions with $\lambda$.

For a general p.s.d. matrix ${\boldsymbol{A}}\in\mathbb{R}^{q\times q}$,
define the functionals

$\displaystyle\Phi_{1}({\boldsymbol{X}};{\boldsymbol{A}},\lambda):=$
$\displaystyle~{}{\rm
Tr}\left({\boldsymbol{A}}{\boldsymbol{\Gamma}}^{1/2}({\boldsymbol{X}}^{\mathsf{T}}{\boldsymbol{X}}+\lambda)^{-1}{\boldsymbol{\Gamma}}^{1/2}\right),$
$\displaystyle\Phi_{2}({\boldsymbol{X}};\lambda):=$ $\displaystyle~{}{\rm
Tr}\left(\frac{{\boldsymbol{X}}^{\mathsf{T}}{\boldsymbol{X}}}{n}({\boldsymbol{X}}^{\mathsf{T}}{\boldsymbol{X}}+\lambda)^{-1}\right),$
$\displaystyle\Phi_{3}({\boldsymbol{X}};{\boldsymbol{A}},\lambda):=$
$\displaystyle~{}{\rm
Tr}\left({\boldsymbol{A}}{\boldsymbol{\Gamma}}^{1/2}({\boldsymbol{X}}^{\mathsf{T}}{\boldsymbol{X}}+\lambda)^{-1}{\boldsymbol{\Gamma}}({\boldsymbol{X}}^{\mathsf{T}}{\boldsymbol{X}}+\lambda)^{-1}{\boldsymbol{\Gamma}}^{1/2}\right),$
$\displaystyle\Phi_{4}({\boldsymbol{X}};{\boldsymbol{A}},\lambda):=$
$\displaystyle~{}{\rm
Tr}\left({\boldsymbol{A}}{\boldsymbol{\Gamma}}^{1/2}({\boldsymbol{X}}^{\mathsf{T}}{\boldsymbol{X}}+\lambda)^{-1}\frac{{\boldsymbol{X}}^{\mathsf{T}}{\boldsymbol{X}}}{n}({\boldsymbol{X}}^{\mathsf{T}}{\boldsymbol{X}}+\lambda)^{-1}{\boldsymbol{\Gamma}}^{1/2}\right).$

These functionals are well approximated by quantities proportional to

$\displaystyle\Psi_{1}(\lambda_{*};{\boldsymbol{A}}):=$ $\displaystyle~{}{\rm
Tr}\left({\boldsymbol{A}}{\boldsymbol{\Gamma}}({\boldsymbol{\Gamma}}+\lambda_{*})^{-1}\right),$
$\displaystyle\Psi_{2}(\lambda_{*}):=$ $\displaystyle~{}\frac{1}{n}{\rm
Tr}\left({\boldsymbol{\Gamma}}({\boldsymbol{\Gamma}}+\lambda_{*})^{-1}\right),$
$\displaystyle\Psi_{3}(\lambda_{*};{\boldsymbol{A}}):=$
$\displaystyle~{}\frac{1}{n}\cdot\frac{{\rm
Tr}({\boldsymbol{A}}{\boldsymbol{\Gamma}}^{2}({\boldsymbol{\Gamma}}+\lambda_{*})^{-2})}{n-{\rm
Tr}({\boldsymbol{\Gamma}}^{2}({\boldsymbol{\Gamma}}+\lambda_{*})^{-2})}.$

Without loss of generality, we can assume that ${\rm
Tr}({\boldsymbol{A}}{\boldsymbol{\Gamma}})<\infty$ for $\Phi_{1}$, as
otherwise
$\Phi_{1}({\boldsymbol{X}};{\boldsymbol{A}},\lambda)=\Psi_{1}(\mu_{*};{\boldsymbol{A}},\lambda)=\infty$
almost surely, and ${\rm
Tr}({\boldsymbol{A}}{\boldsymbol{\Gamma}}^{2})<\infty$ for $\Phi_{3}$ and
$\Phi_{4}$, as otherwise
$\Phi_{j}({\boldsymbol{X}};{\boldsymbol{A}},\lambda)=\Psi_{j}(\mu_{*};{\boldsymbol{A}},\lambda)=\infty$,
$j=3,4$, almost surely.

Our relative approximation bound will depend on the covariance matrix
${\boldsymbol{\Sigma}}$ through

$\rho_{\lambda}(n)=1+\frac{n\gamma_{\lfloor\eta_{*}\cdot
n\rfloor}^{2}}{\lambda}\left\\{1+\frac{r_{{\boldsymbol{\Gamma}}}(\lfloor\eta_{*}\cdot
n\rfloor)\vee n}{n}\log\big(r_{{\boldsymbol{\Gamma}}}(\lfloor\eta_{*}\cdot
n\rfloor)\vee n\big{missing})\right\\},$ (52)

where $\eta_{*}\in(0,1/2)$ is a constant that will only depend on ${\sf
c}_{*},{\sf C}_{*}$ and we used the convention that
$\gamma_{\lfloor\eta_{*}\cdot n\rfloor}^{2}=0$ if $\lfloor\eta_{*}\cdot
n\rfloor>q$.

The following theorem gathers the approximation guarantees for the different
functionals stated above, and is obtained by modifying [Misiakiewicz and
Saeed, 2024, Theorem 4].

######  Theorem A.2 (Dimension-free deterministic equivalents).

Assume the features $({\boldsymbol{x}}_{i})_{i\in[n]}$ satisfy Assumption A.1
with some constants ${\sf c}_{x},{\sf C}_{x},\beta>0$. For any $D,K>0$, there
exist constants $\eta:=\eta_{x}\in(0,1/2)$ (only depending on ${\sf
c}_{x},{\sf C}_{x},\beta$), $C_{D,K}>0$ (only depending on $K,D$), and
$C_{x,D,K}>0$ (only depending on ${\sf c}_{x},{\sf C}_{x},\beta,D,K$), such
that the following holds. For all $n\geq C_{D,K}$ and $\lambda>0$, if it holds
that

$\lambda\cdot\rho_{\lambda}(n)\geq\|{\boldsymbol{\Gamma}}\|_{\rm op}\cdot
n^{-K},\qquad\rho_{\lambda}(n)^{5/2}\log^{3/2}(n)\leq K\sqrt{n},$ (53)

then for any p.s.d. matrix ${\boldsymbol{A}}$, we have with probability at
least $1-n^{-D}$ that

$\displaystyle\big{|}\Phi_{1}({\boldsymbol{X}};{\boldsymbol{A}},\lambda)-\frac{\lambda_{*}}{\lambda}\Psi_{1}(\lambda_{*};{\boldsymbol{A}})\big{|}\leq$
$\displaystyle~{}C_{x,D,K}\frac{\rho_{\lambda}(n)^{5/2}\log^{3/2}(n)}{\sqrt{n}}\cdot\frac{\lambda_{*}}{\lambda}\Psi_{1}(\lambda_{*};{\boldsymbol{A}}),$
(54)
$\displaystyle\big{|}\Phi_{2}({\boldsymbol{X}};\lambda)-\Psi_{2}(\lambda_{*})\big{|}\leq$
$\displaystyle~{}C_{x,D,K}\frac{\rho_{\lambda}(n)^{5/2}\log^{3/2}(n)}{\sqrt{n}}\Psi_{2}(\lambda_{*}),$
(55)
$\displaystyle\big{|}\Phi_{3}({\boldsymbol{X}};{\boldsymbol{A}},\lambda)-\left(\frac{n\lambda_{*}}{\lambda}\right)^{2}\Psi_{3}(\mu_{*};{\boldsymbol{A}},\lambda)\big{|}\leq$
$\displaystyle~{}C_{x,D,K}\frac{\rho_{\lambda}(n)^{6}\log^{5/2}(n)}{\sqrt{n}}\cdot\left(\frac{n\lambda_{*}}{\lambda}\right)^{2}\Psi_{3}(\mu_{*};{\boldsymbol{A}},\lambda),$
(56)
$\displaystyle\big{|}\Phi_{4}({\boldsymbol{X}};{\boldsymbol{A}},\lambda)-\Psi_{3}(\lambda_{*};{\boldsymbol{A}})\big{|}\leq$
$\displaystyle~{}C_{x,D,K}\frac{\rho_{\lambda}(n)^{6}\log^{3/2}(n)}{\sqrt{n}}\Psi_{3}(\lambda_{*};{\boldsymbol{A}}).$
(57)

###### Proof of Theorem A.2.

The only difference between this theorem and [Misiakiewicz and Saeed, 2024,
Theorem 4] comes from the definition of $\rho_{\lambda}(n)$. This new
definition is obtained by slightly modifying the proof bounding the operator
norm of
${\boldsymbol{\Gamma}}^{1/2}{\boldsymbol{R}}{\boldsymbol{\Gamma}}^{1/2}$ from
[Cheng and Montanari, 2022, Lemma 7.2] and [Misiakiewicz and Saeed, 2024,
Lemma 1]. In particular, we will simply modify step 2 in the proof of
[Misiakiewicz and Saeed, 2024, Lemma 1]. Consider
${\boldsymbol{X}}_{+}=[{\boldsymbol{x}}_{+,1},\ldots,{\boldsymbol{x}}_{+,n}]^{\mathsf{T}}\in\mathbb{R}^{n\times(q-k_{*})}$
where ${\boldsymbol{x}}_{+,i}$ correspond to the projection orthogonal to the
top $k_{*}:=\lfloor\eta_{*}n\rfloor-1$ eigenspaces with covariance matrix

${\boldsymbol{\Gamma}}_{+}:=\mathbb{E}[{\boldsymbol{x}}_{+,i}{\boldsymbol{x}}_{+,i}^{\mathsf{T}}]={\rm
diag}(\gamma_{k_{*}}^{2},\gamma_{k_{*}+1}^{2},\ldots,\gamma_{q}^{2}).$

Then, denoting ${\boldsymbol{S}}=\sum_{i\in[n]}{\boldsymbol{S}}_{i}$ with
${\boldsymbol{S}}_{i}:={\boldsymbol{x}}_{+,i}{\boldsymbol{x}}_{i,+}^{\mathsf{T}}$,
we have with probability at least $1-n^{-D}$, for any $i\in[n]$,

$\|{\boldsymbol{S}}_{i}\|_{\rm op}\leq{\rm
Tr}({\boldsymbol{\Gamma}}_{+})+C_{*,D}\cdot\log(n)\sqrt{\gamma_{k_{*}}^{2}{\rm
Tr}({\boldsymbol{\Gamma}}_{+})}\leq{\rm
Tr}({\boldsymbol{\Gamma}}_{+})\left(1+C_{*,D}\frac{\log(n)}{\sqrt{r_{\boldsymbol{\Gamma}}(k_{*})}}\right)=:L_{n}.$

Denoting
$\widetilde{{\boldsymbol{S}}}=\sum_{i\in[n]}\widetilde{{\boldsymbol{S}}}_{i}$
with
$\widetilde{{\boldsymbol{S}}}_{i}:={\boldsymbol{S}}_{i}\mathbbm{1}_{\|{\boldsymbol{S}}_{i}\|_{\rm
op}\leq L_{n}}$, so that $\widetilde{{\boldsymbol{S}}}={\boldsymbol{S}}$ with
probability at least $1-n^{-D}$, we obtain

$\|\widetilde{{\boldsymbol{S}}}\|_{\rm op}\leq
nL_{n}\gamma_{k_{*}}^{2}=:v_{n},\qquad\quad\|\mathbb{E}[\widetilde{{\boldsymbol{S}}}]\|_{\rm
op}\leq n\|\mathbb{E}[{\boldsymbol{S}}_{i}]\|_{\rm op}=n\gamma_{k_{*}}^{2}.$

Therefore, applying the matrix Bernstein’s inequality with intrinsic dimension
[Tropp et al., 2015, Theorem 7.3.1] to $\widetilde{{\boldsymbol{S}}}$ gives
that with probability at least $1-n^{-D}$,

$\displaystyle\|\widetilde{{\boldsymbol{S}}}\|_{\rm op}\leq$
$\displaystyle~{}n\gamma_{k_{*}}^{2}+C_{D}\left(\sqrt{v_{n}}+L_{n}\right)\sqrt{\log(r_{\boldsymbol{\Gamma}}(k_{*})n)}$
$\displaystyle\leq$
$\displaystyle~{}n\gamma_{k_{*}}^{2}+C_{D}L_{n}\log(r_{\boldsymbol{\Gamma}}(k_{*})n)$
$\displaystyle\leq$
$\displaystyle~{}n\gamma_{k_{*}}^{2}\left\\{1+\frac{r_{{\boldsymbol{\Gamma}}}(k_{*})}{n}\left(1+C_{*,D}\frac{\log(n)}{\sqrt{r_{\boldsymbol{\Gamma}}(k_{*})}}\right)\log(r_{\boldsymbol{\Gamma}}(k_{*})n)\right\\}.$

Note that by the condition of our theorem, $\log(n)\leq K\sqrt{n}$, and
therefore

$\displaystyle\|\widetilde{{\boldsymbol{S}}}\|_{\rm op}\leq$
$\displaystyle~{}C_{*,D,K}\cdot
n\gamma_{k_{*}}^{2}\left\\{1+\frac{r_{{\boldsymbol{\Gamma}}}(k_{*})}{n}\left(1+\sqrt{\frac{n}{r_{\boldsymbol{\Gamma}}(k_{*})}}\right)\log(r_{\boldsymbol{\Gamma}}(k_{*})n)\right\\}$
$\displaystyle\leq$ $\displaystyle~{}C_{*,D,K}\cdot
n\gamma_{k_{*}}^{2}\left\\{1+\frac{r_{{\boldsymbol{\Gamma}}}(k_{*})\vee
n}{n}\log(r_{{\boldsymbol{\Gamma}}}(k_{*})\vee n)\right\\}.$

Following the rest of the argument in [Misiakiewicz and Saeed, 2024, Lemma 1]
we obtain $\rho_{\lambda}(n)$ in Eq. (52). ∎

##  Appendix B Proof of the deterministic equivalent for RFRR

In this appendix, we prove the approximation guarantees stated in Theorem 3.3
between the test error of RFRR and its deterministic equivalent. We start in
Section B.1 by introducing background and notations that we will use
throughout the proof. Section B.2 introduces key results on the covariance
matrix and the fixed points. We then leverage these results to prove
deterministic equivalents for different functionals of
${\boldsymbol{Z}}=(\sigma(\langle{\boldsymbol{x}}_{i},{\boldsymbol{w}}_{j}\rangle))_{i\in[n],j\in[p]}\in\mathbb{R}^{n\times
p}$ conditional on $({\boldsymbol{w}}_{j})_{j\in[p]}$ in Section B.3, and
functionals of
${\boldsymbol{F}}=(\xi_{k}\phi_{k}({\boldsymbol{w}}_{j}))_{j\in[p],k\geq
1}\in\mathbb{R}^{p\times\infty}$ in Section B.4. Given these deterministic
equivalents, we prove our approximation guarantees for the variance term in
Section B.5, and for the bias term in B.6. Finally, we deffer the proof of
some technical results to Section B.7.

###  B.1 Preliminaries

Recall that throughout the paper, we will keep track of the parameters of the
problem $(n,p,{\boldsymbol{\Sigma}},\lambda,\sigma_{\varepsilon}^{2})$. For
the other constants ${\sf C}_{*},K,D$, we will denote
$C_{a_{1},a_{2},\ldots,a_{k}}$ constants that only depend on the values of
$\\{a_{i}\\}_{i\in[k]}$. We use $a_{i}=`*$’ to denote the dependency on the
constant ${\sf C}_{*}$ appearing in Assumption 3.1 and Assumption 3.2.

Throughout this appendix, we will directly work in the ‘feature space’

${\boldsymbol{g}}_{i}:=(\psi_{k}({\boldsymbol{x}}_{i}))_{k\geq
1},\qquad\quad\text{ and
}\qquad\quad\boldsymbol{f}_{j}:=(\xi_{k}\psi_{k}({\boldsymbol{w}}_{j}))_{j\geq
1},$

with distribution induced by ${\boldsymbol{x}}_{i}\sim\mu_{x}$ and
${\boldsymbol{w}}_{j}\sim\mu_{w}$. We will denote the covariate feature and
weight feature matrices by

${\boldsymbol{G}}:=[{\boldsymbol{g}}_{1},\ldots,{\boldsymbol{g}}_{n}]^{\mathsf{T}}\in\mathbb{R}^{n\times\infty},\qquad\qquad{\boldsymbol{F}}:=[\boldsymbol{f}_{1},\ldots,\boldsymbol{f}_{p}]^{\mathsf{T}}\in\mathbb{R}^{p\times\infty}.$

We denote the random feature weight vector

${\boldsymbol{z}}_{i}:=\frac{1}{\sqrt{p}}[\sigma(\langle{\boldsymbol{w}}_{1},{\boldsymbol{x}}_{i}\rangle),\ldots,\sigma(\langle{\boldsymbol{w}}_{p},{\boldsymbol{x}}_{i})]=\frac{1}{\sqrt{p}}{\boldsymbol{F}}{\boldsymbol{g}}_{i}\in\mathbb{R}^{p},$

and the associated feature matrix

${\boldsymbol{Z}}=[{\boldsymbol{z}}_{1},\ldots,{\boldsymbol{z}}_{n}]^{\mathsf{T}}=\frac{1}{\sqrt{p}}{\boldsymbol{G}}{\boldsymbol{F}}^{\mathsf{T}}\in\mathbb{R}^{n\times
p}.$

Note that $\boldsymbol{f}$ has covariance matrix

${\boldsymbol{\Sigma}}:=\mathbb{E}[\boldsymbol{f}\boldsymbol{f}^{\mathsf{T}}]={\rm
diag}(\xi_{1}^{2},\xi_{2}^{2},\xi_{3}^{2},\ldots).$

We will further introduce the covariance matrix of ${\boldsymbol{z}}$
conditional on the weight feature matrix ${\boldsymbol{F}}$ (i.e., conditional
on $({\boldsymbol{w}}_{j})_{j\in[p]}$)

$\widehat{{\boldsymbol{\Sigma}}}_{{\boldsymbol{F}}}:=\mathbb{E}_{{\boldsymbol{z}}}\left[{\boldsymbol{z}}{\boldsymbol{z}}^{\mathsf{T}}\Big{|}{\boldsymbol{F}}\right]=\frac{1}{p}{\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}\in\mathbb{R}^{p\times
p}.$ (58)

Note that under Assumption 3.1, the features ${\boldsymbol{z}}$ and
$\boldsymbol{f}$ satisfy the following assumption.

######  Assumption B.1 (Concentration of the features ${\boldsymbol{z}}$ and
$\boldsymbol{f}$).

There exists a constant ${\sf C}_{*}>0$ such that for any weight feature
matrix ${\boldsymbol{F}}\in\mathbb{R}^{p\times\infty}$ and deterministic
p.s.d. matrix ${\boldsymbol{A}}\in\mathbb{R}^{p\times p}$ with ${\rm
Tr}(\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}{\boldsymbol{A}})<\infty$,
we have

$\mathbb{P}_{{\boldsymbol{z}}|{\boldsymbol{F}}}\left(\left|{\boldsymbol{z}}^{\mathsf{T}}{\boldsymbol{A}}{\boldsymbol{z}}-{\rm
Tr}(\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}{\boldsymbol{A}})\right|\geq
t\cdot\big{\|}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}^{1/2}{\boldsymbol{A}}\widehat{{\boldsymbol{\Sigma}}}^{1/2}_{{\boldsymbol{F}}}\big{\|}_{F}\right)\leq{\sf
C}_{*}\exp\left\\{-t/{\sf C}_{x}\right\\},$ (59)

and for any deterministic p.s.d. matrix
${\boldsymbol{B}}\in\mathbb{R}^{\infty\times\infty}$ with ${\rm
Tr}({\boldsymbol{\Sigma}}{\boldsymbol{B}})<\infty$,

$\mathbb{P}_{\boldsymbol{f}}\left(\left|\boldsymbol{f}^{\mathsf{T}}{\boldsymbol{A}}\boldsymbol{f}-{\rm
Tr}({\boldsymbol{\Sigma}}{\boldsymbol{B}})\right|\geq
t\cdot\big{\|}{\boldsymbol{\Sigma}}^{1/2}{\boldsymbol{B}}{\boldsymbol{\Sigma}}^{1/2}\big{\|}_{F}\right)\leq{\sf
C}_{*}\exp\left\\{-t/{\sf C}_{x}\right\\}.$ (60)

We will assume in the rest of this appendix that Assumption B.1 holds. Using
the notations introduced above, we restate our setting below. Recall that we
consider learning a target function
$h_{*}({\boldsymbol{g}}):={\boldsymbol{g}}^{\mathsf{T}}{\boldsymbol{\beta}}_{*}$
from i.i.d. samples $(y_{i},{\boldsymbol{g}}_{i})_{i\in[n]}$ with

$y_{i}={\boldsymbol{g}}_{i}^{\mathsf{T}}{\boldsymbol{\beta}}_{*}+\varepsilon_{i},$

where $\varepsilon_{i}$ are independent noise with
$\mathbb{E}[\varepsilon_{i}]=0$ and
$\mathbb{E}[\varepsilon_{i}^{2}]=\sigma_{\varepsilon}^{2}$. Denote
${\boldsymbol{y}}=(y_{1},\ldots,y_{n})$ the vector containing the labels. We
fit this data using a random feature model with i.i.d. random weight features
$(\boldsymbol{f}_{j})_{j\in[p]}$

$\hat{f}({\boldsymbol{g}})=\frac{1}{\sqrt{p}}{\boldsymbol{g}}^{\mathsf{T}}{\boldsymbol{F}}^{\mathsf{T}}{\boldsymbol{a}},\qquad\quad{\boldsymbol{a}}\in\mathbb{R}^{p}.$
(61)

We fit the parameter ${\boldsymbol{a}}$ using random feature ridge regression
(RFRR)

${\hat{\boldsymbol{a}}}_{\lambda}=\operatorname*{arg\,min}_{{\boldsymbol{a}}\in\mathbb{R}^{p}}\left\\{\|{\boldsymbol{y}}-{\boldsymbol{Z}}{\boldsymbol{a}}\|_{2}^{2}+\lambda\|{\boldsymbol{a}}\|_{2}^{2}\right\\}=({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\lambda)^{-1}{\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{y}}.$
(62)

The test error is then given by

$\displaystyle\mathcal{R}_{{\rm
test}}(h_{*};{\boldsymbol{G}},{\boldsymbol{F}},\lambda):=$
$\displaystyle~{}\mathbb{E}_{\boldsymbol{\varepsilon}}\left\\{\mathbb{E}_{{\boldsymbol{g}}}\left[\left({\boldsymbol{g}}^{\mathsf{T}}{\boldsymbol{\beta}}_{*}-\frac{1}{\sqrt{p}}{\boldsymbol{g}}^{\mathsf{T}}{\boldsymbol{F}}^{\mathsf{T}}{\hat{\boldsymbol{a}}}_{\lambda}\right)^{2}\right]\right\\}$
(63) $\displaystyle=$
$\displaystyle~{}\mathcal{B}({\boldsymbol{\beta}}_{*};{\boldsymbol{G}},{\boldsymbol{F}},\lambda)+{\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda),$

where the bias and variance terms are given explicitly by

$\displaystyle\mathcal{B}({\boldsymbol{\beta}}_{*};{\boldsymbol{G}},{\boldsymbol{F}},\lambda)=$
$\displaystyle~{}\|{\boldsymbol{\beta}}_{*}-p^{-1/2}{\boldsymbol{F}}^{\mathsf{T}}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\lambda)^{-1}{\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{G}}{\boldsymbol{\beta}}_{*}\|_{2}^{2},$
(64) $\displaystyle{\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)=$
$\displaystyle~{}\sigma_{\varepsilon}^{2}\cdot{\rm
Tr}\big{(}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}{\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\lambda)^{-2}\big{)}.$
(65)

Note that both the bias and variance terms are random quantities that depend
on the random matrices ${\boldsymbol{G}},{\boldsymbol{F}}$. The goal of this
appendix is to prove non-asymptotic and multiplicative approximation
guarantees between these two terms and deterministic quantities that only
depend on the parameters of the model
$(n,p,{\boldsymbol{\Sigma}},{\boldsymbol{\beta}}_{*},\lambda,\sigma_{\varepsilon}^{2})$,
i.e., we will show that with high probability

$\displaystyle\left|\mathcal{B}({\boldsymbol{\beta}}_{*};{\boldsymbol{G}},{\boldsymbol{F}},\lambda)-\mathsf{B}_{n,p}({\boldsymbol{\beta}}_{*},\lambda)\right|=$
$\displaystyle~{}\widetilde{O}\left(n^{-1/2}+p^{-1/2}\right)\cdot\mathsf{B}_{n,p}({\boldsymbol{\beta}}_{*},\lambda),$
$\displaystyle\left|{\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)-\mathsf{V}_{n,p}(\lambda)\right|=$
$\displaystyle~{}\widetilde{O}\left(n^{-1/2}+p^{-1/2}\right)\cdot\mathsf{V}_{n,p}(\lambda),$

where $\mathsf{B}_{n,p}({\boldsymbol{\beta}}_{*},\lambda)$ and
$\mathsf{V}_{n,p}(\lambda)$ are defined in Eqs (18) and (19), and the
approximation rates $\widetilde{O}(\cdot)$ are explicit in terms of the model
parameters.

The proof of these approximation guarantees will proceed in two steps. We
first show that the bias and variance terms conditional on ${\boldsymbol{F}}$
are well approximated by functionals that only depend on ${\boldsymbol{F}}$,
i.e.,

$\displaystyle\left|\mathcal{B}({\boldsymbol{\beta}}_{*};{\boldsymbol{G}},{\boldsymbol{F}},\lambda)-\widetilde{\mathcal{B}}({\boldsymbol{\beta}}_{*};{\boldsymbol{F}},\lambda)\right|=$
$\displaystyle~{}\widetilde{O}\left(n^{-1/2}\right)\cdot\widetilde{\mathcal{B}}({\boldsymbol{\beta}}_{*};{\boldsymbol{F}},\lambda),$
(66)
$\displaystyle\left|{\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)-\widetilde{{\mathcal{V}}}({\boldsymbol{F}},\lambda)\right|=$
$\displaystyle~{}\widetilde{O}\left(n^{-1/2}\right)\cdot\widetilde{{\mathcal{V}}}({\boldsymbol{F}},\lambda).$

We then show that
$\widetilde{\mathcal{B}}({\boldsymbol{\beta}}_{*};{\boldsymbol{F}},\lambda)$
and $\widetilde{{\mathcal{V}}}({\boldsymbol{F}},\lambda)$ are well
approximated by $\mathsf{B}_{n,p}({\boldsymbol{\beta}}_{*},\lambda)$ and
$\mathsf{V}_{n,p}(\lambda)$ with

$\displaystyle\left|\widetilde{\mathcal{B}}({\boldsymbol{\beta}}_{*};{\boldsymbol{F}},\lambda)-\mathsf{B}_{n,p}({\boldsymbol{\beta}}_{*},\lambda)\right|=$
$\displaystyle~{}\widetilde{O}\left(p^{-1/2}\right)\cdot\mathsf{B}_{n,p}({\boldsymbol{\beta}}_{*},\lambda),$
(67)
$\displaystyle\left|\widetilde{{\mathcal{V}}}({\boldsymbol{F}},\lambda)-\mathsf{V}_{n,p}(\lambda)\right|=$
$\displaystyle~{}\widetilde{O}\left(p^{-1/2}\right)\cdot\mathsf{V}_{n,p}(\lambda).$

For each of these two steps, we will apply general results showing
deterministic equivalents for functionals of (possibly infinite-dimensional)
random matrices proved in Misiakiewicz and Saeed [2024] (see Appendix A and in
particular Theorem A.2 for some background). Note that when writing the proof,
we will directly show Eq. (66) assuming that ${\boldsymbol{F}}$ is in some
good event ${\boldsymbol{F}}\in{\mathcal{A}}_{\mathcal{F}}$, where
$\mathbb{P}_{\boldsymbol{F}}({\mathcal{A}}_{\mathcal{F}})\geq 1-p^{-D}$, so
that we can immediately write functionals with regularization parameter that
does not depend on $\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}$, and
therefore the rate will be directly
$\widetilde{O}\left(n^{-1/2}+p^{-1/2}\right)$. However, we can reorganize the
proof to indeed get the separate contributions (66) and (67) to the
approximation error rate.

The rest of Appendix B is devoted to implementing this proof strategy. We
start in the next three sections by introducing key technical results which we
will use in the analysis of the bias and variance terms.

###  B.2 Fixed points, feature covariance matrix, and tail rank

Recall that our deterministic equivalents will depend on the fixed points
$(\nu_{1},\nu_{2})\in\mathbb{R}^{2}_{>0}$ stated in Definition 1. Furthermore,
our approximation guarantees will depend on the covariance matrix
${\boldsymbol{\Sigma}}$ through $\rho_{\kappa}(p)$ and
$\widetilde{\rho}_{\kappa}(n,p)$ which we restate below for convenience

$\displaystyle M_{\boldsymbol{\Sigma}}(k)=$
$\displaystyle~{}1+\frac{r_{{\boldsymbol{\Sigma}}}(\lfloor\eta_{*}\cdot
k\rfloor)\vee k}{k}\log\left(r_{{\boldsymbol{\Sigma}}}(\lfloor\eta_{*}\cdot
k\rfloor)\vee k\right),$ (68) $\displaystyle\rho_{\kappa}(p)=$
$\displaystyle~{}1+\frac{p\cdot\xi^{2}_{\lfloor\eta_{*}\cdot
p\rfloor}}{\kappa}M_{\boldsymbol{\Sigma}}(p),$ (69)
$\displaystyle\widetilde{\rho}_{\kappa}(n,p)=$
$\displaystyle~{}1+\mathbbm{1}[n\leq
p/\eta_{*}]\cdot\left\\{\frac{n\xi_{\lfloor\eta_{*}\cdot
n\rfloor}^{2}}{\kappa}+\frac{n}{p}\cdot\rho_{\kappa}(p)\right\\}M_{\boldsymbol{\Sigma}}(n),$
(70)

where $\eta_{*}\in(0,1/4)$ is a constant that only depends on ${\sf C}_{*}$
appearing in Assumption B.1, and $r_{\boldsymbol{\Sigma}}(k)$ is the intrinsic
dimension of ${\boldsymbol{\Sigma}}$ at level $k$ (see Definition 3)

$r_{\boldsymbol{\Sigma}}(k)=\frac{\sum_{j=k}^{p}\xi^{2}_{j}}{\xi^{2}_{k}}.$

Observe that $\widetilde{\rho}_{\kappa}(n,p)$ is well defined for $n\to\infty$
while $p$ stays constant with $\widetilde{\rho}_{\kappa}(\infty,p)=1$, and for
$p\to\infty$ while $n$ stays constant with
$\widetilde{\rho}_{\kappa}(n,\infty)=\rho_{\kappa}(n)$ (under the conditions
in our setting that $\rho_{\kappa}(p)\leq K\sqrt{p}$ for some constant $K$).

In this section, we introduce and prove properties on the fixed point
$(\nu_{1},\nu_{2})\in\mathbb{R}^{2}_{>0}$ and the weight feature matrix
${\boldsymbol{F}}$ which we will use to prove deterministic equivalents.

##### Feature covariance matrix.

The features ${\boldsymbol{z}}_{i}\in\mathbb{R}^{p}$ conditional on
${\boldsymbol{F}}$ are i.i.d. random vectors with covariance
$\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}={\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}/p$.
We first show that with high probability over ${\boldsymbol{F}}$, this feature
covariance matrix has eigenvalues and intrinsic dimensions bounded by the ones
of ${\boldsymbol{\Sigma}}$.

Denote $(\hat{\xi}_{1}^{2},\hat{\xi}_{2}^{2},\ldots\hat{\xi}_{p}^{2})$ the $p$
eigenvalues of $\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}$ in
nonincreasing order. Applying the definition of the intrinsic dimension at
level $k$ to $\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}$, we have for
any $k=1,\ldots,p$,

$r_{\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}}(k)=\frac{\sum_{j=k}^{p}\hat{\xi}_{j}^{2}}{\hat{\xi}_{k}^{2}}.$
(71)

Applying Theorem A.2 directly to functionals of ${\boldsymbol{Z}}$ conditional
on ${\boldsymbol{F}}$, the approximation guarantees depend on

$\widehat{\rho}_{\lambda}(n)=1+\frac{n\cdot\hat{\xi}^{2}_{\lfloor\eta_{*}\cdot
n\rfloor}}{\lambda}\left\\{1+\frac{r_{\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}}(\lfloor\eta_{*}\cdot
n\rfloor)\vee
n}{n}\log\left(r_{\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}}(\lfloor\eta_{*}\cdot
n\rfloor)\vee n\right)\right\\},$ (72)

which simply corresponds to $\rho_{\lambda}$ defined in Eq. (52) applied to
$\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}$ where we recall that
$\hat{\xi}^{2}_{\lfloor\eta_{*}\cdot n\rfloor}=0$ if $\lfloor\eta_{*}\cdot
n\rfloor>p$. The next lemma shows that with high probability over
${\boldsymbol{F}}$, we have
$\widehat{\rho}_{\lambda}(n)\lesssim\widetilde{\rho}_{\lambda}(n,p)$ for all
$n\in{\mathbb{N}}$.

######  Lemma B.2 (Feature covariance matrix).

Assume the feature vectors $\\{\boldsymbol{f}_{j}\\}_{j\in[p]}$ satisfy
Assumption B.1. Then for any $D,K>0$, there exist constants
$\eta_{*}\in(0,1/4)$ and $C_{*,D,K}>0$ such that the following holds. For any
$p\geq C_{*,D,K}$, the event

$\widetilde{{\mathcal{A}}}_{{\mathcal{F}}}=\left\\{{\boldsymbol{F}}\in\mathbb{R}^{p\times\infty}\;:\;\|\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}\|_{\rm
op}\geq\frac{1}{2},\;\;\;\widehat{\rho}_{\lambda}(n)\leq
C_{*,D,K}\cdot\widetilde{\rho}_{\lambda}(n,p),\;\;\forall
n\in{\mathbb{N}},\lambda\in\mathbb{R}\right\\}$ (73)

holds with probability at least $1-p^{-D}$.

We defer the proof of this lemma to Section B.7.1.

##### High-degree part of the feature matrix ${\boldsymbol{F}}$.

Recall that $(\nu_{1},\nu_{2})\in\mathbb{R}_{>0}^{2}$ are the solutions to the
fixed point equations stated in Definition 1. In order to get approximation
guarantees when $p\nu_{1}\to 0$ as $n\to\infty$, we will analyze separately
the top eigenspaces of ${\boldsymbol{F}}$ from the rest. For an integer
${\mathsf{m}}\in{\mathbb{N}}$, we split the feature vector
$\boldsymbol{f}_{j}=[\boldsymbol{f}_{0,j},\boldsymbol{f}_{+,j}]$ where
$\boldsymbol{f}_{0,j}\in\mathbb{R}^{{\mathsf{m}}}$ corresponds to the top
${\mathsf{m}}$ coordinates with covariance

${\boldsymbol{\Sigma}}_{0}:=\mathbb{E}[\boldsymbol{f}_{0,j}\boldsymbol{f}_{0,j}^{\mathsf{T}}]={\rm
diag}(\xi_{1}^{2},\xi_{2}^{2},\ldots,\xi_{{\mathsf{m}}}^{2}),$

and $\boldsymbol{f}_{+,j}\in\mathbb{R}^{\infty}$ corresponds to the high
degree features orthogonal to the top ${\mathsf{m}}$ eigenspaces. We denote
their covariance

${\boldsymbol{\Sigma}}_{+}:=\mathbb{E}[\boldsymbol{f}_{+,j}\boldsymbol{f}_{+,j}^{\mathsf{T}}]={\rm
diag}(\xi_{{\mathsf{m}}+1}^{2},\xi_{{\mathsf{m}}+2}^{2},\ldots).$

We split the weight feature matrix intro
${\boldsymbol{F}}=[{\boldsymbol{F}}_{0},{\boldsymbol{F}}_{+}]$, where

${\boldsymbol{F}}_{0}=[\boldsymbol{f}_{0,1},\ldots,\boldsymbol{f}_{0,p}]^{\mathsf{T}}\in\mathbb{R}^{p\times
m},\qquad\quad{\boldsymbol{F}}_{+}=[\boldsymbol{f}_{+,1},\ldots,\boldsymbol{f}_{+,p}]^{\mathsf{T}}\in\mathbb{R}^{p\times\infty}.$

We will use that for ${\mathsf{m}}$ chosen such that
$p\cdot\xi_{{\mathsf{m}}+1}\ll{\rm Tr}({\boldsymbol{\Sigma}}_{+})$, we have
with high probability

$\|{\boldsymbol{F}}_{+}{\boldsymbol{F}}_{+}^{\mathsf{T}}-{\rm
Tr}({\boldsymbol{\Sigma}}_{+})\cdot{\mathbf{I}}_{p}\|_{\rm
op}\lesssim\sqrt{p\cdot\xi_{{\mathsf{m}}+1}{\rm
Tr}({\boldsymbol{\Sigma}}_{+})}\ll{\rm Tr}({\boldsymbol{\Sigma}}_{+}),$

and therefore

${\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}+\kappa\approx{\boldsymbol{F}}_{0}{\boldsymbol{F}}_{0}^{\mathsf{T}}+\gamma(\kappa),$

where we defined the function

$\gamma(\kappa):=\kappa+{\rm Tr}({\boldsymbol{\Sigma}}_{+}).$

To simplify the final statement of our results, we assume that we can choose
${\mathsf{m}}$ such that
$p^{2}\xi_{{\mathsf{m}}+1}^{2}\leq\gamma(p\lambda/n)$. Note that
$\nu_{1}\geq\lambda/n$ from the fixed point equations and
$\gamma(p\lambda/n)\leq\gamma(p\nu_{1})$ (e.g., see Equation (76)). For
convenience, we will further denote

$\gamma_{+}:=\gamma(p\nu_{1}),\qquad\qquad\gamma_{\lambda}:=\gamma(p\lambda/n).$
(74)

######  Lemma B.3 (Concentration of high-degree part of ${\boldsymbol{F}}$).

Assume that $(\boldsymbol{f}_{+,j})_{j\in[p]}$ satisfy Assumption B.1 and
${\mathsf{m}}\in{\mathbb{N}}$ is chosen such that
$p^{2}\xi_{{\mathsf{m}}+1}^{2}\leq\gamma(p\lambda/n)$. Then for any $D>0$,
there exists a constant $C_{*,D}>0$ such that with probability at least
$1-p^{-D}$,

$\|{\boldsymbol{F}}_{+}{\boldsymbol{F}}_{+}^{\mathsf{T}}-{\rm
Tr}({\boldsymbol{\Sigma}}_{+})\cdot{\mathbf{I}}_{p}\|_{\rm op}\leq
C_{*,D}\frac{\log^{3}(p)}{\sqrt{p}}\gamma_{\lambda}\leq
C_{*,D}\frac{\log^{3}(p)}{\sqrt{p}}\gamma_{+}.$

This lemma follows directly from [Misiakiewicz and Saeed, 2024, Proposition
9].

##### Effective regularization and fixed points.

Conditional on ${\boldsymbol{F}}$, the bias and variance are functionals of
the random matrix ${\boldsymbol{Z}}$ which has $n$ i.i.d. rows with
regularization parameter $\lambda$ and covariance
$\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}$. The deterministic
approximations to these functionals depend on an “effective regularization”
$\tilde{\nu}_{1}$ associated to
$(n,\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}},\lambda)$ (see Definition
2 in Appendix A for background) which is given as the unique non-negative
solution to the equation

$n-\frac{\lambda}{\tilde{\nu}_{1}}={\rm
Tr}\big{(}\widehat{{\boldsymbol{\Sigma}}}_{{\boldsymbol{F}}}\big{(}\widehat{{\boldsymbol{\Sigma}}}_{{\boldsymbol{F}}}+\tilde{\nu}_{1}\big{)}^{-1}\big{)}.$

Note that the right-hand side can be rewritten as

${\rm
Tr}\big{(}\widehat{{\boldsymbol{\Sigma}}}_{{\boldsymbol{F}}}\big{(}\widehat{{\boldsymbol{\Sigma}}}_{{\boldsymbol{F}}}+\tilde{\nu}_{1}\big{)}^{-1}\big{)}={\rm
Tr}\big{(}{\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}+p\tilde{\nu}_{1})^{-1}\big{)},$
(75)

which is itself of functional of the random matrix ${\boldsymbol{F}}$ which
has $p$ i.i.d. rows with regularization parameter $p\tilde{\nu}_{1}$ and
covariance ${\boldsymbol{\Sigma}}$. Note that $\tilde{\nu}_{1}$ is a random
variable depending itself on ${\boldsymbol{F}}$. However we will show that it
concentrates on a deterministic value $\nu_{1}$. We therefore introduce a
second effective regularization $\nu_{2}$ associated to
$(p,{\boldsymbol{\Sigma}},p\nu_{1})$ given as the unique non-negatice solution
of the equation

$p-\frac{p\nu_{1}}{\nu_{2}}={\rm
Tr}\left({\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\right).$

The functional (75) is then well approximated by

${\rm
Tr}\big{(}{\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}+p\tilde{\nu}_{1})^{-1}\big{)}=(1+o_{p,\mathbb{P}}(1))\cdot{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\big{)}.$

This motivates to define $(\nu_{1},\nu_{2})\in\mathbb{R}_{>0}^{2}$ as the
unique non-negative solutions to the coupled fixed point equations

$\displaystyle n-\frac{\lambda}{\nu_{1}}=$ $\displaystyle~{}{\rm
Tr}\left({\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\right),$
(76) $\displaystyle p-\frac{p\nu_{1}}{\nu_{2}}=$ $\displaystyle~{}{\rm
Tr}\left({\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\right).$

Writing $\nu_{1}$ as a function of $\nu_{2}$ indeed produces the equations
stated in Definition 1.

To show that $\tilde{\nu}_{1}$ concentrates on $\nu_{1}$, we define the
following fixed points
$(\tilde{\nu}_{1},\tilde{\nu}_{2})\in\mathbb{R}_{>0}^{2}$ to be the unique
positive solutions to the random equations

$\displaystyle n-\frac{\lambda}{\tilde{\nu}_{1}}=$ $\displaystyle~{}{\rm
Tr}\big{(}\widehat{{\boldsymbol{\Sigma}}}_{{\boldsymbol{F}}}\big{(}\widehat{{\boldsymbol{\Sigma}}}_{{\boldsymbol{F}}}+\tilde{\nu}_{1}\big{)}^{-1}\big{)},$
(77) $\displaystyle p-\frac{p\tilde{\nu}_{1}}{\tilde{\nu}_{2}}=$
$\displaystyle~{}{\rm
Tr}\left({\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\tilde{\nu}_{2})^{-1}\right).$

The following proposition shows that $(\tilde{\nu}_{1},\tilde{\nu}_{2})$ is
well approximated by $(\nu_{1},\nu_{2})$ with high probability.

######  Proposition B.4 (Concentration of the fixed points).

Assume that $(\boldsymbol{f}_{j})_{j\in[p]}$ satisfy Assumption B.1. Then for
any $D,K>0$, there exist constants $\eta_{*}\in(0,1/4)$ and $C_{*,D,K}>0$ such
that the following holds. Let $\rho_{\kappa}(p)$ and
$\widetilde{\rho}_{\kappa}(n,p)$ be defined as per Eqs. (69) and (70), and
$\gamma_{\lambda}$ and $\gamma_{+}$ as per Eq. (74). For any $p\geq C_{*,D,K}$
and $\lambda>0$, if it holds that

$\gamma_{\lambda}\geq
p^{-K},\qquad\quad\widetilde{\rho}_{\lambda}(n,p)\cdot\rho_{\gamma_{\lambda}}(p)^{5/2}\log^{4}(p)\leq
K\sqrt{p},$ (78)

then with probability at least $1-p^{-D}$, we have

$\max\left\\{\frac{|\tilde{\nu}_{2}-\nu_{2}|}{\nu_{2}},\frac{|\tilde{\nu}_{1}-\nu_{1}|}{\nu_{1}}\right\\}\leq
C_{*,D,K}\cdot{\mathcal{E}}_{\nu}(p),$

where we defined

${\mathcal{E}}_{\nu}(p):=\frac{\widetilde{\rho}_{\lambda}(n,p)\cdot\rho_{\gamma_{+}}(p)^{5/2}\log^{3}(p)}{\sqrt{p}}.$

The proof of this proposition can be found in Section B.7.2.

To study functionals of ${\boldsymbol{Z}}$ conditional on ${\boldsymbol{F}}$,
we will assume that ${\boldsymbol{F}}$ belonds to the good event

${\mathcal{A}}_{\mathcal{F}}:=\widetilde{{\mathcal{A}}}_{\mathcal{F}}\cap\left\\{{\boldsymbol{F}}\in\mathbb{R}^{p\times\infty}\;\;:\;\;|\tilde{\nu}_{1}-\nu_{1}|\leq
C_{*,D,K}\cdot{\mathcal{E}}_{\nu}(p)\cdot\nu_{1}\right\\},$ (79)

where $\widetilde{{\mathcal{A}}}_{\mathcal{F}}$ is defined in Lemma B.2. In
particular, as long as $p\geq C_{*,D,K}$ and condition (78) hold, then
$\mathbb{P}({\mathcal{A}}_{\mathcal{F}})\geq 1-2p^{-D}$ by Lemma B.2 and
Proposition B.4.

##### Truncated fixed point.

As mentioned above, we will separate the analysis of the low-degree part of
the feature matrix ${\boldsymbol{F}}_{0}$ and the high-degree part
${\boldsymbol{F}}_{+}$. For the high-degree part, we will simply use the
concentration stated in Lemma B.3. For the low degree part, we will study
functional of ${\boldsymbol{F}}_{0}$ with regularization
$\gamma_{+}=p\nu_{1}+{\rm Tr}({\boldsymbol{\Sigma}}_{+})$. We therefore
introduce an effective regularization $\nu_{2,0}$ associated to the model
$(p,{\boldsymbol{\Sigma}}_{0},\gamma_{+})$, i.e., the unique positive solution
to the equation

$p-\frac{\gamma_{+}}{\nu_{2,0}}={\rm
Tr}\big{(}{\boldsymbol{\Sigma}}_{0}({\boldsymbol{\Sigma}}_{0}+\nu_{2,0})^{-1}\big{)}.$
(80)

Intuitively, $\nu_{2,0}$ will be closed to $\nu_{2}$ as soon as
$\lambda_{\max}({\boldsymbol{\Sigma}}_{+})\ll\nu_{2}$ as

$n-\frac{p\nu_{1}}{\nu_{2}}\approx{\rm
Tr}\left({\boldsymbol{\Sigma}}_{0}({\boldsymbol{\Sigma}}_{0}+\nu_{2})^{-1}\right)+\frac{{\rm
Tr}({\boldsymbol{\Sigma}}_{+})}{\nu_{2}},$

and uniqueness of the positive solution $\nu_{2,0}$. This is formalized in the
following lemma.

######  Lemma B.5 (Truncated fixed point).

Let ${\mathsf{m}}$ be chosen such that
$p^{2}\xi_{{\mathsf{m}}+1}^{2}\leq\gamma_{\lambda}$, then

$\frac{|\nu_{2,0}-\nu_{2}|}{\nu_{2}}\leq\frac{1}{p}.$ (81)

Furthermore, there exists an absolute constant $C>0$ such that

$\left|{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}_{0}({\boldsymbol{\Sigma}}_{0}+\nu_{2,0})^{-1}\big{)}+\frac{{\rm
Tr}({\boldsymbol{\Sigma}}_{+})}{\nu_{2,0}}-{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\big{)}\right|\leq\frac{C}{p}{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\big{)}.$
(82)

###### Proof of Lemma B.5.

The first bound (81) follows directly from [Misiakiewicz and Saeed, 2024,
Lemma 6]. For the second inequality, we decompose this difference into

$\displaystyle~{}\left|{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}_{0}({\boldsymbol{\Sigma}}_{0}+\nu_{2,0})^{-1}\big{)}+\frac{{\rm
Tr}({\boldsymbol{\Sigma}}_{+})}{\nu_{2,0}}-{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\big{)}\right|$
$\displaystyle\leq$ $\displaystyle~{}\left|\nu_{2,0}-\nu_{2}\right|{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}_{0}({\boldsymbol{\Sigma}}_{0}+\nu_{2,0})^{-1}({\boldsymbol{\Sigma}}_{0}+\nu_{2})^{-1}\big{)}+\frac{\xi_{{\mathsf{m}}+1}^{2}+|\nu_{2,0}-\nu_{2}|}{\nu_{2,0}}{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}_{+}({\boldsymbol{\Sigma}}_{+}+\nu_{2})^{-1}\big{)}$
$\displaystyle\leq$
$\displaystyle~{}\left\\{\frac{\xi_{{\mathsf{m}}+1}^{2}}{\nu_{2,0}}+\frac{|\nu_{2,0}-\nu_{2}|}{\nu_{2,0}}\right\\}{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\big{)}$
$\displaystyle\leq$ $\displaystyle~{}\frac{3}{p}{\rm
Tr}\big{(}{\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1}\big{)},$

where we used that
$\xi_{{\mathsf{m}}+1}^{2}/\nu_{2,0}\leq\gamma_{+}/(p^{2}\nu_{2,0})\leq 1/p$ by
the assumption on ${\mathsf{m}}$ and identity (80). ∎

###  B.3 Deterministic equivalents for functionals of $\mathbb{Z}$ conditional
on $\mathbb{F}$

As mentioned in Section B.1, we will first show that the test error
concentrates over ${\boldsymbol{Z}}$ conditional on ${\boldsymbol{F}}$ on some
quantity that only depends on
$\widehat{{\boldsymbol{\Sigma}}}_{{\boldsymbol{F}}}$. The bias and variance
terms can be written in terms of the following three functionals of the
feature matrix ${\boldsymbol{Z}}$: for a general p.s.d. matrix
${\boldsymbol{A}}\in\mathbb{R}^{p\times p}$ and positive scalar $\kappa>0$,
define

$\displaystyle\Phi_{2}({\boldsymbol{Z}};\kappa):=$ $\displaystyle~{}{\rm
Tr}\left(\frac{{\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}}{n}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\kappa)^{-1}\right),$
(83) $\displaystyle\Phi_{3}({\boldsymbol{Z}};{\boldsymbol{A}},\kappa):=$
$\displaystyle~{}{\rm
Tr}\left({\boldsymbol{A}}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}^{1/2}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\kappa)^{-1}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\kappa)^{-1}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}^{1/2}\right),$
$\displaystyle\Phi_{4}({\boldsymbol{Z}};{\boldsymbol{A}},\kappa):=$
$\displaystyle~{}\left({\boldsymbol{A}}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}^{1/2}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\kappa)^{-1}\frac{{\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}}{n}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\kappa)^{-1}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}^{1/2}\right),$

where we recall that ${\boldsymbol{Z}}$ has i.i.d. rows with covariance
$\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}={\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}/p$.
We show that these functional are well approximated by functionals of
${\boldsymbol{F}}$ that can be written in terms of the following functionals:

$\displaystyle\widetilde{\Phi}_{2}({\boldsymbol{F}};\kappa):=$
$\displaystyle~{}{\rm
Tr}\left(\frac{{\boldsymbol{F}}^{\mathsf{T}}{\boldsymbol{F}}}{p}({\boldsymbol{F}}^{\mathsf{T}}{\boldsymbol{F}}+\kappa)^{-1}\right),$
(84)
$\displaystyle\widetilde{\Phi}_{5}({\boldsymbol{F}};{\boldsymbol{A}},\kappa):=$
$\displaystyle~{}\frac{1}{n}\cdot\frac{\widetilde{\Phi}_{6}({\boldsymbol{F}};{\boldsymbol{A}},\kappa)}{n-\widetilde{\Phi}_{6}({\boldsymbol{F}};{\mathbf{I}},\kappa)},$
$\displaystyle\widetilde{\Phi}_{6}({\boldsymbol{F}};{\boldsymbol{A}},\kappa):=$
$\displaystyle~{}{\rm
Tr}\left({\boldsymbol{A}}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}})^{2}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}+\kappa)^{-2}\right).$

The following proposition gather the approximation guarantees for
$\Phi_{2},\Phi_{3},\Phi_{4}$ listed in Eq. (83).

######  Proposition B.6 (Deterministic equivalents for
$\Phi({\boldsymbol{Z}})$ conditional on ${\boldsymbol{F}}$).

Under Assumption B.1 and assuming that
${\boldsymbol{F}}\in{\mathcal{A}}_{\mathcal{F}}$ defined in Eq. (79), for any
$D,K>0$, there exist constants $\eta_{*}\in(0,1/4)$, $C_{D,K}>0$, and
$C_{*,D,K}>0$ such that the followings holds. Let $\rho_{\kappa}(p)$ and
$\widetilde{\rho}_{\kappa}(n,p)$ be defined as per Eqs. (69) and (70). For any
$n\geq C_{D,K}$ and regularization parameter $\lambda>0$, if it holds that

$\displaystyle\lambda\geq
n^{-K},\qquad\qquad\widetilde{\rho}_{\lambda}(n,p)^{5/2}\log^{3/2}(n)\leq
K\sqrt{n},$ (85)
$\displaystyle\widetilde{\rho}_{\lambda}(n,p)^{2}\cdot\rho_{\gamma_{+}}(p)^{5/2}\log^{3}(p)\leq
K\sqrt{p},$

then for any p.s.d. matrix ${\boldsymbol{A}}\in\mathbb{R}^{p\times p}$
(independent of ${\boldsymbol{Z}}|{\boldsymbol{F}}$), with probability at
least $1-n^{-D}$ on ${\boldsymbol{Z}}$ conditional on ${\boldsymbol{F}}$, we
have

$\displaystyle\left|\Phi_{2}({\boldsymbol{Z}};\lambda)-\frac{p}{n}\widetilde{\Phi}_{2}({\boldsymbol{F}};p\nu_{1})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot{\mathcal{E}}_{1}(n,p)\cdot\frac{p}{n}\widetilde{\Phi}_{2}({\boldsymbol{F}};p\nu_{1}),$
(86)
$\displaystyle\left|\Phi_{3}({\boldsymbol{Z}};{\boldsymbol{A}},\lambda)-\left(\frac{n\nu_{1}}{\lambda}\right)^{2}\widetilde{\Phi}_{5}({\boldsymbol{F}};{\boldsymbol{A}},p\nu_{1})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot{\mathcal{E}}_{1}(n,p)\cdot\left(\frac{n\nu_{1}}{\lambda}\right)^{2}\widetilde{\Phi}_{5}({\boldsymbol{F}};{\boldsymbol{A}},p\nu_{1}),$
(87)
$\displaystyle\left|\Phi_{4}({\boldsymbol{Z}};{\boldsymbol{A}},\lambda)-\widetilde{\Phi}_{5}({\boldsymbol{F}};{\boldsymbol{A}},p\nu_{1})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot{\mathcal{E}}_{1}(n,p)\cdot\widetilde{\Phi}_{5}({\boldsymbol{F}};{\boldsymbol{A}},p\nu_{1}),$
(88)

where the approximation rate is given by

${\mathcal{E}}_{1}(n,p):=\frac{\widetilde{\rho}_{\lambda}(n,p)^{6}\log^{5/2}(n)}{\sqrt{n}}+\frac{\widetilde{\rho}_{\lambda}(n,p)^{2}\cdot\rho_{\gamma_{+}}(p)^{5/2}\log^{3}(p)}{\sqrt{p}}.$
(89)

Proposition B.6 is a consequence of [Misiakiewicz and Saeed, 2024, Theorem 4]
(see Appendix A and Theorem A.2 for background) and Proposition B.4. We defer
its proof to Section B.7.3. Note that the term $\widetilde{O}(p^{-1/2})$ in
the approximation rate ${\mathcal{E}}_{1}(n,p)$ defined in Eq. (89) comes from
comparing $p\nu_{1}$ with $p\tilde{\nu}_{1}$ and is equal to
$\widetilde{\rho}_{\lambda}(n,p)\cdot{\mathcal{E}}_{\nu}(n,p)$ where
${\mathcal{E}}_{\nu}(n,p)$ is defined in Proposition B.4. If instead, we
compared to functionals with regularization $p\tilde{\nu}_{1}$, then the
approximation rate in Proposition B.6 would scale $\widetilde{O}(n^{-1/2})$ as
expected.

In the analysis of the bias term, we will further need to show deterministic
equivalents in the case where ${\boldsymbol{A}}$ is itself a random matrix
uncorrelated (but not independent) to ${\boldsymbol{Z}}|{\boldsymbol{F}}$. The
following proposition gather these approximation guarantees and is a
consequence of [Misiakiewicz and Saeed, 2024, Lemma 10] and Proposition B.4.

######  Proposition B.7 (Deterministic equivalents for
$\Phi({\boldsymbol{Z}})$, uncorrelated numerator).

Assume the same setting as Proposition B.6 and the same conditions (85).
Consider a deterministic vector ${\boldsymbol{v}}\in\mathbb{R}^{p}$ and a
random vector ${\boldsymbol{u}}=(u_{i})_{i\in[n]}$ with i.i.d. entries and
$\mathbb{E}[u_{i}]=0$, $\mathbb{E}[u_{i}^{2}]=1$, and
$\mathbb{E}[{\boldsymbol{z}}_{i}u_{i}|{\boldsymbol{F}}]={\boldsymbol{0}}$.
Then with probability at least $1-n^{-D}$ on ${\boldsymbol{Z}}$ conditional on
${\boldsymbol{F}}$, we have

$\displaystyle~{}\left|\langle{\boldsymbol{u}},{\boldsymbol{Z}}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\lambda)^{-1}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\lambda)^{-1}{\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{u}}\rangle-n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})\right|\leq
C_{*,D,K}\cdot{\mathcal{E}}_{2}(n,p),$ (90)
$\displaystyle~{}\left|\langle{\boldsymbol{u}},{\boldsymbol{Z}}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\lambda)^{-1}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\lambda)^{-1}{\boldsymbol{v}}\rangle\right|\leq
C_{*,D,K}\cdot{\mathcal{E}}_{2}(n,p)\cdot\frac{n\nu_{1}}{\lambda}\sqrt{\widetilde{\Phi}_{5}({\boldsymbol{F}};\overline{{\boldsymbol{v}}}\overline{{\boldsymbol{v}}}^{\mathsf{T}},p\nu_{1})},$
(91)

where we denoted
$\overline{{\boldsymbol{v}}}:=\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}^{-1/2}{\boldsymbol{v}}$
and the approximation rate is given by

${\mathcal{E}}_{2}(n,p):=\frac{\widetilde{\rho}_{\lambda}(n,p)^{6}\log^{7/2}(n)}{\sqrt{n}}+\frac{\widetilde{\rho}_{\lambda}(n,p)^{2}\cdot\rho_{\gamma_{+}}(p)^{5/2}\log^{3}(p)}{\sqrt{p}}.$
(92)

We defer the proof of Proposition B.7 to Section B.7.3.

###  B.4 Deterministic equivalents for functionals of $\mathbb{F}$

After replacing the bias and variance terms by their deterministic equivalents
over the randomness in ${\boldsymbol{Z}}|{\boldsymbol{F}}$, we obtain
functionals in terms of $\widetilde{\Phi}_{2}({\boldsymbol{F}};p\nu_{1})$ and
$\widetilde{\Phi}_{5}({\boldsymbol{F}};{\boldsymbol{A}},p\nu_{1})$ listed in
Eq. (84). As mentioned in Section B.2, we will analyze the low-degree and high
degree part of the feature matrix separately. Using Lemma B.3, we can replace
the high-degree part ${\boldsymbol{F}}_{+}{\boldsymbol{F}}_{+}^{\mathsf{T}}$
by a deterministic matrix, which results in a regularization parameter
$\gamma(p\nu_{1})=p\nu_{1}+{\rm Tr}({\boldsymbol{\Sigma}}_{+})$.

The functionals of ${\boldsymbol{F}}_{0}$ can be written in terms of the
following quantities: for any deterministic matrix
${\boldsymbol{B}}\in\mathbb{R}^{{\mathsf{m}}\times{\mathsf{m}}}$, define

$\displaystyle\widetilde{\Phi}_{1}({\boldsymbol{F}}_{0};{\boldsymbol{B}},\kappa)=$
$\displaystyle~{}{\rm
Tr}\left({\boldsymbol{B}}{\boldsymbol{\Sigma}}_{0}^{1/2}({\boldsymbol{F}}_{0}^{\mathsf{T}}{\boldsymbol{F}}_{0}+\gamma(\kappa))^{-1}{\boldsymbol{\Sigma}}_{0}^{1/2}\right),$
(93) $\displaystyle\widetilde{\Phi}_{2}({\boldsymbol{F}}_{0};\kappa)=$
$\displaystyle~{}{\rm
Tr}\left(\frac{{\boldsymbol{F}}_{0}^{\mathsf{T}}{\boldsymbol{F}}_{0}}{p}({\boldsymbol{F}}_{0}^{\mathsf{T}}{\boldsymbol{F}}_{0}+\gamma(\kappa))^{-1}\right),$
$\displaystyle\widetilde{\Phi}_{3}({\boldsymbol{F}}_{0};{\boldsymbol{B}},\kappa)=$
$\displaystyle~{}{\rm
Tr}\left({\boldsymbol{B}}_{0}{\boldsymbol{\Sigma}}^{1/2}_{0}({\boldsymbol{F}}_{0}^{\mathsf{T}}{\boldsymbol{F}}_{0}+\gamma(\kappa))^{-1}{\boldsymbol{\Sigma}}_{0}({\boldsymbol{F}}_{0}^{\mathsf{T}}{\boldsymbol{F}}_{0}+\gamma(\kappa))^{-1}{\boldsymbol{\Sigma}}_{0}^{1/2}\right),$
$\displaystyle\widetilde{\Phi}_{4}({\boldsymbol{F}}_{0};{\boldsymbol{B}},\kappa)=$
$\displaystyle~{}\left({\boldsymbol{B}}{\boldsymbol{\Sigma}}_{0}^{1/2}({\boldsymbol{F}}_{0}^{\mathsf{T}}{\boldsymbol{F}}_{0}+\gamma(\kappa))^{-1}\frac{{\boldsymbol{F}}_{0}^{\mathsf{T}}{\boldsymbol{F}}_{0}}{p}({\boldsymbol{F}}_{0}^{\mathsf{T}}{\boldsymbol{F}}_{0}+\gamma(\kappa))^{-1}{\boldsymbol{\Sigma}}^{1/2}\right).$

We show that these functionals can be well approximated by the deterministic
functions that can be written in terms of

$\displaystyle\Psi_{1}(\nu;{\boldsymbol{B}})=$ $\displaystyle~{}{\rm
Tr}\left({\boldsymbol{B}}{\boldsymbol{\Sigma}}_{0}({\boldsymbol{\Sigma}}_{0}+\nu)^{-1}\right),$
(94) $\displaystyle\Psi_{2}(\nu)=$ $\displaystyle~{}\frac{1}{p}{\rm
Tr}\left({\boldsymbol{\Sigma}}_{0}({\boldsymbol{\Sigma}}_{0}+\nu)^{-1}\right),$
$\displaystyle\Psi_{3}(\nu;{\boldsymbol{B}})=$
$\displaystyle~{}\frac{1}{p}\cdot\frac{{\rm
Tr}({\boldsymbol{B}}{\boldsymbol{\Sigma}}_{0}^{2}({\boldsymbol{\Sigma}}_{0}+\nu)^{-2})}{p-{\rm
Tr}({\boldsymbol{\Sigma}}_{0}^{2}({\boldsymbol{\Sigma}}_{0}+\nu)^{-2})}.$

Recall that for $\kappa=p\nu_{1}$, we denote $\gamma_{+}:=\gamma(p\nu_{1})$
and $\nu_{2,0}$ the effective regularization associated to model
$(p,{\boldsymbol{\Sigma}}_{0},\gamma_{+})$. The following proposition gather
the approximation guarantees for
$\widetilde{\Phi}_{1},\widetilde{\Phi}_{2},\widetilde{\Phi}_{3},\widetilde{\Phi}_{4}$
listed in Eq. (93).

######  Proposition B.8 (Deterministic equivalents for
${\boldsymbol{F}}_{0}$).

Under Assumption B.1, for any $D,K>0$, there exist constants
$\eta_{*}\in(0,1/4)$, $C_{D,K}>0$, and $C_{*,D,K}>0$ such that the followings
holds. Let $\rho_{\kappa}(p)$ be defined as per Eq. (69). For any $p\geq
C_{D,K}$ and $\lambda>0$, if it holds that

$\displaystyle\gamma_{+}\geq
p^{-K},\qquad\qquad\rho_{\gamma_{+}}(p)^{5/2}\log^{3/2}(p)\leq K\sqrt{p},$
(95)

then for any deterministic p.s.d. matrix
${\boldsymbol{B}}\in\mathbb{R}^{{\mathsf{m}}\times{\mathsf{m}}}$, with
probability at least $1-p^{-D}$, we have

$\displaystyle\left|\widetilde{\Phi}_{1}({\boldsymbol{F}}_{0};{\boldsymbol{B}},p\nu_{1})-\frac{\nu_{2,0}}{\gamma_{+}}\Psi_{1}(\nu_{2,0};{\boldsymbol{B}})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot{\mathcal{E}}_{3}(p)\cdot\frac{\nu_{2,0}}{\gamma_{+}}\Psi_{1}(\nu_{2,0};{\boldsymbol{B}}),$
(96)
$\displaystyle\left|\widetilde{\Phi}_{2}({\boldsymbol{F}}_{0};p\nu_{1})-\Psi_{2}(\nu_{2,0})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot{\mathcal{E}}_{3}(p)\cdot\Psi_{2}(\nu_{2,0}),$
(97)
$\displaystyle\left|\widetilde{\Phi}_{3}({\boldsymbol{F}}_{0};{\boldsymbol{B}},p\nu_{1})-\left(\frac{p\nu_{2,0}}{\gamma_{+}}\right)^{2}\Psi_{3}(\nu_{2,0};{\boldsymbol{B}})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot{\mathcal{E}}_{3}(p)\cdot\left(\frac{p\nu_{2,0}}{\gamma_{+}}\right)^{2}\Psi_{3}(\nu_{2,0};{\boldsymbol{B}}),$
(98)
$\displaystyle\left|\widetilde{\Phi}_{4}({\boldsymbol{F}}_{0};{\boldsymbol{B}},p\nu_{1})-\Psi_{3}(\nu_{2,0};{\boldsymbol{B}})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot{\mathcal{E}}_{3}(p)\cdot\Psi_{3}(\nu_{2,0};{\boldsymbol{B}}),$
(99)

where the approximation rate is given by

${\mathcal{E}}_{3}(p):=\frac{\rho_{\gamma_{+}}(p)^{6}\log^{3}(p)}{\sqrt{p}}.$
(100)

This proposition is obtained by directly applying Theorem A.2 with no
modifications.

Again, in the analysis of the bias term, because we separated the analysis of
the low-degree and high-degree parts ${\boldsymbol{F}}_{0}$ and
${\boldsymbol{F}}_{+}$, we will further need deterministic equivalents when
${\boldsymbol{B}}$ is itself a random matrix uncorrelated but not independent
to ${\boldsymbol{F}}$. We gather the associated deterministic equivalents in
the following proposition.

######  Proposition B.9 (Deterministic equivalents for ${\boldsymbol{F}}_{0}$,
uncorrelated numerator).

Assume the same setting as Proposition B.8 and the same conditions (95).
Consider a deterministic vector ${\boldsymbol{v}}\in\mathbb{R}^{\mathsf{m}}$
and a random vector ${\boldsymbol{u}}=(u_{j})_{j\in[p]}$ with i.i.d. entries
and $\mathbb{E}[u_{j}]=0$, $\mathbb{E}[u_{j}^{2}]=1$, and
$\mathbb{E}[\boldsymbol{f}_{0,j}u_{j}]={\boldsymbol{0}}$. Then with
probability at least $1-p^{-D}$, we have

$\displaystyle~{}\left|\frac{1}{p}\langle{\boldsymbol{u}},({\boldsymbol{F}}_{0}{\boldsymbol{F}}_{0}^{\mathsf{T}}+\gamma_{+})^{-2}{\boldsymbol{u}}\rangle-\frac{1}{(p\nu_{2,0})^{2}}\frac{1}{1-\frac{1}{p}{\rm
Tr}({\boldsymbol{\Sigma}}_{0}^{2}({\boldsymbol{\Sigma}}_{0}+\nu_{2,0})^{-2})}\right|\leq
C_{*,D,K}\cdot{\mathcal{E}}_{4}(p)\cdot\frac{1}{\gamma_{+}^{2}},$ (101)
$\displaystyle~{}\left|\frac{1}{p}\langle{\boldsymbol{u}},({\boldsymbol{F}}_{0}{\boldsymbol{F}}_{0}^{\mathsf{T}}+\gamma_{+})^{-2}{\boldsymbol{F}}_{0}{\boldsymbol{v}}\rangle\right|\leq
C_{*,D,K}\cdot{\mathcal{E}}_{4}(p)\frac{p\nu_{2,0}}{\gamma_{+}^{2}}\sqrt{\Psi_{3}(\nu_{2,0};\overline{{\boldsymbol{v}}}\overline{{\boldsymbol{v}}}^{\mathsf{T}})},$
(102)

where we denoted
$\overline{{\boldsymbol{v}}}:={\boldsymbol{\Sigma}}_{0}^{-1/2}{\boldsymbol{v}}$
and the approximation rate is given by

${\mathcal{E}}_{4}(p):=\frac{\rho_{\gamma_{+}}(p)^{6}\log^{7/2}(p)}{\sqrt{p}}.$
(103)

This proposition is a direct consequence of [Misiakiewicz and Saeed, 2024,
Lemma 10].

Throughout the proofs, with a slight abuse of notations, we will denote
functionals
$\widetilde{\Phi}_{i}({\boldsymbol{F}}_{0};{\boldsymbol{B}},\kappa)$,
$i\in[4]$, the functionals listed in Eq. (93) applied to the truncated feature
matrix ${\boldsymbol{F}}_{0}$, with covariance ${\boldsymbol{\Sigma}}_{0}$,
regularization $\gamma(\kappa)$, and deterministic matrix
${\boldsymbol{B}}\in\mathbb{R}^{{\mathsf{m}}\times{\mathsf{m}}}$, and
$\widetilde{\Phi}_{i}({\boldsymbol{F}};{\boldsymbol{B}},\kappa)$, $i\in[4]$,
the functionals applied to the full feature matrix
${\boldsymbol{F}}\in\mathbb{R}^{p\times\infty}$, where
${\boldsymbol{\Sigma}}_{0}$ is replaced by ${\boldsymbol{\Sigma}}$, the
regularization parameter is $\kappa$, and the deterministic matrix
${\boldsymbol{B}}\in\mathbb{R}^{\infty\times\infty}$. Similarly, we will us
the notation $\Psi_{i}(\nu_{2,0};{\boldsymbol{B}}),i\in[3]$ for the truncated
deterministic functionals (94), and the notation
$\Psi_{i}(\nu_{2};{\boldsymbol{B}}),i\in[3]$ to denote the full functionals
with ${\boldsymbol{\Sigma}}_{0}$ replaced by ${\boldsymbol{\Sigma}}$ and
${\boldsymbol{B}}\in\mathbb{R}^{\infty\times\infty}$.

###  B.5 Approximation guarantee for the variance term

Recall the expressions for the variance term

${\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)=\sigma_{\varepsilon}^{2}\cdot{\rm
Tr}\big{(}\widehat{{\boldsymbol{\Sigma}}}_{\boldsymbol{F}}{\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}({\boldsymbol{Z}}^{\mathsf{T}}{\boldsymbol{Z}}+\lambda)^{-2}\big{)},$

and its associated deterministic equivalent

$\displaystyle\mathsf{V}_{n,p}(\lambda)=$
$\displaystyle~{}\sigma_{\varepsilon}^{2}\frac{\Upsilon(\nu_{1},\nu_{2})}{1-\Upsilon(\nu_{1},\nu_{2})},$
(104) $\displaystyle\Upsilon(\nu_{1},\nu_{2})=$
$\displaystyle~{}\frac{p}{n}\left[\left(1-\frac{\nu_{1}}{\nu_{2}}\right)^{2}+\left(\frac{\nu_{1}}{\nu_{2}}\right)^{2}\frac{{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}{p-{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}\right].$
(105)

We prove in this section an approximation guarantee between
${\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)$ and
$\mathsf{V}_{n,p}(\lambda)$. For convenience, we state a separate theorem for
this term.

######  Theorem B.10 (Deterministic equivalent for the variance term).

Assume the features $({\boldsymbol{z}}_{i})_{i\in[n]}$ and
$(\boldsymbol{f}_{j})_{j\in[p]}$ satisfy Assumption B.1, and the covariance
${\boldsymbol{\Sigma}}$ and target coefficients ${\boldsymbol{\beta}}_{*}$
satisfy Assumption 3.2. Then, for any $D,K>0$, there exist constants
$\eta_{*}\in(0,1/2)$ and $C_{*,D,K}>0$ such that the following holds. Let
$\rho_{\kappa}$ and $\widetilde{\rho}_{\kappa}$ be defined as per Eqs. (69)
and (70). For any $n,p\geq C_{*,D,K}$ and $\lambda>0$, if it holds that

$\displaystyle\lambda\geq n^{-K},\qquad\gamma_{\lambda}\geq
p^{-K},\qquad\qquad\quad\widetilde{\rho}_{\lambda}(n,p)^{5/2}\cdot\log^{3/2}(n)\leq$
$\displaystyle~{}K\sqrt{n},$ (106)
$\displaystyle\widetilde{\rho}_{\lambda}(n,p)^{2}\cdot\rho_{\gamma_{+}}(p)^{7}\cdot\log^{4}(p)\leq$
$\displaystyle~{}K\sqrt{p},$

then with probability at least $1-n^{-D}-p^{-D}$, we have

$\left|{\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)-\mathsf{V}_{n,p}(\lambda)\right|\leq
C_{*,D,K}\cdot{\mathcal{E}}_{V}(n,p)\cdot\mathsf{V}_{n,p}(\lambda),$

where the approximation rate is given by

${\mathcal{E}}_{V}(n,p):=\frac{\widetilde{\rho}_{\lambda}(n,p)^{6}\log^{5/2}(n)}{\sqrt{n}}+\frac{\widetilde{\rho}_{\lambda}(n,p)^{2}\cdot\rho_{\gamma_{+}}(p)^{7}\log^{3}(p)}{\sqrt{p}}.$
(107)

###### Proof of Theorem B.10.

First, note that ${\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)$
can be written in terms of the functional $\Phi_{4}$ defined in Eq. (83):

${\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)=\sigma_{\varepsilon}^{2}\cdot
n\Phi_{4}({\boldsymbol{Z}};{\mathbf{I}},\lambda).$

Recall that ${\mathcal{A}}_{\mathcal{F}}$ is the event defined in Eq. (79).
Under the assumptions of Theorem B.10, we can apply Lemma B.2 and Proposition
B.4 to obtain

$\mathbb{P}({\mathcal{A}}_{\mathcal{F}})\geq 1-p^{-D}.$

Hence, applying Proposition B.6 for
${\boldsymbol{F}}\in{\mathcal{A}}_{\mathcal{F}}$ and via union bound, we
obtain that with probability at least $1-p^{-D}-n^{-D}$,

$\left|n\Phi_{4}({\boldsymbol{Z}};{\mathbf{I}},\lambda)-n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})\right|\leq
C_{*,D,K}\cdot{\mathcal{E}}_{1}(p,n)\cdot
n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1}),$ (108)

where ${\mathcal{E}}_{1}(n,p)$ is defined in Eq. (89) and we recall the
expressions

$n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})=\frac{\widetilde{\Phi}_{6}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})}{n-\widetilde{\Phi}_{6}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})},\qquad\quad\widetilde{\Phi}_{6}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})={\rm
Tr}\big{(}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}})^{2}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}+p\nu_{1})^{-2}\big{)}.$

Let us decompose
$\widetilde{\Phi}_{6}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})$ into

$\widetilde{\Phi}_{6}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})={\rm
Tr}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}{\boldsymbol{G}})-p\nu_{1}{\rm
Tr}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}{\boldsymbol{G}}^{2}).$

From Lemma B.11 stated below, we have with probability at least $1-p^{-D}$

$\displaystyle\left|\frac{1}{p}{\rm
Tr}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}+p\nu_{1})^{-1})-\Psi_{2}(\nu_{2})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot{\mathcal{E}}_{3}(p)\cdot\Psi_{2}(\nu_{2}),$
$\displaystyle\left|\frac{1}{p}{\rm
Tr}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}({\boldsymbol{F}}{\boldsymbol{F}}^{\mathsf{T}}+p\nu_{1})^{-2})-\Psi_{3}(\nu_{2};{\boldsymbol{\Sigma}}^{-1})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot\rho_{\gamma_{+}}(p){\mathcal{E}}_{3}(p)\cdot\Psi_{3}(\nu_{2};{\boldsymbol{\Sigma}}^{-1}),$

where ${\mathcal{E}}_{3}(p)$ is the approximation rate defined in Eq. (100).
Note that

$\displaystyle
p\Psi_{2}(\nu_{2})-p^{2}\nu_{1}\Psi_{3}(\nu_{2};{\boldsymbol{\Sigma}}^{-1})=$
$\displaystyle~{}{\rm
Tr}({\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-1})-\frac{\nu_{1}{\rm
Tr}({\boldsymbol{\Sigma}}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}{1-\frac{1}{p}{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}$
$\displaystyle=$
$\displaystyle~{}p\left\\{1-\frac{\nu_{1}}{\nu_{2}}-\frac{\nu_{1}}{\nu_{2}}\frac{1-\frac{\nu_{1}}{\nu_{2}}-\frac{1}{p}{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}{1-\frac{1}{p}{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}\right\\}$
$\displaystyle=$
$\displaystyle~{}p\left\\{\left(1-\frac{\nu_{1}}{\nu_{2}}\right)^{2}+\left(\frac{\nu_{1}}{\nu_{2}}\right)^{2}\frac{{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}{p-{\rm
Tr}({\boldsymbol{\Sigma}}^{2}({\boldsymbol{\Sigma}}+\nu_{2})^{-2})}\right\\}$
$\displaystyle=$ $\displaystyle~{}n\Upsilon(\nu_{1},\nu_{2}).$

Combining the above displays, we deduce that

$\displaystyle\left|\widetilde{\Phi}_{6}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})-n\Upsilon(\nu_{1},\nu_{2})\right|\leq$
$\displaystyle~{}C_{*,D,K}\cdot\rho_{\gamma_{+}}(p){\mathcal{E}}_{3}(p)\cdot\left[p\Psi_{2}(\nu_{2})+p^{2}\nu_{1}\Psi_{3}(\nu_{2};{\boldsymbol{\Sigma}}^{-1})\right]$
$\displaystyle\leq$
$\displaystyle~{}C_{*,D,K}\cdot\rho_{\gamma_{+}}(p){\mathcal{E}}_{3}(p)\cdot\left[n\Upsilon(\nu_{1},\nu_{2})+2p^{2}\nu_{1}\Psi_{3}(\nu_{2};{\boldsymbol{\Sigma}}^{-1})\right]$

Using Eq. (120) in Lemma B.14 stated in Section B.7, we conclude that with
probability at least $1-p^{-D}$,

$\left|\widetilde{\Phi}_{6}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})-n\Upsilon(\nu_{1},\nu_{2})\right|\leq
C_{*,D,K}\cdot\rho_{\gamma_{+}}(p){\mathcal{E}}_{3}(p)\cdot
n\Upsilon(\nu_{1},\nu_{2}).$ (109)

Finally, by simple algebra, we have

$\displaystyle~{}\left|n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})-\frac{\Upsilon(\nu_{1},\nu_{2})}{1-\Upsilon(\nu_{1},\nu_{2})}\right|$
(110) $\displaystyle\leq$
$\displaystyle~{}\left\\{n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})+1\right\\}\frac{|\widetilde{\Phi}_{6}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})-n\Upsilon(\nu_{1},\nu_{2})|}{n-\Upsilon(\nu_{1},\nu_{2})}$
$\displaystyle\leq$
$\displaystyle~{}\left\\{\left|n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})-\frac{\Upsilon(\nu_{1},\nu_{2})}{1-\Upsilon(\nu_{1},\nu_{2})}\right|+\frac{1}{1-\Upsilon(\nu_{1},\nu_{2})}\right\\}\cdot
C_{*,D,K}\cdot\rho_{\gamma_{+}}(p){\mathcal{E}}_{3}(p)\frac{\Upsilon(\nu_{1},\nu_{2})}{1-\Upsilon(\nu_{1},\nu_{2})}.$

Note that by Eq. (119) in Lemma B.14, we have

$\frac{\Upsilon(\nu_{1},\nu_{2})}{1-\Upsilon(\nu_{1},\nu_{2})}\leq(1-\Upsilon(\nu_{1},\nu_{2}))^{-1}\leq
C_{*}\cdot\widetilde{\rho}_{\lambda}(n,p).$

Hence rearranging the terms in Eq. (110) and using from conditions (106) and
that $p\geq C_{*,D,K}$, we obtain with probability at least $1-p^{-D}$ that

$\left|n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})-\frac{\Upsilon(\nu_{1},\nu_{2})}{1-\Upsilon(\nu_{1},\nu_{2})}\right|\leq
C_{*,D,K}\cdot\widetilde{\rho}_{\lambda}(n,p)\rho_{\gamma_{+}}(p){\mathcal{E}}_{3}(p)\frac{\Upsilon(\nu_{1},\nu_{2})}{1-\Upsilon(\nu_{1},\nu_{2})}.$
(111)

Using an union bound and combining bounds Eqs. (108) and (111), we obtain with
probability at least $1-n^{-D}-p^{-D}$, that

$\displaystyle~{}\left|{\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)-\mathsf{V}_{n,p}(\lambda)\right|$
$\displaystyle\leq$
$\displaystyle~{}\left|{\mathcal{V}}({\boldsymbol{G}},{\boldsymbol{F}},\lambda)-\sigma_{\varepsilon}^{2}\cdot
n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})\right|+\sigma_{\varepsilon}^{2}\left|n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})-\frac{\Upsilon(\nu_{1},\nu_{2})}{1-\Upsilon(\nu_{1},\nu_{2})}\right|$
$\displaystyle\leq$
$\displaystyle~{}C_{*,D,K}\cdot\left\\{{\mathcal{E}}_{1}(p,n)+\widetilde{\rho}_{\lambda}(n,p)\rho_{\gamma_{+}}(p){\mathcal{E}}_{3}(p)\right\\}\cdot\left[\sigma_{\varepsilon}^{2}\cdot
n\widetilde{\Phi}_{5}({\boldsymbol{F}};{\mathbf{I}},p\nu_{1})+\mathsf{V}_{n,p}(\lambda)\right]$
$\displaystyle\leq$
$\displaystyle~{}C_{*,D,K}\cdot\left\\{{\mathcal{E}}_{1}(p,n)+\widetilde{\rho}_{\lambda}(n,p)\rho_{\gamma_{+}}(p){\mathcal{E}}_{3}(p)\right\\}\cdot\mathsf{V}_{n,p}(\lambda),$

where we used Eq. (111) and conditions (106) in the last line. Replacing the
rates ${\mathcal{E}}_{j}$ by their expressions conclude the proof of this
theorem. ∎

######  Lemma B.11.