On The Relative Error of Random Fourier Features for Preserving Kernel Distance
Authors: Kuan Cheng
Shaofeng H.-C. Jiang
Luojian Wei
Zhide Wei
Venue: ICLR 2023 poster (2023)
Keywords: random Fourier features
kernel methods
dimension reduction
clustering
Laplacian kernel

Abstract: The method of random Fourier features (RFF), proposed in a seminal paper by Rahimi and Recht (NIPS'07), is a powerful technique to find approximate low-dimensional representations of points in (high-dimensional) kernel space, for shift-invariant kernels. While RFF has been analyzed under various notions of error guarantee, the ability to preserve the kernel distance with \emph{relative} error is less understood. We show that for a significant range of kernels, including the well-known Laplacian kernels, RFF cannot approximate the kernel distance with small relative error using low dimensions. We complement this by showing as long as the shift-invariant kernel is analytic, RFF with $\mathrm{poly}(\epsilon^{-1} \log n)$ dimensions achieves $\epsilon$-relative error for pairwise kernel distance of $n$ points, and the dimension bound is improved to $\mathrm{poly}(\epsilon^{-1}\log k)$ for the specific application of kernel $k$-means. Finally, going beyond RFF, we make the first step towards data-oblivious dimension-reduction for general shift-invariant kernels, and we obtain a similar $\mathrm{poly}(\epsilon^{-1} \log n)$ dimension bound for Laplacian kernels. We also validate the dimension-error tradeoff of our methods on simulated datasets, and they demonstrate superior performance compared with other popular methods including random-projection and Nystr\"{o}m methods.

ON THE RELATIVE ERROR OF RANDOM FOURIER FEATURES FOR PRESERVING KERNEL DISTANCE
Kuan Cheng
Shaofeng H.-C.
Peking University
Peking University
Email: ckkcoh@pku. edu.
Email: shaofeng Saarnng-iange jiangāpku edu.cn
Luojian Wei
Zhide Wei
Peking University
Peking University
Email: luojiiawei@pku. edu
Email: zhidewei@pku. edu.
ABSTRACT
The method of random Fourier features (RFF), proposed in seminal paper by Rahimi and Recht (NIPS'07), a powerful technique to find approximate low- dimensional representations of points in (high-dimensional) kernel space, for shift-invariant kernels. While RFF has been analyzed under various notions of error guarantee, the ability preserve the kernel distance with relative error is less understood. We show that for a significant range of kernels, including the well-known Laplacian kernels, RFF cannot approximate the kernel distance with small relative error using low dimensions. We complement this by showing as long the shift-invariant kernel is analytic, RFF with poly(e logn) dimen- sions achieves g-relative error for pairwise kernel distance of n points, and the dimension bound is improved poly( log k) for the specific application of kernel k-means. Finally, going beyond RFF, we make the first step towards data- oblivious cinnension-reducttion for general shift-invariant kernels, and we obtain a similar poly(e- log n) dimension bound for Laplacian kernels. We also vali- date the dimension-eree -error tradeoff of our methods on simulated datasets, and they demonstrate superior performance compared with other popular methods includ- ing candom-projection and Nyström methods.
INTRODUCTION
) for preserving the relative error for the kernel distance. Kernel method (Schölkopf & Smola 2002) is systematic way to map the input data into a (indefinitely) high dimensional feature space to introduce richer structures, such non-linearity. In particular, for of data points P, kernel function
We study the ability of the random Fourier features (RFF) method (Rahimi & Recht 2007
K : P x P + R implicitly defines a feature mapping yp + H. to a feature space H. which is Hilbert space, such that Vz, y, K Kx, 3) (p(x). poy) Kernel methods have been successfully applied to classical machine learning (Boser et al. 1992, Schölkopf et al.) 1998 Girolami] 2002). and it has been recently established that certain sense the behavior of neural networks may be modeled as kernel (Jacot et al. 2018).
Despite the superior power and wide applicability, the scalability has been an outstanding issue of applying kernel methods. Specifically, the representation of data points in the feature space is only implicit, and solving for the explicit representation, which is crucially required in many algorithms, takes least M(n²) time in the worst case. While for many problems such kernel SVM, it is possible to apply the so-called "kernel trick" to rewrite the objective terms K (x, 3), the explicit representation is still often preferred, since the representation is compatible with larger range of solvers/algorithms which allows better efficiency.
In seminal work (Rahimi & Recht 2007), Rahimi and Recht addressed this issue by introducing the method of random Fourier features (see Section for detailed description), to compute an explicit low-dimensional mapping s TR D (for 1) & n1) such that (yp' (.), (V)) as (1o(x), (()))

---

[(x, y). for shift-invarian kemelss (i.e., there exists K P - R. such that ((x, v) = K(x y)) which includes widely-used Gaussian kernels, Cauchy kernels and Laplacian kernels.
Towards understanding this fundamental method of RFF, long line of research has focused on analyzing the tradeoff between the target dimension and the accuracy of approximating K under
certain error measures. This includes additive error max=.y y ((((=))))()) - ((0(x))
s (y)) (Rahimi & Recht] 2007] Sriperumbuuuu & Szabó [015 [Sutherland & Schneider, (015)) spectral error (Avron
al.) 2017] Choromanski al.] [0188] Zhang et al.j [019] [rrdelyi et al. 2020 Ahle et al.) 2020),
and the generalization error of several learning tasks such as kernel SVM and kernel ridge regres-
sion (Avron et al., 2017, Sun et al. 2018: Li al., (02I). A more comprehensive overview of the study of RFF can be found in a recent survey (Liu et al. 2021).
We focus on analyzing RFF with respect the kernel distance. Here, the kernel distance of two data points x, is defined as their (Euclidean) distance in the feature space, i.e.,
dist,p (zr, :) |1<p(x)) (2())l2-
While previous results on the additive error of [(x, 3) (Rahimi & Recht, 2007: Sriperumbudur & Szabó 2015. Sutterland & Schneider 2015; Avron al., (017)) readily implies additive error guarantee of dist (x. the relative error guarantee is less understood. As far as we know, Chen
& Philllips (0077 is the only previous work that gives a relative error bound for kernel distance, but unfortunately, only Gaussian kernel is studied in that work, and whether or not the kernel distance for other shift-invariant kernels preserved by RFF, is still largely open.
In spirit, this multiplicative error guarantee of RFF, if indeed exists, makes it a kernelized version of Lemma (Johnson & Lindenstrauss 1984) which one of the central result in dimension reduction. This guarantee is also very useful for downstream applications, since one can combine it directly with classical geometric algorithms such as k-means++ (Arthur & Vassil- vitskii 2007), locality sensitive hashing (Indyk & Motwani, 1998) and fast geometric matching al- gorithms (Raghvendra & Agarwal (2000) to obtain very efficient algorithms for kernelized k-means clustering, nearest neighbor search, matching and many more.
1.1 OUR CONTRIBUTIONS
Our main results are characterizations of the kernel functions on which RFF preserves the kernel distance with small relative error using poly log target dimensions. Furthermore, we also explore how to obtain data-oblivious dimension-reduucton for kernels that cannot be handled by RFF.
As mentioned, it has been shown that RFF with small dimension preserves the additive error of kernel distance for all shift-invariant kernels (Rahimi & Recht 2007 Sriperumbudur & Szabó 2015 Sutherland & Schneider 2015). In addition, has been shown in Chen & Phillips) (2017) that RFF indeed preserves the relative error of kernel distance for Gaussian kernels (which is shift-invariang Hence, by analogue to the additive case and as informally claimed in Chen Phillips (011)). one might be tempted to expect that RFF also preserves the relative error for general ihift-invariant kernels as well.
Lower Bounds. Surprisingly, show that this is not the case. In particular, we show that for a wide range of kernels, including the well-known Laplacian kernels, it requires unbounded target dimension for RFF preserve the kernel distance with constant multiplicative error. We state the result for Laplacian kernel in the following, and the full statement of the general conditions of ker- nels can be found in Theorem 4.1 In fact, what we show is a quantitatively stronger result, that if the input is (A, p)bbonnded, then preserving any constant multiplicative error requires ((poyyAAP)) target dimension. Here, a point æ IRd is ()ouuddddd if || I A and min [x, P. i.., the magnitude is (upper) bounded by A and the resolution is (lower) bounded by p.
Theorem 1.1 (Lower bound; see Remark 4.I). For every A 2 > O and some feature mapping exp(-I|æ - -vll)), if for every x, E Rd that are (A, bbuudddd the RFF mapping π for K with target dimension satisfies (x.tz(x,)) e
P Rd + H of Laplacian kernel K (x,y)
(1 + E)) dist, y) with constant probability, then D 2 (( This holds even when d = 1.
Upper Bounds. Complementing the lower bound, we show that REF can indeed preserve the kernel distance within 1 + error using po nog target dimensions with high probability,
2

---

as long the kernel function is shift-invariant and analytie, which includes Gaussian kernels and Cauchy kernels. Our target dimension nearly matches (up to the degree of polynomial of parameters) that is achievable by the SaihnssonLiidenstrauus transform (Johnson & Lindenstrauss 1984), which is shown to be tight (Larsen & Nelson, (017). This upper bound also greatly generalizes the result of [Cen & Phillips (217) which only works for Gaussian kernels (see Section G for detailed comparison).
Theorem 1.2 (Upper bound). Let K : R x IR + R be a kernel function which is shift-in shift-invarians and analytic at the origin, with feature mapping v Rd H. for some feature space H. For every O < 8 < e S 2-11,, every d, D E N. D 2 max (1/8))) O(==2 ( if T R + R is an RFF mapping for K with target dimension D, then for every x, y E R
Pr[] dist v) (r, f)1 S e. dist v)) 2 8.
The technical core of our analysis is moment bound for RFF, which is derived by analysis tech- niques such as Taylor expansion and Cauchy's integral formula for multi-variate functions, The moment bound is slightly weaker than the moment bound of Gaussian variables, and this is the primary reason that we obtain a bound weaker than that of the Johnson-Lindeestraun transform. Fi- nally, several additional steps are required fit this moment bound in Bernstein's inequality, which implies the bound in Theorem 1.2
Improved Dimension Bound for Kernel k-MMans. We show that if we focus on a specific ap- plication of kernel k-means, then it suffices to set the target dimension D poly(= log k). in- stead of D = poly(s log n)) to preserve the kernel k-means clustering cost for every k-partition. This follows from the probabilistic guarantee of RFF in Theorem 1.2 plus generalization of the dimension-reduction
result proved in a recent paper (Makarychev et al.] 2019). Here, given a data set P Rd and a kernel function K Rd x IR R. denoting the feature mapping as : Rd + H. the kernel k-means problem asks to find k-partition C == (Ci,..., Ok} of P. such that cost* c (P.C) E mine,EH Exec; [1ıp(z) c112 is minimized.
Theorem 1.3 (Dimension reduction for clustering; see Theorem 3.1). For kernel k-means problem whose kernel function K I2d x Rdd - TR. shift-invariant and analytic at the origin, for every data set P Rdd the RFF mapping π Rdd + RD with target dimension D 2 O I + log" 2)),
with probability at least 1 8. preserves the clustering cost within 1 + E error for every k-partition simultaneously.
Applying RFF to speed up kernel k-means has also been considered in Chitta et al. (2012). but their error bound is much weaker than ours (and theirs is not a generic dimension-reduution bound).
Also, similar reduuctinnn-euutiion bounds (i.e., independent of n) for kernel k-means were obtained using Nyström methods (Musco & Musco 2017 Wang et al. 2019). but their bound is poly(k) which worse than our poly log(k); furthermore, our RFF-bbsed approach is unique in that it is data-oblivious, which enables great applicability in other relevant computational settings such as streaming and distributed computing.
Going beyond RFF. Finally, even though we have proved RFF cannot preserve the kernel distance for every shift-invariant kernels, it does not rule out the existence of other efficient data-oblivious di- mension reduction methods for those kernels, particularly for Laplacian kernel which is the primary example in our lower bound. For instance, in the same paper where RFF was proposed, Rahimi and Recht (Rahimi & Recht 2007) also considered an alternative embedding called "binning features" that can work for Laplacian kernels. Unfortunately, to achieve a relative error of s, it requires a dimension that depends linearly on the magnitude/aspecttratte of the dataset, which may be expo- nential in the input size. Follow-up works, such as (Backurs et al. 2019). also suffer similar issues.
We make the first successful attempt towards this direction, and we show that Laplacian kernels do admit an efficient data-oblivious dimension reduction. Here, we focus on the (A, -bbunnee case, Here, we use similar setting to our lower bound (Theorem 1.1 where we focus on the (A, p)- bounded case.
Theorem 1.4 (Oblivious dimension-reduction for Laplacian kernels, see Theorem F.I. Let K be Laplacian kernel, and denote its feature mapping as ip Rd - H. For every 0 S 2 (1gg(1/6)) ( ((ooo))))))))) every A 2 p O. there is a mapping
every D 2
3

