Orthogonal Random Features: Explicit Forms and Sharp Inequalities
Authors: Nizar Demni
Hachem Kadri
Venue: Accepted by TMLR ()

Abstract: Random features have been introduced to scale up kernel methods via randomization techniques. In particular, random Fourier features and orthogonal random features were used to approximate the popular Gaussian kernel. Random Fourier features are built in this case using a random Gaussian matrix. In this work, we analyze the bias and the variance of the kernel approximation based on orthogonal random features which makes use of Haar orthogonal matrices. We provide explicit expressions for these quantities using normalized Bessel functions, showing that orthogonal random features does not approximate the Gaussian kernel but a Bessel kernel. We also derive sharp exponential bounds supporting the view that orthogonal random features are less dispersed than random Fourier features.

Published in Transactions on Machine Learning Research (09/2024)
Orthogonal Random Features: Explicit Forms and Sharp In- equalities
Nizar Demni
niaor. niaar. diaarddmmntuuniu-mm..
Deportment of Mathematics Aix- Marseille Universily, CNRS, LIS Marseille, Fronce
Hachem Kadri
Bacheem.kdrr@@uriiiine
Department of Computer Science
Aiz- Marseille University, CNRS, LIS Marseille, France
Reviewed on OpenReview: oppnneeveee. net/ formm ? id= FNtRZ402S
Abstract
Random features have been introduced to scale up kernel methods via randomization tech- niques. In particular, random Fourier features and orthogonal random features were used lo approxinate the popular Gaussian kernel. Random Fourier fealures are built in this case using a random Gaussian matrix. In this work, we analyze the bias and the variance of the kernel approximation based on orthogonal random features which makes use of Haar orthogonal matrices. We provide explicit expressions for these quantities using normalized Bessel functions, showing that orthogonal random features does not approximate the Gaus- sian kernel but a Bessel kernel. We also derive sharp exponential bounds supporting the view that orthogonal random features are less dispersed than random Fourier features.
1 Introduction
Since their introduction over fifteen years ago in the seminal paper by Rahimi & Recht 2007), random Teatures have become an important subject of research in the field of machine learning (see the review article by Liu al., 20021). The primary motivation behind introducing them is to reduce the computation and storage requirements of kernel methods one of the most popular machine loarning approaches (Schōökooff
& Smola 2002 [Shawe-Tayal
& Cristianini] 2004 Yang et al.] 2012 Le al.] 2013 Pennington et al, Likhosherstov et al. 2022 They have also been used in peer-parameterized settings and as a tool for generating and testing hypotheses on the generalization of deep
2015 Chamakh et al. 2020 Han et al.
2022
learning (Jacot et al. 2018 Belkin et al.
2019 Yehudai & Shamir 2019 Jacot et al. 2020 Liu et al.) 2022
Mei Montanari 2022). Another recent research focus has involved the study of the Gaussian equivalence
phenomenon in the context of random fcature models in order to characterize the generalization error
the asymptotic regime. (Gerace et al. 2020 Goldt et al. 2022 Hu & Lu 2022 Montanari & Saeed 2022
Schröder et al. 2023 Dandi al. 2024).
Random Fourier fcatures (RFF) are undoubtedly the most common and widely used random feature method
for kernel approximation (Rahimi& & Recht, 2007]. This approach applies lo radial basis function kernels a large class kernel functions. is based on Bochner's theorem (Bochner 1932 Rudin 1962), which estab- lishes a onc-to-one correspondence between continuous positivo-definite functions and the Fourier transform of probability measures. In particular, y a real positive definite function on I, i.c. the inequality Σij=1 030)f((;; æz)) holds for any 2 1 and æ1, Tny Ch.... On R, and if k(x, v) = se[| vll)

---

