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

Authors: leonardo  defilippis
bruno  loureiro
theodor  misiakiewicz
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 18:29:34

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.

Main paper: 
 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:F RF = f (x; a) = 1 √ p j∈[p]a j φ(x, w j ) : a = (a j ) j∈[p] ∈ R p .(1)Here x ∈ X denotes the inputs and W = (w j ) j∈[p] a set of weight vectors which are taken to be random w j ∈ W ⊆ R d ∼ iid µ w . Hence, as the name suggests the feature map φ : X × W → R defines a random function. A few examples of random feature maps include the fully connected neural network features φ(x, w) = σ(⟨w, x⟩), σ : R → R, and the convolutional features with global average pooling φ(x, w) = 1 /d d ℓ=1 σ(⟨w, g ℓ • x⟩) where σ : R → R and g ℓ • x = (x ℓ+1 , . . . , x d , x 1 , . . . , x ℓ ) is the ℓ-shift operator with cyclic boundary conditions (both with X = R d ).Random features [Balcan et al., 2006, Rahimi and Recht, 2007] were originally introduced as a computationally efficient approximation for the limiting kernel:EQUATIONAlthough 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 -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 φ(x, w) = σ(⟨w, x⟩), 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 = Θ(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 = Θ(d κ ) 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 Belkin et al. [2019] and benign overfitting Bartlett et al. [2020] . 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 R test ≈ R n,p which is independent of the feature map dimension. More precisely, with high-probability over the input data and random weights:EQUATIONwhere the deterministic equivalent R n,p can be computed by solving a set of self-consistent equations of the type x = f (x), with f a contractive map. 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] , and provides the first rigorous, non-linear extension of [Bahri et al., 2024 , 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 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] . 
setting: 
 In this work, we focus on the generalization properties of the random feature class F RF defined in eq. ( 1) in a supervised regression setting. More precisely, consider a data set D = {(x i , y i ) i∈[n] } composed of n independent and identically distributed samples from a joint distribution µ x,y on X × R. Let f ⋆ (x) = E[y|x] denote the target function. We assume f ⋆ ∈ L 2 (µ x ), where µ x is the marginal distribution over X . Moreover, we assume the noise ε := y -f ⋆ (x) has zero mean and finite variance E[ε 2 ] = σ 2 ε < ∞. Note this is equivalent to:EQUATIONGiven the training data, we are interested in the properties of the minimiser:âλ (Z, y) := arg minEQUATIONwhere we have defined the feature matrix Z ij = p -1 /2 φ(x i ; w j ) and the label vectors y = (y i ) i∈ [n] .In particular, we are interested in its capacity of generalising to unseen data, as quantified by the excess population risk:EQUATIONIt will be convenient to decompose the excess risk above in terms of the standard bias and variance: R(f ⋆ ; X, W , λ) := E ε [R(f ⋆ ; X, W , ε, λ)] = B(f ⋆ ; X, W , λ) + V(X, W , λ),where:EQUATIONV(X, W , λ) := E x∼µx Var ε ( f (x; âλ )) .Note that to simplify the exposition, we have explicitly taken an expectation over the training data noise ε = (ε i ) i∈ [n] . Indeed, it can be shown that the excess risk eq. ( 6) concentrates on its expectation over ε under mild assumptions (see for example Misiakiewicz and Saeed [2024] ). 