---

T: RR R., such that for every z. E R that are (A, (A,,)))bouddal -bounded it holds that
Pr[l (x. v) - dist.p (z; v)1 dist ( v)] 2 11-6.
The time for evaluating π is dD poly(log A 8 1ogg-1).
Our target dimension only depends on log which may be interpreted as the precision of the input.
have an embedding with target dimension D = poly(s-1 log where the success probability is 1 1/ poly(n) and the overall running time of embedding the n points is O(n poly (de-1 log log n)).
Hence, immediate corollary, for any n-points dataset with precision 1/ poly(n),
Our proof relies on the fact that every & metric space can be embedded into squared & metric space isometrically, We explicitly implement an approximate version of this embedding (Kahane) 1981], and eventually reduce our problem of Laplacian kernlls to Gaussian kernels. After this reduction, we use the RFF for Gaussian kernels to obtain the final mapping. However, since the embedding to squared & is only of very high dimension, to implement this whole idea efficiently, we need utilize the special structures of the embedding, combined with an application of space bounded pseudo-random generators (PRGs) (Nisan. 1992).
Even though our algorithm utilizes the special property of Laplacian kernels and eventually still partially use the RFF for Gaussian kernels, it is still of conceptual importance. It opens up the direction exploring general methods for Oohnson-Lindenstrauss style dimension reduction for shift-invariant kernels. Furthermore, the lower bound suggests that the Lindeenn-indesstrrauss style dimension reduction for general shift-invariant kernels has to be not differentiable, which is a fun- damental difference to RFF. This requirement of "not analytical" seems very counter-intuitive, but our construction of the mapping for Laplacian kernels indeed provides valuable insights on how the non-analytical mapping behaves.
Experiments and Comparison to Other Methods. Apart from RFF, the Nyström and the random-projection methods are alternative popular methods for kernel dimension reduction. In Sec- tion 6 we conduct experiments to compare their empirical dimension-error tradeoffs with that of methods simulated dataset. Since we focus the error, we use the "ideal" implementa- tion of both methods that achieve the best accuracy, so they are only in favor of the two baselines for Nyström, use SVD the kernel matrix, since Nyström methods can be viewed fast and approximate low-rank approximations to the kemel matrix; for random-projection, we apply the Johnson-Liindenstrauss transform on the explicit representations of points in the feature space. We run two experiments to compare each of RFF (on Gaussian kernel) and our new algorithm Theorem 1.4 (on a Laplacian kernel) with the two baselines respectively. Our experiments dicate that the Nyström method is indeed incapable of preserving the kernel distance in relative error, and more interestingly, our methods perform the best among the three, even better than the transform which is the optimal in the worst case.
1.2 RELATED WORK
Variants of the vanilla RFF, partieularly those that use information in the input data and/or sam- ple random features non-uniformly, have also been considered, including leverage score sampling
random Fourier features (LSS-RFF) (Rudi al. 2018 Liu al., 2020; Erdélyi et al.. 2020 Li al.
2021), weighted random features (Rahimi & Recht 20088 Avron et al. 2016 Chang et al. 2017
Dao et al. 2017), and kernel alignment (Shahrampour et al. 2018 Zhen et al. 2020).
The RFF-based methods usually work for shift-invariant kernels only. For general kernels, techniques that are based on low-rank approximation of the kernel matrix, notably Nyström
method (Williams & Seeger) 2000 Gittens & Mahoney| 2016 Musco & Musco, 2017 Oglic &
Gärtner 2017; Wang et al. 2019) and incomplete Cholesky factorization (Fine & Scheinberg 2001
Bach & Jordan 2002 Chen al. 2021
1 Jia et al.) (2021)) were developed. Moreover, specific sketch-
ing techniques were known for polynomial kernels (Avron et al. 20044) Woodruff & Zandich 2020
Ahle et al. 2020 Song et al. 2021), basic type of kernel that is not shift-invariant.
4

---