Published in Transactions on Machine Learning Research (09/2024)
is translation-invarian and radial kernel on Rd x R then there exists a non-negative measure μ such that
/ Rd
k(z, y) = +(12= yll
exp(iw" -y))dd(())
(1)
where T stands for the transpose operation, and l is invariant under orthogonal transformations. consist in approximating the kernel by the following one defined by:
RFF
k(z,8) == (((x))(())))) V.
(2)
where
Ō(x) = vp
(sin(w: ..,...., si).r.,,inn(,,
J 2) cos(w] a)..... cos(w;]x)) =
(3)
and Wi...., wp E Rd are sampled from the distribution μ. Indeed, one has
2 Σ cos(w] (x y)),, p
T(v)
so that the expected value of k(z, y) fits exactly the integral displayed in the RHS of equation The imaginary part of the integral in equation [ vanishes because the kernel function radial. In particular, if Wlp...,pp are centered Gaussian vectors (0,, then RFF approximate the well-known Gaussian kernel:
E E [K(x, v)1 = -1=
(4)
Orthogonal random features (ORF is a variant of RFF that uses a random orthogonal matrix O instead of the Gaussian matrix W. RFF are built out of i.idd. random Gaussian matrices. Assuming i.id. feature transformation samples may be too restrictive and may neglect structural information in the data. ORF might be more effective model since takes into accounts the correlations between samples. The feature transformation samples in ORF are no longer independent. as they drawn from the Haar measure the orthogonal group. ORF was first proposed by Yu et al. (2016), with the goal of approximating the Gaussian kernel. They showed that imposing orthogonality on the randomly generated transformation matrix can reduce the kernel approximation error of RFF when a Gaussian kernel is used. This has led to a number of studies investigating the effectiveness of random orthogonal embeddings and showing empirically and theoretically that ORF estimators achieve more accurate kernel approximation and better prediction accuracy than standard mechanisms based on i.idd sampling (Choromanski et al.) 2017 2018 2019). The superiority of orthogonal against random Gaussian projections in learning with random features has also been observed in Gerace et al. (2020).
In this paper, we build on this line of research and provide an analytic characterization of the bias and of the variance of ORF using normalized Bessel functions of the first kind. These special functions appear naturally in harmonic analysis on Euclidean spheres since they are Fourier transforms of uniform measures on these spaces (Watson 1995). Specifically, we make the following contributions:
We give explicit forms of the bias and of the variance of ORF in the case where the random orthogonal
matrix O is drawn from the Haar measure. In particular, we show that the bias of ORF is given by a Bessel kernel instead of a Gaussian one.
We derive sharp exponential bounds for these two quantities that are much lighter than the already known ones.
We prove that the variance of ORF is less than the one of RFF in an interval whose length grows linearly with the data dimension.
'The model we consider here is the denoted ORF in Yu al. 2016 Section 4, and instance of Definition 2.2. in Choromanski al. (2018) corresponding to one block features.
2

---

and Published in Transactions on Machine Learning Research (09/2024)
We corroborate theoretical findings with numerical experiments, supporting previous works showing the beneficial effect of orthogonality on random features.
The rest of the paper is organized follows. Section lays out notations needed for the statement of our main results, the latter being subsequently presented in Section 3 Numerical validation of them is provided in Scction while Section concludes the paper. Proofs all results are deferred to appendices.
2 Notation and preliminaries
Let p.d, be positive integers such that 2 S Σ and take a Haar x orthogonal matrix O. For the reader's convenience, recall that the Haar measure on the orthogonal group the unique left and right invariant measure and that a Haar orthogonal matrix may be obtained using the Gram-Schmidt procedure applied Gaussian matrix G. In particular, the columns (and rows) of O are uniformly distributed on the sphere (for further details see Meckes 2019 Chapter 1). It is worth noting that the value p= =11 is excluded since trivial. Tf p d, then the ORF feature map, introduced in Choromanski et al. (2018) is built out of independent blocks of vectors sampled from independent Haar orthogonal matrices. By linearity and statistical independence, the compulations of the bias and of the variance of the ORP estimator follows in this case from summing those we will compute below.
We denote by ΦoRF the random features of ORF computed using equation with wi,...,, wpp being columns of O. We also use the notation ORFF for the random features of RFF when W1,-.., Wp are columns of Gaussian matrix G (i.e., a random matrix whose entries independent and centered Gaussian random variables). The approximate kernels obtained using ORF and RFF will be denoted by kons y) and KRFF(E; v), respectively (i.e., foRP(x, y) == ΦORF(r) "oRR (y) and kRFF(I, y) == ÓRFF " (RFF(y)). In order to simplify the exposition and without loss of generality, we will assume throughout this paper that the bandwidth of the Gaussian kernel a is equal to In this respect and for sake of completeness, let us recall the expressions of the bias and the variance of RFF.
Theorem (Bias and variance of KRFF kRFF(x,y)) (x. Let kRFF(I, y) be the RFF- approrimate kernel com- puled with p random vectors in Rdd Then its expectation and ils variance given by
(l = exp (- | y11?
(5)
2
(1)r 1 2p (1 (1- --exp(
| u11
(6)
2
respectively.
Proof. See Yu et al. (2016 Lemma 1).
It worth noting that the equality equation 5 remains valid if one replaces the Gaussian matrix by the product SO, where O is a Haar orthogonal matrix and S is a diagonal matrix whose entries are independent and Xe-distributed random variables with d degrees of freedom (Yu et all 2016 Theorem 1). However, it fails when w....., Up are columns of O. We will see in the next section how the bias and the variance change and behave in this case.
3
Main results
In this section, we state the main results of this paper and comment on our findings. We start with an explicit expression of the bias of
kernel approximation.
Theorem (Bias of kx y)). Let koRF(I, (x, be the ORF-based approzimate kernel computed with p random vectors in dRd, Then ils expectation reads:
Elkonr (2. v) ja/2-1(2), =: | vll
(7)
3

---

Published in Transactions on Machine Learning Research (09/2024)
where 12)2-1(+) is the normalized Bessel function of the first kind defined by:
ja/2-1(z) Σ (dd) (2) (2)2) 2n
(8)
nn (d/2) 2
R20
with T()) being the Gamma function.
Sktcch of proof. The proof of Theorem 2 is routine calculation in Euclidean harmonic analysis. Loosely speaking, it relies the invariance under rotations of the uniform (Haar) measure the unit sphere gd-1 which allows to reduce the expectation [[KORF(T, y)] to the one-dimensional Fourier transform of the symmetric Beta distribution whose density is proportional to
(1 (1-w u- u [-1,]
The detailed proof is available in Appendix A
Theorem shows that ORF approximate the kernel defined by the normalized Bessel function of the first kind Watson 1995 Shishkina & Sitnik 2020, Chapter 1). This function is oscillating in contrast to the so-called Matern kernel given by the modified Bessel function of the second kind (see Equation 12 in Genton 2001]. Morcover, the absolute value of the former admits a polynomial decay to zero as its argument becomes
large while the latter decays exponentially.
To address the question of how the bias of ORF behaves compared that of RFF, we use Theorem 2 prove the following result.
Proposition 3. For all x, Z.yE Ed, let || ---yl yll and define
by = 21/4 2/4
d2 2,
2v20/22 d'
d ( -1)
1/2
8
ca =
d d25. 5.
d2
2d
4
Then for all z E [0, max (ba, ea)), we have
E S -=2
(9)
where we convent that max(ba, ca) ba when < d I 4. The upper bound is valid up the second zero of 14/2-1-
Sketch of proof. The series expansion equation is clearly sign alternating and does not help in proving inequalities for Bessel functions of the first kind by killing oscillations. For that reason, appeal to the Weierstrass infinite product of j(d-2)/2 and make use of estimates of its smallest positive zero. Though the Bessel function j(a-2)/2 admits infinitely many simple zeros, the estimates on the smallest one are sufficient enough for our purposes. The detailed proof is provided in Appendix
For fixed d 2 5, the constants by and ca are the values of the increasing function
4
d d+4
Sa uuru+ uN
2n² d'
18 and equation 19 below. Moreover, ca > by for sufficiently large (d > 35) and offers therefore a linear growth of the interval [0, cal compared d3/4 for [0, by]. As a matter of fact, the incqualitics displayed in equation hold true for a large range of provided that d is large as well. As we shall see later from the proof of proposition equation 3 the lower bound even holds true in larger interval which almost reaches the first zero of j(d/2)-1 d becomes large.
at two lower bounds of the first. zero of j(d/2)-1; see eqs. equation
4

---

Published in Transactions on Machine Learning Research (09/2024)
On the other hand, the Bessel function J(4/2)-1 takes negative values after vanishing at its first zero that our lower bound is quite sharp.
As to the upper bound, it clearly remains valid up to the second zero of j(d/2)-1 since the latter is non positive between its first and its second zeroes. Note also that the lower and the upper bounds correspond to Gaussian kernels with standard deviations equal to one and vd respectively.
On the other hand, we may equivalently write
0 f ([ - B[KRFF((,, MM S 1e-2) 12 Va [0, max(ba,
(10)
which considerably improves Theorem 2 in Yu et al. (016)) Indeed, our upper bound decays exponentially fast while the one given in Yu et al. (2016) admits an exponential growth. This growth is due to the fact that the triangular inequality used in the proof there kills the oscillations of the normalized Bessel
function 14/2-1 and leads to the normalized modified Bessel function of the first kind which is known grow exponentially (Watson 1995).
It is also worth mentioning that for large enough d, the differences between B[koRF(z,, y)] and the exponential bounds displayed in equation 9 become very small for large z (= >>> d) since [(d/2)-1 has a polynomial decay to zero.
We now state our second main result providing an explicit closed expression of the variance of ORF by means of normalized Bessel functions of the first kind.
Theorem 4 (Variance of KORF y)). Let (2, v) be the ORF-based approzimate kernel built out of random vectors in Rdd, Then its variance is given by:
Vihonr(E, v)] ( 1(222)-1 (p 1)(2) ((0
(11)
2
where we recall the nolation z = | - y|1-
Sketch of proof. The derivation of VÍKORE (z, y)] is to the best of our knowledge new. Since koRF (z. y) is the of correlated random variables in opposite to the RFF kernel, one has compute explicitly the covariance terms which perform by exploiting once more the invariance of the uniform measure on Sd-1 which leads to double integral that we evaluate using polar coordinates. The full details of the proof can be found in Appendix C
Remark 5. When = 1, the variance reduces to
1 1 j(a ((2-2)/2(22)) (i(d (i(d-2)/2(2))
V (K(z, y))
2
The non negativity of the RHS follows also from the inequality:
[z(x)) + + [1+ jo( w) + ju(x -y)l
valid for any v >> -1/2 and any x, y E RR. Newman 2004).
Using equation 9 this variance can be bounded as follows for all E [0, maxaaxxaaa ca)]:
1 1 e 2
< --le----t14
p p-l
-2- -
(1
1 2202/
p p-1
1 p-1e-s2/e =0
(12)
2p
2p
p
Similarly to equation 10 the upper bound in equation 12 much sharper than the one Yu al. 2016 Theorem 2). However, does not give information about how the variance of ORF compares that of RFF. The following proposition provides answer to this question.
5

---

Published in Transactions on Machine Learning Research (09/2024)
x10
0.014
3.5
Bios approximation
0.01
Variance asproxmation
0.006
1.5
0.002
10
50
100
150
200
250
300
50
Figure 1: The absolute difference between thcoretical and empírical values of the bias and the variance of ORF for different values of the number of random features p. Left: |emmp- ([ -Vikon/] y)]l- The bias and variance of kour (z, y), E[konr (2, y)] and Víkonr (z), v)l, are computed using the explicil closed expressions provided in Theorems and 1 Memp and Vemp are the empirical bias and variance, respectively. Data points z and y are randomly generated from a normal distribution with zero mean and unit variance. We consider here the case where the value of 2 == |x - yll is not small (z is equal to 24 in this sirulattonn..
Right:
Proposition 6. For d 2 2, denole
3/4
d
ad
Bd = 2 V 4 1.
Then for any x. E Rdd and any z = ||0 yll E [0, max(ad, Ba)], we have
Vikonr(x, - ((
(13)
Sketch of proof. Since our random features are independent, one has focus on the covariance terms. Appealing to the infinite product representation of the spherical Bessel function j(4/2)-1, turns out that these terms are negative. As such, we are led to analyse the variance of single random feature which is proved to be less than the variance of RFF in the indicated interval. The complete proof is given in Appendix
Proposition 6 shows that RORP less dispersed than kRPP when the norm difference between data points lies within interval whose length is linear in the data dimension d when the latter is sufficiently large. This is in agreement with previous results (Choromanski et al. 2017 2018 z-neighborhood of zero.
2019 though holding in small
Another striking feature of this proposition is its independence of the number of random features Actually, its proof relics again on the Weicrstrass infinite product of j(d/2)-1 and shows in particular that the covariance of cossww](e (xr y). cos(w:f (= v)), j, is negative in the interval [0. v max max Ba)] As matter of fact. one is left with bounding from above the variance of single mode cos(w (x y)) by that of the RFF kernel. Even more, proof shows that the inequality equation 13 remains valid only in slightly larger interval where (V22)) is negative.
4 Numerical illustrations
In this section we provide experimental results on synthetic and real data that corroborate our theoretical findings.

---

Published in Transactions on Machine Learning Research (09/2024)
d= p-2
d=10, p-10
exp-t
exp-
0.8
max Gi)
Bise ORF
0.8
maxx (bus cd)
Blss ORF
(2d)
exp-2122
0.6
0.6
0.2
-0.2
10
15
20
25
30
5
10
15
20
25
30
d=50, p=10
d=200, p=10
exp 22/2
exp 22/2
ORF
1/2d)
122d)
max((n 1
max Gr
0
17.2
17.4
17.5
5
15
20
25
30
20
40
60
100
120
Figure 2: The bias of koRF( v) and bounds of Proposition 3 function of == || v/1
d=4, p=2
d=10, p=10
[I. (84)
Var RFF
max((ash 36)
Var RFF
Var OFF
Var OFF
0.04
0.15
0.03
0.1
0.02
0.06
0.01
d-50, p=10
do200,,
0.05
0.05
Ver RFF
Ver RFF
Ver ORF
Ver ORF
0.04
0.04
0.00
0.00
Imax( 3d)
max((aa, (8))
0.02
0.02
0.01
0.01
100
Figure The variance of kone (x, y) and knrr (z, y) as function of = || y/1-

---

Published in Transactions on Machine Learning Research (09/2024)
Table 1: Dataset statistics, d is the dimension of the features.
Datasets d
# data points
lonospher 2
34
351
Ovariancance
100
216
Campaign
62
41,188
Backdoor
196
95,329
4.1 Synthetic data results
We generate synthetic data with dimension d 300 and varying values of the random features p = (10,50 50, 100, 200, 250, 300). The data are randomly generated from normal distribu- tion with zero mean and unit variance, We compute Memp == E k( and Vemp == i (k,())))))))
Memp]?, the empirical bias and variance of KORF respectively, Each kernel & is computed using a random Haar orthogonal matrix O' i.c., (4(x,y) J (sin(w, z),... r)....,sin((() æ), cos(wf 2)....,
di(x) (v()) where Φń(x)) z)) and wi..... w'y are the columns of O The experiment is repeated 10 times with different random seeds. Figure [ shows the approximation errors MMmp - Bl (z. w)] and variance of koRF(x, 3). ElKORF (zz, y)] and V[KORF (z, y),, are computed using the explicit closed expressions provided in Theorems 2 and 4 As can be seen, the mean and variance approximation errors are very small, which are in agreement with our results.
- -ViK-PR w)ll for s 50 and for different values of p. The mean and
Figure 2 shows the bias of FORF(I,)) v) and the bounds of Proposition 3 function of = |æ vll- It illustrates that inequalities in equation g hold for any 2 E [0, max(ba, ca]] Figure 3 depicts the variance of konr and knFF. It confirms that ORF has smaller variance compared to the standard RFF, as claimed in Proposition 6
4.2 Real data results
We also conduct experiments on real-world datasets to confirm our theoretical findings. The number of feature dimension and data samples for each dataset are provided in Table I The accuracy of the ker- nel estimation is calculated by measuring the mean squared error (MSF) between the true kernel matrix and the approximated onc. Figure f compares the MSE of ORF and RFF, i.c., || kTlp//2 where K : [k( æ; ]] is the Bessel or Gaussian kernel matrix and K is its approximation via ORF or RFF, respectively. The Gaussian kernel bandwidth a is set as the average distance between all pairs of data points, i.., a= 11/n ||:,-112: 22112. For the ORF estimator, introducing such bandwidth somehow artifi- cial since the uniform measure on the sphere may be realized as normalized Gaussian vector (so even if we start with Gaussian vector whose standard deviation is σ, this parameter disappears after normalization). The experiment is repeated five times with different random seeds. ORF often achieves lower MSE than RFF. Note that the MSE measures the quadratic variability with respect to the empirical data between the estimator and its theoretical mean (the latter is taken with respect to the random features). In other words, the MSE corresponds to an empirical approximation of the variance. Figure A supports Proposition t since it shows that for the same number of feature p, the approximation error of the kernel function (i.c., empirical variance) in the ORF setting is smaller than the in the RFF setting.
lonosphere data from the UCI machine learning repository: https://archive. 1cs uci edu wwtp://attaeet////ooooopppee
4 4Ovarian cancer data (Conrads et al. 2004): https://fr nathworks www.cctp/ccccecccccccecccco httphhhhppppttt/eeeeeeeehhhsaath sampl a-da-a---aae html
5 CCampaign data is data set of direct bank marketing campaigus phone calls (Pang ct 2019
https://githul.
CuansongPang//DDeppooo Anwaa///aae/oottooooooooaaaaaa-.
"Hakkoor attackk delection data extracted hrmm the UNSW-NH dataset (Moustafa & Slay
2015
https://github.com
GuantsongPang/DDeeppsttoor hnwpritoorr-ooomomm-eeeetteeeeee

---

Published in Transactions on Machine Learning Research (09/2024)
lonosphere
0.08
0.014
RFF
RFF
0.014
MSE
MSE
0.006
0.002
10
15
20
26
30
20
40
60
80
100
0.012
Campeign
0.025
Backdoor
RFF
RFF
0.01
MSE
0.006
MSE
0.005
20 30
40
50
60
50
100
150
Figure 4: Mean squared error (MSF) between the kernel matrix approximated by ORF RFF and the full kernel matrix computed by the Bessel or the Gaussian kernel, for different values of the nunber of random features p.
5 Conclusion
In this paper, provided explicit closed expressions of the bias and of the variance of ORF by means of normalized Bessel functions of the first kind. We also derived exponential bounds that improve previously known ones. In particular, we proved that the variance of ORF is less than the one of RFF when the norm difference between data points lies in an interval of length O(d), d being the data dimension.
Acknowledgments
We thank the reviewers for their helpful comments and suggestions. This work has been funded by the French National Research Agency (ANR) under Grant No. 11R-19-CE23-0011 (project QuantML).
References
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumiik Mandal. Reconciling modern machine-learning practice and the classical bias variance 15854, 2019.
bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849-
Salomon Bochner. Vorlesungen über Fouriersche Integrale. Akademische Verlagsgesellschaft, 1932.
Linda Chamakh, Emmanuel Gobet, and Zoltán Szabó. Orlicz random Fourier features. The Journal of Machine Learning Research, 21(1):5739 5775, 2020.
Krzysztof Choromanski, Mark Rowland, and Adrian Weller. The unreasonable effectiveness of structured random orthogonal embeddings. Advances Neural Information Processing Systems, 30, 2017.
Krzysztof Choromanski, Mark Rowland, Tamás Sarlós, Vikas Sindhwani, Richard Turner, and Adrian Weller. The geometry of random features. In International Conference on Artificial Intelligence and Statistics, pp. 1-9, 2018.
Krzysztof Choromanski, Mark Rowland, Wenyu Chen, and Adrian Weller, Unifying orthogonal monte carlo methods. In International Conference Machine Learning, pp. 1203-124 1212, 2019.

---

Published in Transactions on Machine Learning Research (09/2024)
Thomas P. Conrads, Vincent A. Fusaro, Sally Ross, Don Johann, Vinodh Rajapakse, Ben A. Hitt, Seth M. Steinberg, Elise C. Kohn, David A. Fishman, Gordon Whitely, et al. High-resolution serum proteomic features for ovarian cancer detection. Endocrine-related cancer, 11(2):163 178, 2004.
Yatin Dandi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro, and Lenka Zdcborová. Universality laws for gaussian mixtures in generalized linear models. Advances in Neural Information Processing Systems, 36, 2024.
Pedro Freitas. Bessel quotients and robin eigenvalues. Pacific Journal of Mathematics, 315(1):75-87, 2021.
Marc G. Genton. Classes of kernels for machine learning: statistics perspective. Journal of machine learning research, 2:299-312, 2001.
Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Generalisation сгтor in learning with random features and the hidden manifold model. In International Conference on Machine Learning, pp. 8452-3462. 2020.
Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. The gaussian equivalence of generative models for learning with shallow neural networks. In Mathematical and Scientific Machine Learning, pp. 426-471, 2022.
Izrail Solomonovich Gradshteyn and Iosif Moiscevich Ryzhik. Table of integrals, series, and products. Aca- demic press, 2014.
Insu Han, Amir Zandich, and Haim Avron. Random Gegenbauer features for scalable kernel methods. In International Conference on Machine Learning, pp. 8330 8358, 2022.
Hong Hu and Yue M Ta. Universality laws for high-dimensional learning with random features. IEEE Transactions on Information Theory, 69(3):1932 1964, 2022.
EK Ifantis and PD Siafarikas. Inequalities involving bessel and modified bessel functions. Journal of math- ematical analysis and applications, 147(1):214-277, 1990.
Mourad EH Ismail and Martin E Muldoon. On the variation with respect to a parameter of zeros of bessel and besesl functions. Journal of mathematical analysis and applications, 135(1):187-201 1988.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Implicit regular- ization of random feature models. In International Conference on Machine Learning, pp. 4631-4640, 2020.
Chandra Mohan Joshi and K. Bissu. Inequalities for some special functions. Journal of compulational and applied mathematics, 69(2):251 259, 1996.
Quoe Le, Tamás Sarlós, Alex Smola, et al. aestfood-approxinatin kernel expansions in loglinear time. In International Conference on Machine Learning, pp. 244-252, 2013.
Valerii Likhosherstov, Krzysztof Choromanski, Kumar Avinava Dubey, Frederick Liu, Tamas Sarlos, and Adrian Weller. Chefs' random tables: Non-trigonometric random features. Advances in Neural Information Processing Systems, 35:34559 34573, 2022.
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan Suykens. Random features for kernel approxima- tion: A survey on algorithms, theory, and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10):7128- -748, 2021.
Fanghui Liu, Johan Suykens, and Volkan Cevher. On the double descent of random features models trained with SGD. Advances in Newral Information Processing Systems, 35, 2022.
10

---

Published in Transactions on Machine Learning Research (09/2024)
Elizabeth S. Mockes. The random matriz theory of the classical compact groups, volume 218. Cambridge University Press, 2019.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptolics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-70) 2022.
Andrea Montanari and Basil N Saeed. Universality of empirical risk minimization. In Conference on Learning Theory, pp. 4310 2012,,12,100 2022.
Nour Moustafa and Jill Slay. UNSW-NB15: a comprehensive data set for network intrusion detection systems (unsw-nb15 network data set). 2015 military communicattons and information systems conference (MICII), pp. 1 6, 2015.
Edward Neuman. Inoqualities involving bessel functions of the first kind. J. Ineq. Pure and Appl. Math, 5 (4), 2004.
Guansong Pang, Chunhua Shen, and Anton van den Hengel. Deep anomaly detection with deviation net- works. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 353 362, 2019.
Jeffrey Pennington, Felix X. Yu, and Sanjiv Kumar. Spherical random features for polynomial kernels. Aduances in Newral Information Processing Systems, 28, 2015.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Walter Rudin. Fourier Analysis Groups. Wiley, 1962.
Bernhard Schölkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Dominik Schröder, Hugo Cui, Daniil Dmitriev, and Bruno Loureiro. Deterministic equivalent and error universality of deep random features learning. In International Conference on Machine Learning, pp. 30285-30320, 2023.
John Shawe- Shawe-Taylor and Nello Cristianini. Kernel methods for pattern analysis. Cambridge university press, 2004.
Elina Shishkina and Sergei Sitnik. Trunsmatations, singular and fractional differential equations with appli- cations to mathematical physics. Academic Press, 2020.
George N. Watson. Treatise on the Theory of Bessel Functions. Cambridge University Press, 1995.
Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou. Nyström method vs random Fourier features: A theoretical and empirical comparison. Advances in Neural Information Processing Systems, 25, 2012.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. Advances Newral Information Processing Systems, 32, 2019.
Felix X. Yu, Ananda Theertha Suresh, Krzysztof Choromanski, Daniel Holtmann- and Sanjiv Kumar. Orthogonal random features. Advonces in Neural Information Processing Systems, 29, 2016.
11

---

Published in Transactions on Machine Learning Research (09/2024)
A Proof of Theorem 2
Proof. By lincarity of the expectation and since all the vectors wy S s are uniformly distributed on the sphere, we obviously have:
Elkonr (2, y)] = Elcos(wf (x - y)].
Moreover, we can find an orthogonal matrix Oz. such that
Ox - y) || yllei,
where ei is the first vector of the canonical basis of Rd. Indeed, the columms of the transpose matrix O consists of the normalized vector (x y)/ll yll together with any set of vectors forming orthonormal basis of Rd.
Now, since the uniform measure on the sphere is invariant by orthogonal transformation, we further gel: [[koRF( v)] = [[cos(wf O2., (3 y)]
= Efcos(||zr [l[w]))]
where wn is the first coordinate of w1. This real random variable follows the beta distribution whose density is given by:
T(d/2) (1 (1- u3) -1 -k<u<l V - 1)/2)
Theorem follows from the Poisson integral representation of the normalized Bessel function of the first kind Watson 1995), Ch. II):
T(v I(v+1) 1) j=(z) VTI(I+ + (1/2))
S
cos(zu)(1 (1-)z=))113)00111 11/2.
which may be derived by expanding the cosine function in the right- hand side into power series and integrating termwise.
B Proof of Proposition 3
Proof As briefly sketched right after the statement of Proposition we shall make use of the infinite product representation of The normalized Bessel function j4/2-1 recalled below. To this end, recall from Watson (1995) that this function admits an infinite number of positive simple zeros increasing to infinity:
0 < ad,1 < ad,2 ....
As a matter of fact, one has [Watson 1995
p.498):
z2
j(d/2)-1 (2)
II
(14)
(a
Now, order to prove the upper bound, we further use the so-called first Rayleigh sum WWatson 1995 502):
Σ
(15)
2d
11
Indeed, the inequality 1 u 5 " E [0, 1] holds so that if 5 ad, then
(()))) S En x ( = ((2d)
(16)
yielding the upper bound. Note that the latter remains true in the interval [ad,1, 2222] since the Bessel function non positive there.
12

---

Published in Transactions on Machine Learning Research (09/2024)
As to the derivation of the lower bound, it is more technical and relies fine properties of Bessel functions. Firstly, We differentiate the function
ha 2 e ((a/2))1(2))) 0 S 2 ad.1
and note using straightforward computations that
(=)) -()/2))))))
It follows that:
ex (2)811/0)-12)) (a j(d/2)(z)
Ra(2)=
5(4/2) (2)
Secondly, we appeal to the Mittag-Lefler expansion [Tantis & Siafarikas
1990
eq- 2.9):
)(2/2)(2)
1
2d
1(d/2)-1(z)
d,m
to infer that the equation R[(=) 0,0 < < dd,,, is equivalent to
m=1 amm 22 = 1/2.
But the LHS of the last equality is obviously increasing in the z-variable and tends to to0 ad,1 As result, the first Rayleigh sum equation 15 (giving the value of the above series at =) implies the existence of one and only one solution (d( to the equation h'((2) = 0 in (0, 00,0).). Therefore,
ha(z) 1
22 < 1(d)))-1()),
for any [0, [d)]
It then remains to seek more precise estimate of the real number (d). To this end, we appeal to the following incquality which readily follows from Thcorem 2.1 in Freitas 2021
d
Σ
+
2
22
4a d.1
d,m
see that
1
d
<
2 021
[=)
4a
Equivalently,
4
2o(d)= 2
ad,1
fa(aa,1).
(17)
2a
The sought estimate follows then from the lower bounds below:
Ismail & Muldoon 1988 eq. 5.4):
d
1/4
0d,1
22d
2 2/1
d > 2,
(18)
2
and WWtssnn 1995 eq. 5, p. 486)
d22
0d,1 V
-1, d2 2.
(19)
Actually, fa is increasing for fixed so that
=o(d) > max (121/48/44 = bar
-1) cd
dd
[
which completes the proof.
13

---

Published in Transactions on Machine Learning Research (09/2024)
Remark 7. If we use the following inequality (Joshi & Bissu 1996.
eq. 2.6):
x² S (())))-
2d
we can prove that the lower bound holds the interval [0, vd..
C Proof of Theorem 4
Proof Let us consider the variance of K ((x,))
V (konr(z..)) V p²
1
Σ cos(wf (x y))
[cos( (x - y)}] + pp-1 cov [cos(wf (x y)), coss(w3(( (x y)}]
Now, the lincarization formula for the cosine function
c cos(20)
entails
V [cos(u]] (x y)}} = B Blcos "wo?
T (x:
y))]
[E[cos( ue (xr w))l]
(122)
(()))))=1=)))
2
As to the covariance term, the invariance of the Haar distribution (keep in mind the orthogonal matrix Oz.y) logether with the product formula
cas(a) cb) [cos(a + b) + cos(a b)]
yield:
cov [cos(w] (x v)), cosccoosss (x -))] Efcos(wi (a v) cos((w3 y))l (Jaa-2)/2(2)
Elcos(w111)) c0s(=)==ss2 (f(=22)/(2))²
= 2 [E(cos((wn + w12) Elcos( (wn w12)=)]}
(2))
where and W12 are the first coordinates of the column vectors and w2. But (W11, W12) is the first row of the Haar orthogonal matrix which is uniformly distributed on 5d-1, Consequently, the joint distribution of (Wi1, w12) given by the following probability density:
d d 2-2(1- (1 (1-12 u² 02)1d12) -1 (122)(2111
2T
with respect to Lebesgue measure du du, whence
cov (wf (a - y)), cos(wn (o - y))] = -E(cos(wnn + w12) - (1))
Moving to polar coordinates:
W11 co)) W12 (in
14

---

Published in Transactions on Machine Learning Research (09/2024)
it follows that
2
f /0²0 [cos(cos + sin ()n2]rr111111 - (22)) drdd.
2TT
((cos((wn) + w12)2)]
(20)
2π
Expanding further the cosine into power series, we are left with the following two integrals:
l r 2i+ 11 (1-1)) T(j T -
j20.
(21)
2r + (d/2))
and (equation 3.66.1.2., p. 405 in Gradshteyn Ryzhik 2014
2m
(2j 1)!!
(cos sin 0) 2n (2j)!!
where (2j)!! (2)) - -2) ... (2) is the double factorial and likewise (2j - 1)!! (2) 1)(2j - ... 3)))).3)(11. Writing
(2j)!
(2j)!! 2r, (2) 1)!! 20
we equivalently get:
2T
(cos + sin 0)25 d0 = 2T (2j)1
0)35
(22)
()1)
Gathering equation
20
equation
21 and equation
22
end up with the expression:
(-1)223
E E[coss( (Wll + w12)22] (d ((d-))(((-22))) Σ
+
$20
= -112)))-1(223)
where we used the formula (d-2)[((d = Finally
1
+ j(d/2)-1
((/a/)))(3))² p-1 (11a)))=((22)) (z))))-1(3))
(2,
p
+ /(d/2)-1
+ (p
- (13)))
p
2
as desired.
Proof of Proposition 6
Proof The infinite product equation and the inequality
2u $ (1 u)², u u20 0,
implies that the covariance term computed above non positive:
(p - (V2))))) -()))) 0o
the interval [0, a.,1 1/2). Consequently,
1 + j(d/2) (()))
(K(x,)) B) <
2
Similarly,
- 4u) < (1 -u)
2 0,
15

---

Published in Transactions on Machine Learning Research (09/2024)
holds since the discriminant of u² 4u + 6, 0,
is negative. Applying this inequality to each factor in the product equation 14 entails:
((22))- - [=()
on the interval [0, ad, ad.1/2). Keeping in mind the lower bound derived in Proposition 3 which remains valid in [0, zo(d) (see the proof), we get on the interval [0, i=f((z(d)) dd,1/2)]
pV (K(x,y)) 5 1+ ((22))-1(22)
(1())))))))) v
+ 120/2)-1(2)) -2 (1()
(11)))))(3))3}
2
22p2
2
giving the incquality stated in the proposition.
Finally, remains to compare zo(d) and aa /2. To proceed, note that by the virtue of equation 17 led to compare
we are
2a d
d,1
and the value 1/2. In this respect, the lower bound given in Ismail Muldoon (1988), eq. (5.4), shows that
2a > 11/2,
whence infer that (u(d) > 22,1/2. Consequently, the inequality Víkonr (z, v)l s VikRFF(E, y)] holds true for any || yll [0, a.,1 /2). Recalling equation 18 and equation 19 we are done.
16


Reviews:
[{"review_id": "EMO4sZFRF6", "reviewer": "Reviewer_MxJY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\n\n- Overall, the paper is very well written and clear.\n- Topic is of interest to the TMLR community.\n- The authors went to great lengths to explain the findings, giving precious insights beyond the theorems themselves.\n- The experimental section is convincing and highlights well the theoretical findings.\n\nWeaknesses:\n\n- The proposed formulation of ORF differs from the original paper and corresponds to what is denoted by structured ORF in the original paper. I have nothing against this choice but it should be mentioned to help the reader.\n- The treatment of the relationship between $p$ and $d$ is insufficient in my opinion. It is stated in the notation that $2 \\leq p \\leq d$ however the paper presents results in expectation over the law of the random features: how useful are such theorems if one cannot take more that $d$ random features ? In the original ORF paper, this was circumvented by taking ORFs from independent sources (hence overall they are not orthogonal anymore), but I do not see it used here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an analysis of the bias and variance associated to a special scheme of random features where the features are orthogonal to each other. More precisely:\n- Theorem 2 gives the bias of the associated kernel in terms of a normalized Bessel function.\n- Proposition 3 gives additional insights about this bias by bounding it by Gaussian kernels.\n- Theorem 4 explicits the variance associated to the computation of the approximated kernel.\n- Proposition 6 relates this variance to the one associated to the classical RFF kernel.\n\nNumerical experiments complement the theoretical derivations and highlight the main contributions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Clarification of ORF vs structured ORF.\n- Clarification on the number of random features.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3T9E5jsNNn", "reviewer": "Reviewer_LSFZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The explicit expectation and variance expressions seem to be novel, and given the common use of ROF these are beneficial results.\n- The empirical validation of the results, although they have some issues (see below) are useful support of the theory.\n\nWeaknesses:\n- Clarity: Some of the experimental results lack sufficient discussion for total clarity. For example, in relation to Fig. 1, the empirical bias is decreasing with p, and yet the theory says it is independent of p. What should I be concluding from this then? It is also not generally given what value of $z = ||x-y||$ is being used. \n\n- Motivation: Beyond the expectation and variance expressions, I find it hard to see the motivation underlying other parts of what is presented. For example, what is the usefulness of the bounds on the Bessel kernel (the average ROF kernel)? One can see that ROF may be preferable to RFF because it has lower variance, but if one wants to be using a Gaussian kernel and not a Bessel kernel then what should a user choose? This point pertains to the MSE experiment as well. Surely a user of an approximation method, or choosing between two, will have an objective in mind. That is, they may wish to use a Gaussian kernel but are \"happy\" with an approximate method. Comparing MSE of the two in estimating different things (RFF estimating the Gaussian kernel and ROF estimating the Bessel kernel) doesn't really tell me anything. In relation to this experiment too, why is the Gaussian kernel given a bandwidth and not the Bessel kernel? The scaling of the data within the kernel via a bandwidth is universal to all kernels, so this experiment isn't comparing like with like unless both are given this scaling.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents some theoretical results associated with Random Orthogonal Features based kernel approximation. In particular explicit expectation and variance expressions are derived, showing that contrary to prior belief the expectation is of a Bessel kernel and not a Gaussian kernel. Some exponential bounds on the average ROF kernel are also presented over fairly large range of the distance between its arguments. Some numerical experiments are presented to corroborate the theory.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Can you add some clarity regarding what the reader is to gain from the paper. I appreciate the derivations of the mean and variance of the ORF approximated kernel, but as a reader I do not know what I should be taking away from the paper beyond that. Generally speaking, I would expect most users \"want\" to approximate the Gaussian kernel due to its popularity. You have shown that the ORF would be biased for this objective, but your MSE experiments don't clarify if the reduction in variance overcomes this bias. I also argue that these do not show a relevant comparison since they have a different \"target\" (I would argue that most users do not want to approximate the Bessel kernel, and so I question the relevance of the MSE for estimating that target). As it is I see the ORF is biased if I want a Gaussian kernel, but has lower variance. There are also some exponential bounds on the difference between these two kernels over a range which doesn't offer immediate intuitive understanding. The range grows linearly with dimension, as you have shown, but what is relevant to a user is how this range overlaps/not with the range of pairwise distances between observations (after appropriate scaling a la via the use of a bandwidth scaling) which is likely also going to grow with dimension.", "broader_impact_concerns": "Nothing obvious", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "mE8VOAu5RD", "reviewer": "Reviewer_ZMow", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of this paper stands in the nice theoretical contribution. The precise bias-variance characterization of the Orthogonal Random Feature (ORF) approximation scheme is a nice technical result. All the main results are presented with coherent numerical illustrations, which is welcomed.\n\nThe main weakness of this work is the presentation. In the introduction and global overview of Random Features approximation methods, the relevance of the considered setting is barely discussed; moreover, several works on the topic are missing in the related works description.  Subsequently, the formal presentation of the main results is carried over without any proof sketch and insufficient description of the main ideas, which strongly worsens the readability of the text. Similarly, the appendix consists of a series of disconnected mathematical statements.\n\nI propose in the section below many structural changes that I believe would strongly enhance the presentation of this submission.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript characterizes the bias and variance associated with orthogonal random feature approximation of kernel matrices. The authors tackle the scenario in which the orthogonal matrices are drawn from the Haar measure. The main theoretical results consist of providing sharp bounds on bias and variance of this approximation scheme. The formal results are accompanied by numerical illustrations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My concerns regard mainly the readability of the main text, I list below different changes that I believe will enhance the presentation.\n\n\n# Main concerns\n- This manuscript nicely finds that, in contrast with the community wisdom, Orthogonal Random Feature approximates a different kernel w.r.t the Gaussian one. This is briefly mentioned in the abstract, but not emphasized enough in the introduction of the main results; more precisely, the authors should explain explicitly the common belief that ORF approximates the Gaussian kernel.\n- Similarly to the above, the Orthogonal Random Feature approach is presented in five lines (Page 2) before listing the main theoretical contribution. The authors should justify in deeper detail (with proper references to related works) the important role that ORF plays. For example, “ORF are more accurate with respect to i.i.d sampling…” is an insufficient explanation; e.g., “more accurate” in what respect? \n- It is difficult to navigate the writing of the main technical results. There are no proof sketches and they lack intuitive explanations that would help to better interpret the main results. For example after the first main theorem: “Theorem 2 shows ORF approximate kernel defined by Bessel function of the first kind. This function oscillates contrary to Bessel function of the second kind”. This statement is not actually helping the reader understand the result: a) there is no mention of how Bessel functions behave as a function of the subscript $d$; b) how does this relate with the Gaussian expression that was previously expected?  I believe a concise proof sketch with more detailed intuitive explanations would strongly help the reader.\n- Similar considerations as above hold for the appendix. As of now, the appendix consists of a disconnected series of mathematical statements with no linking effort. This strongly penalizes the readability of the text and the quality of the contribution.\n\n\n# Other comments\n- There is no reference for kernel methods, see e.g. [1,2].\n- Given that Random Feature models are the main subject of this work, a more extensive coverage of the related work is needed. Indeed, Random Features models have been extensively studied in the learning theory community under the umbrella of the Gaussian Equivalence Principle [3,4,5,6]. These works paved the way for developing a complete theory of the generalization properties of Random Feature models, see e.g. [8]. Analytical approaches based on Random Matrix Theory tools have been developed to study the deep case, see e.g. [9]. As an interesting remark for the authors: [7] analyzes the separability transition for Gaussian and Orthognal Random Features.\n- The presented analysis works at finite size. Such a nice aspect should be emphasized more in the manuscript.\n- There is a (clearly stated) condition $1<p<d+1$. Why is this assumption necessary? It would be interesting to point out where the proof scheme would fail as in the related RF literature general $(p,d)$ scaling is considered. For example, in the context of learning theory, the generalization properties are identified by m = min(p,d).\n- In the introduction/preliminaries please introduce in a few lines Bessel functions for the non-expert reader.\n\n\n# Minor comments:\n- Please rephrase the sentence in the abstract “the former is performed by a random Gaussian matrix and leads exactly to the Gaussian kernel after averaging” .\n- Page 2: RHS of equation (2) -> (1)\n- Page 2: dxd orthogonal matrix -> pxp orthogonal matrix\n- Page 3: please define $\\xi$ distributed\n- Page 7: scalar product should be denoted by transpose for consistency\n\n\n# References \n- [1] Schölkopf, B., Smola, A. J., Bach, F., et al. Learning with kernels: support vector machines, regularization, optimization, and beyond. 2002. \n- [2] Geoffrey S. Watson. Smooth regression analysis.1964.\n- [3] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mezard, and Lenka Zdeborova. The gaussian equivalence of generative models for learning with shallow neural networks 2022.\n- [4] Hong Hu and Yue M Lu. Universality laws for high-dimensional learning with random features. 2022.\n- [5]  Yatin Dandi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro, and Lenka Zdeborová. Universality laws for gaussian mixtures in generalized linear models. 2024.\n- [6] Andrea Montanari and Basil N Saeed. Universality of empirical risk minimization.  2022.\n- [7] Generalisation error in learning with random features and the hidden manifold model\nF Gerace, B Loureiro, F Krzakala, M Mézard, L Zdeborová. 2020. \n- [8] Asymptotics of random feature regression beyond the linear scaling regime. H Hu, YM Lu, T Misiakiewicz. 2024.\n- [9] Deterministic equivalent and error universality of deep random features learning\nDominik Schroder, Hugo Cui, Daniil Dmitriev, Bruno Loureiro. 2024.", "broader_impact_concerns": "I do not have any concerns about the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The theoretical results are sound and interesting, and for this reason I am recommending the paper for acceptance at TMLR.

There were some divergence points in the discussion with Reviewer LSFZ concerning: (a) How meaningful is using the MSE to compare RFF and ORF, e.g. in Fig. 4; (b) Whether ORF is more "realistic" than RFF". 

After a careful reading of this discussion and of the revised version, I believe point (a) was addressed. There might be some discussion on what conclusions can be taken from this comparison, but at least the authors have clarified the rationale.

However, I am on the side of Reviewer LSFZ on point (b).  What is "realistic" in the design of an algorithm or approximation scheme is subjective and unclear. I believe the word "effective" that follows already conveys a more precise meaning in terms of the theoretical results for the variance. Since this word is not really adding anything to the discussion, I request the authors to remove it from the camera-ready version.
Decision: Accept (poster)