deterministic equivalents: 
 The excess risk eq. ( 6) is a function of the covariates X and the weights 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 φ ∈ L 2 (X × W), and define the Fredholm integral operator T : L 2 (X ) → V ⊆ L 2 (W):EQUATIONwhere we define V = Im(T). This is a compact operator, and therefore can be diagonalized:EQUATIONwhere (ξ k ) k≥1 ⊆ R are the eigenvalues and (ψ k ) k≥1 and (ϕ k ) k≥1 are orthonormal bases of L 2 (X ) and V respectively:EQUATION)Without loss of generality, we assume the eigenvalues are ordered in non-increasing absolute values |ξ 1 | ≥ |ξ 2 | ≥ . . . , and for simplicity of presentation we assume that all eigenvalues are non-zero, i.e., ker(T) = {0}. Denote Σ = diag(ξ 2 1 , ξ 2 2 , . . .) ∈ R ∞×∞ the diagonal matrix of the squared eigenvalues. Similarly, since f ⋆ ∈ L 2 (µ x ), it admits the following decomposition in (ψ) k≥1 :f ⋆ = k≥1 β ⋆,k ψ k (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 vectors1 ψ := (ξ k ψ k (x)) k≥1 and ϕ := (ξ k ϕ k (w)) k≥1 . There exists a constant C x > 0 such that for any deterministic p.s.d. matrix A ∈ R ∞×∞ , i.e. a linear operator acting on an infinite-dimensional Hilbert space, with Tr(ΣA) < ∞, we haveEQUATIONEQUATION)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 m ∈ N such thatEQUATION)Furthermore, we will assume that for some C * > 0 that we haveEQUATIONAssumption 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 ξ 2 k ∝ k -α if we take m = O(p 2 ). Condition (17) was also considered in Cheng and Montanari [2022] , and is satisfied in many settings of interest, for example under source and capacity conditions β k ≍ k -β and ξ 2 k ≍ k -α 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 Σ and regularization parameter λ ≥ 0. Consider the parameter ν 2 ∈ R >0 defined as the unique solution of the selfconsistent equation:EQUATIONand ν 1 ∈ R >0 is given by:EQUATION)We introduce the short-hand:EQUATIONχ(ν 2 ) := Tr(Σ(Σ + ν 2 ) -2 ) p -Tr(Σ 2 (Σ + ν 2 ) -2 ) . (21)Then, the deterministic equivalents for the bias, variance and test error are defined as:EQUATIONV n,p (λEQUATIONEQUATION)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 Σ, and regularization λ > 0. More precisely, the approximation rates will depend on them through the following quantities:EQUATIONEQUATIONEQUATIONBelow we denote C a1,...,a k constants that only depend on the values of {a i } i∈ [k] . We use a i = ' * ' to denote the dependency on the constants in Assumptions 3.1 and 3.2. Theorem 3.3 (Test error of RFRR). Under Assumptions 3.1, 3.2 and for any D, K > 0, there exist constants η * ∈ (0, 1/2) and C * ,D,K > 0 such that the following holds. For any n, p ≥ C * ,D,K , regularization λ > 0, and target functionEQUATIONEQUATIONthen with probability at least 1 -n -D -p -D , we haveEQUATIONwhere R n,p (β * , λ) has been defined in eq. ( 24) and:EQUATION)and the approximation rate is given byEQUATION)For typical settings, with regularly varying spectrum, ρ κ (p) ≲ log(p) C /κ and ρ κ (n, p) ≲ log(n ∧ p) C /κ. In this case, the approximation rate scales as E(n, p) = Õ(n -1/2 + p -1/2 ), which matches the optimal rates expected from local law fluctuations. A few remarks on this theorem are in order:(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 β ⋆ , as for instance in [Dobriban and Wager, 2018 , Richards et al., 2021 , Wu and Xu, 2020] . y i = erf(⟨β, x i ⟩)+ ε i , σ 2 ε = 0.1, x i ∼ i.i.d. N (0, I d ), with a spiked random feature map φ(x, w) = tanh(⟨w + uv, x⟩) where v ∈ R d has a fixed overlap γ = ⟨v, β⟩ with the teacher vector, w ∼ N (0,d -1 I d ), u ∼ N (0, 1). (Right) Training data (x i , y i ) i∈[n], n = 300, sub-sampled from the FashionMNIST data set [Xiao et al., 2017] , with feature map given by φ(x; w) = erf(⟨w, x⟩) and µ w = N (0, d -1 I d ).(b) They are not explicitly dependent on the feature map dimension.(c) They are multiplicative, and therefore relative to the scale of the risk. In particular, they hold even if R ≍ n -γ , which will be crucial to the discussion in section 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 → ∞ discussion below) to the case of feature maps φ : X × W → 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 = Θ(d) [Mei and Montanari, 2022 , Loureiro et al., 2022 , Schröder et al., 2023] and polynomial n, p = Θ(d κ ) [Xiao et al., 2022 , Hu et al., 2024 , Aguirre-López et al., 2024] scaling.(e) The bounds depend on λ -1 and λ -1 >m . 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 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. ( 24). First, note that at the interpolation threshold n = p, we have 1 -Υ(ν 1 , ν 2 ) ∼ √ λ. Therefore, the risk R n,p ∼ λ -1/2 diverges as λ → 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 → ∞ where, in the generic case, the features span an infinite-dimensional RKHS. Typically, the resulting kernel will be universal, implying it can approximate any function in L 2 (µ x ). In this limit, the risk bottleneck is given by the finite amount of data n.Corollary 3.4 (Kernel limit). In the p → ∞ limit both ν 1 and ν 2 converge to a single ν K which is the unique positive solution to the following self-consistent equationn - λ ν K = Tr Σ(Σ + ν K ) -1 . (33)Moreover, the bias eq. ( 22) and variance eq. ( 23) terms simplify to:EQUATION)We denote the corresponding test errorR K,n (β * , λ) = B K,n (β * , λ) + V K,n (λ).Note that eq. ( 23) 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 → ∞ 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 F RF eq. ( 1) to approximate the target f ⋆ . Corollary 3.5 (Approximation limit). In the n → ∞ limit, we have ν 1 → 0 and ν 2 → ν A satisfying the following simplified self-consistent equation:p = Tr Σ(Σ + ν A ) -1 .(35) Moreover, the bias eq. ( 22) and variance eq. ( 23) terms simplify to:EQUATION)We denote the risk in this case R A,p (β * ) = B A,p (β * ), which as expected does not depend on λ. 
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 ⋆ ?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:TrΣ 1 /α < ∞, ||Σ -r β ⋆ || 2 < ∞.(37) where α ∈ (1, ∞) and r ∈ (0, ∞), with the case r = 1 /2 corresponding to f ⋆ belonging to the RKHS of the asymptotic random feature kernel eq. ( 2). The optimal minmax rate O n -2αr 2αr+1 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 n α-1+2r 1+2αr features. However, this is only an upper bound, and understanding how tight it is, as well as the full picture in the hard regime r ∈ (0, 1 /2), remains an open question. In this section, we leverage our tight characterization of the excess risk in 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 Σ = diag(ξ 2 k ) k≥1 , and we consider the case where the exponents exactly saturate the source and capacity conditions eq. ( 37):ξ 2 k = k -α , β * ,k = k -1+2αr 2 .(38) Further, we assume a relative scaling of the number of features p and the regularization λ with the number of samples n: p = n q , λ = n -(ℓ-1) .(39) with q ≥ 0 and ℓ ≥ 0.ℓ q 0 1 -ℓ α 2ℓ(r ∧ 1) α-1 α ℓ + q 1 -q αq α ℓ * 1 q * q ℓ q 0 1 -q 1 -ℓ α 2αqr 2ℓr α ℓ * 1 q * Figure 2: Excess error rate γ in the regime n ≫ σ -1 /(γ B (ℓ,q)-γ V (ℓ,q)) εas a function of (ℓ, q), defined in eq. ( 40) and eq. ( 39) for r ≥ 1 /2 (Left) and r ∈ [0, 1 /2) (Right). The explicit crossover points ℓ ⋆ , q ⋆ , q are defined in eq. ( 43) as a function of the source r and capacity α exponents.Theorem 4.1 (Excess risk rates). Under source and capacity conditions eq. ( 38) and scaling assumptions eq. (39), the deterministic equivalent eq. ( 24) rate is given by:EQUATIONwhere γ(ℓ, q) := γ B (ℓ, q)∧γ V (ℓ, q) for non-zero noise variance σ 2 ε ̸ = 0, otherwise γ(ℓ, q) = γ B (ℓ, q). The exponents γ B and γ V are respectively the decay rates of the bias and variance terms eqs. ( 22) and (23), and are explicitly given byEQUATIONEQUATION)Remark 4.1. Under the scaling in eqs. (38) and (39), one can check that the approximation rates E(n, p) in Theorem 3.3 are vanishing for ℓ ≤ α + 1 /12 if q ≥ 1, and for ℓ ≤ q((α + 1 /16) ∨ 1 /16(α -1)) if q < 1, which includes the optimal vertical line ℓ = ℓ * . Hence, for these regions of scaling, Theorem 3.3 readily implies that the excess risk eq. (6) indeed has the decay rates described in Theorem 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 γ(ℓ, q) as a function of the parameters ℓ and q, in the case where σ 2 ε ̸ = 0 for r ≥ 1 /2 (left) and r < 1 /2 (right). Note that the key difference between the diagrams is the presence of an additional region for r ≥ 1 /2. 2 Defining the following shorthand:ℓ ⋆ := α 2α(r ∧ 1) + 1 , q ⋆ := 1 -ℓ ⋆ (2r ∧ 1), q := 1 α(2r ∧ 1) + 1 = q ⋆ ∨ 1 α + 1 (43)we can identify two main regions in the (ℓ, q) plane, corresponding to a trade-off between the bias γ B and variance γ V terms:(a) Variance dominated region (γ V < γ B ): if ℓ > ℓ ⋆ , q > q and p > λ, the excess risk is dominated by the variance term, provided the number of samples is large enough n ≫ σ-1 /(γ B (ℓ,q)-γ V (ℓ,q)) ε.3 Inside this region it is possible to further distinguish between two regimes: 2 Recall that these two cases correspond to the target function f⋆ belonging (r ≥ 1 /2) or not (r < 1 /2) to the RKHS spanned by the asymptotic kernel 3 The noise dominated regime where n < σ -1/(γ B (ℓ,q)-γ V (ℓ,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.• slow decay regime (orange and brown): for ℓ < α and q < 1 (p ≪ n), γ V = 1 -( ℓ /α ∧ q), hence the decay depends on the interplay between regularization strength and number of random features and it is slower as ( ℓ /α ∧ q) increases; • plateau regime (red): for ℓ ≥ α and q ≥ 1 (p ≥ n) the excess risk converges to a constant value and does not decay as n increases. (b) Bias dominated region (γ V > γ B ): if ℓ < ℓ ⋆ , q < q and p < λ, the excess risk is dominated by the bias term, whose decay is faster as ( ℓ /α ∧ q) increases (cyan, emerald and teal).Note that in the limit of large number of random features p → ∞, 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 decays the fastest with the number of samples n, and what is the minimum number of random features p ⋆ 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):EQUATION)and it is attained for:EQUATIONλ = λ ⋆ p ≥ p ⋆ = λ -1 ⋆ n 1 /α or λ ≤ λ ⋆ p = p ⋆ = λ -1 ⋆ n 1 /α for r < 1 /2 (46)corresponding to the bold red line (-) in Fig. 2 . In particular, the minimal number of random features p ⋆ = n q⋆ required to achieve the optimal rate γ ⋆ is given by:q ⋆ = 1 - α(2r ∧ 1) 2α(r ∧ 1) + 1 (47)and corresponds to the bold red dot (•) 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 ⋆ = n q⋆ in eq. ( 47) achieving the optimal rate eq. ( 44) in the r ≥ 1 /2 regime is strictly smaller than the lower bound p > p 0 of Rudi and Rosasco [2017] . More precisely, letting p 0 = n q0 , for r ∈ [ 1 /2, 1):EQUATION)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 has sparked a renewed wave of interest in the theoretical investigation of power laws [Kaplan et al., 2020] . 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., 2024 , Maloney et al., 2022] .The model studied in these works is given by ridge regression on datay i = ⟨β ⋆ , x i ⟩ with x ∼ N (0, diag(( d /k) α )) and β ⋆ ∼ N (0, 1 /dI d ) with a linear projection model f (x, a) = ⟨a, W x⟩,where W is an i.i.d. Gaussian matrix. Note this model is a particular case of the one studied here, corresponding to a linear feature map and random target function. Moreover, since the variance of the target is constant, the source is entirely determined by the capacity α of the asymptotic kernel, here controlled by the decay of the covariance of the input data.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., 2024] . They correspond precisely to the bottlenecks in the excess risk arising from the limited approximation Excess Risk = 1.2, r = 0.9, = * = 0.38 q = * = 0.38 q = 0.45 q = 0.53 q = 0. q* = 0.62 q = 0.7 q = 0.8 n 2 * r n q * + * / 10 2 10 3 10 4 n = 3.5, r = 1.5, q = 1.25= 0.1 = 0.3 = * = 0.44 = 1 = 2.5 = = 3.5 = 4 n 2 r n 2 * r n 1 + (1 / )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 λ = n -(ℓ-1) , p = n q , with noise variance σ 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 Theorem 4.1, stated in the legend. The colour scheme corresponds to the regions of Fig. 2 . capacity of the random feature model or the limited availability of training data. As this model is a particular case of ours, the rates in the variance limited regime can also be obtained from Theorem 4.1, and correspond to particular cases in Fig. 2 , see Appendix E for a detailed discussion. Contemporary to our work, Atanasov et al. [2024] has extended the analysis in this linear model to the case where β ⋆ also has a power-law decay, and provided a comprehensive discussion of the different scaling regimes for this model. Their rates can be put in a one-to-one correspondence with the rates derived in section 4. We refer the interested reader to Section VI.6 of Atanasov et al. [2024] for a detailed discussion of this relationship. We stress, however, that beside being rigorous, our results hold for features in infinite-dimensional Hilbert spaces and are not restricted to a particular asymptotic limit in the dimensions.Complementary to the sample and model complexity bottlenecks, Kaplan et al. [2020] also observed the emergence of computational scaling laws in the risk as a function of flops used in training. A recent line of work has investigated this question on the aforementioned linear random feature model under different training algorithms, such as gradient flow [Bordelon et al., 2024] and SGD [Paquette et al., 2024 , Lin et al., 2024] . Due to the simplicity of this setting, the risk of ridge regression with a particular choice of regularization λ is closely related to the risk of different descent algorithms for least-squares at a fixed running horizon [Ali et al., 2019 , 2020 , Sonthalia et al., 2024] . A similar analogy allows us to compare our results to the ones obtained in [Paquette et al., 2024 , Lin et al., 2024] . In particular, our setting cover three of the phases identified by Paquette et al. [2024] , and correspond to the result in Theorem 4.1 with λ = 1 (ℓ = 1). Similarly, the rates of Lin et al. [2024] are obtained by taking λ to be the inverse of the learning rate. A detailed connection to this line of work is discussed in Appendix E. 
conclusion: 
 In this paper, we have investigated the generalization properties of random feature models, deriving a non-asymptotic deterministic equivalent for the risk of random feature ridge regression-which recovers (and unifies) previous asymptotic findings as special limits. Our results provide a rigorous multiplicative approximation rate, enabling us to analyze error scaling laws under source and capacity conditions, and offers a complete view of the different scaling regimes and their cross-overs. Our analysis relies on Assumption 3.1 which, while popular in theoretical investigations, excludes more realistic random feature models, such as φ(x, w) = σ(x ⊤ w) with x, w Gaussian vectors and non-linear σ. Although restrictive, this assumption allowed us to derive tight multiplicative approximation bounds for a generic random feature model with infinite-dimensional features-which was essential for obtaining the rigorous excess risk rates that are the primary motivation of our work. We further note that numerical simulations in Figure 1 and Appendix C suggest that the predictions of Theorem 3.3 remain accurate much beyond Assumption 3.1. We consider lifting this technical condition-e.g., by following the approach in Misiakiewicz and Saeed [2024] -to be an important direction for future research. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: The experiments are simple illustrations of the theorems. They are simple enough to be ran on a standard laptop in a a few hours.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: This work is of theoretical nature, and therefore has no major ethical implications.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This work is of theoretical nature, and therefore has no relevant societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: This work is of theoretical nature, and therefore has no risk of misusage. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: All resources used from other works are properly acknowledged. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We consider a feature vector f ∈ R q , q ∈ N ∪ {∞}, with covariance matrixΣ = E[f f T ]. We denote γ 2 1 ≥ γ 2 2 ≥ γ 2 3 ≥ • •• the eigenvalues of Σ in non-increasing order. In the case of infinite-dimensional features q = ∞, we will further assume that Tr(Σ) < ∞, i.e., we consider Σ to be a trace-class self-adjoint operator.We assume that the feature f satisfies the following assumption. Assumption A.1 (Feature concentration). There exist c * , C * > 0 such that for any p.s.d. matrix A ∈ R q×q with Tr(ΣA) < ∞, we haveEQUATION)Recall that we denote C a1,...,a k constants that only depend on the values of {a i } i∈ [k] . We use a i = ' * ' to denote the dependency on the constants c * , C * from Assumption A.1.We will further define the following two quantities. Definition 2 (Effective regularization). For an integer n, covariance Σ, and regularization λ ≥ 0, we define the effective regularization λ * associated to model (n, Σ, λ) to be the unique non-negative solution to the equationEQUATION)Throughout this appendix, we assume that λ > 0. The existence and uniqueness follow from noticing that the left-hand side is monotonically increasing in λ * while the right-hand side is monotonically decreasing. We consider the change of variable µ * := µ * (λ) = λ/λ * , such that µ * is the unique non-negative solution ofEQUATIONBoth µ * and λ * are increasing functions with λ. Definition 3 (Intrinsic dimension). For a covariance matrix Σ ∈ R q×q with eigenvalues in nonincreasing order γ 2 1 ≥ γ 2 2 ≥ γ 2 3 ≥ • • • , we define the intrinsic dimension r Σ (k) at level k ∈ N of Σ to be the intrinsic dimension of the covariance matrix Σ ≥k = diag(γ 2 k , γ 2 k+1 , . . .), i.e., the covariance matrix projected orthogonally to the top k -1 eigenspaces, which is given byr Σ (k) := Tr(Σ ≥k ) ∥Σ ≥k ∥ op = q j=k γ 2 j γ 2 k .The intrinsic dimension of Σ ≥k captures the number of dimensions of Σ ≥k that have significant spectral content, i.e., γ 2 j ≈ ∥Σ ≥k ∥ op (see [Tropp et al., 2015, Chapter 7] for further background). We are given n i.i.d. features (f i ) i∈[n] , and we denote F = [f 1 , . . . , f n ] T ∈ R n×q the feature matrix. The train and test errors are functionals of the feature matrix F . In particular, they depend on the following resolvent matrix R = (F T F + λI q ) -1 . In this section we consider functionals that depend on products of F , R and deterministic matrices.For a general p.s.d. matrix A ∈ R q×q , define the functionalsΦ 1 (F ; A, λ) := Tr AΣ 1/2 (F T F + λ) -1 Σ 1/2 , Φ 2 (F ; λ) := Tr F T F n (F T F + λ) -1 , Φ 3 (F ; A, λ) := Tr AΣ 1/2 (F T F + λ) -1 Σ(F T F + λ) -1 Σ 1/2 , Φ 4 (F ; A, λ) := Tr AΣ 1/2 (F T F + λ) -1 F T F n (F T F + λ) -1 Σ 1/2 .These functionals are well approximated by quantities proportional toΨ 1 (λ * ; A) := Tr AΣ(Σ + λ * ) -1 , Ψ 2 (λ * ) := 1 n Tr Σ(Σ + λ * ) -1 , Ψ 3 (λ * ; A) := 1 n • Tr(AΣ 2 (Σ + λ * ) -2 ) n -Tr(Σ 2 (Σ + λ * ) -2) .Without loss of generality, we can assume that Tr(AΣ)< ∞ for Φ 1 , as otherwise Φ 1 (F ; A, λ) = Ψ 1 (µ * ; A, λ) = ∞ almost surely, and Tr(AΣ 2 ) < ∞ for Φ 3 and Φ 4 , as otherwise Φ j (F ; A, λ) = Ψ j (µ * ; A, λ) = ∞, j = 3, 4, almost surely.Our relative approximation bound will depend on the covariance matrix Σ throughEQUATIONwhere η * ∈ (0, 1/2) is a constant that will only depend on c * , C * and we used the convention thatγ 2 ⌊η * •n⌋ = 0 if ⌊η * • n⌋ > 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 featuresEQUATIONthen for any p.s.d. matrix A, we have with probability at least 1 -n -D thatEQUATIONEQUATIONEQUATIONEQUATION)Proof of Theorem A.2. The only difference between this theorem and [Misiakiewicz and Saeed, 2024, Theorem 4 ] comes from the definition of ρ λ (n). This new definition is obtained by slightly modifying the proof bounding the operator norm of Σ 1/2 RΣ 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] . ConsiderF + = [f +,1 , . . . , f +,n ] T ∈ R n×(q-k * )where f +,i correspond to the projection orthogonal to the top k * := ⌊η * n⌋ -1 eigenspaces with covariance matrixΣ + := E[f +,i f T +,i ] = diag(γ 2 k * , γ 2 k * +1 , . . . , γ 2 q ).Then, denoting S = i∈[n] S i with S i := f +,i f T i,+ , we have with probability at least 1 -n -D , for any i ∈ [n],∥S i ∥ op ≤ Tr(Σ + ) + C * ,D • log(n) γ 2 k * Tr(Σ + ) ≤ Tr(Σ + ) 1 + C * ,D log(n) r Σ (k * ) =: L n .Denoting S = i∈[n] S i with S i := S i 1 ∥Si∥op≤Ln , so that S = S with probability at least1 -n -D , we obtain ∥ S∥ op ≤ nL n γ 2 k * =: v n , ∥E[ S]∥ op ≤ n∥E[S i ]∥ op = nγ 2 k * .Therefore, applying the matrix Bernstein's inequality with intrinsic dimension [Tropp et al., 2015, Theorem 7.3.1] to S gives that with probability at least 1 -n -D ,∥ S∥ op ≤ nγ 2 k * + C D ( √ v n + L n ) log(r Σ (k * )n) ≤ nγ 2 k * + C D L n log(r Σ (k * )n) ≤ nγ 2 k * 1 + r Σ (k * ) n 1 + C * ,D log(n) r Σ (k * ) log(r Σ (k * )n) .Note that by the condition of our theorem, log(n) ≤ K √ n, and therefore∥ S∥ op ≤ C * ,D,K • nγ 2 k * 1 + r Σ (k * ) n 1 + n r Σ (k * ) log(r Σ (k * )n) ≤ C * ,D,K • nγ 2 k * 1 + r Σ (k * ) ∨ n n log(r Σ (k * ) ∨ n) .Following the rest of the argument in [Misiakiewicz and Saeed, 2024 , Lemma 1] we obtain ρ λ (n) in Eq. ( 52).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 Z = (σ(⟨x i ,w j ⟩)) i∈[n],j∈[p] ∈ R n×p conditional on (w j ) j∈[p] in Section B.3, and functionals of F = (ξ k ϕ k (w j )) j∈[p],k≥1 ∈ R p×∞ 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.Recall that throughout the paper, we will keep track of the parameters of the problem (n, p, Σ, λ, σ 2 ε ). For the other constants C * , K, D, we will denote C a1,a2,...,a k constants that only depend on the values of {a i } i∈ [k] . We use a i = ' * ' to denote the dependency on the constant C * appearing in Assumption 3.1 and Assumption 3.2.Throughout this appendix, we will directly work in the 'feature space'g i := (ψ k (x i )) k≥1 ,andf j := (ξ k ϕ k (w j )) k≥1 ,with distribution induced by x i ∼ µ x and w j ∼ µ w . We will denote the covariate feature and weight feature matrices byG := [g 1 , . . . , g n ] T ∈ R n×∞ , F := [f 1 , . . . , f p ] T ∈ R p×∞ .We denote the random feature weight vectorz i := 1 √ p [σ(⟨w 1 , x i ⟩), . . . , σ(⟨w p , x i ⟩)] = 1 √ p F g i ∈ R p ,and the associated feature matrixZ = [z 1 , . . . , z n ] T = 1 √ p GF T ∈ R n×p .Note that f has covariance matrixΣ := E[f f T ] = diag(ξ 2 1 , ξ 2 2 , ξ 2 3 , . . .).We will further introduce the covariance matrix of z conditional on the weight feature matrix F (i.e., conditional on (w j ) j∈[p] )EQUATION)Note that under Assumption 3.1, the features z and f satisfy the following assumption. Assumption B.1 (Concentration of the features z and f ). There exists a constant C * > 0 such that for any weight feature matrix F ∈ R p×∞ and deterministic p.s.d. matrix A ∈ R p×p with Tr( Σ F A) < ∞, we haveEQUATIONand for any deterministic p.s.d. matrix B ∈ R ∞×∞ with Tr(ΣB) < ∞,EQUATION)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 * (g) := g T β * from i.i.d. samples (y i , g i ) i∈[n]withy i = g T i β * + ε i , where ε i are independent noise with E[ε i ] = 0 and E[ε 2 i ] = σ 2 ε . Denote y = (y 1 , .. . , y n ) the vector containing the labels. We fit this data using a random feature model with i.i.d. random weight featuresEQUATIONWe fit the parameter a using random feature ridge regression (RFRR) âλ = arg minEQUATION)The test error is then given byEQUATIONwhere the bias and variance terms are given explicitly byEQUATIONEQUATION)Note that both the bias and variance terms are random quantities that depend on the random matrices G, 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, Σ, β * , λ, σ 2 ε ), i.e., we will show that with high probability|B(β * ; G, F , λ) -B n,p (β * , λ)| = O n -1/2 + p -1/2 • B n,p (β * , λ), |V(G, F , λ) -V n,p (λ)| = O n -1/2 + p -1/2 • V n,p (λ),where B n,p (β * , λ) and V n,p (λ) are defined in Eqs ( 22) and ( 23), and the approximation rates O(•) 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 F are well approximated by functionals that only depend on F , i.e.,EQUATIONWe then show that B(β * ; F , λ) and V(F , λ) are well approximated by B n,p (β * , λ) and V n,p (λ) withEQUATIONFor 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 F is in some good event F ∈ A F , whereP F (A F ) ≥ 1 -p -D, so that we can immediately write functionals with regularization parameter that does not depend on Σ F , and therefore the rate will be directly O n -1/2 + p -1/2 . 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 rankRecall that our deterministic equivalents will depend on the fixed points (ν 1 , ν 2 ) ∈ R 2 >0 stated in Definition 1. Furthermore, our approximation guarantees will depend on the covariance matrix Σ through ρ κ (p) and ρ κ (n, p) which we restate below for convenienceEQUATIONEQUATIONEQUATIONwhere η * ∈ (0, 1/4) is a constant that only depends on C * appearing in Assumption B.1, and r Σ (k) is the intrinsic dimension of Σ at level k (see Definition 3)r Σ (k) = p j=k ξ 2 j ξ 2 k .Observe that ρ κ (n, p) is well defined for n → ∞ while p stays constant with ρ κ (∞, p) = 1, and for p → ∞ while n stays constant with ρ κ (n, ∞) = ρ κ (n) (under the conditions in our setting that ρ κ (p) ≤ K √ p for some constant K).In this section, we introduce and prove properties on the fixed point (ν 1 , ν 2 ) ∈ R 2 >0 and the weight feature matrix F which we will use to prove deterministic equivalents.Feature covariance matrix. The features z i ∈ R p conditional on F are i.i.d. random vectors with covariance Σ F = F F T /p. We first show that with high probability over F , this feature covariance matrix has eigenvalues and intrinsic dimensions bounded by the ones of Σ.1 , ξ2 2 , . . . ξ2 p ) the p eigenvalues of Σ F in nonincreasing order. Applying the definition of the intrinsic dimension at level k to Σ F , we have for any k = 1, . . . , p,r Σ F (k) = p j=k ξ2 j ξ2 k .(71)Applying Theorem A.2 directly to functionals of Z conditional on F , the approximation guarantees depend onEQUATIONwhich simply corresponds to ρ λ defined in Eq. ( 52) applied to Σ F where we recall that ξ2 ⌊η * •n⌋ = 0 if ⌊η * • n⌋ > p. The next lemma shows that with high probability over F , we have ρ λ (n) ≲ ρ λ (n, p) for all n ∈ N. Lemma B.2 (Feature covariance matrix). Assume the feature vectors {f j } j∈[p] satisfy Assumption B.1. Then for any D, K > 0, there exist constants η * ∈ (0, 1/4) and C * ,D,K > 0 such that the following holds. For any p ≥ C * ,D,K , the eventA F = F ∈ R p×∞ : ∥ Σ F ∥ op ≥ 1 2 , ρ λ (n) ≤ C * ,D,K • ρ λ (n, p), ∀n ∈ N, λ ∈ R (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 F . Recall that (ν 1 , ν 2 ) ∈ R 2 >0 are the solutions to the fixed point equations stated in Definition 1. In order to get approximation guarantees when pν 1 → 0 as n → ∞, we will analyze separately the top eigenspaces of F from the rest. For an integer m ∈ N, we split the feature vector f j = [f 0,j , f +,j ] where f 0,j ∈ R m corresponds to the top m coordinates with covarianceΣ 0 := E[f 0,j f T 0,j ] = diag(ξ 2 1 , ξ 2 2 , .. . , ξ 2 m ), and f +,j ∈ R ∞ corresponds to the high degree features orthogonal to the top m eigenspaces. We denote their covarianceΣ + := E[f +,j f T +,j ] = diag(ξ 2 m+1 , ξ 2 m+2 , . . .). We split the weight feature matrix intro F = [F 0 , F + ],whereF 0 = [f 0,1 , . . . , f 0,p ] T ∈ R p×m , F + = [f +,1 , . . . , f +,p ] T ∈ R p×∞ .We will use that for m chosen such that p • ξ m+1 ≪ Tr(Σ + ), we have with high probability∥F + F T + -Tr(Σ + ) • I p ∥ op ≲ p • ξ m+1 Tr(Σ + ) ≪ Tr(Σ + ), and therefore F F T + κ ≈ F 0 F T 0 + γ(κ), where we defined the function γ(κ) := κ + Tr(Σ + ).To simplify the final statement of our results, we assume that we can choose m such that p 2 ξ 2 m+1 ≤ γ(pλ/n). Note that ν 1 ≥ λ/n from the fixed point equations and γ(pλ/n) ≤ γ(pν 1 ) (e.g., see Equation ( 76)). For convenience, we will further denoteEQUATION) Lemma B.3 (Concentration of high-degree part of F ). Assume that (f +,j ) j∈[p] satisfy Assumption B.1 and m ∈ N is chosen such that p 2 ξ 2 m+1 ≤ γ(pλ/n).Then for any D > 0, there exists a constant C * ,D > 0 such that with probability at least 1 -p -D ,∥F + F T + -Tr(Σ + ) • I p ∥ op ≤ C * ,D log 3 (p) √ p γ λ ≤ C * ,D log 3 (p) √ p γ + .This lemma follows directly from [Misiakiewicz and Saeed, 2024, Proposition 9] .Effective regularization and fixed points. Conditional on F , the bias and variance are functionals of the random matrix Z which has n i.i.d. rows with regularization parameter λ and covariance Σ F . The deterministic approximations to these functionals depend on an "effective regularization" ν1 associated to (n, Σ F , λ) (see Definition 2 in Appendix A for background) which is given as the unique non-negative solution to the equationn - λ ν1 = Tr Σ F Σ F + ν1 -1 .Note that the right-hand side can be rewritten asEQUATIONwhich is itself of functional of the random matrix F which has p i.i.d. rows with regularization parameter pν 1 and covariance Σ. Note that ν1 is a random variable depending itself on F . However we will show that it concentrates on a deterministic value ν 1 . We therefore introduce a second effective regularization ν 2 associated to (p, Σ, pν 1 ) given as the unique non-negatice solution of the equationp - pν 1 ν 2 = Tr Σ(Σ + ν 2 ) -1 .The functional ( 75) is then well approximated byTr F F T (F F T + pν 1 ) -1 = (1 + o p,P (1)) • Tr Σ(Σ + ν 2 ) -1 .This motivates to define (ν 1 , ν 2 ) ∈ R 2 >0 as the unique non-negative solutions to the coupled fixed point equationsEQUATION)Writing ν 1 as a function of ν 2 indeed produces the equations stated in Definition 1.To show that ν1 concentrates on ν 1 , we define the following fixed points (ν 1 , ν2 ) ∈ R 2 >0 to be the unique positive solutions to the random equationsEQUATIONThe following proposition shows that (ν 1 , ν2 ) is well approximated by (ν 1 , ν 2 ) with high probability.Proposition B.4 (Concentration of the fixed points). Assume that (f j ) j∈[p] satisfy Assumption B.1. Then for any D, K > 0, there exist constants η * ∈ (0, 1/4) and C * ,D,K > 0 such that the following holds. Let ρ κ (p) and ρ κ (n, p) be defined as per Eqs. ( 26) and (25), and γ λ and γ + as per Eq. (74).For any p ≥ C * ,D,K and λ > 0, if it holds thatEQUATIONthen with probability at least 1 -p -D , we havemax |ν 2 -ν 2 | ν 2 , |ν 1 -ν 1 | ν 1 ≤ C * ,D,K • E ν (p),where we definedE ν (p) := ρ λ (n, p) • ρ γ+ (p) 5/2 log 3 (p) √ p .The proof of this proposition can be found in Section B.7.2.To study functionals of Z conditional on F , we will assume that F belonds to the good eventEQUATIONwhere A F is defined in Lemma B.2. In particular, as long as p ≥ C * ,D,K and condition (78) hold, then P(A F ) ≥ 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 F 0 and the high-degree part 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 F 0 with regularization γ + = pν 1 + Tr(Σ + ). We therefore introduce an effective regularization ν 2,0 associated to the model (p, Σ 0 , γ + ), i.e., the unique positive solution to the equationEQUATION)Intuitively, ν 2,0 will be closed to ν 2 as soon asλ max (Σ + ) ≪ ν 2 as n - pν 1 ν 2 ≈ Tr Σ 0 (Σ 0 + ν 2 ) -1 + Tr(Σ + ) ν 2 ,and uniqueness of the positive solution ν 2,0 . This is formalized in the following lemma. Lemma B.5 (Truncated fixed point). Let m be chosen such thatEQUATION)Furthermore, there exists an absolute constant C > 0 such thatEQUATION)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 intoTr Σ 0 (Σ 0 + ν 2,0 ) -1 + Tr(Σ + ) ν 2,0 -Tr Σ(Σ + ν 2 ) -1 ≤ |ν 2,0 -ν 2 | Tr Σ 0 (Σ 0 + ν 2,0 ) -1 (Σ 0 + ν 2 ) -1 + ξ 2 m+1 + |ν 2,0 -ν 2 | ν 2,0 Tr Σ + (Σ + + ν 2 ) -1 ≤ ξ 2 m+1 ν 2,0 + |ν 2,0 -ν 2 | ν 2,0 Tr Σ(Σ + ν 2 ) -1 ≤ 3 p Tr Σ(Σ + ν 2 ) -1 ,where we used that ξ 2 m+1 /ν 2,0 ≤ γ + /(p 2 ν 2,0 ) ≤ 1/p by the assumption on m and identity (80).As mentioned in Section B.1, we will first show that the test error concentrates over Z conditional on F on some quantity that only depends on Σ F . The bias and variance terms can be written in terms of the following three functionals of the feature matrix Z: for a general p.s.d. matrix A ∈ R p×p and positive scalar κ > 0, defineEQUATIONwhere we recall that Z has i.i.d. rows with covariance Σ F = F F T /p. We show that these functional are well approximated by functionals of F that can be written in terms of the following functionals:EQUATION)The following proposition gather the approximation guarantees for Φ 2 , Φ 3 , Φ 4 listed in Eq. ( 83). Proposition B.6 (Deterministic equivalents for Φ(Z) conditional on F ). Under Assumption B.1 and assuming that F ∈ A F defined in Eq. (79), for any D, K > 0, there exist constants η * ∈ (0, 1/4), C D,K > 0, and C * ,D,K > 0 such that the followings holds. Let ρ κ (p) and ρ κ (n, p) be defined as per Eqs. ( 26) and (25). For any n ≥ C D,K and regularization parameter λ > 0, if it holds thatEQUATIONthen for any p.s.d. matrix A ∈ R p×p (independent of Z|F ), with probability at least 1 -n -D on Z conditional on F , we haveEQUATIONEQUATIONEQUATION)where the approximation rate is given byEQUATION)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 O(p -1/2 ) in the approximation rate E 1 (n, p) defined in Eq. ( 89) comes from comparing pν 1 with pν 1 and is equal toρ λ (n, p) • E ν (n, p) where E ν (n, p) is defined in Proposition B.4. If instead,we compared to functionals with regularization pν 1 , then the approximation rate in Proposition B.6 would scale 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 A is itself a random matrix uncorrelated (but not independent) to Z|F . The following proposition gather these approximation guarantees and is a consequence of [Misiakiewicz and Saeed, 2024, Lemma 10] EQUATIONEQUATION)where we denoted v := Σ -1/2 F v and the approximation rate is given byEQUATION)We defer the proof of Proposition B.7 to Section B.7.3.After replacing the bias and variance terms by their deterministic equivalents over the randomness in Z|F , we obtain functionals in terms of Φ 2 (F ; pν 1 ) and Φ 5 (F ; A, pν 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 F + F T + by a deterministic matrix, which results in a regularization parameter γ(pν 1 ) = pν 1 + Tr(Σ + ).The functionals of F 0 can be written in terms of the following quantities: for any deterministic matrix B ∈ R m×m , defineEQUATION)We show that these functionals can be well approximated by the deterministic functions that can be written in terms ofEQUATION)Recall that for κ = pν 1 , we denote γ + := γ(pν 1 ) and ν 2,0 the effective regularization associated to model (p, Σ 0 , γ + ). The following proposition gather the approximation guarantees for Φ 1 , Φ 2 , Φ 3 , Φ 4 listed in Eq. ( 93).Proposition B.8 (Deterministic equivalents for F 0 ). Under Assumption B.1, for any D, K > 0, there exist constants η * ∈ (0, 1/4), C D,K > 0, and C * ,D,K > 0 such that the followings holds. Let ρ κ (p) be defined as per Eq. (26). For any p ≥ C D,K and λ > 0, if it holds thatEQUATIONthen for any deterministic p.s.d. matrix B ∈ R m×m , with probability at least 1 -p -D , we haveEQUATIONEQUATIONEQUATIONEQUATIONwhere the approximation rate is given byEQUATION)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 highdegree parts F 0 and F + , we will further need deterministic equivalents when B is itself a random matrix uncorrelated but not independent to F . We gather the associated deterministic equivalents in the following proposition.Proposition B.9 (Deterministic equivalents for F 0 , uncorrelated numerator). Assume the same setting as Proposition B.8 and the same conditions (95). Consider a deterministic vector v ∈ R m and a random vector u = (u j ) j∈[p] with i.i.d. entries and E[u j ] = 0, E[u 2 j ] = 1, and E[f 0,j u j ] = 0.Then with probability at least 1 -p -D , we haveEQUATIONwhere we denoted v := Σ -1/2 0 v and the approximation rate is given byEQUATION)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 Φ i (F 0 ; B, κ), i ∈ [4], the functionals listed in Eq. ( 93) applied to the truncated feature matrix F 0 , with covariance Σ 0 , regularization γ(κ), and deterministic matrix B ∈ R m×m , and Φ i (F ; B, κ), i ∈ [4], the functionals applied to the full feature matrix F ∈ R p×∞ , where Σ 0 is replaced by Σ, the regularization parameter is κ, and the deterministic matrix B ∈ R ∞×∞ . Similarly, we will us the notationΨ i (ν 2,0 ; B), i ∈ [3]for the truncated deterministic functionals (94), and the notation Ψ i (ν 2 ; B), i ∈ [3] to denote the full functionals with Σ 0 replaced by Σ and B ∈ R ∞×∞ .Recall the expressions for the variance termV(G, F , λ) = σ 2 ε • Tr Σ F Z T Z(Z T Z + λ) -2, and its associated deterministic equivalentEQUATIONEQUATION)We prove in this section an approximation guarantee between V(G, F , λ) and V n,p (λ). For convenience, we state a separate theorem for this term. EQUATIONthen with probability at least 1 -n -D -p -D , we have|V(G, F , λ) -V n,p (λ)| ≤ C * ,D,K • E V (n, p) • V n,p (λ),where the approximation rate is given byEQUATION)Proof of Theorem B.10. First, note that V(G, F , λ) can be written in terms of the functional Φ 4 defined in Eq. ( 83):V(G, F , λ) = σ 2 ε • nΦ 4 (Z; I, λ).Recall that A 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 obtainP(A F ) ≥ 1 -p -D .Hence, applying Proposition B.6 for F ∈ A F and via union bound, we obtain that with probability at leastEQUATIONwhere E 1 (n, p) is defined in Eq. ( 89) and we recall the expressionsn Φ 5 (F ; I, pν 1 ) = Φ 6 (F ; I, pν 1 ) n -Φ 6 (F ; I, pν 1 ) , Φ 6 (F ; I, pν 1 ) = Tr (F F T ) 2 (F F T + pν 1 ) -2 .Let us decompose Φ 6 (F ; I, pν 1 ) intoΦ 6 (F ; I, pν 1 ) = Tr(F F T (F F T + pν 1 ) -1 ) -pν 1 Tr(F F T (F F T + pν 1 ) -2 ).From Lemma B.11 stated below, we have with probability at least1 -p -D 1 p Tr(F F T (F F T + pν 1 ) -1 ) -Ψ 2 (ν 2 ) ≤ C * ,D,K • E 3 (p) • Ψ 2 (ν 2 ), 1 p Tr(F F T (F F T + pν 1 ) -2 ) -Ψ 3 (ν 2 ; Σ -1 ) ≤ C * ,D,K • ρ γ+ (p)E 3 (p) • Ψ 3 (ν 2 ; Σ -1 ),where E 3 (p) is the approximation rate defined in Eq. ( 100). Note thatpΨ 2 (ν 2 ) -p 2 ν 1 Ψ 3 (ν 2 ; Σ -1 ) = Tr(Σ(Σ + ν 2 ) -1 ) - ν 1 Tr(Σ(Σ + ν 2 ) -2 ) 1 -1 p Tr(Σ 2 (Σ + ν 2 ) -2 ) = p 1 - ν 1 ν 2 - ν 1 ν 2 1 -ν1 ν2 -1 p Tr(Σ 2 (Σ + ν 2 ) -2 ) 1 -1 p Tr(Σ 2 (Σ + ν 2 ) -2 ) = p 1 - ν 1 ν 2 2 + ν 1 ν 2 2 Tr(Σ 2 (Σ + ν 2 ) -2 ) p -Tr(Σ 2 (Σ + ν 2 ) -2 ) = nΥ(ν 1 , ν 2 ).Combining the above displays, we deduce thatΦ 6 (F ; I, pν 1 ) -nΥ(ν 1 , ν 2 ) ≤ C * ,D,K • ρ γ+ (p)E 3 (p) • pΨ 2 (ν 2 ) + p 2 ν 1 Ψ 3 (ν 2 ; Σ -1 ) ≤ C * ,D,K • ρ γ+ (p)E 3 (p) • nΥ(ν 1 , ν 2 ) + 2p 2 ν 1 Ψ 3 (ν 2 ; Σ -1 )Using Eq. ( 120) in Lemma B.14 stated in Section B.7, we conclude that with probability at leastEQUATIONFinally, by simple algebra, we haven Φ 5 (F ; I, pν 1 ) - Υ(ν 1 , ν 2 ) 1 -Υ(ν 1 , ν 2 ) ≤ n Φ 5 (F ; I, pν 1 ) + 1 | Φ 6 (F ; I, pν 1 ) -nΥ(ν 1 , ν 2 )| n -Υ(ν 1 , ν 2 ) ≤ n Φ 5 (F ; I, pν 1 ) - Υ(ν 1 , ν 2 ) 1 -Υ(ν 1 , ν 2 ) + 1 1 -Υ(ν 1 , ν 2 ) • C * ,D,K • ρ γ+ (p)E 3 (p) Υ(ν 1 , ν 2 ) 1 -Υ(ν 1 , ν 2 ).(110) Note that by Eq. ( 119) in Lemma B.14, we haveΥ(ν 1 , ν 2 ) 1 -Υ(ν 1 , ν 2 ) ≤ (1 -Υ(ν 1 , ν 2 )) -1 ≤ C * • ρ λ (n, p).Hence rearranging the terms in Eq. ( 110) and using from conditions (106) and that p ≥ C * ,D,K , we obtain with probability at least 1 -p -D that n Φ 5 (F ; I, pν 1 ) -EQUATION)Using an union bound and combining bounds Eqs. ( 108) and ( 111), we obtain with probability at least 1 -n -D -p -D , that|V(G, F , λ) -V n,p (λ)| ≤ V(G, F , λ) -σ 2 ε • n Φ 5 (F ; I, pν 1 ) + σ 2 ε n Φ 5 (F ; I, pν 1 ) - Υ(ν 1 , ν 2 ) 1 -Υ(ν 1 , ν 2 ) ≤ C * ,D,K • E 1 (p, n) + ρ λ (n, p)ρ γ+ (p)E 3 (p) • σ 2 ε • n Φ 5 (F ; I, pν 1 ) + V n,p (λ) ≤ C * ,D,K • E 1 (p, n) + ρ λ (n, p)ρ γ+ (p)E 3 (p) • V n,p (λ),where we used Eq. ( 111) and conditions (106) in the last line. Replacing the rates E j by their expressions conclude the proof of this theorem.Lemma B.11. Under the setting of Theorem B.10 and assuming the same conditions (106), we have with probability at least 1 -p -D ,EQUATIONEQUATION)where E 3 (p) is the approximation rate defined in Eq. (100).The proof of this lemma can be found in Section B.7.4.Recall the expression for the bias termB(β * ; G, F , λ) = ∥β * -p -1/2 F T (Z T Z + λ) -1 Z T Gβ * ∥ 2 2, and its associated deterministic equivalentχ(ν 2 ) = Tr(Σ(Σ + ν 2 ) -2 ) p -Tr(Σ 2 (Σ + ν 2 ) -2 ) , B n,p (β * , λ) = ν 2 2 1 -Υ(ν 1 , ν 2 ) ⟨β * , (Σ + ν 2 ) -2 β * ⟩ + χ(ν 2 )⟨β * , Σ(Σ + ν 2 ) -2 β * ⟩ .We prove in this section an approximation guarantee between B(β * ; G, F , λ) and B n,p (β * , λ). For convenience, we state a separate theorem for this term. Theorem B.12 (Deterministic equivalent for the bias term). Assume the features (z i ) i∈[n] and (f j ) j∈[p] satisfy Assumption B.1, and that there exists m ∈ N such that p 2 ξ 2 m ≤ γ m (nλ/p). Then, for any D, K > 0, there exist constants η * ∈ (0, 1/2) and C * ,D,K > 0 such that the following holds. Let ρ κ and ρ κ be defined as per Eqs. ( 26) and (25), and recall that γ λ := γ m (nλ/p) and γ + := γ m (pν 1 ). For any n, p ≥ C * ,D,K and λ > 0, if it holds thatEQUATIONthen with probability at least 1 -n -D -p -D , we have|B(β * ; G, F , λ) -B n,p (β * , λ)| ≤ C * ,D,K • E B (n, p) • B n,p (β * , λ),where the approximation rate is given byEQUATION)Before starting the proof, let us introduce some notations. First, define P F the projection onto the span of F , and P ⊥,F the projection orthogonal to the span of F , i.e.,P F := (F T F ) † F T F , P ⊥,F = I -P F .We can decompose the feature g with respect to the orthogonal sum of these two subspacesg = P F g + P ⊥,F g = √ p(F T F ) † F T z + P ⊥,F g.We define r := P ⊥,F g and R = [r 1 , . . . , r n ] T ∈ R n×∞ . Similarly, we can decompose the target function h * (g) = ⟨β * , g⟩ = ⟨β F , z⟩ + ⟨β ⊥,F , r⟩,where we introducedβ F := √ pF (F T F ) † β * , β ⊥,F = P ⊥,F β * .Note that in particular E[z⟨r, β ⊥,F ⟩] = 0 by orthogonality.Proof of Theorem B.12.Step 0: Decomposing the bias term.Note that using the notations introduced above, we can decompose the bias term intoB(β * ; G, F , λ) = ∥β * -p -1/2 F T (Z T Z + λ) -1 Z T Gβ * ∥ 2 2 = 1 p F T β F -(Z T Z + λ) -1 Z T (Zβ F + Rβ ⊥,F ) 2 2 + ∥β ⊥,F ∥ 2 2 = T 1 -2T 2 + T 3 + ∥β ⊥,F ∥ 2 2 .where we denotedT 1 := λ 2 ⟨β F , (Z T Z + λ) -1 Σ F (Z T Z + λ) -1 β F ⟩, T 2 := λ⟨β F , (Z T Z + λ) -1 Σ F (Z T Z + λ) -1 Z T Rβ ⊥,F ⟩, T 3 := ⟨β ⊥,F , R T Z(Z T Z + λ) -1 Σ F (Z T Z + λ) -1 Z T Rβ ⊥,F ⟩.We proceed similarly to the proof for the variance term, by first considering the deterministic equivalent over Z conditional on F , and then over F . We omit some repetitive details for the sake of brevity.Step 1: Deterministic equivalent over Z conditional on F .Ã * = Σ -1/2 F β F β T F Σ -1/2 F, we haveT 1 = λ 2 Φ 3 (Z; Ã * , λ).Furthermore, T 3 and T 2 correspond respectively to the terms ( 90) and ( 91) in Proposition B.7 with v = β F and u = Rβ ⊥,F whereE[z i u i ] = E[z i ⟨r i , β ⊥,F ⟩] = 0, E[u 2 i ] = ∥β ⊥,F ∥ 2 2 .Thus, under the assumptions of Theorem B.12, we can apply Propositions B.8 and B.7 to obtain (via union bound) that with probability at least1 -n -D -p -D , T 1 -(nν 1 ) 2 Φ 5 (F ; Ã * , pν 1 ) ≤ C * ,D,K • E 1 (p, n) • (nν 1 ) 2 Φ 5 (F ; Ã * , pν 1 ), |T 2 | ≤ C * ,D,K • E 2 (p, n) • ∥β ⊥,F ∥ 2 2 • (nν 1 ) 2 Φ 5 (F ; Ã * , pν 1 ), T 3 -∥β ⊥,F ∥ 2 2 • n Φ 5 (F ; I, pν 1 ) ≤ C * ,D,K • E 2 (p, n) • ∥β ⊥,F ∥ 2 2 .Hence we deduce thatB(β * ; G, F , λ) -(nν 1 ) 2 Φ 5 (F ; Ã * , pν 1 ) -∥β ⊥,F ∥ 2 2 • n Φ 5 (F ; I, pν 1 ) -∥β ⊥,F ∥ 2 2 ≤ C * ,D,K • {E 1 (n, p) + E 2 (n, p)} • (nν 1 ) 2 Φ 5 (F ; Ã * , pν 1 ) + ∥β ⊥,F ∥ 2 2 .Let us simplify these terms. Recall that n Φ 5 (F ; Ã * , pν 1 ) = Φ 6 (F ; Ã * , pν 1 ) n -Φ 6 (F ; I, pν 1 ) , n Φ 5 (F ; I, pν 1 ) Φ 6 (F ; I, pν 1 ) n -Φ 6 (F ; I, pν 1 ) .For the term involving Ã * , we can rewrite it asν 2 1 Φ 6 (F ; Ã * , pν 1 ) = ν 2 1 ⟨β F , Σ -1 F (F T F ) 2 (F T F + pν 1 ) -2 β F ⟩ = (pν 1 ) 2 ⟨β * , (F T F ) † (F T F )(F T F + pν 1 ) -2 (F T F )(F T F ) † β * ⟩ = (pν 1 ) 2 ⟨β * , (F T F + pν 1 ) -2 β * ⟩ -∥β ⊥,F ∥ 2 2 .Hence the terms involving ∥β ⊥,F ∥ 2 2 cancel out and we obtain(nν 1 ) 2 Φ 5 (F ; Ã * , pν 1 )+∥β ⊥,F ∥ 2 2 •n Φ 5 (F ; I, pν 1 )+∥β ⊥,F ∥ 2 2 = (pν 1 ) 2 ⟨β * , (F T F + pν 1 ) -2 β * ⟩ 1 -1 n Φ 6 (F ; I, pν 1 ).Combining the above displays, we deduce that with probability at leastEQUATION)Step 2: Deterministic equivalents over F .Following the same steps as Eq. ( 110) in the proof of Theorem B.10, we have with probability at least 1 -p -D ,(1 -n -1 Φ 6 (F ; I, pν 1 )) -1 -(1 -Υ(ν 1 , ν 2 )) -1 ≤ C * ,D,K • ρ λ (n, p)ρ γ+ (p)E 3 (p)•(1-Υ(ν 1 , ν 2 )) -1 .Furthermore, from Lemma B.13 stated below, with probability at least 1 -p -D ,(pν 1 ) 2 ⟨β * , (F T F + pν 1 ) -2 β * ⟩ -B n,p (β * , λ) ≤ C * ,D,K • ρ γ+ (p) 2 E 4 (p) • B n,p (β * , λ),where B n,p (β * , λ) is defined in Eq. ( 118). Combining these two bounds and recalling conditions (114), we obtain(pν 1 ) 2 ⟨β * , (F T F + pν 1 ) -2 β * ⟩ 1 -1 n Φ 6 (F ; I, pν 1 ) - B n,p (β * , λ) 1 -Υ(ν 1 , ν 2 ) ≤ C * ,D,K ρ λ (n, p)ρ γ+ (p)E 3 (p) + ρ γ+ (p) 2 E 4 (p) • B n,p (β * , λ) 1 -Υ(ν 1 , ν 2 ) . Noting that B n,p (β * , λ) = B n,p (β * , λ)/(1 -Υ(ν 1 , ν 2 )), we can combine this bound with Eq. ( 116) to obtain via union bound that with probability at least1 -n -D -p -D , |B(β * ; G, F , λ) -B n,p (β * , λ)| ≤ C * ,D,K E 1 (n, p) + E 2 (n, p) + ρ λ (n, p)ρ γ+ (p)E 3 (p) + ρ γ+ (p) 2 E 4 (p) • B n,p (β * , λ).Replacing the rates E j by their expressions conclude the proof of this theorem.Lemma B.13. Under the setting of Theorem B.12 and assuming the same conditions (114), we have with probability at least 1 -p -D ,EQUATION)where E 3 (p) and E 4 (p) are the approximation rates defined in Eqs. (100) and (103), and we denotedEQUATION)The proof of Lemma B.13 can be found in Section B.7.5.In this section, we prove the technical results that were deferred from the previous sections. We start with a lemma that gathers useful bounds on the deterministic functionals. Lemma B.14. There exists a constant C * > 0 such thatEQUATION) where we recall that Υ(ν 1 , ν 2 ) is defined as per Eq. (105). Furthermore, under Assumption 3.2, we haveEQUATIONEQUATIONwhere B n,p (β * , λ) is defined as per Eq. (118) in Lemma B.13.Proof of Lemma B.14.Step 1: Equation (119).Note that we haveΥ(ν 1 , ν 2 ) ≤ 1 n Tr(Σ(Σ + ν 2 ) -1 ) ≤ p n .In particular, if n ≥ p/η * , then we can simply write(1 -Υ(ν 1 , ν 2 )) -1 ≤ 1 1 -η * = C * .For n ≤ p/η * , note that using the first identity in Eq. ( 76), we have(1 -Υ(ν 1 , ν 2 )) -1 ≤ 1 - 1 n Tr(Σ(Σ + ν 2 ) -1 ) -1 ≤ nν 1 λ ≤ C * ρ λ (n).Combining the previous two displays, we obtain Eq. ( 119).Step 2: Equation (120).We rewrite the left-hand side aspν 1 Tr(Σ(Σ + ν 2 ) -2 ) p -Tr(Σ 2 (Σ + ν 2 ) -2 ) ≤ pν 1 p -Tr(Σ(Σ + ν 2 ) -1 ) Tr(Σ(Σ + ν 2 ) -2 ) = Tr(Σ(Σ + ν 2 ) -1 ) -Tr(Σ 2 (Σ + ν 2 ) -2 ) ≤ 1 - 1 C * Tr(Σ(Σ + ν 2 ) -1 ),where we uses the second of the identities (76) in the second line, and Assumption 3.2 in the third line. Hence,pν 1 Tr(Σ(Σ + ν 2 ) -2 ) p -Tr(Σ 2 (Σ + ν 2 ) -2 ) ≤ (C * -1) • Tr(Σ(Σ + ν 2 ) -1 ) -pν 1 Tr(Σ(Σ + ν 2 ) -2 ) p -Tr(Σ 2 (Σ + ν 2 ) -2 ) = (C * -1) • nΥ(ν 1 , ν 2 ).Step 3: Equation (121).Similarly, we get again using Eq. ( 76) and Assumption 3.2 thatpν 1 ⟨β * , Σ(Σ + ν 2 ) -2 β * ⟩ p -Tr(Σ 2 (Σ + ν 2 ) -2 ) ≤ ν 2 ⟨β * , (Σ + ν 2 ) -1 β * ⟩ -ν 2 ⟨β * , Σ 2 (Σ + ν 2 ) -2 β * ⟩ ≤ 1 - 1 C * • ν 2 ⟨β * , (Σ + ν 2 ) -1 β * ⟩,and thereforepν 1 ⟨β * , Σ(Σ + ν 2 ) -2 β * ⟩ p -Tr(Σ 2 (Σ + ν 2 ) -2 ) ≤ (C * -1) ν 2 ⟨β * , (Σ + ν 2 ) -1 β * ⟩ -pν 1 ⟨β * , Σ(Σ + ν 2 ) -2 β * ⟩ p -Tr(Σ 2 (Σ + ν 2 ) -2 )= B n,p (β * , λ), which concludes the proof of this lemma.Proof of Lemma B.2. Recall that we consider Σ F = p -1 F F T , with F = [f 1 , . . . , f p ] T ∈ R p×∞ and the f i are i.i.d. random vectors satisfying Assumption B.1. For any integers k 2 ≥ k 1 ≥ 1, we split the weight feature matrix into  and F 3 = [f 3,1 , . . . , f 3,p ] T ∈ R p×∞ contains the rest of the coordinates. In other words, we split the feature vector intoF = [F 1 , F 2 , F 3 ], where F 1 = [f 1,1 , . . . , f 1,p ] T ∈ R p×k1 with f 1,j the first k 1 coordinates of the feature vector f j , F 2 = [f 2,1 , . . . , f 2,p ] T ∈ R p×(k2-k1) with f 2,j the next k 2 -k 1 coordinates of f j ,f j = [f 1,j , f 2,j , f 3,j ]. Denote Σ 1 = E[f 1,j f T 1,j ] = diag(ξ 2 1 , . . . , ξ 2 k1 ) ∈ R k1×k1 , Σ 2 = E[f 2,j f T 2,j ] = diag(ξ 2 k1+1 , . . . , ξ 2 k2 ) ∈ R (k2-k1)×(k2-k1) , Σ 3 = E[f 3,j f T 3,j ] = diag(ξ 2 k2+1 , ξ 2 k2+2 , . . .) ∈ R ∞×∞ .We decompose the feature covariance matrix intoEQUATION)Step 1: Bounding the eigenvalues of F 1 and F 2 .Introduce the whitened matricesF 1 = F 1 Σ -1/2 1 = [f 1,1 , . . . , f 1,p ] T , F 2 = F 2 Σ -1/2 2 = [f 2,1 , . . . , f 2,p ] T ,so that the feature vectors f 1,j and f 2,j have covariance I k1 and I k2-k1 respectively. We have∥F T 1 F 1 /p -I k1 ∥ op = sup v∈R k 1 ,∥v∥2=1 1 p j∈[p] ⟨v, f 1,j ⟩ 2 -1Denote Z j := ⟨v, f 1,j ⟩ 2 -1. Then we have from Equation (60) applied toB = Σ -1/2 1 vv T Σ -1/2 1 , for any integer q ≥ 1, E[|Z j | q ] ≤ qC * ∞ 0 t q-1 e -cxt dt = C * q! c q * .Hence we can apply Bernstein's inequality for centered sub-exponential random variable and obtainEQUATION)Following the proof of [Vershynin, 2010, Theorem 5 .39], we deduce that there exist constants C * , C * ,D > 0 such that with probability at least 1 -p -D ,∥F T 1 F 1 /p -I k1 ∥ op ≤ C * k 1 p + C * ,D log(p) p .In particular, there exists η * ∈ (0, 1/4) and C * ,D > 0 such that for p ≥ C * ,D and via union bound, we have with probability at least 1 -p -D (reparametrizing D), that for anyk 1 ≤ ⌊η * • p⌋, ∥F T 1 F 1 /p -I k1 ∥ op ≤ 1/2.From Eq. ( 122), we deduce that the k 1 -th eigenvalue of Σ F for k 1 < ⌊η * • p⌋ is lower bounded byEQUATION)andλ max F 1 F T 1 p ≤ 3 2 ξ 2 1 = 3 2 .Similarly for F 2 , we have with probability at least 1 -p -D that for anyEQUATION)Step 2: Bounding the eigenvalues of F .Equation ( 124) provides a lower bound on the eigenvalues ξ2 k of Σ F up to k < ⌊η * • p⌋. Let's upper bound the p eigenvalues of Σ F . From now on, set k 2 = p * -1 where p * := ⌊η * • p⌋.For the contribution of ∥F + ∥, we use the matrix Bernstein's inequality as in [Misiakiewicz and Saeed, 2024 , Lemma 1] (see proof of Theorem A.2 in Appendix A) and obtain that for p ≥ C K , with probability at least 1 -p -D ,1 p ∥F 3 F T 3 ∥ op ≤ C * ,D,K • ξ 2 p * 1 + r Σ (p * ) ∨ p p log (r Σ (p * ) ∨ p) .By the min-max theorem, we have with probability at least 1 -p -D for all k 1 < p * -1,ξ2 k1+1 ≤ λ max F 2 F T 2 p + F 3 F T 3 p ≤ 3 2 ξ 2 +C * ,D,K •ξ 2 p * 1 + r Σ (p * ) ∨ p p log (r Σ (p * ) ∨ p) ,where we used Eq. ( 125). For k ≥ p * , we use thatξ2 k ≤ 1 p ∥F 3 F T 3 ∥ op ≤ 3 2 ξ 2 k + C * ,D,K • ξ 2 p * 1 + r Σ (p * ) ∨ p p log (r Σ (p * ) ∨ p) .We deduce from the above two displays that with probability at least 1 -p -D , we have for any k ≤ pEQUATIONwhere we recall that we definedM Σ (k) := 1 + r Σ (⌊η * • k⌋) ∨ k k log (r Σ (⌊η * • k⌋) ∨ k) .Step 3: Bounding r Σ F (k) for k ≤ p.Recall that the intrinsic dimension r Σ F (k) at level k ≤ p is given byr Σ F (k) = p j=k ξ2 j ξ2 k .First note that for p ≥ k ≥ ⌊η * • p⌋, we simply use that and the eigenvalues are nonincreasing to getp j=k ξ2 j ξ2 k ≤ (p + 1 -k) ≤ C(1 -η * )p ≤ C 1 -η * η * k.For k ≤ p * -1, we use that from Eq. ( 124) with probability at least 1 -p -D ,p j=k ξ2 j ξ2 k ≤ 2 ξ 2 k   3 2 ⌊η * •p⌋-1 j=k ξ 2 k + p j=⌊η * •p⌋ ξ2 j   .Let's bound the second term on the right-hand side. Notice thatp j=⌊η * •p⌋+1 ξ2 j = min V Tr( Σ F (I -V V T )) ≤ 1 p Tr(F 3 F T 3 ),where the minimization is over V ∈ R p×(⌊η * •p⌋-1) with V T V = I ⌊η * •p⌋-1 and the second inequality is obtained by taking V orthogonal to the matrix [F 1 , F 2 ]. We can rewrite1 p Tr(F 3 F T 3 ) -Tr(Σ 3 ) = 1 p j∈[p] ∥f 3,j ∥ 2 2 -Tr(Σ 3 ).Introduce Z j := ∥f 3,j ∥ 2 2 -Tr(Σ 3 ). By Assumption B.1 with B = diag(0, I) (identity on the subspace Σ 3 and 0 otherwise), we haveE[|Z j | q ] ≤ qC x ∥Σ 3 ∥ q F ∞ 0 t q-1 e -cxt dt ≤ C x • Tr(Σ 3 ) q q! c q x .We therefore we can apply Bernstein's inequality (123) again and we getP   1 p j∈[p] Z j ≥ t • Tr(Σ 3 )   ≤ 2 exp(-c * min(pt 2 , pt)).Hence, for any p ≥ C * ,D with probability at least 1 -p -D ,1 p Tr(F 3 F T 3 ) ≤ 2Tr(Σ 3 ).Combining the above display with the previous inequalities yields with probability at least 1 -p -D that for any k ≤ ⌊η * • p⌋,r Σ F (k) = p j=k ξ2 j ξ2 k ≤ C ∞ j=k ξ 2 j ξ 2 k .We deduce that there exist a constant C * > 0 such that with probability at least 1 -p -D , we have for anyEQUATIONwhere r Σ (n) is the effective rank associated to Σ.Step 4: Concluding the proof.For any n * = ⌊η * • n⌋ > p, we have ρ λ (n) = ρ λ (n, p) = 1. Hence, we only need to consider the case n * ≤ p. Using Eqs. ( 126) and ( 127), we getρ λ (n) = 1 + n ξ2 n * λ 1 + r Σ F (n * ) ∨ n n log r Σ F (n * ) ∨ n ≤ 1 + C * ,D,K • nξ 2 n * λ + n p • p • ξ p * λ M Σ (p) M Σ (n) ≤ 1 + C * ,D,K • nξ 2 n * λ + n p • ρ λ (p) M Σ (n),which concludes the proof.Proof of Proposition B.4. Recall that (ν 1 , ν2 ) ∈ R 2 >0 are the unique solution to the random fixed point equations (77). From the first equation, we have the following bounds on ν1 :pλ n ≤ pν 1 ≤ p∥ Σ F ∥ op + pλ n .From Lemma B.2, we have with probability at least 1 -p -D that ∥ Σ F ∥ op ≤ C * ,D,K ≤ p. Hence, by the uniform concentration over κ ∈ [pλ/n, (p 3 + pλ)/n] in Lemma B.15 stated below and an union bound, we deduce that with probability at least 1 -p -D ,Tr F F T (F F T + pν 1 ) -1 -Tr Σ(Σ + ν2 ) -1 ≤ C * ,K,D ρ γ+ (p) 5/2 log 3 (p) √ p Tr Σ(Σ + ν2 ) -1 =: E 2 • Tr Σ(Σ + ν2 ) -1 .Therefore, we can rewrite the fixed equations (77) asn - λ ν1 = Tr Σ Σ + ν2 -1 • (1 + δ(F )), p - pν 1 ν2 = Tr Σ(Σ + ν2 ) -1 .where with probability at least 1 -p -D , we have |δ(F )| ≤ E(p). Therefore, by condition (78) andp ≥ C * ,D,K C * E(p) • ρ λ (n, p) ≤ C * ,D,K log(p) ≤ 1 2 ,and we can directly use Lemma B.17 stated below to obtain with probability at least 1 -p -D ,|ν 1 -ν 1 | ν 1 ≤ C * • E 2 (p) • ρ λ (n, p), |ν 2 -ν 2 | ν 2 ≤ C * • E 2 (p) • ρ λ (n, p).This concludes the proof of this proposition.For any κ ≥ 0, denote ν 2 (κ) ∈ R >0 the unique positive solution toEQUATION)We will further define analogously to Eq. ( 80) the truncated fixed pointEQUATIONwhere we recall that we denoted γ(κ) = κ + Tr(Σ + ). It will be convenient to recall the notationsΦ 2 (F ; κ) = 1 p Tr F F T (F F T + κ) -1 , Φ 2 (F 0 ; γ(κ)) = 1 p Tr F 0 F T 0 (F 0 F T 0 + γ(κ)) -1 ,and the deterministic equivalentsΨ 2 (ν 2 (κ)) = 1 p Tr Σ(Σ + ν 2 (κ)) -1 , Ψ 2 (ν 2,0 (κ)) = 1 p Tr Σ 0 (Σ 0 + ν 2,0 (κ)) -1 .The next lemma show that Φ 2 (F , κ) concentrates on Ψ 2 (ν 2 (κ)) uniformly on an interval of κ. Lemma B.15. Under the setting of Proposition B.4 and for any D, K ≥ 0, there exist constants η * ∈ (0, 1/4) and C * ,D,K > 0 such that the following holds. For any p ≥ C * ,D,K and λ > 0, if it holds thatEQUATION)then with probability at least 1 -p -D , we have for any κ ∈ [pλ/n, p(p 2 + λ)/n],EQUATION)Proof of Lemma B.15. Throughout the proof we assume that we are working on the event∥F + F T + -γ(0)I p ∥ op ≤ C * ,D log 3 (p) √ p γ(pλ/n),which happens with probability at least 1 -p -D by Lemma B.3 via union bound. Note that γ(κ) ≥ γ(pλ/n) for all the κ ∈ [pλ/n, p(p 2 + λ)/n]. Furthermore, we assume that p ≥ C * ,D chosen large enough so that∥F + F T + -γ(0)I p ∥ op ≤ 1/2 • γ(pλ/n) so that F F T + κ ⪰ 1 2 γ(κ).The proof will proceed via a standard union bound argument over κ in the interval [pλ/n, p(p 2 +λ)/n].Let us first prove Eq. ( 131) for a fixed κ. We first simplify the functional by rewriting it asΦ 2 (F ; κ) = 1 - κ p Tr (F F T + κ) -1 = 1 - κ p Tr (F 0 F T 0 + γ(κ)) -1 + κ p ∆,where we denoted|∆| = Tr (F F T + κ) -1 -Tr (F 0 F T 0 + γ(κ)) -1 = Tr (F F T + κ) -1 (F 1 F T 1 -γ(0)I p )(F 0 F T 0 + γ(κ)) -1 ≤ C * ,D log 3 (p) √ p Tr (F 0 F T 0 + γ(κ)) -1 .Using again the above identity, we rewrite1 p Tr (F 0 F T 0 + γ(κ)) -1 = 1 γ(κ) - 1 γ(κ) Φ 2 (F 0 ; γ(κ)).We can now apply Eq. ( 55) in Theorem A.2: under the assumption of Proposition B.4 and recalling the conditions ( 130), we have with probability at least 1 -p -D ,Φ 2 (F 0 ; γ(κ)) -Ψ 2 (ν 2,0 (κ)) ≤ C * ,D,K ρ γ(κ) (p) 5/2 log 3/2 (p) √ p Ψ 2 (ν 2,0 (κ)).Combining the above displays, we obtain that with probability at least1 -p -D Φ 2 (F ; κ) -Ψ 2 (ν 2,0 (κ)) - Tr(Σ + ) pν 2,0 ≤ κ γ(κ) Φ 2 (F 0 ; γ(κ)) -Ψ 2 (ν 2,0 (κ)) + κ|∆| ≤ C * ,D,K ρ γ(κ) (p) 5/2 log 3/2 (p) √ p Ψ 2 (ν 2,0 (κ)) + C * ,D log 3 (p) √ p κ p Tr (F 0 F T 0 + γ(κ)) -1 ,where we used in the first inequality identity (129) to get1 - κ γ(κ) 1 - 1 p Tr(Σ 0 (Σ 0 + ν 2,0 ) -1 ) = Tr(Σ + ) pν 2,0 .Further note that using condition (130), we can simplify the right-hand sideκTr (F 0 F T 0 + γ(κ)) -1 ≤ κ γ(κ) |1 -Ψ 2 (ν 2,0 (κ))| + C * ,D,K • K • Ψ 2 (ν 2,0 (κ)) ≤ C * ,D,K Ψ 2 (ν 2,0 (κ)) + Tr(Σ + ) pν 2,0 .We can now use Eq. ( 82) in Lemma B.5 applied to ν 2 (κ) and ν 2,0 (κ) to concluded that with probability at leastEQUATION)We now consider a p -P -grid P n of the interval κ ∈ [pλ/n, p(p 2 + λ)/n], which contains at most p P +3 points. We can use a union bound over κ ∈ P n and reparametrizing D ′ = D + P + 3, so that with probability at least 1 -p -D , Equation ( 132) holds for any κ ∈ P n . Then for any point κ 1 ∈ [pλ/n, p(Kp 2 + λ)/n], denote κ 0 ∈ P n its closest point. Then by Lemma B.16 stated below, we haveΦ 2 (F ; κ 1 ) -Ψ 2 (ν 2 (κ 1 )) ≤ Φ 2 (F ; κ 1 ) -Φ 2 (F ; κ 0 ) + Φ 2 (F ; κ 0 ) -Ψ 2 (ν 2 (κ 0 )) + |Ψ 2 (ν 2 (κ 0 )) -Ψ 2 (ν 2 (κ 1 ))| ≤ p CK |κ 1 -κ 0 | Φ 2 (F ; κ 0 ) + E(p) • Ψ 2 (ν 2 (κ 0 )) + p CK |κ 1 -κ 0 |Ψ 2 (ν 2 (κ 1 )) ≤ p CK-P + E(p) 1 + p CK-P + E(p) • Ψ 2 (ν 2 (κ 1 )).where we used that |κ 1 -κ 0 | ≤ p -P . Taking P = CK + 1 concludes the proof.Lemma B.16. Under the setting of Proposition B.4 and for any D, K ≥ 0, there exist constants η * ∈ (0, 1/4), C > 0 and C * ,D > 0 such that the following holds. For any p ≥ 1 and λ > 0, it holds thatEQUATION)then for any κ 0 , κ 1 ≥ pλ/n, we haveEQUATION)Furthermore, if p ≥ C * ,D , then we have with probability 1 -p -D that for any κ 1 , κ 2 ≥ pλ/n,EQUATION)Proof of Lemma B.16. Using the identity (128), we can decompose the first difference intoΨ 2 (ν 2 (κ 1 )) Ψ 2 (ν 2 (κ 0 )) -1 = κ0 ν2(κ0) -κ1 ν2(κ1) pΨ 2 (ν 2 (κ 0 )) ≤ 1 ν 2 (κ 0 ) • pΨ 2 (ν 2 (κ 0 )) |κ 1 -κ 0 | + ν 2 (κ 0 ) ν 2 (κ 1 ) -1 .From condition ( 133) and the proof of [Misiakiewicz and Saeed, 2024, Lemma 11] , we have1 ν 2 (κ 0 ) • pΨ 2 (ν 2 (κ 0 )) ≤ p 3+2K , ν 2 (κ 0 ) ν 2 (κ 1 ) -1 ≤ p 2+2K |κ 1 -κ 0 |.Combining the above inequalities, we deduce that there exists a constant C > 0 such thatΨ 2 (ν 2 (κ 1 )) Ψ 2 (ν 2 (κ 0 )) -1 ≤ p CK |κ 1 -κ 0 |.For the second inequality (135), we rewrite the difference asΦ 2 (F ; κ 1 ) Φ 2 (F ; κ 0 ) -1 = Tr(F F T (F F T + κ 1 ) -1 (F F T + κ 0 ) -1 ) Tr(F F T (F F T + κ 0 ) -1 ) |κ 1 -κ 0 | ≤ ∥(F F T + κ 1 ) -1 ∥ op |κ 1 -κ 0 |.Hence, recalling Lemma B.3 and condition (133), for any p ≥ C * ,D , we get with probability at least 1 -p -D and for all κ 1 , κ 2 ≥ pλ/n,Φ 2 (F ; κ 1 ) Φ 2 (F ; κ 0 ) -1 ≤ 2 γ(κ 1 ) |κ 1 -κ 0 | ≤ n K |κ 1 -κ 0 |,which concludes the proof of this lemma.We consider (ν ε 1 , ν ε 2 ) ∈ R ≥0 the unique positive solutions of the perturbed equations:EQUATIONEQUATION)where we use in the last inequality that ν 0 1 /ν 0 2 ≤ 1 and the definition of the effective rank. Rearranging the terms we obtainν 0 1 λ Tr(Σ(Σ + ν 0 2 ) -1 ) ≤ 1 1 -η * 1 + Tr(Σ ≥⌊η * •n⌋ ) λ .Combining the above bounds we deduce that|δ 1 | ≤ C * |ε| • 1 + 1 n≤p/η * Tr(Σ ≥⌊η * •n⌋ ) λ ≤ C * • ρ λ (n, p) • |ε|.By assumptionC * • ρ λ (n, p) • |ε| ≤ 1/2 and therefore ν ε 1 ≤ 2ν 0 1 . We conclude the first inequality ν ε 1 -ν 0 1 ν 0 1 ≤ ν ε 1 ν 0 1 |δ 1 | ≤ C * • ρ λ (n, p) • |ε|.Recalling Eq. ( 138), we have directly|δ 2 | ≤ |δ 1 | ν ε 1 ν 0 2 ν 0 1 ν ε 2 =⇒ ν ε 2 -ν 0 2 ν 0 2 ≤ ν ε 1 -ν 0 1 ν 0 1 ,which concludes the proof.Proof of Proposition B.6. Recall that ρ λ (n) is defined in Eq. ( 72) and that for F ∈ A F , we haveρ λ (n) ≤ C * ,D,K ρ λ (n, p) for all n ∈ N.Under the assumptions of Proposition B.6, we can apply Theorem A.2 to Z conditional on F to obtain that with probability at least1 -n -D , Φ 2 (Z; λ) - p n Φ 2 (F ; pν 1 ) ≤ C * ,D,K ρ λ (n, p) 5/2 log 3/2 (n) √ n • p n Φ 2 (F ; pν 1 ), Φ 3 (Z; A, λ) - nν 1 λ 2 Φ 5 (F ; A, pν 1 ) ≤ C * ,D,K ρ λ (n, p) 6 log 5/2 (n) √ n • nν 1 λ 2 Φ 5 (F ; A, pν 1 ), Φ 4 (Z; A, λ) -Φ 5 (F ; A, pν 1 ) ≤ C * ,D,K ρ λ (n, p) 6 log 3/2 (n) √ n • Φ 5 (F ; A, pν 1 ),where ν1 is the solution of the fixed point equation ( 77). We conclude the proof using Lemma B.18 stated below and that by condition (85), we haveC * ,D,K • ρ λ (n, p)E ν (p) ≤ C * ,D,K K.Proof of Proposition B.7. Again, under the assumptions of the proposition and for F ∈ A F , we can apply [Misiakiewicz and Saeed, 2024, Lemma 10] to get⟨u, Z(Z T Z + λ) -1 Σ F (Z T Z + λ) -1 Z T u⟩ -n Φ 5 (F ; I, pν 1 ) ≤ C * ,D,K ρ λ (n, p) 6 log 7/2 (n) √ n , ⟨u, Z(Z T Z + λ) -1 Σ F (Z T Z + λ) -1 Z T v⟩ ≤ C * ,D,K ρ λ (n, p) 6 log 7/2 (n) √ n • nν 1 λ Φ 5 (F ; vv T , pν 1 ).We conclude by combining these inequalities with Lemma B.18.Lemma B.18. For F ∈ A F , we haveEQUATIONEQUATIONandEQUATIONProof of Lemma B.18. For convenience, we denote κ := ν 1 , κ ′ := ν1 , and Γ := Σ F . For Eq. ( 140), we simply use thatp Φ 2 (F ; pν 1 ) -p Φ 2 (F ; pν 1 ) = Tr Γ(Γ + κ ′ ) -1 -Tr Γ(Γ + κ) -1 = |κ -κ ′ |Tr Γ(Γ + κ ′ ) -1 (Γ + κ) -1 ≤ |κ ′ -κ| κ ′ Tr Γ(Γ + κ) -1 ≤ C * ,D,K • E ν (p) • p Φ 2 (F ; pν 1 ).Similarly, by simple algebra, we haveEQUATIONFurthermore, note that by the identity (77),Φ 6 (F ; I, pν 1 ) n -Φ 6 (F ; I, pν 1 ) -1 ≤ Φ 2 (F ; pν 1 ) n -Φ 2 (F ; pν 1 ) -1 = ν1 λ Φ 2 (F ; pν 1 ).Furthermore, we have from the previous computation and simple algebra thatν1 λ Φ 2 (F ; pν 1 ) ≤ (1 + C * ,D,K E ν (p)) • ν 1 λ Tr(Σ(Σ + ν 2 ) -1 ) ≤ C * ,D,K • ρ λ (n, p),where we used the same argument as in the proof of Lemma B.17 in the last inequality as well as condition ( 85). The proof of Eqs. ( 142) and ( 141) from simple algebra from the above displays and (143).Proof of Lemma B.11. For convenience, we introduce the notationsEQUATIONwhere we recall that we denoted γ + = γ(pν 1 ) = pν 1 +Tr(Σ + ). Recall that for the first approximation guarantee, we denoteΦ 2 (F ; pν 1 ) = 1 p Tr(F F T G F ), Φ 2 (F 0 ; pν 1 ) = 1 p Tr(F 0 F T 0 G 0 ),and the deterministic equivalentsΨ 2 (ν 2 ) = 1 p Tr(Σ(Σ + ν 2 ) -1 ), Ψ 2 (ν 2,0 ) = 1 p Tr(Σ 0 (Σ 0 + ν 2,0 ) -1 ).For the second approximation guarantee, recall that we denoteΦ 4 (F ; Σ -1 , pν 1 ) = 1 p Tr(F F T G 2 F ), Φ 4 (F ; Σ -1 0 , pν 1 ) = 1 p Tr(F 0 F T 0 G 2 0 ),and their associated deterministic equivalentsΨ 3 (ν 2 ; Σ -1 ) = 1 p • Tr(Σ(Σ + ν 2 ) -2 ) p -Tr(Σ 2 (Σ 2 + ν 2 ) -2 ) , Ψ 3 (ν 2,0 ; Σ -1 0 ) = 1 p • Tr(Σ 0 (Σ 0 + ν 2,0 ) -2 ) p -Tr(Σ 2 0 (Σ 2 0 + ν 2,0 ) -2 ).We separate the analysis of the low-degree part F 0 from the high-degree part F + . To remove the dependency on the high-degree part F + , we recall that by Lemma B.3, we have with probability at leastEQUATIONwhere we denoted ∆ := F + F + -Tr(Σ + ) • I p and we recall that γ + = γ(pν 1 ) = pν 1 + Tr(Σ + ).In particular, taking p ≥ C * ,D , we have ∥∆∥ op ≤ 1 2 γ + and thereforeEQUATIONStep 1:Bound on | Φ 2 (F ; pν 1 ) -Ψ 2 (ν 2 )|.First note that we have the identityΦ 2 (F ; pν 1 ) = 1 -ν 1 Tr(G F ) = 1 -ν 1 Tr(G 0 ) + ν 1 Θ,where we denoted Θ = Tr(G 0 ) -Tr(G F ). By Eqs. ( 145) and ( 146), we haveEQUATIONUsing again the above identity, we haveEQUATIONUnder the assumption of the lemma, we can apply Proposition B.8 and obtain with probability at leastEQUATIONwhere E 3 (p) is defined in Eq. ( 100). Furthermore note that using identity (80), we haveTr(Σ + ) γ + + pν 1 γ + Ψ 2 (ν 2,0 ) = Ψ 2 (ν 2,0 ) + Tr(Σ + ) pν 2,0 ,and that by Eq. ( 82) in Lemma B.5,EQUATIONThus combining Eqs. ( 147), ( 149) and ( 150), we obtain| Φ 2 (F ; pν 1 ) -Ψ 2 (ν 2 )| ≤ ν 1 |Θ| + pν 1 γ + Φ 2 (F 0 ; pν 1 ) -Ψ 2 (ν 2,0 ) + Ψ 2 (ν 2,0 ) + Tr(Σ + ) pν 2,0 -Ψ 2 (ν 2 ) ≤ C * ,D,K log 3 (p) √ p + E 3 (p) + 1 p ν 1 Tr(G 0 ) + pν 1 γ + Ψ 2 (ν 2,0 ) + Ψ 2 (ν 2 ) ,with probability at least 1 -p -D via union bound. Using condition (106), we can simplify the right-hand side using identity (148) and bounds ( 149) and (150) to getκ 1 Tr(G 0 ) ≤ pν 1 γ + |1 -Ψ 2 (ν 2,0 )| + C * ,D,K KΨ 2 (ν 2,0 ) ≤ C * ,D,K Ψ 2 (ν 2,0 ) + Tr(Σ + ) pν 2,0 ≤ C * ,D,K • Ψ 2 (ν 2 ).This concludes the proof of the first part of this lemma.Step 2: Bound on | Φ 4 (F ; Σ -1 , pν 1 ) -Ψ 3 (ν 2 ; Σ -1 )|.We proceed similarly as in the first part and omit some repetitive details. First note that we can rewriteΦ 4 (F ; Σ -1 , pν 1 ) = 1 p Tr(G F ) -ν 1 Tr(G 2 F ) = 1 p Tr(G 0 ) -ν 1 Tr(G 2 0 ) + Θ = Tr(Σ + ) γ 2 + 1 -Φ 2 (F 0 ; pν 1 ) + pν 1 γ + Φ 4 (F 0 ; Σ -1 0 , pν 1 ) + Θ,whereEQUATIONAgain, by Proposition B.8, we get that with probability at least 1 -p -D thatEQUATIONFurthermore, note that by Lemma B.19 stated below, we haveEQUATION)Combining Eqs. ( 151), ( 152) and ( 153), we deduce via union bound that with probability at least1 -p -D | Φ 4 (F ; Σ -1 , pν 1 ) -Ψ 3 (ν 2 ; Σ -1 )| ≤ C * ,D,K • E 3 (p) 1 p Tr(G 0 ) + ν 1 Tr(G 2 0 ) + Tr(Σ + ) 2 γ 2 + Ψ 2 (ν 2,0 ) + pν 1 γ + Ψ 3 (ν 2,0 ; Σ -1 0 ) + Ψ 3 (ν 2 ; Σ -1 ) .Let us simplify the right hand side. First, from the proof of Lemma B.19, we haveTr(Σ + ) 2 γ 2 + Ψ 2 (ν 2,0 ) + pν 1 γ + Ψ 3 (ν 2,0 ; Σ -1 0 ) ≤ Cρ γ+ (p) • Ψ 3 (ν 2 ; Σ -1 ).Combining the above two displays with E 3 (p) ≤ K from conditions (106) yields1 p Tr(G 0 ) -ν 1 Tr(G 2 0 ) ≤ C * ,D,K • ρ γ+ (p) • Ψ 3 (ν 2 ; Σ -1 ).Finally, note that using Eq. ( 152) and again E 3 (p) ≤ K thatν 1 Tr(G 2 0 ) ≤ pν 1 γ + Φ 4 (F ; Σ -1/2 0 , pν 1 ) ≤ C * ,D,K Ψ 3 (ν 2 ; Σ -1 ),which concludes the proof of this lemma.Lemma B.19. Assuming that p 2 ξ 2 m ≤ γ + , we haveTr(Σ + ) γ 2 + (1 -Ψ 2 (ν 2,0 )) + pν 1 γ + Ψ 3 (ν 2,0 ; Σ -1 0 ) -Ψ 3 (ν 2 ; Σ -1 ) ≤ C ρ γ+ (p) p Ψ 3 (ν 2 ; Σ -1 ).Proof of Lemma B.19. For convenience, we introduceΥ(ν 2,0 ) := 1 p Tr(Σ 2 0 (Σ 0 + ν 2,0 ) -2 ), Υ(ν 2 ) := 1 p Tr(Σ 2 (Σ + ν 2 ) -2 ).Using that1 p Tr(Σ 0 (Σ 0 + ν 2,0 ) -2 ) = 1 ν 2,0 {Ψ 2 (ν 2,0 ) -Υ(ν 2,0 )} ,we obtain by simple algebra and using identity (80) thatTr(Σ + ) γ 2 + (1 -Ψ 2 (ν 2,0 )) + pν 1 γ + Ψ 3 (ν 2,0 ; Σ -1 0 ) = 1 ν 2,0 Ψ 2 (ν 2,0 ) + Tr(Σ+) pν2,0 -Υ(ν 2,0 ) p(1 -Υ(ν 2,0 )).Following the proof of [Misiakiewicz and Saeed, 2024, Lemma 7] , we get that|Υ(ν 2,0 ) -Υ(ν 2 )| ≤ 10 pξ 2 m γ + ≤ C p , (1 -Υ(ν 2,0 )) -1 ≤ (1 -Ψ 2 (ν 2,0 )) -1 = pν 2,0 γ + ≤ Cρ γ+ (p).Recalling Eq. ( 82) in Lemma B.5, we can conclude the proof using simple algebraic manipulations similarly to [Misiakiewicz and Saeed, 2024, Lemma 7] .Proof of Lemma B.13. We will follow similar steps as in the proof of Lemma B.11. For the sake of brevity, we omit some repetitive details. Recall that we introduced the notations (144). We decompose the coefficient vector β * = [β 0 , β + ] with β 0 ∈ R m the first m coordinates of β * (aligned with the top m eigenspaces), while β + ∈ R ∞ corresponds to the rest of the coordinates. Further introduce the matricesA * := Σ -1/2 β * β T * Σ -1/2 , A 0 := Σ -1/2 0 β 0 β T 0 Σ -1/2 0 ,and recall the expressions of the functionalsΦ 1 (F ; A * , pν 1 ) = Tr A * Σ 1/2 RΣ 1/2 , Φ 1 (F 0 ; A 0 , pν 1 ) = Tr A 0 Σ 1/2 0 R 0 Σ 1/2 0 , as well as Φ 4 (F ; A * , pν 1 ) = 1 p Tr A * Σ 1/2 RF T F RΣ 1/2 , Φ 4 (F 0 ; A 0 , pν 1 ) = 1 p Tr A 0 Σ 1/2 0 R 0 F T 0 F 0 R 0 Σ 1/2 0 .We further recall the expressions of the deterministic equivalentsΨ 1 (ν 2 ; A * ) = Tr A * Σ(Σ + ν 2 ) -1 , Ψ 1 (ν 2,0 ; A 0 ) = Tr A 0 Σ 0 (Σ 0 + ν 2,0 ) -1 ,andψ 3 (ν 2 ; A * ) = 1 p • Tr(A * Σ 2 (Σ + ν 2 ) -2 ) p -Tr(Σ 2 (Σ + ν 2 ) -2 ) , ψ 3 (ν 2,0 ; A 0 ) = 1 p • Tr(A 0 Σ 2 0 (Σ 0 + ν 2,0 ) -2 ) p -Tr(Σ 2 0 (Σ 0 + ν 2,0 ) -2 ).We first rewrite our functionals into(pν 1 ) 2 ⟨β * , R 2 β * ⟩ = (pν 1 )⟨β * , Rβ * ⟩ -(pν 1 )⟨β * , RF T F R⟩ = (pν 1 ) Φ 1 (F ; A * , pν 1 ) -p Φ 4 (F ; A * , pν 1 ) ,and study each term separately.Step 1: Bounding term Φ 1 (F ; A * , pν 1 ).Let us start by removing the dependency on the high-degree part F + in the denominator. Note that we can rewrite the matrix R in block matrix form(pν 1 )R = (pν 1 ) F T 0 F 0 + pν 1 F T 0 F + F T + F 0 F T + F + + pν 1 -1 =: R 00 R 0+ R T 0+ R ++ , so that (pν 1 ) Φ 1 (F ; A * , pν 1 ) = β T 0 R 00 β 0 + 2β 0 R 0+ β + + β T + R ++ β + .Let us study each of these terms separately. Denote G + := F + F T + + pν 1 . By simple algebra, we haveβ T 0 R 00 β 0 = β T 0 F T 0 G + F 0 + 1 -1 β 0 = γ + Φ 1 (F 0 ; A 0 , pν 1 ) + Θ 00 ,where|Θ 00 | = γ + β T 0 R 0 β 0 -β T 0 F T 0 G + F 0 + 1 -1 β 0 ≤ C R 1/2 0 F T 0 (I -γ + G + )F 0 R 1/2 0 op • γ + β T 0 R 0 β 0 ≤ C * ,D log 3 (p) √ p γ + Φ 1 (F 0 ; A 0 , pν 1 ).Furthermore, from Proposition B.8, we have with probability at least 1 -p -D thatγ + Φ 1 (F 0 ; A 0 , pν 1 ) -ν 2,0 Ψ 1 (ν 2,0 ; A 0 ) ≤ C * ,D,K • E 3 (p) • ν 2,0 Ψ 1 (ν 2,0 ; A 0 ).Hence, combining the previous two displays and using that E 3 (p) ≤ K by conditions (114), we haveEQUATIONSimilarly, denoting G 0 = (F 0 F T 0 + pν 1 ) -1 , we can rewrite the third term asβ T + R ++ β + = β T + F T + G 0 F + + 1 -1 β + = ∥β + ∥ 2 2 -Θ ++ ,where with probability at least 1 -p -D ,EQUATIONwhere we used the same concentration argument as in Step 3 of the proof of Lemma B.2.Finally, we rewriteβ T 0 R 0+ β + = -β T 0 F T 0 G + F 0 + 1 -1 F T 0 (F + F T + + pν 1 ) -1 F + β + .Hence, using Eqs. ( 154) and ( 155) as well as conditions (114), we obtainEQUATIONFinally, note that by Lemma B.20 stated below, we haveEQUATIONCombining Eqs. ( 154), ( 155), (156), and (157), we deduce that with probability at least 1 -p -D ,EQUATION)Step 2: Bounding term Φ 4 (F ; A * , pν 1 ).We rewrite this term asEQUATION)Let us decompose⟨β * , F T G 2 0 F β * ⟩ = ⟨β 0 , F T 0 G 2 0 F 0 β 0 ⟩ + 2⟨β + , F T + G 2 0 F 0 β 0 ⟩ + ⟨β + , F T + G 2 0 F + β + ⟩.For the first term, we have directly from Proposition B.8 thatEQUATIONFor the two other terms, notice that they correspond to the terms ( 101) and ( 102) in Proposition B.9 with v = β 0 and u = F + β + , whereE[f 0,j ⟨f +,j , β + ⟩] = 0, E[u 2 i ] = ∥Σ 1/2 + β * ∥ 2 2 .Hence, by Proposition B.9, we have with probability at least 1 -p -D that⟨β + , F T + G 2 0 F + β + ⟩ - 1 ν 2 2,0 ∥Σ 1/2 + β + ∥ 2 2 p -Tr(Σ 2 0 (Σ 0 + ν 2,0 ) -2 ) ≤ C * ,D,K • E 4 (p) • p∥Σ 1/2 + β + ∥ 2 2 γ 2 + , ⟨β + , F T + G 2 0 F 0 β 0 ⟩ ≤ C * ,D,K • E 4 (p) • ∥Σ 1/2 + β + ∥ 2 p 2 ν 2,0 γ 2 + Ψ 3 (ν 2,0 ; A 0 ).(161) Furthermore, by Lemma B.20 stated below⟨β 0 , Σ 0 (Σ 0 + ν 2,0 ) -2 β 0 ⟩ + ⟨β + , Σ + β + ⟩/ν 2 2,0 p -Tr(Σ 2 0 (Σ 0 + ν 2,0 ) -2 ) -pΨ 3 (ν 2 ; A * ) ≤ C ρ γ+ (p) p • pΨ 3 (ν 2 ; A * ).(162) Combining Eqs. ( 154), ( 155), ( 156), and (157), we deduce that with probability at least 1 -p -D , p Φ 4 (F ; A * , pν 1 ) -pΨ 3 (νEQUATION)where we used thatpν 2,0 γ + p∥Σ 1/2 + β * ∥ 2 2 γ 2 + pΨ 3 (ν 2,0 ; A 0 ) ≤ Cρ γ+ (p) ∥Σ 1/2 + β * ∥ 2 2 /ν 2 2,0 p -Tr(Σ 2 0 (Σ 0 + ν 2,0 ) -2 ) + pΨ 3 (ν 2,0 ; A 0 ) , p∥Σ 1/2 + β + ∥ 2 2 γ 2 + ≤ Cρ γ+ (p) 2 ∥Σ 1/2 + β * ∥ 2 2 /ν 2 2,0 p -Tr(Σ 2 0 (Σ 0 + ν 2,0 ) -2 ).Step 3: Combining the terms.From Eqs. ( 158) and ( 163), we have with probability at least 1 -p -D that(pν 1 ) 2 ⟨β * , R 2 β * ⟩ -ν 2 Ψ 1 (ν 2 ; A * ) + (pν 1 )pΨ 3 (ν 2 ; A * ) ≤ C * ,D,K • ρ γ+ (p) 2 E 4 (p) • [ν 2 Ψ 1 (ν 2 ; A * ) + (pν 1 )pΨ 3 (ν 2 ; A * )] .First, it is straightforward to verify that indeed ν 2 Ψ 1 (ν 2 ; A * ) -(pν 1 )pΨ 3 (ν 2 ; A * ) = B n,p (β * , λ).Then by Eq. ( 121) in Lemma B.14, we conclude that with probability at least 1 -p -D ,(pν 1 ) 2 ⟨β * , R 2 β * ⟩ -B n,p (β * , λ) ≤ C * ,D,K • ρ γ+ (p) 2 E 4 (p) • B n,p (β * , λ),which concludes the proof of this lemma.Lemma B.20. Assuming that p 2 ξ 2 m ≤ γ + , we haveν 2,0 ⟨β 0 , (Σ 0 + ν 2,0 ) -1 β 0 ⟩ + ∥β + ∥ 2 2 -ν 2 Ψ 1 (ν 2 ; A * ) ≤ C p ν 2 Ψ 1 (ν 2 ; A * ), ⟨β 0 , Σ 0 (Σ 0 + ν 2,0 ) -2 β 0 ⟩ + ⟨β + , Σ + β + ⟩/ν 2 2,0 p -Tr(Σ 2 0 (Σ 0 + ν 2,0 ) -2 ) -pΨ 3 (ν 2 ; A * ) ≤ C ρ γ+ (p) p • pΨ 3 (ν 2 ; A * ).Proof of Lemma B.20. This lemma follows from the same arguments as in the proofs of Lemma B.5 and Lemma B.19.In this section we provide further examples of comparison between the excess risk computed using the deterministic equivalent in Theorem 3.3 and numerical simulations, together with details about their realization. , 5, 6, 7, 8 , for which this procedure was used, we take both N, P = 10 4 (with the exception of Fig. 7 (right), where P = 8000) and approximate µ x and µ w respectively with the empirical distributions μx = N i=1 N -1 δ(x -x i ) and μw = P j=1 P -1 δ(w -w j ). Then eq. (2) becomesEQUATIONand since eq. ( 11) impliesE x K(x, x ′ )ψ k (x) = ξ 2 k ψ k (x ′), defining the Gram matrix K emp ∈ R N ×N with elements Kii ′ = K(x i , x i ′ )N -1 and the vectors ψk = (ψ k (x 1 ), . . . , ψ k (x N )) ⊤ , we can write the following eigenvalue problems, for k ∈ [N ]:EQUATION)We then constructed the matrix Σ = diag( ξ2 1 , . . . , ξ2 N ) and used it as an approximation of Σ. One should note that in this situation E x ψ k (x)ψ k ′ (x) = δ kk ′ corresponds to ψk ψk ′ = N δ kk ′ . Similarly, eq. ( 13) implies β * ,k = E x [f * (x)ψ k (x)], which can be approximated by βk = N -1 y ⊤ ψk .(171)Algorithm 1 Empirical diagonalization At initialization, the weights are randomly drawn; then, after sampling a training dataset X tr ∈ R ntr×d , y tr R ntr , the weights of the first layer are trained using gradient descent, iterating for t = 1, . . . , T the followingRequire: {x i } i∈[N ] ∼ i.i.d. µ x , {y i = f * (x i )} i∈[N ] , {w j } j∈[P ] ∼ i.i.d. µ w Ensure: Σ, β * , R n,p (β * , λ) for i, i ′ ∈ {1, . . . , N } do Kii ′ ← (N P ) -1 P j=1 φ(x i , w j )φ(x i ′ , w j ) end for {( ξk , ψk ) k∈[N ] } ← eig( K) ▷ ψk ψk ′ ! = N δ kk ′ for k ∈ {1, . . . , N } do βk ← N -1 y ⊤ ψk end for Σ ← diag(EQUATION)where η is the learning rate, ⊙ is the Hadamard product, f and φ are applied component-wise; finally, the weights of the second layer are minimized using ridge regression, as in eq. ( 5). In this appendix we present a sketch of the derivation of the decay rates for the excess error given in Section 4. We choose p = n q , λ = n -(ℓ-1) , with q, l ≥ 0 and we assumeη k = k -α , β * k = k -1+2αr 2 , with α > 1, r > 0,which follows the source and capacity conditions stated in (37). In order to simplify the derivation of the rates, we introduce the following notation:T s δγ (ν) := ∞ k=1 k -s-δα (k -α + ν) γ , s ∈ 0, 1, 0 ≤ δ ≤ γ.For s + α(δ -γ) < 1 and in the limit ν → 0, this term can be written as a Riemann sum as followsEQUATIONOtherwise, if s + α(δ -γ) > 1, we can write:EQUATIONRewriting (18-19) as follows, we study the dependence of the positive parameters ν 1 and ν 2 with n:ν 2 = ν2 p T 0 11 (ν 2 ) + ν 1 ν 1 = ν1 n T 0 11 (ν 2 ) + λ n .In the limit n → ∞, we can distinguish the following regimes   T 0 11 (ν 2 ) ≪ n, p ν 1 = n -1 λ 1 + O T 0 11 (ν 2 )n -1 ν 2 = n -1 λ 1 + O T 0 11 (ν 2 )(n ∧ p) -1 ν2=o(1) =⇒ ν -1 /α 2 ≪ n 1∧q =⇒ ℓ < α(1 ∧ q) ν 1 ≈ ν 2 ≈ n -ℓ        T 0 11 (ν 2 ) ≪ p ν 1 ≫ λn -1 T 0 11 (ν 2 ) = n -(nν 1 ) -1 λ ν 2 = ν 1 (1 + O T 0 11 (ν 2 )p -1 ) (a) =⇒          ν -1 /α 2 ≪ n q ν 1 ≫ n -ℓ ν -1 /α 2 = O (n + o(n)) ν 2 = ν 1 (1 + o(1)) =⇒ q > 1, ℓ > α ν 1 ≈ ν 2 ∝ n -α        T 0 11 (ν 2 ) ≪ n ν 1 ≪ ν 2 ν 1 = n -1 λ 1 + O T 0 11 (ν 2 )n -1 T 0 11 (ν 2 ) = p -ν 1 ν -1 2 (a) =⇒          ν -1 /α 2 ≪ n ν 1 ≪ ν 2 ν 1 = n -ℓ (1 + o(1)) ν -1 /α 2 = n q -o(1) =⇒    q < 1 ∧ ℓα -1 ν 1 ≈ n -ℓ ν 2 ∝ n -αqIn (a) we have used the fact that, for ν 2 constant or diverging with n, T 0 11 (ν 2 ) is respctively O(1) or infinitesimal, while we have that T 0 11 (ν 2 ) is diverging in both cases. Hence, ν 2 must be infinitesimal, allowing us to use (173).In conclusion, as n → ∞,EQUATIONEQUATIONin particularEQUATIONConsidering the results (176-178), we can write eq. ( 20) asEQUATIONOne could notice, using the integral approximation of the Riemann sum T 0 22 (ν 2 ) given in ( 173), that 1 -Υ(ν 1 , ν 2 ) = O(1) for any choice of ℓ and q. Hence, the variance term given by ( 23) decays with n with rateγ V (ℓ, q) = 1 - ℓ α ∧ q ∧ 1 .Using again (176-178), we can compute the rate of χ(ν 2 ) defined in eq. ( 21), as n → ∞:χ(ν 2 ) = T 0 12 (ν 2 ) p -T 0 22 (ν 2 )) = n -q O ν -1-1 /α 2 1 + n -q O ν -1 /α 2 = n -q O ν -1-1 /α 2Using the integral approximation given in (173), one could verify that p -T 0 22 (ν 2 ) = O(p) for any choice of ℓ and q. The deterministic equivalent for the bias term, given in eq. ( 22), can be written asEQUATIONwhere we have used (175) to compute the scalings of the terms T 1 δγ and the fact that 1-Υ(ν 1 , ν 2 ) = O(1).From eq. ( 183), and using the result (177), it is straightforward to see that the decay rate of the bias term is given byEQUATION)Examples of the results of Theorem 4.1 and Corollary 4.2 are shown in Fig. 3 and 9 . Excess Risk = 3.0, r = 0.4, = * = 0.88 q = 0.55 q = 0.45 q = q* = 0.294 q = 0.25 n 2 rq (bias) n 2 * r (optimal) n 1 + q (variance) 10 2 10 3 10 4 10 5 n = 3.0, r = 0.4, q = q* = 0.294 = * = 0.88 = 1.5 = 2.5 least squares n 2 * r (optimal)Figure 9 : Excess risk eq. ( 6) of random features ridge regression as a function of the number of samples n under source and capacity conditions eq. ( 37) and power-law assumptions λ = n -(ℓ-1) , p = n q , with noise variance σ 2 ε = 1, obtained from the deterministic equivalent Theorem 3.3. Dashed and dotted lines are the analytical rates from Theorem 4.1, stated in the legend. The colour scheme is the following: variance dominated region: orange and brown for the slow decay regime; cyan for the bias dominated region; shades of green for the optimal decay (red lines in Fig. 2 (right). In particular we show: (left) the crossover between the orange and teal regions in Fig. 2 at fixed regularization and r < 1 /2; (right) the optimal decay rate along the horizontal red line line in Fig. 2 at q = q * and r < 1 /2, for any λ ≤ λ * , included the non regularized case.In order to extend the results of Theorem 4.1 and Corollary 4.2 to the excess risk defined in (6), in this section we compute the intervals for ℓ and q such that the assumptions of Theorem 3.3 hold and the approximation rates E(n, p) are vanishing, under source and capacity conditions. Given n, p = n q , λ -(ℓ-1) and ν 2 as in (177) assumption 3.2 is verified for m = n q+ℓ and C * = O(ν -12 ). In factEQUATIONand the inequality in ( 16) holds ifEQUATIONThe inequalities in (17) can be written asEQUATIONEQUATION)Then, introducing η * ∈ (0, 1 /2), we can compute the following quantities of interest (introduced in eqs. ( 25) to ( 27)):EQUATIONEQUATIONEQUATIONSimilarly, considering ν 1 scaling as in eq. ( 176), we have that eq. ( 31)EQUATIONEQUATIONEQUATIONFixing K > 0 and considering the , we consider condition (28):EQUATIONEQUATIONEQUATIONand, similarly, condition (29EQUATIONwhile, for q < 1, if EQUATION1 + α 1 + α α Source r 1 /2(1 -1 /(α+1)) 1 /2(1 -1 /(α+1)) r Target decay (in L 2 ) αr + 1 /2 1 /2(1 + α) 1 /2(1 + α) αr + 1 /2Table 1 : Dictionary of notation between the source and capacity conditions defined in eq. ( 38) and the scalings in different neural scaling laws works. Note that since Bahri et al. [2024] , Maloney et al.[2022] also employ the greek letter "α", we denote theirs by α to avoid confusion.where the last step is a consequence ofEQUATIONEQUATIONFinally, the approximation rate defined in remark 4.1 isEQUATIONwhere the second term vanishes under the conditions in ( 203) and ( 206), and the first term vanishes by further assuming, for q ≥ 1 ℓ < α + 1 12 .(211)In this appendix we discuss the relationship between our results and the recent literature of the theory of neural scaling laws with linear models. We adopt a notation close to ours, with dictionary to their notation given in Table 1 and Table 2 . Bahri et al. [2024] and Maloney et al. [2022] have considered a model where with Gaussian input data and linear target function:EQUATIONThe covariance matrix Λ = diag(λ k ) k∈[d] is taken to be diagonal, with eigenvalues following a power-law scaling:EQUATIONwith α > 1 and the target weights are assumed to be random Gaussian vectors β ⋆ ∼ N (0, 1 /dI d ).In particular, note that TrΛ ∼ d for d → ∞. Given the training data, they consider least-squares regression in the class of linear random features predictor:EQUATIONwhere W ∈ R p×d is a Gaussian random matrix elements in N (0, 1 /dI d ). 2 : Dictionary of notation between the source and capacity conditions defined in eq. ( 38) and the scalings in different neural scaling laws works. Note that since Paquette et al. [2024] also employs the greek letter "α", we denote theirs by α to avoid confusion.This setting is a particular case of the one introduced in Section 2. In particular, it satisfies particular source and capacity conditions eq. ( 38). To see this, note that the feature population covariance is identical to the input data covariance:EQUATION215) Therefore, we can identify Σ = 1 /dΛ which has TrΣ < ∞ for α > 1 in the limit d → ∞. Therefore, the features satisfy a capacity condition with scaling α. Moreover, the asymptotic kernel is simply the linear kernel:EQUATION)Since the target variance is constant, this is equivalent to a source condition with:EQUATIONSince α ∈ (1, ∞), we are always in the hard regime r ∈ (0, 1 /2) where the target does not belong to the RKHS H = R d . Indeed, since β ⋆ ∼ N (0, 1 /dI d ), we have:EQUATIONwhich indeed diverges as d → ∞. Moreover, note that least-squares regression correspond to the case ℓ = ∞.From the discussion above, the bias term scalings from Bahri et al. [2024] (resolution limited regime) and Maloney et al. [2022] (underparametrized regime n ≫ p, i.e. q ≪ 1, and overparametrized regime n ≪ p, i.e. q ≫ 1), correspond to a vertical cross-section on the large ℓ region of Fig. 2 (Right). Indeed, we recover exactly the rate of the label term in eqs. ( 167)-( 168) of Maloney et al. [2022] :EQUATIONEQUATIONSimilarly, it is possible to recover the rates for the noise term (first two results in eq. ( 86) of Maloney et al. [2022] ) as the vertical cross-section on the large ℓ region of Figure 2 for the rates of the variance term. In particular:EQUATION)Comparison with the SGD rates from Paquette et al. [2024] , Lin et al. [2024] -Furthermore, in the linear noiseless target setting, lifting the condition in eq. ( 217), it is possible to compare our results to the compute-optimal rates for the risk obtained through stochastic gradient descent in Paquette et al. [2024] . In particular, we consider unitary batch-size and the correspondence between the number of iterations of stochastic gradient descent and the number of samples n in ridge regression. Then, defining γ the decay rate of the compute-optimal curves for the risk R ≍ n -γ in Paquette et al. [2024] , corresponding to the compute-optimal number of features p ≍ p =: n q ,6 • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Note that we can consider both ψ and ϕ random elements of the Hilbert space ℓ2 with distribution induced by x ∼ µx and w ∼ µw, where E[ψψ T ] = E[ϕϕ T ] = Σ and Tr(Σ) < ∞.Under this last condition, if K ≥ α -1 + 1 /16, both inequalities (199) and (200) are satisfied.In[Maloney et al., 2022], β ⋆ has variance σw /d, the spectrum has a scale λand the random projection W has variance σu /d. Here we take σw = λ-= σu = 1 since it is irrelevant to the discussion.Note that this quantity is denoted d⋆ inPaquette et al. [2024].The Phases Ib, Ic and IV correspond to α < 1, i.e. to an activation σ / ∈ L2.The stepsize inLin et al. [2024] is denoted by the greek letter γ, which we changed to η to avoid confusion with the symbol we use for the risk decay rate. 


Decision: The paper investigates the generalization performance of random feature-based ridge regression by providing a deterministic equivalent for the test error. The key contribution is that this approximation result is non-asymptotic, multiplicative, and independent of the feature map dimension allowing for infinite-dimensional features. As an application, this result is employed in random feature-based kernel ridge regression to provide a tight bound on the smallest number of random features needed to achieve the optimal minimax error rate, thereby improving the result in the literature. The paper is well-written and the contribution is solid. All the reviewers are positive about the paper's novelty and contributions, which I agree with. Based on the discussion with the reviewers, I think the paper is a nice contribution to the literature and therefore I am recommending acceptance. I strongly urge the authors to incorporate all the reviewer comments along with any clarifications they provided in the rebuttal into the camera-ready version.

Reviews: review: paper_summary: paper_summary: The paper studied the non-asymptotic generalization error for random feature ridge regression (RFRR) models. By considering the eigendecomposition of random features with respect to data distribution and weight distribution, the authors proved a feature-dimension-free deterministic equivalence for the generalization error of RFRR, where the sample size and number of features bound the approximation error. From this deterministic equivalence, fixing the number of data points, this paper presented the minimal number of features for the optimal decay rate of the excess risk of RFRR when considering power law assumptions for data covariance and target. This analysis provides a clear picture of the generalization error scaling law for source and capacity conditions of RFRR.
strength_weakness: strength_weakness: 1. One concern is how we can check Assumptions 3.1 and 3.2 for specific nonlinear feature models with some concrete data and weight distributions. The results of this paper rely on the eigen decomposition in (11) but can we get some specific examples of eigenvectors $\psi_k$ and $\phi_k$? For instance, in a classical high-dim statistics setting, if we consider a nonlinear RFRR model with i.i.d. sub-Gaussian dataset and weight matrix and a certain nonlinear teacher model, can we justify Assumptions 3.1 and 3.2 in this case?

2. There should be more clarification for the notations and conditions of the main results, Theorem 3.3. For instance, what would be the meaning of (25-27) and (28-29)? Are these bounds and approximation rates necessary or due to some technical reasons? If we apply the bounds in (28-29) to (32) for the error bound of the deterministic equivalence, the bound of $\mathcal{E}(n,p)$ seems to be loose and cannot get $\tilde O(n^{-1/2}+p^{-1/2})$.
questions: questions: 1.  In the simulation, the authors provide an empirical diagonalization method for estimating $\Sigma$ and $\beta$ by considering $N=P\gg n,p$ and computing the eigendecomposition of the empirical feature covariance. Is there any theoretical guarantee for this approximation? This approximation seems to indicate that we can still apply the asymptotic results for empirical feature covariance under the proportional or polynomial scaling regime for $n, p$, e.g. [Mei and Montanari, 2022, Gerace et al., 2021, Dhifallah and Lu, 2020, Hu and Lu, 2023, Hu et al., 2024], to analyze the deterministic equivalence and the generalization errors. 

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

3. Typo (7): $h_*\to f_*$

4. What is $\nu_2$ in (17) in Assumption 3.2? You did not introduce this notation until Definition 1.

5. You did not introduce intrinsic dimension around (25).

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

7. Line 183, typo: spam; Line 230: (37) $\to$ (38)?

8. In Definition 3, typo in the definition $r_\Gamma(k)$: $p \to q$. Line 546, $\Sigma\to \Gamma$.

9. In Theorem A.2, what is the typical order of $\rho_\lambda (n)$? From (53), we cannot claim the error term in (54) will be vanishing.

10. How do you prove the last equation on page 16, for the upper bound the $||S_i||_{op}$? Can you explain it? And in the same proof, how do you apply the matrix Bernstein inequality for infinite dimension $\tilde S$?

11. Below Line 587, typo in $f_j$: $j\ge 1\to k\ge 1$; typo in (60): $A\to B$.

12. In Line 634, you consider $\eta_*\in (0,1/4)$ but in the main results, you have $\eta_*\in (0,1/2)$. Can you clarify it?

13. How do you prove $||\hat \Sigma_F||_{op}\ge 1/2$?

14. Below Line 800 and in Line 1033, you use $G$ to denote the resolvent which has been used as the data feature matrix as well.
limitations: limitations: N/A
paper_summary: paper_summary: Prior work on random feature (ridge) regression study the test error in the high-dimensional asymptotic. However, ideally one would hope for a non-asymptotic deterministic characterization of the test error.   In this paper, the authors tackle this problem and show that under a concentration assumption,  the test error is well approximated by a closed-form expression that only depends on the feature map eigenvalues. They use this result to study various problem in random features regression.
strength_weakness: strength_weakness: I suggest the authors expand the discussion around Assumption 3.1 and provide more detailed examples for which this assumption holds.
questions: questions: The paper is very well written and I have no particular question.
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_summary: EDIT: updated my score after rebuttal. 

The authors investigate the excess risk in random feature ridge regression. They give a deterministic expression that approximates the excess risk, with a controlled relative error. The dependence of the deterministic "equivalent" w.r.t. to key quantities in the problem is examined.
strength_weakness: strength_weakness: ## General comments
My main concern is the format of the paper, which I think is more suited to a mathematical-minded ML/stats journal than a conference. The main paper is very dense but misses key details such as proofs or proof outlines, while the full proof of the main result is 28 pages long, which makes the full paper 50 pages long (i.e., appendices included). It is not reasonable to expect reviewers to go through such a long technical proof in the context (short time span and heavy workload) of NeurIPS reviews. As a journal submission, I would have the time required to go through the proofs and get to the heart of the proposed (interesting) result. 

## Major
1. Eqn 4: don't you want $\epsilon$ to be zero-mean as well?
2. p3 L104; "we define wlog $\mathcal{V} = Im(T)$": if this is indeed a definition, I don't see why we need to add "wlog". If this is a statement about the image of $T$ being the whole of $\mathcal{V}$, we need to define $\mathcal{V}$ beforehand.
3. Eqn 13 is only true in $L^2(\mu_x)$ so I would avoid involving $\mathbf{x}$ in the statement of the equation, which suggests you mean a pointwise equality and requires a quantifier. If you actually meant a pointwise equality, then this should be explained, and further assumptions should likely be made on $\varphi$.
4. Assumption 3.1. I am unsure what is meant by an infinite matrix $A$. Especially when one needs to talk about the trace of $\Sigma A$, so that I assume we want to guarantee that $\Sigma A$ is a trace-class operator. Can you rephrase the assumption in terms of operators? 
Similarly, the Frobenius norm for operators should be defined. 
5. p4 L117: can you give more details on why cases 1) and 2) are covered by your assumption? Same for p4 L128: can you detail why these power decays satisfy Assumption 3.2?
6. Definition 1: For easier reading, I would define $\nu_1, \nu_2$ first, then $\Upsilon$, and then only $B$ and $R$. Otherwise, the reader has to wait until Eqn (24) to understand Eqn (18), which requires a lot of buffer memory from the reader's brain.
7. p5 L156 is there an implicit dependence on the feature map dimension? Can you explain where? 
8. Figure 1: I would keep the caption short and descriptive, and move the definition of the data generating process to the main text. This would allow to explain more, for instance, what you mean by $v$ has a fixed overlap with the teacher vector".
9. The bibliography needs to be harmonized. There are many missing journal/conference names (if it's an arxiv preprint, say so and give the arxiv number), and a few initials mixed with full first names.
10. p9 A short discussion section summarizing the main points and limitations of the paper would be a good addition.  

## Minor
* p1 L23: here and in the rest of the paper, you use the notation $\mu_w(\mathcal{W})$ to indicate that $\mu_w$ is a probability measure on $\mathcal{W}$. I would say that is not standard notation, and I would rather keep $\mu_w(\mathcal{W})$ for the measure of the whole space $\mathcal{W}$, i.e. 1. 
* p1 L25: I think $\sigma$ has not been defined yet.
* p2 L46 "demystifying phenomena such as double descent and benign overfitting". I would give a reference for each concept.
* p2 L55 no need to boldface "our main contributions".
* Eqn 9: I would write $\mathrm{Var}$ instead of $\mathrm{Cov}$.
* p4 L127: settings
* p4 L135: what is a "self-consistent" equation?
* p5 L142 "we use $a_i = '*'$ to denote [...]": I don't understand the exact meaning of this statement.
* Eqn 30: I would remind the reader that $R_{n,p}$ has been defined in Definition 1.
* p5 L151 "in place" reads strangely. "In order", maybe?
* p5 L152 what does "fully" mean in "fully non-asymptotic"?
* p6 L171 what do you mean by "single-index"?
* p6 L183 span, not spam!
* p6 L183 infinite-dimensional
* p7 L216 understanding
* p8 L255 decays
* Figure 3 is too small to read.
questions: questions: * Item 4 in my major comments.
limitations: limitations: This is fundamental work and does not have any immediate potentially harmful impact.
paper_summary: paper_summary: This paper provides a non-asymptotic bound (Theorem 3.3) on the test error of random feature ridge regression (RFRR) using dimension-free (in the sense of the feature space) deterministic equivalents, which are the solutions to some self-consistent equations, under a concentration assumption (Assumption 3.1) on the features. As a result, they recover (Corollary 3.5) the deterministic equivalents result on the test error of kernel ridge regression (KRR) from previous literature, and they prove the exact decay rate of the neural scaling law (Corollary 4.1), filling the gap from previous literature.
strength_weakness: strength_weakness: My main concern, however, is the significance of the theoretical contribution of this paper. From the first sight, this paper is merely an extension of the paper [Misiakiewicz2024] with same techniques of deterministic equivalents. 

Also, the result holds only under the strong concentration Assumption 3.1. As mentioned in the paper (line 119-121), I think that this paper could have been more significant if Assumption 3.1 had been relaxed in this paper.
questions: questions: Regarding the above comments, 

1. Could the authors explain more how different it is to implement the deterministic equivalents techniques in RFRR than in KRR?

2. How difficult it would be to relax Assumption 3.1 as in [Misiakiewicz2024]? And what datasets and random feature model could satisfy Assumption 3.1 empirically?

3. Despite not essential, but it could help the readers a lot if the authors could explain more on the quantities and their intuitions in the paper, like Eq (21-27). From my point of view, Theorem 3.3 is not the easiest to read.

Besides the questions, I found some potential typos in the appendix:

- A paragraph (line 536 - 540) seems misplaced: they should be directly after Eq (50). 

- The equation below line 587 should be $\mathbf{f}\_j = ((\xi\_k\phi\_k(\mathbf{w}\_j)))\_{j\geq1}$ instead of $\mathbf{f}\_j = ((\xi\_k\psi\_k(\mathbf{w}\_j)))\_{j\geq1}$. 

- a ``\rangle`` is missing in the equation under line 590: it should be $\sigma(\langle \mathbf{w}\_p,\mathbf{x}\_i \rangle)$ instead of  $\sigma(\langle \mathbf{w}\_p,\mathbf{x}\_i )$.
limitations: limitations: This paper is theoretical paper and the authors have addressed the assumptions and conditions explicitly in the paper.

Comments: title: Official Comment by Reviewer b7dx
comment: Many thanks for the authors' response and explanations. The rebuttal has resolved most of my questions. I tend to accept this paper and expect the authors to include more discussions in the revision, especially for Assumption 3.1 and Remark 4.1.
Thanks for the clarifications! I am still in two minds: one the one hand, I agree that the 9-pager already conveys an interesting technical contribution, with clarity, provided the authors implement the minor changes recommended by the reviewers. On the other hand, I would have preferred having had the time to proofread the proof carefully, in a journal submission like JMLR. But, after having read the other reviews, and anticipating over the reviewer discussion period, I am willing to increase my score and not argue for rejection.
Thank you for your detailed answer. I acknowledge the contribution of this paper that it unifies asymptotic prediction using deterministic equivalents despite restrictive assumptions. I will therefore keep my score unchanged and tend to accept this paper in the conference, under the condition that the authors include the above discussion in the revised version of the paper.