2 PRELIMINARIES
Random Fourier Features. RFF was first introduced by Rahimi and Recht (Rahimi & Recht 2007 It is based on the fact that, for shift-invariant kernel K IR I. such that K (this can be assumed w.l.o.g. by normalization), function 1.
R + R such that p(w) =
2x Jgd ((z)e dz, which is the Fourier transform of K(-). is probability distribution (guar- anteed by Bochner's theorem (Bochner, 1933 Rudin 1991)). Then, the RFF mapping is defined
as
sin x)) cos (18,,1,44 x))
(x)
V D
sin x) cos (us 2)
where wi, ..,,..,,,))) wp E Rd are i.i.d. samples from distribution with densitiy
Theorem 2.1 Rahimi & Recht 2007). B((T(z), - - E Elcos(ws, x w)1 K(x (x - y).
Fact 2.1. Let w be random variable with distribution p over Rdd. Then
VER,, Elcos (t/w, x y))l = R J Hwwwel dw = K(t(x - y)),
(1)
and Var(cos (w, I 8)) 1+K(2(2- v) 22
3
UPPER BOUNDS
We present two results in this section. We start with Section 3.1 to show RFF preserves the relative error of kernel distance using poly(s log n) target dimensions with high probability, when the ker- nel function is shift-invariant and analytic at origin. Then in Section 3.2, combining this bound with a generalized analysis from a recent paper (Makarychev et al., 2019), we show that RFF also pre- serves the clustering cost for kernel k-clustering problems with & ob-obeec,,ve, with target dimension only (o log k) which is independent of
3.1 PROOF THEOREM 1.2 THE RELATIVE ERROR FOR PRESERVING KERNEL DISTANCE
Since K is shift-invariant, we interpret K as function on Idd instead of Rd x Rd, such that K(2,8) 9) K(x y). As in Section 2 let p F - be the Fourier transform of K, and suppose in the RFF mapping æ, the random variables wi,..., Wid E Rd are i.i.d. sampled from the distribution with density p. When we say K analytic at the origin, we mean there exists some constant s.t. K is analytic in {z E Rd ||x||| < <r}. We pick т to be the maximum of such constant r. Also notice that in D > max max{O( (0 1loe-loo'" (1/0)) O log(11))) there are constants about K hidden inside the θ, i.e. Rg as Lemma 3.2
Fact 3.1. The following holds.
dist, 3) = /2 2/D cos(ws, x - y). and dist (2. = /2 - 2K(r 8) Pr[[ (I, y) dist v)1 dist v)] > Pr[l dist (x, u)² dist (2,, y) <
E (2,)
K(x). As a crucial step, we next analyze the moment of random variables X,(r 1/. This bound will be plugged into Bernstein's 's inequality conclude the proof.
Define X²(x) == cos
Lemma 3.1. for some r > K analytic in {a Rd || r), then for every being
[Ak]|<=]]]
even and every s.t. || < we have E[[X((=))
Proof. The proof can be found in Section A
5

---

Lemma 3.2. For kernel K which is shift-innon hhift-invarian and analytic at the origin, there exist CK Rg such that for all || S Rg,
1-K(z)
ox.
|
Proof. The proof can be found in Section
Proof sketch of Theorem 1.2 We present a proof sketch for Theorem 1.2 and the full proof can be found in Section C full proof). Then by Lemma 3.2 we have 2K(x - y) 2 c| x - ylli. Then we have:
We focus the case when | yll < Rx (the other case can be found in the
D Σ
2 D
2 D
Pr
x1 v) se. 2K(x - u))
2 Pr
X1(x: y) S CE 1| u11?
We take rk for simplicity of exhibition. Assume min (e, 2 2-1,, let k: (0gg(222/5)) 64x² /r2 is even. By Markov's inequality and Lemma 3.1
(41))
6
(r v) 2 +|| yll Pr [xx (I f)1* 11 vll
4 - 2DD22
tk
For simplicity denote X,(r y) by X1, || u by l and define X; 1 12 sgn(X,) +
[[xx X,, note that [[X,] = O. By some further calculations and plugging in the parameters t, 6. D, we can eventually obtain E [|]]]| < St. Denote o²2 the variance of X then again by Lemma 3.1 we immediately have o' S 64f/r². The theorem follows by straightforward
application of Bernstein's inequality.
3.2 DIMENSION REDUCTION FOR KERNEL CLUSTERING
We present the formal statement for Theorem 1.3 in Theorem 3.1 In fact, we consider the more general k-clustering problem with Eg -ojjecttvvv defined in the following Definition 3.1 which gen- eralizes kernel k-means (by setting p = 2).
Definition 3.1. Given a data set P C Rd and kernel function K Rd x Rd + R. denoting the feature mapping as 1 : Fd + H. the kernel k-clustering problem with f--objective asks for k-partition C = (C1, C2. C of P that minimizes the cost function: cost =
Σ min Exec, (1x((r) - G.
Theorem 3.1 (Generalization of Makarychev et al. 2019
Theorem 3.6). For kernel k-clustering Ra x R + R is shift-invurint and analytic
problem with -goojecttvve whose kernel function the origin, for every data set P CRd, the RFF mapping Ed E D with target dimension D Up log k +pp log 1 : + p/2/ satisfies
Pr[yk--prrittin C of P (P,C) (1 cost 2 -
Proof. The proof can be found in Section
LOWER BOUNDS
Theorem 4.1. Consider 2 p >>>00 O, and chift-invarian kernel function K Rd + R, denoting its feature mapping 1p Rd + H. Then there exists z, y E Rd that are (A, p) pbbondeed such that for every < E < 1, the RFF mapping n for K with target dimension satisfies
e 3/12 ds Op (2)
Pr[ dist y) dist, (x, y)1 2 e dist (x, (x,y)) 2 V2T 60 B D
(A.p) where 8K sup, p) bonnded x (x)x), and sK (z) = 1 K(2x) 2K(x)2
2(1 -()))²
Proof. The proof can be found in Section B

---

Note that the right hand side of (2) is always less than 1, since the first term 2_
Dr V2T sey D/sk e == /2 ds achieves its maximum at (...)) O. and this maximum I. On the 5x
other hand, we need the right hand side of to be > 0 in order to obtain a useful lower bound, and a typical setup to achieve this is when D
2
(A,p)
SK
Intuition of SK- Observe that sk (a) measures the ratio between the variance of RFF and the (squared) expectation evaluated at z. The intuition of considering this comes from the central limit theorem. Indeed, when the number of samples/target dimension is sufficiently large, the er- ror/difference behaves like a Gaussian distribution where with constant probability the error s Var. Hence, this KK measures the "typical" relative error when the target dimension is sufficiently large, and an upper bound of $ (A.p) is naturally necessary condition for the bounded relative error. The following gives a simple (sufficient) condition for kernels that not have a bounded 8 (2:).
Remark 4.1 (Simple sufficient conditions for lower bounds). Assume the input dimension is 1, so K R - R, and assume A 1, P < 1. Then the (A, pb-bundde property simply requires S x I 1. We claim that, if K's first derivative at 0 is non-zero, i.e., (0) + 0, then RFF cannot preserve relative error for such K. To see this, we use Taylor's expansion for K the origin, and simply use the approximation to degree one, i.e., ((x) s 1 +ax (noting that x S so this is good approximation), where (0).. Then
+ 1 2ar 2(1 + oz.)
SK (x)
2a²x²
ax
So a K' * O, then for sufficiently small p and |x| 2 p. sx(p) 2 2(1/p). This also implies the claim in Theorem [.I for Laplacian kernels (even though one needs to slightly modify this analysis since strictly speaking K' is not well defined at 0 for Laplacian kernels). As a sanity check, for shift-invariant kernels that are analytic at the origin (which include Gaussian kernels), is necessary that K' K'(0)= O.
BEYOND RFF: OBLIVIOUS EMBEDDING FOR LAPLACIAN KERNEL
In this section we provide a proof sketch for theorem I.4 A more detailed proof is deferred to section i
Embedding To handle Laplacian kernel function K v) = - عااساا with some constant we cannot directly use the RFF mapping o, since our lower bound shows that the output dimension has to be very large when K is not analytical around the origin. To overcome this issue, up with the following idea. Notice that L(z, y) relies on the fi-distance between 2, y. If one can embed (embedding function f) the data points from the original & metric space to a space and ensure that there is an kernel function K', analytical around the origin, for the new space s.t. K(x, y) (' f()) for every pair of original data points x, y, then one can use the function composition @ o to get a desired mapping.
come
metric
Indeed, we find that é, can be embedded to L isometrically (Kahane) 1981 in the following way. Here for simplicity of exhibition we only handle the case where input data are from No, upper bounded by natural number N. Notice that even though input data points are only consisted of integers, the mapping construction needs to handle fractions, as we will later consider some numbers generated from Gaussian distributions or numbers computed the RFF mapping. So we first setup two numbers, A' = Poly(N,5 5-1) large enough and p' 1/ 1/poly(N, 5-) small enough. All our following operations are working on numbers that are (A',p')-boundees do the following transformation. Let Ti N - E be such that for every E N, < N, the first æ entries of Ti (x)) is the number 1, while all the remaining entries are 0. Then consider all d dimensions. The embedding function (d) Ndd Nd be such that for every E Nd <
For each dimension we
N. Vi [d], we have o| (4) (x) being the concatenation of d vectors गi (xx), é E [d]. After embedding, consider a new kernel function K' 1e'-0'1 where x' T/00 (z). (((1) (z). One can
immediately that (' .yy) K(x, y). Hence, we can apply REF then, i.c. the mapping is á = which has small output dimension. Detailed proofs be seen in section
F.
7

---

However, there is another issue. In our setting, if the data is (A, bounded, then we have to pick N = ( The computing time has a linear factor in N, which is too large.
Polynomial Time Construction To reduce computing time, we start from the following observa- tion about the RFF mapping o(x'), Each output dimension is actually function of (w, x²), where w a vector of i.i.d Gaussian random variables. For simplicity description we only consider that has only one dimension and x' TT (z). So x' is just a vector consists of I number of I's starting from the left and then all the remaining entries are O's. Notice that a summation of Gaussian random variables is still Gaussian. So given 2, one can generate (w, x²) according to the summation of Gaussians. But here comes another problem. For two data points x; y, we need to use the same w. So if we generate (w) and (w',y' separately, then w, w' are independent.
To bypass this issue, first consider the following alternate way to generate (w,x'). Let h be the smallest integer s.t. N < 2 Consider binary tree where each node has exactly 2 children. The depth is h. So it has exactly 2 leaf nodes in the last layer. For each node v, we attach a random variable a, in the following way. For the root, we attach Gaussian variable which is the summation of 2d independent Gaussian variable with distribution wl. Then we proceed layer by layer from the root leaves. For each u, v being children of a common parent w, assume that a the summation of 2 independent wp distributions. Then let Ou be the summation of the first 2 distributions among them and o, be the summation of the second 2/-1 distributions. That is 0w = Oa + O2 with Oa,, O₂ being independent. Notice that conditioned on a' a, then an takes the value 6 with probability Pro..o, iid. aa,, = b an + a2 = a]. ag takes the value a b when dy takes value b.
The randomness for generating every random variable corresponding to node, is presented sequence, in the order from root to leaves, layer by layer, from left to right. We define a² to be the summation of the random variables corresponding to the first leaves. Notice that a" can be sampled efficiently in the following way. Consider the path from the root to the æ-th leaf. First sample the root, which use a variable z to record this sample outcome, calling an accumulator for convenience. Then we visit each node along the path. When visiting v, assume its parent is w, where Ow has already been sampled previously with outcome a. If v is a left child of w, then we sample ag conditioned on aw = a. Assume this sampling has outcome Then we add -a + to the current accumulator 2. If v is a right child of a node w, then we keep the current accumulator unchanged. After visiting all nodes in the path, is the sample outcome for a². We can show that the joint distribution a", a has basically the same distribution as (w, n (x)), (w, m (v)). See lemma F.2
be computed using the corresponding part of the randomness. We
The advantage of this alternate construction that given any x, to generate a", one only needs to visit the path from the root to the z-th leaf, using the above generating procedure. To finally reduce the time complexity, the last issue is that the uniform random string for generating random variables here is very long. If sweep the random tape to locate the randomness used to generate variable corresponding to a node, then we still need a linear time of N. Fortunately, PRGs for space bounded computation, e.g. Nisan's PRG (Nisan 1992), can be used here to replace the uniform random- ness. Because the whole procedure for deciding whether || o TH (xx) - Φ o क (y) la approximates /2- - K (Ir, y) within (1 + E) multiplicative error, is in poly-logarithmic space. Also the computa- tion of such PRGs can be highly efficient, i.e. given any index of its output, one can compute that bit in time polynomial of the seed length, which is soly-logarithmic of N. Hence the computing time of the mapping only has a factor poly-logarithmic N instead of factor linear in N.
Now we have shown our construction for the case that all input data points are from N. One can generalize this to the case where all numbers are (A, p) bounded, by doing some simple roundings and shiftings of numbers. Then this can be further generalized to the case where the input data has d dimension, by simply handling each dimension and then concatenating them together. More details of this part are deferred to section F.4
EXPERIMENTS
We evaluate the empirical relative error of our methods on a simulated dataset. Specifically, we do two experiments, one evaluate RFF Gaussian kernel, and the other one evaluate the new
8

---

10
Mothod
066
0.-
05-
64-
SVD
02
30
50
20
30
50
60
70
80
Torget mersinn
Torget Oimrriinn
(a) RFF
(b) New-Lap
Figure 1: The dimension-errow tradeoff curves for both experiments, i.e., the experiment that evalu- ates RFF and the one that evaluates New-Lap.
algorithm in Theorem F1 which we call "New-Lap", on a Laplacian kemel. In each experiment, compare against two other popular methods, particularly Nyström and random- proooo-ttooeoionnn methods.
Baselines. Observe that there many possible implementations of these two methods. However, but more accurate
since we focus on the accuracy evaluation, we choose computationally-heuu implementations the baselines (hence the evaluation of the error is only in the baseline's favor). In particular, we consider 1) SVD low-rank approximation which we call "SVD", and 2) the vanilla Johnson-Lindenstrauss algorithm performed on top of the high-dimensional representation of points in the feature space, which we call "JL". Note that SVD is the "ideal" goal/form of Nyström methods and that Johnson-Lingg Saanson-Lindenstrauss applied the feature space obtain theoretically-tight kuret--dimnsion bound (in the worst-case sense).
Experiment Setup. Both experiments are conducted on synthesized dataset X which consists of N 100 points with d = 60 dimensions generated i.i.d. from a Gaussian distribution. For the experiment that we evaluate RFF, we use a Gaussian kernel ((x) cxp(- (00.- ||=|]]), -.=]][== and for that we evaluate New-Lap. we use Laplacian kernel K(x) = exp(-00 - 00. ||æ]|/2). In each experiment, each method, we run it for varying target dimension D (for SVD,
target rank), and we
report its empirical relative error, which is defined as
(xx v) - (x
max
xfyEX
dx(x,y)
where dx is the kernel distance and is the approximated distance. To make the result stabi- lized, conduct this entire experiment for every D for T 20 times and report the average and 95% confident interval. We plot these dimension-error tradeoff curves, and we depict the results in Figure
Results. We conclude that in both experiments, our methods can indeed well preserve the relative of the kernel distance, which verifies theorem. In particular, the dimension-error curve is comparable (and even slightly better) to the computationally heavy (which theoretically optimal in the worst case). On the contrary, the popular Nyström (low-rank approximation) method is largely incapable of preserving the relative error of the kernel distance. In fact, we observe that (ss, y) or often happens for some pairs of (æx, y) such that d(z, y) * 0, which explains the high relative error. This indicates that our methods can indeed well preserve the kernel distance in relative error, but existing methods struggle to achieve this.
algorithm
ACKNOWLEDGMENTS ACKNOWLEDGMENTT
Research is partially supported by national key R&D program of China No. 2021 17FA1000000. startup funds from Peking University, and the Advanced Institute of Information Technology, Peking University.

---

REFERENCES
Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David Woodruff, and Amir Zandieh. Oblivious sketching of high-degree polynomial kernels. In SODA, pp. 141-160. SIAM, 2020.
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In SODA, pp- 1027-1035. SIAM, 2007.
Haim Avron, Huy Nguyen, and David P. Woodruff. Subspace embeddings for the polynomial kernel. In NIPS. pp. 2266, 2014.
Haim Avron, Vikas Sindhwani, Jiyan Yang, and Michael W. Mahoney. Quasi-monte carlo feature maps for shift-invariant kernels. J. Mach. Learn. Res., 17:120:1-120:38, 2016.
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandich. Random fourier features for kernel ridge regression: Approximation bounds and statisti- cal guarantees. In ICML, volume 70 of Proceedings of Machine Learning Research, pp. 253-262. PMLR, 2017.
Francis R. Bach and Michael Jordan. Kernel independent component analysis. Mach. Learn. Res., 3:1-48, 2002.
Arturs Backurs, Piotr Indyk, and Tal Wagner. Space and time efficient kernel density estimation in high dimensions. In NeurlPS, pp. 15773-15782, 2019.
Andrew C Berry. The accuracy of the gaussian approximation to the sum of independent variates. Transactions of the american mathematical society, 49(1):122-136 1941.
Salomon Bochner. Monotone funktionen, stieltjessche integrale und harmonische analyse. Mathe- matische Annalen, 108(():378-414 4100, 1933.
Bernhard E. Boser, Isabelle Guyon, and Vladimir Vapnik. A training algorithm for optimal margin classifiers. COLT, pp. 144-152, ACM, 1992.
Wei-Cheng Chang, Liang Li, Yiming Yang, and Barnabás Póczos. Data-driven random fourier features using stein effect. In IJCAI, pp. 1497-1503. ijcai.org, 2017.
Di Chen and Jeff M. Phillips. Relative error embeddings of the gaussian kernel distance. In ALT, volume 76 Proceedings of Machine Learning Research, pp. 560-576. PMLR, 2017.
Li Chen, Shuisheng Zhou, Jiajun Ma, and Mingliang Xu. Fast kernel k-means clustering using incomplete cholesky factorization. Appl. Math. Comput., 402: 2021.
Radha Chitta, Rong Jin, and Anil Jain. Efficient kernel clustering using random fourier features. In ICDM, pp. 161-170. IEEE Computer Society, 2012.
Krzysztof Choromanski. Mark Rowland, Tamás Sarlós, Vikas Sindhwani, Richard E. Turner, and Adrian Weller. The geometry of random features. In AISTATS, volume 84 of Proceedings of Machine Learning Research, pp. 1-9. PMLR, 2018.
Tri Dao, Christopher De Sa, and Christopher Ré. Gaussian quadrature for kernel features. In NIPS, pp. 6107-6117, 2017.
Tamás Erdélyi, Cameron Musco, and Christopher Musco. Fourier sparse leverage scores and ap- proximate kernel learning. In NeurlPS, 2020.
Carl-Gustav Esseen. On the liapunov limit error in the theory of probability. Ark. Mat. Astr. Fys., 28:1-19, 1942.
Shai Fine and Katya Scheinberg. Efficient SVM training using low-rank kernel representations. J. Mach. Learn Res., 2:243-264, 2001.
Mark A. Girolami. Mercer kernel-based clustering in feature space. IEEE Trans. Neural Nenworks, 13(3):700-74,, 2002.
10

---

Alex Gittens and Michael W. Mahoney. Revisiting the nystrom method for improved large-scale machine learning. J. Mach. Learn. Res., 17:117:1-117:65, 2016.
Lars Hormander. An introduction complex analysis in several variables. van Nostrand, 1966.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In STOC, pp. 604-613. ACM, 1998.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and gen- eralization in neural networks. In NeurIPS, pp. 1580-8589 2018.
Hongjie Jia, Liangjun Wang, Heping Song, Qirong Mao, and Shifei Ding. An efficient nyström spectral clustering algorithm using incomplete cholesky decomposition. Expert Syst. Appl., 186: 115813, 2021.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26:28, 1984.
Jean-Pierre Kahane. Hélices et quasi-hélices. Leopoldo Nachbin (ed.), Mathematical Anal- ysis and Applications, Part pp. 418-432. Academic Pr, first edition edition, 1981. ISBN
0123128029,9780122222888
Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstraaue lemma. In FOCS, pp. 633-6336 IEEE Computer Society, 2017.
Zhu Li, Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards unified analysis of random fourier features. J. Mach. Learn. Res., 100:0,,,, 2021.
Fanghui Liu, Xiaolin Huang. Yudong Chen, Jie Yang. and Johan A. K. Suykens. Random fourier features via fast surrogate leverage weighted sampling. In AAAI, pp. 4844-4851. AAAI Press, 2020.
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel ap- proximation: A survey on algorithms, theory, and beyond. IEEE Transactions on Pattern Analysis & Machine Intelligence, (01):1-1, 2021.
Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In STOC, pp. 1027-1038. ACM, 2019.
Cameron Musco and Christopher Musco. Recursive sampling for the nystrom method. In NIPS, pp. 3833-3845, 2017.
Noam Nisan. Pseudorandom generators for space-bounded computation. Comb, 12(4):449-45 1992.
Dino Oglic and Thomas Gärtner. Nyström method with kernel k-means++ samples as landmarks. In ICML, volume 70 of Proceedings of Machine Learning Research, pp. 2652-2660. PMLR, 2017.
Sharath Raghvendra and Pankaj K. Agarwal. A near-linear time e-approximation algorithm for geometric bipartite matching. J. ACM. 67(3):18:1-18:19) 2020.
Ali Rahimi and Benjamin Recht. Random features for large-scale kemel machines. In NIPS, pp- 11 1177-1184. Curran Associates, Inc., 2007.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In NIPS, pp. 1313-1320. Curran Associates, Inc., 2008
Alessandro Rudi, Daniele Calandriello, Luigi Carratino, and Lorenzo Rosasco. On fast leverage score sampling and optimal learning. In NeurIPS, pp. 5677-5687, 2018.
W. Rudin. Fourier Analysis Groups. Wiley Classics Library. Wiley, 1991. ISBN 9780471523642.

---

Bernhard Schölkopf and Alexander Johannes Smola. Learning with Kernels: support vector chines, regularization. optimization, and beyond. Adaptive computation and machine learning series. MIT Press, 2002.
Bernhard Schölkopf, Alexander J. Smola, and Klaus- Robert Müller. Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput., 10(5): 1299-1199, 1998.
Shahin Shahrampour, Ahmad Beirami, and Vahid Tarokh. On data-dependent random features for improved generalization in supervised learning. AAAI, pp. 4026-4033, AAAI Press, 2018.
Zhao Song, David P. Woodruff, Zheng Yu, and Lichen Zhang. Fast sketching of polynomial kernels of polynomial degree. In ICML, volume 139 of Proceedings of Machine Learning Research, pp- 9812-9823. PMLR, 2021.
Bharath K. Sriperumbudur and Zoltán Szabó. Optimal rates for random fourier features. NIPS, pp. 1144-1152, 2015.
Yitong Sun, Anna C. Gilbert, and Ambuj Tewari. But how does it work in theory? linear SVM with random features. In NewrIPS, pp. 3383-3392, 2018.
Danica Sutherland and Jeff Schneider. On the error of random fourier features. In UAI, pp- 862-877 871. AUAI Press, 2015.
Shusen Wang, Alex Gittens, and Michael W. Mahoney. Scalable kernel k-means clustering with nyström approximation: Relative-error bounds. Mach. Learn. Res., 10:12:1-12::9, 2019.
Christopher K. Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. In NIPS, pp. 682-688. MIT Press, 2000.
David P. Woodruff and Amir Zandich. Near input sparsity time kernel embeddings via adaptive sampling. In ICML, volume 119 of Proceedings of Machine Learning Research, pp. 10324- 10333. PMLR, 2020.
Jian Zhang, Avner May, Tri Dao, and Christopher Ré. Low-precision random fourier features for memory-constrained kernel approximation. In AISTATS, volume 89 Proceedings of Machine Learning Research, pp. 1264-1274. PMLR, 2019.
Xiantong Zhen, Haoliang Sun, Ying-Jun Du, Jun Xu, Yilong Yin, Ling Shao, and Cees Snoek. Learning to learn kernels with variational random features. In ICML, volume 119 of Proceedings of Machine Learning Research, pp. 1409-111419, PMLR, 2020.
Appendices
A PROOF OF LEMMA 3.1
Lemma 3.1. for some r > 0, K is analytic in {a Rd ||a||| r), then for every being
even and every x s.t. ||æ]]] < we have [I]( <A:||=/|1
We first introduce following two lemmas to show the properties of (x))
Lemma A.1. For any wi sampled in RFF and k 2 0, we have E'cos* (Wi, x]]
DE E ([(j-()))))))
Proof. By eq. II sufficient to prove that
* (wi,
Σ j=0
cos cos((2j
kk)w,, x)).
12

---

We prove this by induction. In the case of A 0 the lemma holds obviously. If for k the lemma holds, we have
1
k
cos *o+*+1 ( 2)) = cos( (We, x))
c2s - Ai) (wes, x))
24
1=0
1
kk)
Cos( (wos x)) (2j k) (wo, x))
24 1=0
1
(
k>
cos{ - k + 1) x)) + cos((2] - k -1)(ws x1))
2
0=
k (5)
cos( - 1) (k + (2)((2())))
(x) + ccs(22 - (k + 1)) 2))
2
==
1+1
k
K ()))) cos((2) - (k: + (wi,
+
2
==
1+1
k
++1 1)
cos( - (k: + 1))
2
j
where in the third equality we use the fact that 2 cos a cos 3 cos(a + B) + cos(a - 3).
Lemma A.2. If there exists r > such that K is analytic in {z E Rd ||0|| < r), then Ak 2 0,
1im
(x)(( e. for some constant c.
||>||
Proof. We denote analytic function ((x) as Taylor series around origin as
K(x)=
c
(3)
BEN
where 8 := -I 8. is a monomial and its isefficient By definition, cg = 1 since K(O) = 1. We let No - N, (B)) Σi=1 Br denote the degree of x². Since K(x y) K(I, y) K(y,x)- = (y- - x) by definition, hence K (xx) is an even function, so CB = 0 for x(3) odd.
Recall that (x) == cos(w,, 2) K(x). In the following, we drop the subscripts in X,, 44 and write X,w w for simplicity. By the definition of X we have
& Σ
(
E [[((())
(4)
0=
Note that by Lemma eq.
A.1
B Blcos* k- kiasski-(wwwp (w,z))
1
Ejzó ((()) - (Ic -1- -())z). Plug this in
k Σ
h
B[x(x)*
=
K(x)'(-10 R-i
K((2j (Io - =))=z
25-5
i=0
j=0
K(x)²
(-1)
A-
k
Σ
ce(2i - k 17)
2
1=0
BEN
k
(-1
k- k-í
k:
e 8
Σ
K(r)²
(2j - k i)0(9)
i
2
BEN
1=
3=0
where the second equality comes from the Tyler expansion of K K((j - k + 1)2z). Next we will show that (x:)* is of degree least 2k.
13

---

For 3 = O note that Σ - (z) (K(x) 1)², since (()) is even and ( 1,
have limy-s0 [K(=)-1)* 0, Vt < 2k. For 3 # O, next show that every term of degree less than 2k has coefficient zero.
Fix B A and take Tyler expansion for (xx)²
K(x)*
Σ
08,032-1 ... cp, .....
91.
Without loss of generality, we assume 3141, ,.., B, are all [8 that equals O so we have 6 =
ca 1.
Now we consider the coefficient of term eacØ, CB2 ... C2 x 9+2 8, which would be:
k
Σ
Σ
(2j k + +))o((3)
where is the number of ordered sequence (81, f2,..., Bi), here, for 31 = B2, (31, ..,,.)))) and
(32, .1..... 31) are equivalent.
Next, we show if the degree of monomial s(3) + Ej=1 (B3) 2k, its coefficient is zero. Since all B, A O, we may assume sBB,) 2, therefore sB) 2k 21.
Suppose operator J is a mapping from a function space to itself, such that V : RR R defined by (x)
+I Denote J J. == J jk-1 as its k-time composition, define j to be the identity mapping such that (f) = f. Similarly we can define addition that (f) + J2( and scalar multiplication that (aJ)(f)- = aJ(()). By definition,
(Jr + (f)
JJ o J = Jmh (cJ") = Jm Vc E R, m, n E N.
Let L(r)= = (f), the coefficient can be rewritten as:
()) ()R+)(()(-RR)
Σ
Let P P= ビ
(L), the above is P(- Now we show P P= 0
(
Σ (K- j
(+-))00)) (L)
P P-
Σ
J + J2 k-i)
Σ
11
J
(--
(T))
2
-ÕJ
(1)
(k)
Σ
kh - riml (-
Jo + (-F++
k-t
(L)
i ii-1)
2
iml
-ÖJ (1) (5-
(J-
jo J2 k-1
(L).
Note that (J- 2
(f))z) = (f(x + 1) - f(x))/2 - (f(x + 2) - f(x + 1))/2 calculates
second order difference, namely, Vf that is a polynomial of degree k 2 2, (J 1++ (f) is
polynomial of degree k 2, and / that is a polynomial of degree & < 2, [ "ويو (/) is
Since J, is a polynomial of degree less than 2(k- 1), we have
1 f2
(1-
(L) = 0.
2
Combining the above two cases, we have proved eq. our proof.
(4) is of degree at least 2k, which completes
14

---

Proof of Lemma 3.7
If 2k |2|||
r,
since [Xx(z)] ccos(ur; x) K(x)] 2, we have
4k |rl2
24
([X,(a) & 2 Σ
Otherwise ||=||1 < r/2k. Define gx(x) = [xX,())"), we
r
have:
24 gx(Oz) (2k)
a (x(
a J 0x,
gb (x(x)
IJj
0 [0,
0x,
i=0
where the second equation comes from Lemma A.2 and Taylor expansion with Lagrange remainder.
Lemma A.3 (Cauchy's integral formula for multivariate functions Hormander 1966). For
f(z,..... zd) analytic in (2,rr) { (GI, ...........6 Sa) E 1C 2v Tv, V
......d)
f(g..... Ga) f(21....,22d za) (2 JaD, x8D2x.. xDDs (C1 - 21) (Ld - 2d)
1
d6.
Furthermore,
ghi+...kks tks f(21, 22,
za)
ky!... ka! (2
Sd)
JaD: xaDa.-x0D. (G 21 k1111 ... (Sa za)katt dc.
0z,k: ... kz
If in addition |s| < M, we have the following evaluation:
gh. ghi- ka f221, 22,..., 2d)
Mk1 ! kdd
Oz1 ki ... 0za
r1 h
Recall that Is (z) = ([X = Σi (3) (-)= 2 Ee ( ( - (k- i))
-
so (x) poly(K ((z),, ..... K (kzz) K[ k(-kz)) is analytic when |ж||] S r/k. Applying Cauchy's integral formula Lemma A.3 (here ||= + Ax 2 1//2k is in the analytic area),
t 22
6 gu (Oz)
(x(x)=
Σ
d
!12!
ta! OntiOn'z ... 0r'd
4+ +4
Σ
t t2 ...I" xtd
gh + 0x)
ta+T dz
(2Ti)d
>=E0%11as1=0 2
2d
we have
2k
2k
4k 4k|||=11a
2h
10x(x)) s sup
( Bx))
F2
|a,1=r/2k
r
B PROOF OF LEMMA 3.2
Lemma 3.2. For kernel K which shift-invariant and analytic at the origin, there exist Cg Rx such that for all || & Rg, 1-K(z)
2 9K.
|0ll
Proof. It suffices to prove that lim infz-so 1-K(x) 2 <>> O. for some c. Towards proving this, we -
show that K is strongly convex at origin. In fact, by definition, R fg. p(w))( (ew.)ell.tt) du = K(ta:) for every fixed z, therefore K" K'(tz) R fas || (lp dw O, hence K K(tx) is strongly convex with respect to l. origin, so is K(x).
15

---

C PROOF OF THEOREM 1.2
Theorem 1.2 (Upper bound). Let K : R. x TRd - R be a kernel function which is shift-invariant and analytic at the origin, with feature mapping 4p Rd - H for some feature space H. For every 0 < 8 S E S 2- every d, D E N. D 2 max(O(E-) log" (1/8)), G(= log(1/6))) if T R + P is an RFF mapping for K with target dimension D. then for every x, y E R
Pr[ dist, v) - dist, (z. v)1
dist,, v)] 2 1 1-8 8.
Proof. When ||2 y11 2 Rx, consider the function g(t = K (t(z - y)). It follows from definition
that g((0) = 0, gt) = =-R fo || yll2p(w) (e (ww f) dw < 0, so g(t) strictly decreases
for all > 0. So 2 -2K( y) 2 2 - 2 | Rx K(x - v) > -. We denote =
2 -- 2 max vili - Rx K(x - y)) so by Chernorff bound, when D
2
1 (In
oh + In 2), we have:
2r
Pr
2 D
Σ X1(x= w\
se. se. 12-224 2K- v)) 2 Pr
2
Σ
X₂(x v) st 2 1 1 5.
D
i=1
When | ie-yyll yll S Rx, by Lemma 3.2 we have 2 2-212 2K
v) 2 cl|x -yli Then have:
D Σ (1 v) 6 22((2(x - v)) 2 Pr D
2
2 D
Σ Xz(x y) s || u11
Pr
We take Tk for simplicity of exhibition. Assume d < min(e, 2 2-16), let k: = log(2D22//// /0), 64k² /r2, is even. By Markov's inequality and Lemma 3.1
(r| v) 2 d|I - vllil = Pr [x,(x - w*1* 2 11 - v112a] S (41))2k 2
5
1 <
2k
2D2
For simplicity denote X2 - y) by X,, || u1 by l and define X = 1 11x.12 sgn(X;) +
fux, X,, note that [E[X,] = O. Then:
|[X]|| S ||X
|X|| < t$] Pr[|X| < te] + tl |Pr[X] 2 t0| - Pr[x S -tEl
= |
X
< 40] Pr[[X|| < 18] - 18. |Pr[X; 2 U1] - Pr[X, S -Lel
[X]
E [X |X| 2 M Pr|| 2 4l]
Pr||X < 10] + ue- |Pr|X; 2 (1] Pr[x; S -(e]
Pr |r||X|| < M2]
= -|[[X,] - E [X X, 2 Pr|[X. > 18] 18. |Pr[X 2 18] - Pr(X, -l8l
=| [X.] 2 49] Pr||X,| 2 [4] + 16- [Pr[X; > 10) Pr|X; < -16]
where te. |Pr[X > sl] - Pr(x; < -tl] S tl- Pr[|X > $1/5/88)227) The first inequality by considering the two conditions |X, < tl and [X,] 2 fl, then taking a triangle inequality.
The first and second equations are by definition of XY, The third equation is a straightforward
computation. The last equation is due to E[X.] = O. By Lemma 3.1 for every integer a,
E| B||x,|Va/s
Pr [|x 2 al/r2| = Pr X Va/s 2 (at/r (at/r3)
(at/r2)va/s S 4-/8
The first equality is straightforward The first inequality is by Markov. The second equality is by of va/s which follows from Lemma 3.1 and a rearrangement of parameters, 4rz
E||x,|| va/8| where r is the parameter in Lemma 3.1 Therefore,
[E[
|X, 2 x4] Pr||X.| 2 14 <
X |X,|| 2 PrI|X 2 tc]
S (t+ )e Pr[|X:| 2 El| +
Σ
Pr||X.| 2 al/r?]
integer 2t
x 4
$ +
/ ). 2D
+1
vafi da
tra
1
8
16
< l
(1+
2D
2
In
16

---

The first inequality is by the property of absolute value. The second inequality is because we divide the event [X,] 2 tl into [X, E Jalfr² (a + 1)8/r"), = tr² + 1,... and when [X, E [al/r3, (a + 1)e/r²), [X, < (a 1)e/r². The third inequality is by pluging in the previous bound for Pr[[X,] 2 a./r9. The last inequality by a calculation of the integral.
By plugging in parameters t, 6. D 2 max[@(E (1/6)), ( 2og(1))))))))) we have ||||||| < dl. Note that the (D) hides constant Denote o² as the variance of X So 648/r² by Lemma 3.1
Lemma C.1 (Bernstein's Inequality). Let X1,.,, XD be independent zero-mean random variables. Suppose that X S M, Vi, then for all positive t
D X:
8// Mtt33+ + (TMt/3+
(-
Pr
2
S exp
ER=EE EXX?1
Applying Bernstein's Inequality to X
D
DEED
Pr
Σ
x
DE[X]] 2 (cel/o') cxxp (T cte + 20
CE2
2ee2
S max
exp
exp
2t
40 /
Since D 2 max (0 log(1 θ (s-2 log (1/8)) we have Pr
Li=l X Ell/o')
5
6/2. With ف probability, every X; S th, X X, Therefore, Pr
Σ Ei=1 X, 2 D(ō + :){ S
5/2. Combine it together, Pr|| dist, (z. y) dist (z. v)1 S E dist (z, v) 2 1-
D PROOF OF THEOREM 3.1
Theorem 3.1 (Generalization of Makarychev al. 2019 problem with Eg -boobjective whose kernel function K R x Rd + R is shift-nnvarian and analytic at the origin, for every data set P C Rd, the RFF mapping D = M(p log² k a + & + +p²)/E² satisfies
Theorem 3.6). For kernel k-clustering
Rd + R D with target dimension
1
Pr[Vk=-parittin of P cost. (P,C) E E (1+ cost p
(PPC)) 1
The proof relies on key notion of (s,8, pddimensioon reduction from (Makarychev et al. 2019 and we adopt with respect to our setting/land eetting/lngguae of kernel distance as follows.
Definition D.1 (Makarychev et al. 2019 Definition 2.1). For e, Rd + H for some Hilbert space H. random mapping Ta, Rd - IR is an (8, p)mm reduction, if
p > 0, a feature mapping y :
for every x, Rd. at least - 8, and
I+5 dist,(ar (i,t v) S (1 + e) dist,, (2. v) with probability
for every fixed p o0), E (dist, (1a9))))) dx.t,,
d (x.9))
(1 + =})] s p-
In Makarychev et al. 2019). most results are stated for particular parameter setup of Definition D.1 resulted from
transform (Johnson & Lindenstrauss) 1984). but their analy- sis actually works for other similar parameter setups. The following is a generalized statement of (Makarychev et al., 2019 Theorem 3.5) which also reveals how alternative parameter setups af- fect the distortion. We note that this is simply a more precise and detailed statement of (Makarychev) ct al. 2019 Theorem 3.5), and it follows from exactly the same proof in Makarychev et al. (2019).
Lemma D.1 (Makarychev et 2019 Theorem 3.5). Let < E, min-:20-1--0--11222
and 0 (++I))++) ase/((00(( e) Ap-1), 1/10Pt1]. If some (c, 5, didmmensioo reduction
17

---

for feature mapping Rd - H of some kernel function functionn satisfies 8 I min(6" /600, 8/k), (+)
2 P S 0, then with probability at least - a. for every partition C of P.
cost, " p (P.C) S (1 (1+ +e)+ 3)0 cost 8 p (P,C);
(1 - cost & (P.C) - (1 (1+ +++++) 3p-1 cost, TI (P.C).
pd log + p /ee, the RFF map- (c, p) dimension reduction In fact, Theorem 1.2 already implies such π satisfies that for every 2, y E R T+e (a, y) I dist=(x,)) y) I (I+ E) dist,p 3) with probability at least 1 8, where For the other part,
Proof of TThhorem...1 We verify that setting D = @ _o2
ping π with target dimension D satisfies the conditions in Lemma D.I namely,
1
5 = eof((E for some constant and f(e, D) == max eD/
dist (2), y)
E
dist,
distup (xr, 4)2
(1 + E)P
(2,
((1 + +t) t =)
Pr
t
(I.t)(FI.))
dist, (1st,x y)
mm=+00
1- m) +(1 Pr
+
dist (22. y)
m=c
dist (1.
p(1 + t)p-1 Pr
> 1 df
(integration by part)
distip (zz y)
dist.r (3r, > t + 1 dt (x.
p(1 t)
p(1 1-0--1---1(00 dt.
Where the third equality follows by Pr dist, (a.wy)
dist (2.0) m) decays exponentially fast with respect to
m. Observe that for p 2 1, > (p- p(1 t)p- è -atttt/ /2 decrease when e, and for (p-
D > e(p-1) 1)
2 D/2 decrease when t 2 s. Hence for 2 max +(1++)p t)r-le -e-
1) <(p-1)
have
p(1 1 dt dt { -cffL.D)/2dt <dc ccce-ctie.D11
In conclusion, by setting O(og + pd log + p0)2 for d -ef(e) p= .
-e((s.))
and f(s, D) = max 1/13 it satisfies < min(@ /600, 0 /k), ( < . s 0. This verifies the condition of Lemma [I.1
Finally, we conclude the proof of Theorem 3.1 by plugging e' = c/3p and the above mentioned RFF mapping with target dimension into Lemma D.I.
E PROOF OF THEOREM 4.1
Theorem 4.1. Consider A Z p> O, and shift-invariant kernel function K : Rdd TR denoting its feature mapping & Rd - H. Then there exists x, y E RRd that are (A, p)-bounded, such that for every 0 the RFF mapping π for K with target dimension D satisfies
22 ds d (D- (2)
Pr[] (ast,tt,,,, y) dist (z. v) 2 e (x,
2 be 011/2.00
sup,,,, hooumded (x), and sK (x) = 1 K((x) 2K(x)²
where 8 (A.P)
2(1 (x())
Proof. Our proof requires the following anti-concennratiin inequality.
18

---

Lemma E.1 (Berry 1941|
Esseen 1942). For ii.d. random variables R with mean 0 and Ei=1 Eo then for any 1,
variance 1, let X
VD
1
Pr[X 2 12
ds ds
v 2T
Let X1(x) == cos)) 2) -))))
(ar((X()))) [+K(2(Z)) (k(
choose æ, y such
2
()))) Clearly, such pair of æ, y satisfies that (x y) is (A, p) bounded. In fact, it is without loss of generality to assume that both a and y are (A, p)- bounded,, since one may pick y. We next verify that such 2, y satisfy our claimed
that sk (x- - y)
y' x' = y and still have x' -y properties. Indeed,
Pr[] dist (I, y) dist (z, 1) 2 dist (z., v)l pist (Ir, y)² dist (I,, (), > 68 dist (1. y)
2
PPr
x1(x
y) 2 6e(22 2K 5))
D
D
VD o(x y)
Pr
Σ
X1(x - y) 2 6e(1 K(x y))
VD -0 y)
1=1
2 0(2-1/2)
2
100
1/ ds
2
66e(1-Ko ((z=-)))VDDo
0(D-1/2)
2
2/2 ds.
v 2 JBe /D///
where the second inequality by Lemma E.I and the the second-last equality follows from the definition of s (-), and that of 2, y such that sx(r y) K
(A.p)
F BEYOND RFF: OBLIVIOUS EMBEDDING FOR LAPLACIAN KERNEL WITH SMALL COMPUTING TIME
In this section we show an oblivious feature mapping for Laplacian kernel dimension reduction with small computing time. The following is the main theorem.
Theorem F.1. Let K be Laplacian kernel with feature mapping ş Rdd - H. For every 0 < 5 e S 2-16, every d, D E N, there is mapping π Rdd + RD, such that for every 2, y IR that are (A, bbboodeddd
max log" (0gg())/)) O(e log(1 log(1/6)) 16)]], every A 2 p > 0,
(x. Pr[l dist, (x. u) - dist, w)1 S e dist, (x, v)1 2 1 - 5.
The time for evaluating π is d.D (log à log 8 8-1).
For simplicity of exhibition, we first handle the case when the input data are from Nd. At the end we will describe how to handle the case when the input data from IRd by simple transformation. Let N E N be s.t. every entry of an input data point is at most N. Even though input data are only consisted of integers, the mapping construction needs to handle fractions, as we will later consider some numbers generated from Gaussian distributions or numbers computed in the RFF mapping. So we first setup two numbers, A' poly(N, 8 8-1) large enough and p' 1/ poly(N, 8-1) small enough. All our following operations are working on numbers that are (A' p bbounddd. Denote p as Po for convenience.
EMBEDDING FROM & TO f
Now describe isometric embedding from & norm to E. This construction is based on Ka- hane (198I), in which the first such construction of finite dimension was given, to the best of our
knowledge. Let m. N R be such that for every & E N, & N, m (x)ls 1, if [1, and
19

---

T (x][5} otherwise. Let "1 (d) have T (x) being the concatenation of vectors Tı (rz). i E [d].
(d) N4 + R.Vd be such that for every x E No, 2j N, Vi [d].
we we
Lemma F.1. For every E No with zi, - N, E [d] it holds that
(4) (a) 1 (4) || vll = ||
(v)
Proof. Notice that for every i E [d], TT (2:) has its first entries being 1 while Ii (14) has its first ya entries being 1. Thus || (2rz) Ti (yx) 12 exactly || Vill1- If we consider all the dimensions,
then by the construction of _ (d) the lemma holds.
F.2 FEATURE MAPPING FOR LAPLACIAN KERNEL
Notice that we can apply the mapping मं and the RFF mapping e from Theorem 1.2 for the kernel function exp(- || y v which is actually Gaussian kernel. This gives mapping which preserves kernel distance for Laplacian kernel. To be more precise, we setup the mapping to be π = Φ (d) The only drawback is that the running time is high, as in the above mapping we map d dimension to dN dimension. We formalize this as the following theorem.
Theorem F.2. Let K be Laplacian kernel with feature map y : Rd + H. For every 8 S E 2-16 every d, N N, D max (0 -1 log (1/8)), (0gg((((e=1(()) log(1/6))}, there exists mapping T: Rdd + R.D s.I. for every I, E No. x. < N, (x, v) dist. (z, v)I S d 2 1 5. The time of evaluating n is O(dDN).
Proof. Consider the map defined above. It follows by Lemma F. and Theorem 1.2 The running time is as stated, since we need to compute a vector of length (NN) and then apply the RFF on this vector.
The time complexity is a bit large, since we need to compute "1 which has a rather large dimension dN. Next we show how reduce the time complexity.
F,3 AN ALTERNATE CONSTRUCTION
We give the following map n' which has the same output distribution as that of π & o T Then in the next subsection we will use pseudorandom generators to replace the randomness in a' while using its highly efficiency in computation reduce the time complexity. Notice that in computing ó o T for each output dimension, the crucial step computing (w, ((f) ((f) (z)) for some Gaussian distribution w E Rd which has each dimension being an independent gaussian distribution wo- The final output is a function of (w, _ (x)). So we only need to present the construction for the first part, i.e. the inner product of an N dimension Gaussian distribution and स (21).. For the other parts the computations are the same and finally we only need to sum them up. Hence to make the description simpler, we denote this inner product (w, nı (a:)). where now we let E N, S N and w has N dimensions each being an independent wi-
Let h be the smallest integer s.t. N < 2hh Consider binary tree where each node has exactly children. The depth is h. So it has exactly 2hh 2 N leaf nodes in the last layer. For each node we attach random variable a, in the following way. For the root, we attach Gaussian variable which is the summation of 2 independent Gaussian variable with distribution wo. Then we proceed layer by layer from the root to leaves. For each u, v being children of a common parent w, assume that aw is the summation of 2 independent Wo distributions. Then let au be the summation of the first 21-1 distributions among them and a, be the summation of the second 2 distributions. That is Ow au + aa with Oaa, ar being independent. Notice that conditioned the value with probability Pra..a. iid Ja,, = b au + a. = a). a, takes the value a - when au takes value b.
a = a, then a takes
The randomness for generating every random variable corresponding to node, are presented as a sequence, in the order from root leaves, layer by layer, from left to right. We define a² to be
20

---

the summation of the random variables corresponding the first leaves. Notice that a can be sampled efficiently in the following way. Consider the path from the root to the z-th leaf. First we sample the root, which can be computed using the corresponding randomness. We use variable to record this sample outcome, calling z an accumulator for convenience. Then we visit each node along the path. When visiting v, assume its parent is wo, where Owr has already been sampled previously with outcome a. If v is a left child of w. then we sample O, conditioned on aw a. Assume this sampling has outcome Then we add -a + the current accumulator 2. If u is right child of node w. then we keep the current accumulator unchanged. After visiting all nodes in the path, is the sample outcome for a"
Lemma F.2. The joint distribution a", x 0, 0,1, ,, N has the same distribution as (w, nT ( 0, O.I....,N.
Proof. According to our construction, each leaf is an independent distribution wp. Hence if we take all the leaves and form a vector, then it has the same distribution as w..
Notice that for each parent w with two children u, v, by the construction, Oh = Ou + ag. Here Ou Ovy are independent, each being summation of independent wo. with / being the number of leaves derived from u. Thus for each layer, for every node u in the layer, o2 's are independent and the summation of them is their parent. So for the last layer all the variables are independent and follow the distribution wio- And for each node w in the tree, Ow is the summation of the random variables attached to the leaves of the subtree whose root is w. So a is the summation of the first leaf variables.
We do the same operation for other dimensions of the output of mj (d) and then sum them up to get an alternate construction x' for ग ②b i (d)
We note that to generate an ap, we only need to simulate the conditional distributions. The distri- bution function F of the random variable is easy to derive, since its density function is product of three Gaussian density functions, i.e.
Pr [a., b bb au + a, al Ou iid.
Pr. Ou kid.
1a,, b, a. b)/
[a, a2 Pr Ou hid.
Pr[aa = b] Pr(a.-
b//
Pr
[aku +a a],
au,an Lid.
where ag Og are Gaussians. To compute F we can use the taylor expansion of its density function to get an analytical form of F. and the evaluation then can be computed in time t, poly(p) "). Recall that Pu is defined to be p'/D'. . To sample au, we use T = Ollog (aloogPp')) uniform random bits to generate a number p uniformly with precision poly(p; ') small enough. Then we use binary search to figure out an b such that F(b) E [p- Ep. + En]. for some small enough En poly(po). and the space used is s, poly log(p5))
We remark that simulating a distribution using uniform random bits always has some simulat- ing bias. The above lemma is proved under the assumption that the simulation has no bias. But we can see that the statistical distance between the simulated distribution and the origi- nal distribution is at most poly (po) 1/ PN)y(N), which is small enough by our picking of A' poly(N, 5_ = 11poly((N) (N, 8-1.. So if we consider simulation bias, then we can show that for every subset S C
... the joint distribution a", I E S has a statistical distance O(1S)so) to the joint distribution (w, π (Ix)), x E S. Later will only use the case that |S| 2, i.e. two points. So the overall statistical distance is @11(1) which does not affect our analysis and parameters.
F.4 REDUCING THE TIME COMPLEXITY USING PRGS
Next we use pseudorandom generator to replace the randomness used in the above construction. A function G {0, 13" + {0.1)" a pseudorandom generator for space computations with error
parameter Eg. for every probabilistic TM M with space s using n bits randomness in the read-once manner
|Pr [M(G(U.) = 1] Pr (M,) 1] S Eg.
Here is called the seed length of G.
21

---

Theorem F.3 Nisan 1992). For every NN and E N. there exists an pseudorandom generator G {0, 1 + {0, 1 for space s computations with parameter Eg. where r = Ollog n(log n + s + +loog 1 )). G can be computed in polynomial time (in n, T) and O(T) space. Moreover, given an index i E [r)], the i-th bit of the output of G can be computed in time poly(r).
Let G: (0. 13 + , 2dDNT be a pseudorandom generator for space 8 = ci (log N *++,); with , = 6/2, r 02 log N for some large enough constants c1. C2. Again we only need to consider the construction corresponding to the first output dimension of 600T1 1. We replace the randomness Ug used in the construction by output of G. That is, when need r uniform random bits construct a distribution Og in the tree, we first compute positions of these bits in Ug and then compute the corresponding bits in the output of G. Then use them to do the construction in the same way. We denote this mapping using pseudorandomness as our final mapping n².
Now we provide a test algorithm show that the feature mapping provided by the pseudorandom distribution has roughly the same quality as that of the mapping provided by the true randomness. We denote the test algorithm as T TK,,.y. where x, y E I2 and K Laplacian kernel with feature mapping sp. T works as the following. Its input is the randomness either being U/ or G(U,). T first computes ( y). Notice that actually does not have compute & since the distance can be directly computed as /2 - 2K (z. v). Then T(G(U,)) computes dist,- (z, y) and test dist (z, v) (2,, y)1 S e dist,p(1r,) v). Notice that when the input is Uc. then this algorithm T is instead testing
| cistt (z, y) dist.p (2r, v)1 S (dishp(rr v).
Recall that n' is defined in the previous section as mapping using true randomness.
Next we consider using T on true randomness.
Lemma F.3. Pr(T(U:) = 1] > 1 5/2.
Proof. By Lemma R2 dista (x., v) - dista (x,, v). By Theorem 1.2 setting the error probability to be 8 8/2, we have
Prildist, (2, (as b)l S E dist y) 2 1 8822.
Notice that the event T(U:) = 1 is indeed |dist (2. v) disl (I, v)1 S E dist (2, v). Hence the lemma holds.
Now we show that T is actually a small space computation. Lemma F.4. T runs in space c(log N 87) for some constant and the input is read-once.
Proof. The computing of dist,, (z. y) is in space Olog N), since x, E N, x, S N and the kernel function K can be computed in that space. Now we focus on the computation the construction of a in section F33 n' can be computed using space O(s, + log N). The procedure proceeds as the following. First finds the path to the r-th leaf. This takes space Olog N). Then along this path, for each node we need to compute distribution au. This takes space ((s,). Also notice that since the randomness is presented layer by layer, the procedure only needs to do a read- once sweep of the randomness. T needs to compute n' for both x and y, but this only blow up the space by 2. So the overall space needed is as stated.
n². We claim that by
Finally we prove our theorem by using the property of the PRG.
Proof of Theorem E. We first show our result assuming x. E N, n y S N for an integer N. We
claim that nt the mapping we want. By lemma F3 Pr(T(U:) = 1] 2 1 5/2. By Lemma F.4
T runs in space Olog N + s,) and is read-once. As G for space c(log N + s,) for some large enough constant c,
[P(T(( 1] - Pr(((P)) where seed length r = OllggdDDN /E,) loo()loodDDDi) Notice that T(G(U,)) = is equivalent to dist,- (I, y) - (x,t,(
& Eg.
dist (x, y). Thus
Pr[ dist,,- (s, v) dist (2,, v) dist, (2, w) 2 5/2 Eg 1 8.
22

---

The running time is computed as the following. We only need to consider one dimension of the input data and one output dimension of the mapping, since others can be computed using the same time. So actually
consider the time for sampling a". For a", recall that visit the path from the root to the æ-th leaf. We don't have to compute the whole output of G, but instead only need to use some parts of the output. For sampling each variable on along the path, we use bits in the output of G. By Theorem [33, the computing of each random bit in G's output, given the index of this bit, needs time poly(r). Locating the T bits of randomness for generating 0g needs time Olog N). Generating each of the Gaussian random variable using these random bits needs time t,- Summing up these variables takes less time than sampling all of them. After sampling. the cosine and sine function of the RFF can be computed in time poly (1/ po) poly(log N, N,O''), There are d input dimensions and D output dimensions. So the total time complexity is dD poly N, 8,1
For the case that I, y E Rd, we only need to modify the embedding ( in the following way. We first round every entry so that their decimal part now finite. The rounded parts are small enough (e.g. dropping all digits after the 10 log -th position to the right of the decimal point.) such that this only introduce some small additive errors. Then we shift all the entries to be non-negative numbers by adding common shift Then we multiply every entry of z by common factor f s.t. every entry now only has an integer part. Notice that and s can both be chosen according to A for example
s = ( And we can take N be poly( ). Then we apply Ti, and multiply factor / I/t. Denote this map as #1. Notice that this ensures that ||æ - yll = || (x) 7((0) (v) Then we can apply the same construction and analysis we did for the above natural number case. This shows the theorem.
G REMARKS AND COMPARISONS TO CHEN & PHILLIPS (0017)
Our upper bound in Theorem 1.2 is not directly comparable to that of Chen & Phillips (017) which gave dimension reduction results for Gaussian kernels. Chen & Phillips| (2017) showed in their Theorem 7 a slightly improved target dimension bound than ours, but it only works for the case of || -01 2 a, where is the parameter in the Gaussian kerne For the other case of || - yll a, their Theorem 14 gave a related bound, but their guarantee is quite different from ours. Specifically, their target dimension depends linearly on the input dimension d. Hence, when d is large (c.g.. d = log* nt), this Theorem 14 is worse than ours (for the case of | yll
Finally, we remark that there might be subtle technical issues in the proof of [CP17]. Their The- orem 7 crucially uses a bound for moment generating functions that is established in their Lemma 5. However, we find various technical issues in the proof of Lemma 5 (found in their appendix). Specifically, the term -/==s/="IAIIP in the last line above "But" (in page 17), should actually be B((+11) Even if one fixes this mistake (by negating the exponent), then eventually we can only obtain a weaker bound of In (s) < e
4 |||| + s||A| in the very last step, since the term -s| ->|A A 1 is negated accordingly. Hence, is not clear if the claimed bound can still be obtained in Theorem 7.
Thii condition is not clearly mentioned in the theorem statement, but is indeed used, and is mentioned in line above the statement in Chen & Phillips (017)
23


Reviews:
[{"review_id": "vU4ydV0c1OZ", "reviewer": "Reviewer_pJCZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies dimensionality reduction techniques for estimating the kernel distance up to a (1+eps)-factor. First, the paper shows one can sample the random Fourier features to preserve $\\Vert\\phi(x) - \\phi(y)\\Vert_2$, where $\\phi$ is the feature map such that $\\langle \\phi(x),\\phi(y)\\rangle = K(x,y)$ for some shift-invariant and analytic kernel $K$ and then applies to kernel k-means clustering. Then the paper shows a lower bound on the target dimension, which depends on the ‘condition number’ of the point set. The earlier upper bound requires the kernel function to be analytic at the origin, which excludes the Laplacian kernel. To remedy for this, the paper uses the fact that an $\\ell_1$ metric space can be embedded into a metric space of metric $\\Vert x-y\\Vert_2^2$, thus turning the dimensionality reduction for a Laplacian kernel into that for a Gaussian kernel, for which the earlier random Fourier feature sampling scheme applies. ", "summary_of_the_review": "This is a solid and neat paper. I do enjoy reading it and would recommend accepting it. But I am not sure if ICLR is the correct place. Theoretical conferences may be more suitable, such as AISTATS, ICALP, ESA, RANDOM, ...", "strength_and_weaknesses": "Strengths: Giving dimensionality reduction results for distances induced by shift-invariant kernels, where the kernel is analytic or a Laplacian kernel. The idea is simple (which is good) and some parts of the proof are nontrivial.\n\nWeaknesses: It is not entirely convincing that the method for the Laplacian kernel is a bigger framework for other kernels. The bound $\\max\\{\\epsilon^{-1}\\log^3(1/\\delta), \\epsilon^{-2}\\log(1/\\delta)\\}$ looks less satisfying.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "pTdHxXDK-y-", "reviewer": "Reviewer_vUht", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies when Random Fourier Features (RFF) is able to create a Johnson-Lindenstrauss-like result for preserving the distances between the feature mappings of vectors given a shift-invariant kernel. Prior work emphasized different metrics, like getting an additive error guarantee on the pairwise distances, instead of more JL-like relative error guarantees. This paper really focuses on relative error guarantees.\n\nThree core results are shown:\n1. Suppose a kernel is both shift-invariant and analytic near zero (i.e. kernel is very smooth when it's two input are equal). Then, RFF give a relative error guarantee with a standard $O(\\frac{1}{\\varepsilon^2})$ sample complexity for fixed failure probability. It has a polylog dependence on failure probability where the additive error guarantees have just a log dependence, I believe.\n1. Suppose a kernel is shift-invariant but not analytic near zero, like the Laplacian kernel $K(\\vec x, \\vec y) = e^{-\\|\\|\\vec x - \\vec y\\|\\|_1}$. Then, RFF for all such kernels cannot give relative error guarantees in general. If we assume the input vectors cannot be arbitrarily close to each other, then relative error guarantees become possible. Roughly speaking, two vectors being arbitrarily close to each other corresponds to approaching the non-analytic part of the shift-invariant kernel, which makes relative error estimation hard.\n1. For the Laplacian kernel, a new algorithm is proposed that achieves relative error pairwise distance embedding, but not via RFF. This algorithm relies on embedding an $\\ell_1$ space into a very very high dimensional $\\ell_2$ space, runs RFF in some way on that $\\ell_2$ space, and uses pseudo-random generators to make this computationally efficient.", "summary_of_the_review": "## Summary\n\nThe paper has cool results, but is somewhat lacking in some parts of the presentation. The first results is clear and compelling. The second is compelling but a bit less clear, and the third result isn't clear at all since it's not in the body of the paper.\n\nNevertheless, the clear and compelling parts are absolutely strong enough to merit publication.", "strength_and_weaknesses": "The paper has some really cool results in it. The first 5 pages were a really nice outline of new ideas in thinking about when and why RFF can embed pairwise distances within relative error. The first two major results, at I outlined them in the last box, are really cool and clean. Despite the issues the paper has, which I will discuss momentarily, I think those two results are strong enough to accept the paper.\n\nThere's a nice logical flow the the proofs in the paper, so my review will follow that flow.\n\n## 1. RFF gets relative error for analytic shift-invariant kernels\n\nThe proof is a nice and intuitive statement, complete with a good sample complexity. The high level proof proceeds in three parts: use complex analysis tools to say that being analytic implies a good moment bound on each RFF feature; use being analytic to prove that the kernel has restricted strong convexity about 0; and combine these results in a fairly standard concentration argument. The burden of the proof lies in the first claim -- the moment bound -- which is proven in the appendix and I did not review in detail. Despite this, the message is pretty clean -- the proof clearly and strongly uses being analytic to create geometry that makes RFF give good accuracy near zero.\n\nI suspect there is a very nice corollary to this relative error result, where an epsilon-net argument can give a whole subspace embedding via RFF; proving something akin to the results in [Avron et al, 2017] but with standard RFF sampling and with the regularization parameter set to zero. I'd like to know if the authors ever considered such a guarantee?\n\nI don't know why the authors chose to prove the concentration argument underlying this result on page 6 of the paper. I checked the details, and I have a minor technical concern I'll ask later, but overall it doesn't feel very enlightening to read. Consider making a short paragraph describing the proof, pushing the details to the appendix, and recovering a bunch of space that could be used to describe the third result in the body of the paper (I'll elaborate what I mean by this later).\n\nEither way, first result it cool and clear. All in favor.\n\n## 2. RFF is incapable of relative error embedding for non-analytic kernels\n\nThe key proof under this claim is really simple, and just follows from the asymptotic Gaussianity of individual the RFF features (formalized via the Berry-Eissen theorem). The authors prove that all shift invariant kernels have failure probability that depends on the ratio of the standard deviation of an RFF feature to the mean value of an RFF feature, formally denoted by $s_k$ in Theorem 4.1 on page 7. When we allow two input vectors to get arbitrarily close to each other, this ratio is well controlled for analytic kernels, but may be arbitrarily bad for non-analytic kernels.\n\nSomewhat frustratingly, in Remark 4.1 at the bottom of page 7, the authors intuitively argue why this ratio is bad for Laplacian kernels and good for analytic kernels, but do not include a formal proof. Their description makes it sound pretty easy to prove, but it really should be formalized in the appendix. A concern I have is about the hardness of _other_ non-analytic kernels. Without that proof in the appendix, it's not immediately clear to me how many other non-analytic kernels will suffer the same hardness condition. Can we state an condition on (e.g.) the Laurent coefficients of a kernel that implies RFF is incapable of giving relative error?\n\nEither way, it's a pretty intuitive big picture, but is lacking detail in the formalization.\n\n## 3. Pseudorandom generators and fancier ways to make JL-style guarantees for the Laplacian kernel\n\nThis result is not really described within the body of the paper. It's discussed for 5 paragraphs in the introduction (\"Going beyond RFF\" on page 3). But that's it. The rest is fully described in 4 pages of the appendix. I don't have spare time to review that unfortunately, so I actually have no idea how it really works or how correct it seems. 5 paragraphs of introduction ain't a lot. I'd say the proof on page 6 of the paper should be appendicized. Maybe even cut out the experiments entirely (though I realize other ICLR reviewers may not agree with this). Then the authors could fit the third contribution within the body of the paper.\n\nI can't judge how correct it is, but it would be cool if it was correct, I guess?\n\n## Smaller Notes and Judgements\n\nSection 3.2 on page 7 is a short blurb about improved sample complexity for kernel clustering. The result is neat, I guess, but is not well contextualized within the world of prior work. They also call their metric an $\\ell_p$-objective, where the norm really is $\\|\\|\\cdot\\|\\|_2^p$, which would not usually be called an $\\ell_p$ norm. Pick a new name for it, maybe call it an $\\ell_2^p$-objective?\n\nSimilarly, I know that prior work on RFF like algorithms have cared about certain kinds of relative error guarantees, like in [Avron et al, 2017]. While these are cited in the paper, the results here are not well contrasted against the prior work. This is clear in Section 1.2, which is basically a block of citations without any discussion of similarity. Why does their notions of relative error subspace embedding not extend to the authors' setting? (Formally, make a subspace embedding via RFF or RFF-LS for a 2x2 kernel matrix, and see if that subspace embedding guarantee implies a relative error pairwise guarantee like what the authors are aiming for; I can clarify if this description isn't clear).\n\nIn the experiments, the authors use SVD as an algorithm to attempt to preserve pairwise distances. Why is this a benchmark? Do people really use low-rank approximation algorithms to preserve pairwise distances? This feels intuitively doomed to fail. Also, if you run an algorithm for 20 iterations, could you include measures of confidence intervals in the plot? I'm personally a fan of plotting the medians with 25th and 75th quantiles, but anything that gives a sense of typical variation would be nice.\n\nTheorem 1.4 isn't clearly phrased. The theorem clearly creates a mapping $\\pi$ which has dimension $D$ which does not depend on the precision $\\frac{\\Delta}{\\rho}$, but the first sentence after the theorem clearly sets the dimension depends on $\\log \\frac\\Delta\\rho$.\n\n## Summary\n\nThe paper has cool results, but is somewhat lacking in some parts of the presentation. The first results is clear and compelling. The second is compelling but a bit less clear, and the third result isn't clear at all since it's not in the body of the paper.\n\nNevertheless, the clear and compelling parts are absolutely strong enough to merit publication.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Hok4_Y-kMPM", "reviewer": "Reviewer_KzPf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the relative error of kernel distances when applying the Random Fourier Features (RFF) to the shift-invariant kernels. While a prior work studied only the Gaussian kernel, this work generalizes the prior results to more general shift-invariant kernels. In particular, the authors show that poly(eps*log(n)) features are needed to guarantee the eps-relative errors for all the n data points. They also study a lower bound on the number of features for the Laplace kernel and show that it can be unbounded when an input has a huge magnitude-resolution ratio. In addition, they show that the RFF takes a better bound on the feature dimension on the k-means clustering compared to the Nystrom method. Finally, they provide an alternative embedding for the Laplacian kernel that requires a time in poly-log of the magnitude-resolution ratio. Experimental results evaluating the relative kernel distance under synthetic datasets are provided.\n", "summary_of_the_review": "This paper extends the prior work on the Gaussian kernel to general shift-invariant ones. But, their result is worse than the prior one and technical tools are also very similar. The writing quality needs to be improved and experimental results do not well support the benefit of the RFF on the kernel distance.", "strength_and_weaknesses": "Strength:\n\n- This work extends a prior result on the Gaussian kernel to general shift-invariant kernel distances. They also study for the Laplacian kernel the bound of the number of features can be unbounded.\n- The authors characterize that the kernel distance guarantee can be used for bounding the k-means clustering.\n- They propose an alternative embedding for the Laplacian kernel beyond the RFF. As a result, it requires the number of features poly-log in the magnitude-resolution ratio.\n\n\nWeakness:\n\n- This paper basically improves the work of (Chen and Phillps, 2017), by generalizing the results to general shift-invariant kernels. However, importantly, the proposed result is worse than that of (Chen and Phillps, 2017), which only focuses on the Gaussian kernel. This makes the contributions weak. \n- The results of the upper bound and lower bound have a different notion, i.e., the magnitude-resolution ratio only appears in the lower bound. This makes it hard to compare those bounds. Can the upper bound involve in this ratio?\n- Experiments only show the relative errors on the synthetic datasets. Since the RFF has been used in many practical applications, I think more experiments should be addressed. For example, showing the k-means clustering results and comparing the Nystrom method under real-world datasets would be nice.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster