Entrywise error bounds for low-rank approximations of kernel matrices

Authors: alexander  modell
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 12:05:48

Abstract: In this paper, we derive *entrywise* error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition (or singular value decomposition). While this approximation is well-known to be optimal with respect to the spectral and Frobenius norm error, little is known about the statistical behaviour of individual entries. Our error bounds fill this gap. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues, which takes inspiration from the field of Random Matrix Theory. Finally, we validate our theory with an empirical study of a collection of synthetic and real-world datasets.

Main paper: 
 introduction: 
 Low-rank approximations of kernel matrices play a central role in many areas of machine learning. Examples include kernel principal component analysis [Schölkopf et al., 1998 ], spectral clustering [Ng et al., 2001 , Von Luxburg, 2007] and manifold learning [Roweis and Saul, 2000 , Belkin and Niyogi, 2001 , Coifman and Lafon, 2006] , where they serve as a core component of the algorithms, and support vector machines [Cortes and Vapnik, 1995, Fine and Scheinberg, 2001] and Gaussian process regression [Williams and Rasmussen, 1995, Ferrari-Trecate et al., 1998] where they serve to dramatically speed up computation times.In this paper, we derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition (or singular value decomposition). Entrywise error bounds are important for a number of reasons. The first is practical: in applications where individual errors carry a high cost, such as system control and healthcare, we should seek methods with low entrywise error. The second is theoretical: good entrywise error bounds can lead to improved analyses of learning algorithms which use them.For this reason, a wealth of literature has emerged establishing entrywise error bounds for a variety of matrix estimation problems, such as covariance estimation [Fan et al., 2018 , Abbe et al., 2022] , matrix completion [Candes and Recht, 2012, Chi et al., 2019] , phase synchronisation [Zhong and Boumal, 2018, Ma et al., 2018] , reinforcement learning [Stojanovic et al., 2023] , community detection [Balakrishnan et al., 2011 , Lyzinski et al., 2014 , Eldridge et al., 2018 , Lei, 2019 , Mao et al., 2021] and graph inference [Cape et al., 2019 , Rubin-Delanchy et al., 2022] to name a few.• Our main result (Theorem 1) is an entrywise error bound for the low-rank approximation of a kernel matrix. Under regularity conditions, we find that for kernels with polynomial eigenvalue decay, λ i = O(i -α ), we require a polynomial-rank approximation, d = Ω(n 1/α ), to achieve entrywise consistency. For kernels with exponential eigenvalue decay, λ i = O(e βi γ ), we require a (poly)log-rank approximation, d > log 1/γ (n 1/β ).• The main technical contribution of this paper is to establish a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues (Theorem 3), the proof of which draws on ideas from the Random Matrix Theory literature. To our knowledge, this is the first such result for a random matrix with non-zero mean and dependent entries.• Along the way, we prove a novel concentration inequality for the distance between a random vector (with a potentially non-zero mean) and a subspace (Lemma 1), which may be of independent interest.• We complement our theory with an empirical study on the entrywise errors of low-rank approximations of the kernel matrices on a collection of synthetic and real datasets.Some complementary results to ours use the Johnson-Lindenstrauss lemma [Johnson and Lindenstrauss, 1982] to bound the entrywise error of low-rank matrix approximations obtained via random projections [Srebro and Shraibman, 2005 , Alon et al., 2013 , Udell and Townsend, 2019 , Budzinskiy, 2024a,b] . In Section 3.2 we discuss these results in more detail and compare them with ours.Our proof strategy draws heavily on ideas from the Random Matrix Theory literature, where delocalisation results have been established for certain classes of zero-mean random matrices with independent entries [Erdős et al., 2009b ,a, Tao and Vu, 2011 , Rudelson and Vershynin, 2015 , Vu and Wang, 2015] . In addition, our result is made possible by recent relative eigenvalue concentration bounds for kernel matrices [Braun, 2006 , Valdivia, 2018 , Barzilai and Shamir, 2023] , which improve upon classical absolute concentration bounds [Rosasco et al., 2010] which would not provide sufficient control for our purposes.We use the standard big-O notation where a n = O(b n ) (resp. a n = Ω(b n )) means that for sufficiently large n, a n ≤ Cb n (resp. a n ≥ Cb n ) for some constant C which doesn't depend on the parameters of the problem. We will occasionally write a n ≲ b n to mean that a n = O(b n ).In addition, we say that an event E n holds with overwhelming probability if for every c > 0, P(E n ) ≥ 1 -O(n -c ), where the hidden constant is allowed to depend on c. 
setup: 
 We begin by describing the setup of our problem. We suppose that we observe n, p-dimensional data points {x i } n i=1 , which we assume were drawn i.i.d. from some probability distribution ρ, supported on a set X . Given a symmetric kernel k : X × X → R, we construct the n × n kernel matrix K, with entries K(i, j) := k(x i , x j ).We will assume throughout that the kernel is positive-definite, continuous and bounded. Let K d denote the "best" rank-d approximation of K, in the sense that K d satisfiesEQUATIONwhere ∥•∥ ξ is a rotation-invariant norm, such as the spectral or Frobenius norm. Then by the Eckart-Young-Mirsky theorem [Eckart and Young, 1936, Mirsky, 1960] , K d is given by the truncated eigen-decomposition of K, i.e.K d = d i=1 λ i u i u ⊤ iwhere { λ i } n i=1 are the eigenvalues of K (counting multiplicities) in decreasing order, and{ u i } n i=1are corresponding eigenvectors.We now introduce some population quantities which will form the basis of our theory. Let L 2 ρ denote the Hilbert space of real-valued square integrable functions with respect to ρ, with the inner product defined as ⟨f, g⟩ ρ = f (x)g(x)dρ(x). We define the integral operator K :L 2 ρ → L 2 ρ by (Kf ) (x) = k(x, y)f (y)dρ(y)which is the infinite sample limit of 1 n K. The operator K is self-adjoint and compact [Hirsch and Lacombe, 1999] , so by the spectral theorem for compact operators, there exists a sequence of eigenvalues {λ i } ∞ i=1 (counting multiplicities) in decreasing order, with corresponding eigenfunctions {u i } ∞ i=1 which are orthonormal in L 2 ρ , such that Ku i = λ i u i . Moreover, by the classical Mercer's theorem [Mercer, 1909, Steinwart and Scovel, 2012] , the kernel k can be decomposed intoEQUATIONwhere the series converges absolutely and uniformly in x, y. 
entrywise error bounds: 
 This section is devoted to our main theoretical result. We begin by discussing our assumptions, before presenting our main theorem and giving some special cases of kernels which fit within our framework.In our asymptotics, we will assume that k and ρ are fixed, and that the number of samples n goes to infinity. This places us in the so-called low-dimensional regime, in which the dimension p of the input space is considered fixed.We shall assume that the eigenvalues of the kernel exhibit either polynomial decay, i.e. λ i = O(i -α ) for some α > 1, or (nearly) exponential decay, i.e. λ i = O(e -βi γ ) for some β > 0 and 0 < γ ≤ 1.We will refer to these two hypotheses as (P) and (E) respectively. We also assume a corresponding hypothesis on the supremum-norm growth of the eigenfunctions. Under (P), we assume that ∥u i ∥ ∞ = O(i r ) with α > 2r + 1, and under (E), we assume that ∥u i ∥ ∞ = O(e si γ ) with β > 2s.Our eigenvalue decay hypothesis is commonplace in the kernel literature [Braun, 2006 , Ostrovskii and Rudi, 2019 , Xu, 2018 , Lei, 2021] , and can be related to the smoothness of the kernel. For example, the decay of the eigenvalues is directly implied by a Hölder or Sobolev-type smoothness hypothesis on the kernel (see, for example, Nicaise [2000] , Belkin [2018] , Section 2.2 of Xu [2018] , Section 5 of Valdivia [2018] , Scetbon and Harchaoui [2021] and Proposition 2 in this paper). We don't consider a finite-rank (say, D) hypothesis, since in this case the maximum entrywise error is trivially zero whenever d ≥ D.Our hypothesis on the supremum norm of the eigenfunctions is necessary to control the deviation of the sample eigenvectors from their corresponding population eigenfunctions, and is a requirement of eigenvalue bounds we employ. In the literature, it is common to see much stronger assumptions, such as uniformly bounded eigenfunctions [Williamson et al., 2001 , Lafferty et al., 2005 , Braun, 2006] , which do not hold for many commonly-used kernels (see Mendelson and Neeman [2010] , Steinwart and Scovel [2012] , Zhou [2002] and Barzilai and Shamir [2023] for discussion). This assumption is reminiscent of the incoherence assumption [Candes and Recht, 2012] in the low-rank matrix estimation literature -a supremum norm bound on population eigenvectors -which governs the hardness of many compressed sensing and eigenvector estimation problems [Candès and Tao, 2010 , Keshavan et al., 2010 , Chi et al., 2019 , Abbe et al., 2020 , Chen et al., 2021] .In addition, we introduce a regularity hypothesis, which we will refer to as (R), which relates to the following two quantities:∆ i = max j≥i {λ j -λ j+1 }which measures the largest eigengap after a certain point in the spectrum, andΓ i = ∞ j=i+1 u j (x)dρ(x) 2 λ i ∥u i ∥ ∞ (P) O (i -α ) O (i r ) α > 2r + 1 (E) O e -βi γ O e si γ β > 2s, 0 < γ ≤ 1 ∆ i Γ i (R) O(λ a i ) O(λ b i ) 1 ≤ a < b/16Table 1: Summary of the hypotheses (P), (E) and (R).which measures the squared residual after projecting the unit-norm constant function onto the first i eigenfunctions. Under (R), we assume that ∆ i = Ω (λ a i ) andΓ i = O λ b i with 1 ≤ a < b/16 ≤ ∞.A sufficient condition for (R) to hold, is that the first eigenfunction is constant. This holds, for example, when k is a dot-product kernel and ρ is a uniform distribution on a hypersphere. In such scenarios, Γ i = 0 for all i ≥ 1 and it is not necessary to make any assumptions on the eigengap quantity ∆ i . We remark that (R) permits repeated eigenvalues in the spectrum of K, which occur for many commonly-used kernels, but which are often precluded in the literature [Hall and Horowitz, 2007 , Meister, 2011 , Lei, 2014 , 2021] .The hypotheses (P), (E) and (R) are summarised in Table 1 . We are now ready to state our main theorem. Theorem 1. Suppose that k is a symmetric, positive-definite, continuous and bounded kernel and ρ is a probability measure which satisfy (R) and one of either (P) or (E). If the hypothesis (P) holds and d = Ω n 1/α , thenK d -K max = O n -α-1 α log(n) (3)with overwhelming probability. If the hypothesis (E) holds and d > log 1/γ (n 1/β ), thenK d -K max = O n -1with overwhelming probability.In this section, we provide some examples of kernels which satisfy the assumptions of Theorem 1. Proofs of the propositions in this section are given in Section A of the appendix. We start with a canonical example of a radial basis kernel. Proposition 1. Suppose k(x, y) = exp -∥x -y∥ 2 /2ω 2 is a radial basis kernel, and ρ ∼ N (0, σ 2 I p ) is a isotropic Gaussian distribution on R p . Then the hypotheses (E) and (R) are satisfied withβ = log 1 + υ + √ 1 + 2υ υ , γ = 1where υ := 2σ 2 /ω 2 .For this example, the eigenvalues and eigenfunctions were explicitly calculated in Zhu et al. [1997] (see also Shi et al. [2008] and Shi et al. [2009] ), and we are able to verify the assumptions by direct calculation.For our second example, we consider the case that ρ is the uniform distribution on a hypersphere S p-1 , and k is a dot-product kernel. In this setting, we are able to replace our assumptions with a smoothness hypothesis on the kernel. Note that this class of kernels includes those which are functions of Euclidean distance, since on the sphere we have the identity ∥x -y∥ 2 = 2 -2 ⟨x, y⟩. Proposition 2. Suppose thatk(x, y) = f (⟨x, y⟩) ≡ ∞ i=0 b i (⟨x, y⟩)i is a dot-product kernel and ρ is the uniform distribution on the hypersphere S p-1 with p ≥ 3. If there exists a > (p 2 -4p + 5)/2 such that b i = O(i -a ), then (P) and (R) are satisfied withα = 2a + p -3 p -2 .Alternatively, if there exists 0 < r < 1 such that b i = O(r i ), then (E) and (R) are satisfied withβ = (p -1)! C log(1/r), γ = 1 p -1 for some universal constant C > 0.In this example, the eigenfunctions posses the property that they do not depend on the choice of kernel, and are made up of spherical harmonics [Smola et al., 2000] . In particular, the first eigenfunction is constant, and therefore (R) is satisfied automatically. The eigenvalue bounds are derived in Scetbon and Harchaoui [2021] , and we make use of a supremum norm bound for spherical harmonics in Minh et al. [2006] .We pause here to consider how our entrywise bounds compare with existing bounds in the literature for low-rank matrix obtained via random projections [Srebro and Shraibman, 2005 , Alon et al., 2013 , Udell and Townsend, 2019 , Budzinskiy, 2024a,b] .For an n × n symmetric, positive semi-definite matrix M with bounded entries, the Johnson-Lindenstrauss lemma [Johnson and Lindenstrauss, 1982] can be used to show the existence of a rank-d approximation M d whose entrywise error is bounded by ε when d = Ω(ε -2 log(n)).The proof is via a probabilistic construction. Let X be an n × n matrix such that M = XX ⊤ , and for some d ≤ n, let R be an n × d matrix with i.i.d. entries from N (0, 1/d). Then, the randomised low-rank approximation M d := XRR ⊤ X ⊤ (4) achieves the desired bound with high probability. Here, we state a adaptation of Theorem 1.4 of Alon et al. [2013] which makes the probabilistic construction from the proof explicit.Theorem 2. Let M be an n × n positive semi-definite matrix with bounded entries, and M d be a randomised rank-d approximation of M described in (4). ThenM d -M max = O log(n) dwith overwhelming probability.To obtain a polynomial entrywise error rate, i.e. O(n -c ) for some c > 0, with Theorem 2, requires the rank d to be polynomial in n. In contrast, under our hypothesis (E), we are able to obtain a polynomial entrywise error rate using a spectral low-rank approximation with only poly-logarithmic rank. In addition, while our entrywise error bounds are o(n -1/2 ) for the cases we consider, this rate can never be achieved, regardless of the choice of rank d, by (4) with Theorem 2.On the flip side, Theorem 2 holds for arbitrary positive semi-definite matrix with bounded entries, whereas our theorem only holds for kernel matrices satisfying the hypotheses in Table 1 .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: The assumptions for the main theorem, Theorem 1, are provided in Section 3 and are summarised in Table 1 . The full proof is provided in Section 4 and additonal technical details are provided in Sections B, C and D. Proofs of Propositions 1 and 2 are provided in Section A. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
proof of theorem 1: 
 In this section, we outline the proof of Theorem 1. Without loss of generality, we will assume that k is upper bounded by one. We cover the main details here, and defer some of the technical details to the appendix. By the Eckart-Young-Mirsky theorem, we have thatK d -K max := max 1≤i,j≤n K d (i, j) -K(i, j) = max 1≤i,j≤n n l=d+1 λ l u l (i) u l (j) ≤ n l=d+1 λ l • max d<l≤n ∥ u l ∥ 2 ∞ .Using a concentration bound due to Valdivia [2018] , we are able to show thatn l=d+1 λ l = O n 1/α log(n) under (P) with d = Ω n 1/α O (1)under (E) with d > log 1/γ (n 1/β ).(5) with overwhelming probability, the details of which are given in Section B of the appendix. Then, the proof boils down to showing the following result, which we state as an independent theorem.Theorem 3. Assume the setting of Theorem 1, then simultaneously for alld + 1 ≤ l ≤ n, ∥ u l ∥ ∞ = O n -1/2 (6)with overwhelming probability.When a unit eigenvector satisfies (6) (up to log factors), it is said to be completely delocalised. There is a now expansive literature in the field of Random Matrix Theory proving the delocalisation of the eigenvectors of certain mean-zero random matrices with independent entries [Erdős et al., 2009b ,a, Tao and Vu, 2011 , Rudelson and Vershynin, 2015 , Vu and Wang, 2015] . Theorem 3 may be of independent interest since to our knowledge, it is the first eigenvector delocalisation result for a random matrix with non-zero mean and dependent entries.To prove Theorem 3, we take inspiration from a proof strategy employed in Tao and Vu [2011] (see also Erdős et al. [2009b] ) which makes use of an identity relating the eigenvalues and eigenvectors of a matrix with that of its principal minor. The non-zero mean, and dependence between the entries of a kernel matrix present new challenges which require novel technical insights and tools and make up the bulk of our technical contribution.Proof of Theorem 3. By symmetry and a union bound, to prove Theorem 3, it suffices to establish the bound for the first coordinate of u l for some an arbitrary index d < l ≤ n. We shall let K denote the bottom right principal minor of K , that is the n -1 × n -1 matrix such thatK = z y ⊤ y Kwhere z = k(x 1 , x 1 ) and y = (k(x 1 , x 2 ), . . . , k(x 1 , x n ))⊤ . We will denote the ordered eigenvalues and corresponding eigenvectors of K by { λ l } n-1 l=1 and { u l } n-1 l=1 respectively. By Lemma 41 of Tao and Vu [2011] , we have the following remarkable identity:EQUATIONIn addition, Cauchy's interlacing theorem tells us that the eigenvalues of K and K interlace, i.e.λ i ≤ λ i ≤ λ i+1 for all 1 ≤ i ≤ n -1. By (5) we have that | λ i | = O(1) for all d + 1 ≤ i ≤ nwith overwhelming probability and so by Cauchy's interlacing theorem, we can find a set of indicesJ ⊂ {d + 1, . . . , n -1} with |J| ≥ (n -d)/2 such that | λ j -λ i | = O (1)for all j ∈ J. Combining this observation with (7), we have thatEQUATION)where π J denotes the orthogonal projection onto the subspace spanned by { u j } j∈J . So, to establish (6), it suffices to show that ∥πJ (y)∥ 2 = Ω(n) (9)with overwhelming probability. We condition on x 1 , so that y is a vector of independent random variables and denote its conditional mean by ȳ, which is a constant vector whose entries are less than one. In addition, each entry of y has common conditional variance which we denote byσ 2 = E x∼F {k 2 (x 1 , x)}.To obtain the lower bound (9), we prove a novel concentration inequality for the distance between a random vector and a subspace, which may be of independent interest. Our lemma generalises a similar result in Tao and Vu [2011, Lemma 43] which holds only for random vectors with zero mean and unit variance. The proof is provided in Section C of the appendix.Lemma 1. Let y ∈ R n be a random vector with mean ȳ := Ey whose entries are independent, have common variance σ 2 and are bounded in [0, 1] almost surely. Let H be a subspace of dimension q ≥ 64/σ 2 and π H the orthogonal projection onto H. If H is such that ∥π H (ȳ)∥ ≤ 2(σ 2 q)1/4 , then for any t ≥ 8P ∥π H (y)∥ -σq 1/2 ≥ t ≤ 4 exp -t 2 /32 .In particular, one has ∥π H (y)∥ = σq 1/2 + O log 1/2 (n) (10)with overwhelming probability.Returning to the main thread, we claim for the moment that ∥π J (ȳ)∥ ≤ 2|J| 1/4 . Then, by Lemma 1 we have that, conditional on x 1 ,∥π J (y)∥ 2 ≳ |J| ≥ (n -d)/2 = Ω(n)with overwhelming probability. This holds for all x 1 ∈ X and therefore establishes (9). To complete the proof, then, it remains to prove our claim, and it is here where we require the regularity hypothesis (R). The proof of the claim is quite involved, so we defer the details to Section D of the appendix, given which, the proof of Theorem 3 is complete.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Code to reproduce the experiments is provided with the submission. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
datasets and setup: 
 To see how our theory translates into practice, we examine the maximum entrywise error of the low-rank approximations of kernel matrices derived from a synthetic dataset and a collection of five real-world data sets, which are summarised in the following table Additional details about the dataset are provided in Section E of the appendix.For the purpose of our experiment, we employ kernels in the class of Matérn kernels, of the formk ν (x, y) = 2 1-ν Γ(ν) √ 2ν ∥x -y∥ ω ν K ν √ 2ν ∥x -y∥ ωwhere Γ denotes the gamma function, and K ν is the modified Bessel function of the second kind. The class of Matérn kernels is a generalisation of the radial basis kernel, with an additional parameter ν which governs the smoothness of the resulting kernel. When ν = 1/2, we obtain the nondifferentiable exponential kernel, and in the ν → ∞ limit, we obtain the infinitely-differentiable radial basis kernel. For the intermediate values ν = 3/2 and ν = 5/2, we obtain, respectively, once and twice-differentiable functions.The optimal choice of the bandwidth parameter is problem-dependent, and in supervised settings is typically chosen using cross-validation. In unsupervised settings, it is necessary to rely on heuristics, and for this experiment, we use the popular median heuristic [Flaxman et al., 2016 , Mooij et al., 2016 , Mu et al., 2016 , Garreau et al., 2017] , which has been shown to perform well in practice.For each dataset, we construct four kernel matrices using Matérn kernels with smoothness parameters ν = 1 2 , 3 2 , 5 2 , ∞, each time selecting the bandwidth using the median heuristic. For each kernel, we compute the best rank-d low-rank approximation of the kernel matrix using the svds function in the SciPy library for Python [Virtanen et al., 2020] . We do this for a range of ranks d from 1 to n, where n is the number of instances in the dataset, and record the entrywise errors.Figure 1 shows the maximum entrywise errors for each dataset and kernel. For comparison, the Frobenius norm errors are plotted in Figure 2 in Section E of the appendix.As predicted by our theory, for the four "low-dimensional" datasets, GMM, Abalone, Wine Quality and MNIST, the maximum entrywise decays rapidly as we increase the rank of the approximation, with the exception of the highly non-smooth v = 1 2 kernel, for which the maximum entrywise error decays much more slowly. In addition, the decay rates of the maximum entrywise error are in order of the smoothness of the kernels.For the "high-dimensional" datasets, 20 Newsgroups and Zebrafish, a different story emerges. Even for the smooth radial basis kernel (ν = ∞), the maximum entrywise error decays very slowly. This would suggests that our theory does potentially not carry over to the high-dimensional setting, and that caution should be taken when employing low-rank approximations for such data. Interestingly, the 20 Newsgroups dataset exhibits a sharp drop in maximum entrywise error between d = 2500 and d = 3000 which is not seen in the decay of the Frobenius norm error (Figure 2 in Section E).Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: All datasets used for the experiments are openly available and a link to the code to reproduce the experiments is provided in Section 5.Guidelines:• The answer NA means that paper does not include experiments requiring code. • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
limitations and open problems: 
 To conclude, we discuss some of the limitations of our theory, as well as some of the open problems.Positive semi-definite kernels. One significant limitation of our theory is the assumption that the kernel is positive semi-definite and continuous. This condition is known as Mercer's condition in the literature and ensures that the spectral decomposition of the kernel (2) converges uniformly, however we don't actually require such a strong notion of convergence for our theory. Valdivia [2018, Lemma 22] show that the decomposition converges almost surely under a much weaker condition which is implied by our hypotheses (P) and (E). The only other places we need this assumption is to make use of results in Rosasco et al. [2010] and Tang et al. [2013] . These results make heavy use of reproducing kernel Hilbert space technology though it seems plausible that they could be generalised to the indefinite setting using the framework of Krein spaces [Ong et al., 2004 , Lei, 2021] .Low-dimensional setting. In our asymptotics, we explicitly assume that the dimension of the input space remains fixed as the number of sample increases, which places us in the so-called low-dimensional setting. We do not consider the high-dimensional setting, however our empirical experiments suggest that our conclusions may not carry over.Verification of the assumptions. While there is a established literature studying the eigenvalue decay of kernels under general probability measures [Kühn, 1987 , Cobos and Kühn, 1990 , Ferreira and Menegatto, 2013 , Belkin, 2018 , Li et al., 2024] , except in very specialised settings (such as Propositions 1 and 2), control of the eigenfunctions is typically out of reach. This makes verifying the assumptions of our theory under general probability distributions quite challenging. This is a widespread limitation of many theoretical analyses in the kernel literature, and for an extended discussion, we refer the reader to Barzilai and Shamir [2023] .Randomised low-rank approximations. While the truncated spectral decomposition provides the "ideal" low-rank approximation, it requires computing the whole kernel matrix which can be prohibitive for very large datasets. Randomised low-rank approximations, such as the randomised SVD [Halko et al., 2011] , the Nyström method [Williams and Seeger, 2000, Drineas et al., 2005] and random Fourier features [Rahimi and Recht, 2007, 2008] , have emerged as efficient alternatives, and there is an extensive body of literature examining their statistical performance [Drineas et al., 2005 , Rahimi and Recht, 2007 , Belabbas and Wolfe, 2009 , Boutsidis et al., 2009 , Kumar et al., 2009a ,b, Gittens, 2011 , Gittens and Mahoney, 2013 , Altschuler et al., 2016 , Derezinski et al., 2020] . However, their primary focus is on classical error metrics such as the spectral and Frobenius norm errors and an entrywise analysis would presumably provide greater insights into these approximations, particularly given recently observed multiple-descent phenomena [Derezinski et al., 2020] .Lower bounds. At present, it is unclear whether the bounds we obtain are tight, or indeed whether the truncated spectral decomposition itself is optimal with respect the the entrywise error. An interesting direction for future research would be to investigate lower bounds to understand the fundamental limits of this problem.For notational simplicity, in this section we will assume in this section that the eigenvalues and eigenfunctions are indexed from 0 rather than 1.We will begin by reducing the problem of verifying our assumptions under ρ to verifying them under the probability measure associated with the univariate Gaussian distribution N (0, σ 2 ), which we will denote by µ.Let K : L 2 ρ → L 2ρ denote the integral operator associated with the kernel k and the measure ρ, and let {λ i } denote its eigenvalues, arranged in descending order, and {u i } denote their corresponding eigenfunctions. By the rotation invariance of both k and ρ, the operator K may be written as the p-fold tensor productK = K ⊗ • • • ⊗ K where K : L 2 µ → L 2µ denotes the integral operator associated with the kernel k and the univariate Gaussian measure µ. Let {λ i } denote its eigenvalues, arranged in descending order, and {u i } denote their corresponding eigenfunctions. Then, the eigenvalues and eigenfunctions of K and K are related in the following way (see Shi et al. [2008] or Fasshauer and McCourt [2012] ). For every i, there exists i 1 , . . . , i p satisfying p j=1 i j = i such thatEQUATIONfor all x = (x 1 , . . . , x p ) ⊤ ∈ R p . Now suppose that λ i = Θ e -βi , thenλ i = p j=1 λ ij ≍ p j=1 e -βij = e -β j ij = e -βi ,and suppose that ∥u i ∥ ∞ = O(e si ) for some s < β/2. Then∥u i ∥ ∞ ≤ p j=1 u ij ∞ ≲ p j=1 e sij = e siTherefore to prove that (E) hold under ρ, it suffices to show that it holds under µ. Shi et al. [2008] provide an explicit formula for the eigenvalues and eigenfunctions of K, which is a refinement of an earlier result of Zhu et al. [1997] .Let υ := 2σ 2 /ω 2 and let H i (x) be the ith order Hermite polynomial. Then the eigenvalues and eigenfunctions of K are given byλ i = 2 1 + υ + √ 1 + 2υ υ 1 + υ + √ 1 + 2υ i u i (x) = (1 + 2β) 1/8 √ 2 i i! exp - x 2 2σ 2 √ 1 + 2β -1 2 H i 1 4 + β 2 1/4 x σ .Therefore, we have λ i = C 1 e -βi whereβ = log 1 + υ + √ 1 + 2υ υ .We will now show that each u i is uniformly bounded. By a change of variables, we can write u i asu i (x) = C 2 √ 2 i i! e -y 2 H i (y)for some y ∈ R. On the other hand, we have the following inequality due to Indritz [1961] . For allx ∈ R, e -x 2 H i (x) ≤ 1.09 √ 2 i i!.Therefore u i (x) ≤ 1.09C 2 for all x. We can use the fact that H i (x) is either odd or even to obtain an analogous lower bound. Therefore ∥u i ∥ ∞ ≤ 1.09C 2 for all i, so s = 0 and (E) holds.We will now show that Γ i = 0 for all i ≥ 1 so that (R) holds with b = +∞ and there is no requirement on the eigengaps ∆ i .Expanding u i (x)dµ(x), collecting exponential terms and applying a change-of-variables, one can calculate thatu i (x)dµ(x) = C 3 +∞ -∞ e -y 2 H i (y)dy.It is a standard result that e -y 2 H i (y) = 0 as long as i ̸ = 0 [Gradshteyn and Ryzhik, 2014] , and therefore u i (x)dµ(x) = 0 for all i ≥ 1, and by ( 11), we have that Γ i = 0 for all i ≥ 1.For any p ≥ 3, dot-product kernels with respect to the uniform measure on the sphere exhibit the spectral decompositionk(x, y) = ∞ l=0 λ * l N l m=1 u * l,m (x)u * l,m (y)where the eigenfunctions {u * l,m } are the mth spherical harmonic of degree l, N l = 2l+p-2l l+p-3 p-2 = O(l p-2) is the number of harmonics of each degree, and {λ * l } are the distinct eigenvalues [Smola et al., 2000] .The first spherical harmonic is a constant function, and therefore by the orthogonality of the eigenfunctions in L 2 ρ , u * l,m (x)dρ(x) = 0 for all l ≥ 1, and therefore Γ i = 0 for all i ≥ 1. Therefore (R) holds with s = +∞, and there are no requirements on the eigengaps.In addition, Lemma 3 of Minh et al. [2006] shows that the supremum-norm of a spherical harmonic is upper bounded byEQUATION)The eigenvalue decay rates are obtained from Propositions 2.3 and 2.4 of Scetbon and Harchaoui [2021] , and given (12), the condition a > (p 2 -4p + 5)/2 ensures that the conditions for (P) are met.We begin this section with two upper bounds on polynomial and exponential series, which we prove in Section B.1, and which we will use throughout this proof.Lemma 2. Let α > 1, β > 0 and 0 < γ ≤ 1 for fixed constants. Then the following upper bounds hold:∞ i=d+1 i -α = O d -α+1 , ∞ i=d+1 e -βi γ = O e -βd γ d 1-γ .Throughout this proof, ε > 0 will denote some constant which may change from line to line, and even within lines.To show equation ( 5), we first note that under (P) with d = Ω(n1/α ) n l=d+1 λ l ≲ n i=d+1 i -α ≲ d -α+1 = O n -α-1 αwhere we have used Lemma 2. In addition, under (E) with d > log 1/γ (n 1/β ), we have thatn l=d+1 λ l ≲ n l=d+1 e -βl γ ≲ e -βd γ d 1-γ = n -(1+ε) log (1-γ)/γ (n 1/β ) = O(n -1 )where we have again used Lemma 2. Now, by the triangle inequality we have that1 n n l=d+1 λ l ≤ n l=d+1 λ l + n l=d+1 λ l n -λ land therefore we are left to show thatEQUATION)To bound (13), we employ a fine-grained concentration bound due to Valdivia [2018] . We begin with the polynomial hypothesis. The authors only consider the cases that α, r are natural numbers, since they draw a comparison between between these values and a Sobolev-type notion of regularity.Inspecting their proofs, they treat the cases r = 0 and r ≥ 1 separately, however their proofs follow through in exactly the same way when the r ≥ 1 case is replaced with r > 0, in order to cover all values of α > 2r + 1, r ≥ 0. For the r > 0 case, they derive the following result. Lemma 3. Suppose that the hypothesis (P) holds with r > 0. Then, with overwhelming probabilityλ i n -λ i ≲ B(i, n) log(n)whereB(i, n) =      i -α+ α α-1 (r+ 1 2 ) n -1/2 if 1 ≤ i ≤ n α-1 α 1 2r+1 ; i -α+1+ α-1 α (r+ 1 2 ) n -1/2 if n α-1 α 1 2r+1 ≤ i ≤ n 1 2r ; i -α+r+1 n -1/2 if n 1 2r ≤ i ≤ n;Via some rearrangement we can show thatB(i, n) = O i -α , if 1 ≤ i ≤ n 1 2r, and by Lemma 2 we have thatEQUATIONIn addition, we have thatEQUATION)where we have used that 0 < r < (α -1)/2. Combining ( 14) with ( 15) establishes ( 13) under (P) assuming r > 0. The case with r = 0 follows analogous fashion so we omit the details.We now turn to the hypothesis (E). The authors only explicitly derive a result for the case that γ = 1, however following through their proof with Lemma 2 to hand, we obtain the following for the general case that 0 < γ ≤ 1. Lemma 4. Suppose that the hypothesis (E) holds with s > 0. Then, with overwhelming probabilityλ i n -λ i ≲ e (-β+δ)i γ i 1-γ n -1/2 log(n)for all 1 ≤ i ≤ n.Therefore we have that∞ i=d+1 λ i n -λ i ≲ n -1/2 log(n) n i=d+1 e (-β+s)i i 1-γ ≤ n -1/2 log(n) n i=d+1 e -(β/2+ε)i γ i 1-γ ≲ n -1/2 log(n) n i=d+1 e -(βi γ /2+ε) ≲ n -1/2 log(n)n -(1/2+ε) = O(n -1 )where in the second inequality we have used the assumption that s < β/2 and in the fourth we have used Lemma 2. The case for s = 0 follows similarly, so we omit the details. Then Equation ( 5) is established.To bound the polynomial series, we upper bound it by an integral as∞ i=d+1 i -α ≤ ∞ d t -α dt = d -α+1 -α + 1 = O d -α+1 .To bound the exponential series, we again employ an integral approximation, and upper bound it as∞ i=d+1 e -βi γ ≤ ∞ d e -βt γ dt.We then apply the substitution u = βt γ to obtain∞ d e -βt γ dt = 1 γ ∞ βd γ e -u u (1-γ)/γ du = 1 γ Γ 1 γ , βd γwhere Γ denotes the incomplete Gamma function. We can then use the fact that Γ(s, x) ≤ e -x x s-1 for s > 0 to obtain the upper bound1 γ Γ 1 γ , βd γ ≤ 1 γ e -βd γ (βd γ ) 1/γ-1 = β γ e βd γ d 1-γ , from which we can conclude that ∞ i=d+1 e -βi γ = O e βd γ d 1-γ ,as required.The proof of Lemma 1 generalises the proof of Lemma 43 of Tao and Vu [2011] . We will make use of the following theorem due to Ledoux [2001] which is a corollary of Talagrand's inequality [Talagrand, 1996] .Theorem 4 (Talagrand's inequality). Let y = (y 1 , . . . , y n ) ⊤ be a vector of independent random variables, and let f : R n → R be a convex 1-Lipschitz function. Then, for all t ≥ 0,P (|f (y) -M (f )| ≥ t) ≤ 4 exp -t 2 /16where M (f ) denotes the median of f .It is easy to verify that the map y → ∥π H (y)∥ is convex and 1-Lipschitz, and so by Talagrand's inequality we have thatEQUATION)For t ≥ 8, we have that 4 exp -(t -4) 2 /16 ≤ 4 exp -t 2 /32 , so to conclude the proof, it suffices to show thatEQUATIONLet E + denote the event that ∥π H (x)∥ ≥ σ √ q + 4 and let E -denote the event that ∥π H (x)∥ ≤ σ √ q -4. By the definition of a median, ( 17) is established if we can show that P(E + ) < 1/2 andP(E -) < 1/2.Let ε be the mean-zero random vector such that y = ȳ+ε, and let P = (p ij ) 1≤i,j≤n be the orthogonal projection matrix onto H. We have that tr P 2 = tr P = i p ii = q and |p ii | ≤ 1. Furthermore∥π H (ε)∥ 2 -σ 2 q = 1≤i,j≤n p ij ε i ε j -σ 2 q = S 1 + S 2 .where S 1 = n i=1 p ii (ε 2 i -σ 2 ) and S 2 = 1≤i̸ =j≤n p ij ε i ε j . We now upper bound the expectations of S 2 1 and S 2 2 which we will use later on for bounding the probabilities of E + and E -using Markov's inequality. Before we do, note that since ε ∈ [-ȳ, 1 -ȳ] almost surely, Popoviciu's inequality implies that σ 2 ≤ 1/4. Therefore, we also have that E(ε 4 i ) ≤ σ 2 , and soEQUATIONwhere the second inequality follows from the independence of ε 2 i -σ 2 and ε 2 j -σ 2 for all i ̸ = j. In addition, we have thatEQUATION)To upper bound the probability of E + , we first observe that by assumption∥π H (y)∥ 2 = ∥π H (ȳ)∥ 2 + ∥π H (ε)∥ 2 ≤ 4σ √ q + ∥π H (ε)∥2 and therefore we have thatP(E + ) = P (∥π H (y)∥ ≥ σ √ q + 4) ≤ P ∥π H (y)∥ 2 ≥ σ 2 q + 8σ √ q ≤ P ∥π H (ε)∥ 2 ≥ σ 2 q + 4σ √ q .Using the definitions of S 1 and S 2 , it follows thatP(E + ) ≤ P (S 1 + S 2 ≥ 4σ √ q) ≤ P (S 1 ≥ 2σ √ q) + P (S 2 ≥ 2σ √ q)By Markov's inequality, we have thatP (S 1 ≥ 2σ √ q) = P S 2 1 ≥ 4σ 2 q ≤ E S 2 1 4σ 2 q ≤ 1 4and similarly thatP (S 2 ≥ 2σ √ q) = P S 2 2 ≥ 4σ 2 q ≤ E S 2 2 4σ 2 q ≤ 1 16 .It therefore follows that P(E + ) < 1/2. We upper bound P(E -) in a similar fashion. Since ∥π H (x)∥ ≥ ∥π H (ε)∥, we have thatP (E -) = P(∥π H (y)∥ ≤ σ √ q-4) ≤ P(∥π H (ε)∥ ≤ σ √ q-4) = P(∥π H (ε)∥ 2 ≤ σ 2 q-8σ √ q+16).Again, recalling the definitions of S 1 and S 2 we have thatP (E -) ≤ P (S 1 + S 2 ≤ -8σ √ q + 16) ≤ P(S 1 ≤ 8 -4σ √ q) + P(S 2 ≤ 8 -4σ √ q).As before, applying Markov's inequality we have thatP(S 1 ≤ 8 -4σ √ q) ≤ P(S 2 1 ≥ 64 -64σ √ q + 16σ 2 q) ≤ P S 2 1 ≥ 8σ 2 q ≤ E S 2 1 8σ 2 q ≤ 1 8where we have twice used the assumption that q ≥ 64/σ 2 . SimilarlyP(S 2 ≤ 8 -4σ √ q) ≤ P S 2 2 ≥ 8σ 2 q ≤ E S 2 2 8σ 2 q ≤ 1 32 .It therefore follows that P (E -) < 1/2, thereby establishing ( 17) and concluding the proof.D Proof of the claim that ∥π J (ȳ)∥ ≤ 2|J| 1/4In this section, we prove the claim made in the proof of Theorem 1 thatEQUATION)with overwhelming probability, which we require in order to invoke Lemma 1. For notational convenience, we shall assume we are working in an n-dimensional space, rather than an (n -1)dimensional space as this is immaterial in our big-O bounds.Recall that ȳ is a constant vector with entries in [0, 1], and let 1 denote the all-ones vector. Let ξ be some value such that 8a < ξ < b/2, which exists by assumption (R), and let d ′ denote the smallest index such thatλ d ′ +1 = O n -1/ξ .This implies that under (P), d ′ = O n 1/ξα , and under (E), d ′ < log 1/γ (n 1/ξβ ). Clearly d ′ ≤ d and so J ⊂ {d ′ + 1, . . . , n}, and therefore ∥π J (ȳ)∥ ≤ π {d ′ +1,...,n} (1) .In addition, we observe thatπ {d ′ +1,...,n} (1) 2 = n -π {1,...,d ′ } (1) 2 .Since |J| = Ω(n), it will suffice to show thatEQUATIONwith overwhelming probability.Let U d ′ and U d ′ denote the n × d ′ matrices with entriesU d ′ (i, j) = u j (i), U d ′ (i, j) = u j (x i ) n 1/2 respectively. Then we have 1 n π {1,...,d ′ } (1) 2 = 1 n U d ′ U ⊤ d ′ 1 2 = 1 n U ⊤ d ′ 1 2 = 1 n ( U d ′ W ) ⊤ 1 2 ,where W is an orthogonal matrix which we will define later on. By the triangle inequality, we have that1 n ( U d ′ W ) ⊤ 1 2 ≥ 1 n U ⊤ d ′ 1 2 - 1 n U d ′ W -U ⊤ d ′ 2 ∥1∥ 2 = 1 n U ⊤ d ′ 1 2 -U d ′ W -U ⊤ d ′ 2and therefore to show (21), we need to show thatEQUATIONandEQUATIONwith overwhelming probability.respectively. Then in matrix notation we have thatΦ d ′ = n 1/2 U d ′ Λ 1/2 d ′ , Φ d ′ = n 1/2 U d ′ Λ 1/2 d ′ Now, we decompose U d ′ W d ′ -U d ′ as U d ′ W d ′ -n -1/2 U d ′ = n -1/2 Φ d ′ W d ′ -Φ d ′ + U d ′ W d ′ Λ 1/2 d ′ -Λ 1/2 d ′ W d ′ Λ -1/2and so we have thatU d ′ W d ′ -U d ′ ≤ λ -1/2 d ′ n -1/2 Φ d ′ W d ′ -Φ d ′ F + W d ′ Λ 1/2 d ′ -Λ 1/2 d ′ W d ′ .By the construction of d ′ we have that λ d ′ = Ω(n -1/ξ ) = Ω(n -1/8 ) and therefore λ-1/2 d ′ = O n 1/16. Therefore to show ( 23), it will suffice to show thatΦ d ′ W d ′ -Φ d ′ F = O n 3 16 -Ω(1) (24)andEQUATION)To obtain the bound ( 24), we make use of the following result which is Equation 3.8 of Tang et al. [2013] . Lemma 5. The exists an orthogonal matrix W d (constructed as in ( 29)) such thatΦ d W d -Φ d F = O log 1/2 (n) λ d -λ d+1with overwhelming probability.EQUATIONthen by the assumption (R), we have thatEQUATION)Using Lemma 5, we obtain thatΦ d ′ W d ′ -Φ d ′ F ≤ Φ d ⋆ W d ⋆ -Φ d ⋆ F = O log 1/2 (n) λ d ⋆ -λ d ⋆ +1= O n 1/8-Ω(1) , which establishes (24). Obtaining the bound (25) requires some new concepts, so we dedicate it its own section.We now turn our attention to the bound (25). We begin by defining H, the reproducing kernel Hilbert space associated with the kernel k, and define the operators K H , K H : H → H given byEQUATION)where k x (•) = k(•, x) and ⟨•, •⟩ H is the inner product in H. These operators are known as the "extension operators" of K and 1 n K, respectively, and it may be shown that each has the same eigenvalues as its corresponding operator, possibly up to zeros (see e.g. Propositions 8 and 9 of Rosasco et al. [2010] ). We will make use of the following concentration inequality for K H -K H which is due to De Vito et al. [2005] and appears as Theorem 7 of Rosasco et al. [2010] .Lemma 6 (Theorem 7 of Rosasco et al. [2010] ). The operators K H and K H are Hilbert-Schmidt, andK H -K H HS = O log 1/2 (n) n 1/2with overwhelming probability.Let {u H,i } i≤d denote the eigenfunctions of K H corresponding to the eigenvalues {λ i } i≤d , and let { u H,i } i≤d denote the eigenfunctions of K corresponding to the eigenvalues { λ i /n} i≤d . We define the (infinite-dimensional) "matrices" U H,d and U H,d whose columns contain the eigenfunctions {u H,i } i≤d and { u H,i } i≤d , respectively. These "matrices" are well-defined with matrix multiplication is defined as usual with inner products taken in H. We will refer to U H,d , U H,d and the subspaces spanned by their columns interchangably.LetH d = U ⊤ H,d U H,d with entries H d (i, = ⟨u H,i u H,j⟩ H and denote its singular values by ξ 1 , . . . , ξ d . Then the principal angles between the subspaces U H,d and U H,d , which we will denote by θ 1 , . . . , θ d , are define as via ξ i = cos(θ i ). Define the matrix 1) . Since d ⋆ ≥ d ′ , by the Davis-Kahan theorem, we have thatsin Θ U H,d , U H,d = diag (sin(θ 1 ), . . . , sin(θ d )) . Let d ⋆ be as in (26) so that λ d ⋆ -λ d ⋆ +1 = Ω n -1/8+Ω(sin Θ U H,d ′ , U H,d ′ ≤ sin Θ U H,d ⋆ , U H,d ⋆ ≤ √ 2 K H -K H λ d ⋆ -λ d ⋆ +1 ≤ √ 2 K H -K H HS λ d ⋆ -λ d ⋆ +1 = O n -3/8-Ω(1) .where the second inequality comes from the relationship ∥•∥ ≤ ∥•∥ HS , and the final inequality follows from Lemma 6 and ( 27).We now come to constructing the matrix W d . We denote the singular value decomposition of H as H = W d,1 ΞW ⊤ d,2 and define the matrix W d byEQUATIONwhich is known as the "matrix sign" of H. Let P d and P d to be the projections onto the subspaces U H,d and U H,d , respectively. Then we have the following decomposition.EQUATIONWe first observe that∥H d ′ ∥ ≤ ∥ U H,d ′ ∥∥U H,d ′ ∥ = 1, and by (5), Λ d ′ , ∥Λ d ′ ∥ = O(1).In addition, following the same steps as in the proof Lemma 6.7 of Cape et al. [2019] (who prove similar (in)equalities for finite-dimensional matrices) we have that 1) .P d ′ -P d ′ = sin Θ U H,d ′ , U H,d ′ = O n -3/8-Ω(1) ∥H d ′ -W d ′ ∥ ≤ sin Θ U H,d ′ , U H,d ′ 2 = O n -3/4-Ω(We now turn to bounding∥U ⊤ H,d ( K H -K H )U H,d ∥. To condense notation, let Q = U ⊤ H,d ( K H - K H )U H,d .We will bound ∥Q∥ using a classical ε-net argument. Let S d-1 ε be an ε-net of the (d -1)dimensional unit sphere S d-1 := {v : ∥v∥ = 1}, that is, a subset of S d-1 such that for any v ∈ S d-1 , there exists some w v ∈ S d-1 ε such that ∥v -w v ∥ < ε. Then, we have that∥Q∥ = max v:∥v∥≤1 v ⊤ Qv = max v:∥v∥≤1 (v -w v + w v ) ⊤ Q (v -w v + w v ) ≤ ε 2 + 2ε ∥Q∥ + max w∈S d-1 ε w ⊤ Qw .With ε = 1/3, we have∥Q∥ ≤ 9 2 max w∈S d-1 ε w ⊤ Qw .Using the definitions (28), its (l, m)th entry can be calculated asEQUATIONand so for a given w ∈ S d-1 ε , we have thatw ⊤ Qw = d l,m=1 Q(l, m)w(l)w(m) = d l,m=1 w(l)w(m)   1 n 2 n i,j=1 k(x i , x j )u l (x i )u m (x j ) - k(x, y)u l (x)u m (y)dρ(x)dρ(y)   ≤ max 1≤l≤d ∥u l ∥ ∞ n i=1    d l,m=1 w(l)w(m) u m (x i ) n -u m (x)dρ(x)   where we have used that k(x, y) ≤ 1 for all x, y ∈ X . This is a sum of independent random variables, so by Hoeffding's inequality, we that thatP w ⊤ Qw ≥ t ≤ 2 exp - 2nt 2 max 1≤l≤d ∥u l ∥ 4 ∞where we have used that d l,m=1 w(l)w(m) = 1. The set S d-1 1/3 can be selected so that its cardinality is no greater than 18 d (see, for example, Pollard [1990] ), so using a union bound we have thatP (∥Q∥ ≥ t) ≤ P max w∈S d-1 1/3 w ⊤ Qw ≥ 2 9 t ≤ w ∈ S d-1 1/3 P w ⊤ Qw ≥ 2 9 t ≤ 2 • 18 d ′ exp - 8nt 2 81 • max 1≤l≤d ′ ∥u l ∥ 4 ∞ ≤ 2 exp d ′ log(18) - 8nt 2 81 • max 1≤l≤d ′ ∥u l ∥ 4 ∞ ≤ 2 exp C n 1/8-Ω(1) -n 3/4 t 2where we have used that d ′ = O(n 1/8-Ω(1) ) and max 1≤l≤d ′ ∥u l ∥ ∞ = O(n 1/16 ). Choosing t = 2n -5/16-Ω(1) we have thatP ∥Q∥ ≥ 2n -5/16-Ω(1) ≤ 2 exp -n 1/8 ≤ n -cfor any c > 0 for large enough n. Therefore The Frobenius-norm error against rank for low-rank approximations of kernel matrices constructed from a collection of datasets. The kernel matrices are constructed using Matérn kernels with a range of smoothness parameters, each of which is represented by a line in each plot. Details of the experiment are provided in Section 5.∥Q∥ = O n -5/16-Ω(1)with overwhelming probability.Combining the above bounds with (30) we obtain thatW d ′ Λ 1/2 d ′ -Λ 1/2 d ′ W d ′ = O n -5/16-Ω(1)which establishes (25) and therefore completes the proof.In this section, we provide some additional details and plots relating to the experiments in Section 5.GMM is a synthetic dataset of 1,000 simulated data points from a 10-component Gaussian mixture model with unit isotropic covariances and means of size ten on the axes. Abalone [Nash et al., 1995] and Wine Quality [Cortez et al., 2009] are popular benchmark datasets which we standarised in the usual way by centering and rescaling each feature to have unit variance. We drop the binary Sex feature from the Abalone dataset to retain only the continuous features. MNIST [Deng, 2012] is a dataset of handwritten digits, represented as 28x28 gray-scale pixels which we concatenate into 784 dimensional vectors. These four datasets might be described as "low-dimensional", and are thus representative of the theory we present in Section 3.In addition, we consider two "high-dimensional" datasets. 20 Newsgroups [Lang, 1995] is a popular natural language dataset of messages collected from twenty different "newnews" newsgroups. We remove stop-word and words which appear in fewer than 5 documents or more than 80% of them, and convert each document into a vector using term frequency-inverse document frequency (tf-idf) features for each word. Zebrafish [Wagner et al., 2018] is a dataset of single-cell gene expression in a zebrafish embryo taken during their first day of development. We subsample 10% of the cells, and process the data following the steps in Wagner et al. [2018] .Figure 2 shows the Frobenius norm error of the low-rank approximations. For the low-dimensional datasets GMM, Abalone, Wine Quality and MNIST, the Frobenius norm error decays very quickly. However for the high-dimensional datasets 20 Newsgroups and Zebrafish, the Frobenius norm error decays much more slowly. As pointed out in the main text, the Frobenius norm error of the 20 Newsgroups dataset does not exhibit the sharp drop between d = 2500 and d = 3000 that the maximum entrywise error exhibits.The experiments were performed on the HPC cluster at Imperial College London with 8 cores and 16GB of RAM. The GMM experiment took less than 1 minute; the Abalone, Wine Quality, MNIST and Zebrafish experiments took less than 8 hours; and the 20 Newsgroups experiment took less than 24 hours.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: In the introduction, we discuss the importance of seeking methods with low entrywise error bounds for applications in which individual errors carry a high cost. Our work is foundational theory, and we don't foresee any negative societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Code to reproduce the experiments in this section can be found at https://gist.github.com/alexandermodell/b16b0b29b6d0a340a23dab79219133f2. 
 
 Appendix:  


Decision: The manuscript provides novel entrywise error bounty for low-rank approximations of kernel matrices. Of particular note, the arguments require (and the manuscript provides) a delocalization result for eigenvectors that may be of broader interest. While the delocalization result is stylistically similar to prior work, there are key differences in the regime in which it is valid. There is consensus that the results are interesting and technically correct (see below) and all of the reviewers are positive albeit weakly so. Moreover, some of the highlighted weaknesses are quite common for papers in this area—"unverifiable assumptions" are, unfortunately, common and not just a weakness of this particular work. Given the importance of the problem results of this type are valuable and the rebuttal effectively justified the assumptions to the extent possible.

Of note, the submitted version of the manuscript contained an error in Lemma 1, a reasonable fix was proposed during the rebuttal—it must be incorporated into the manuscript.

NB: while not particularly relevant to the overall rating of the manuscript, I will add that per my own read the "double descent" phenomena is alluded to in a rather ad hoc manner (admittedly the phrase has become somewhat ambiguous over time) and absent more clarification or study (which the authors suggest is out of scope) it may be best to omit it entirely.

Reviews: review: paper_summary: paper_summary: The authors consider the kernel matrices, formed by $n$ vectors i.i.d. drawn from a $p$-dimensional probability distribution $\rho$. Under several assumptions on the associated kernel operator on $L^2_{\rho}$, including the positive definiteness of the kernel and decay condition on the eigenvalues of the kernel, the authors prove an estimate on individual entries of the matrix kernel and those of the low-rank approximation of the kernel. Numerical experiments on the estimate error are done with both synthetic datasets and real-world datasets.
strength_weakness: strength_weakness: - Lemma 1 is wrong, and thus the proofs of the main results do not work. 
Consider an extreme case where $a=0$ with probability $1$. Then, since $\pi$ is an orthogonal projection, $\| \pi_H(a) \| = 0$ and thus Lemma 1 fails. The main issue is that in the proof of Lemma 1, if $S_1 = \sum p_{ii} (\xi_i^2 - 1)$, then $E[S_1^2] = \sum_{i, j} p_{ii} p_{jj} E[\xi_i^2 - 1] E[\xi_j^2 - 1]$, which is different from $\sum_i p_{ii}^2 E[(\xi_i^2 - 1)^2]$ in (17), unless $E[\xi^2]=1$. As a result, (17) and the estimates on $P(E_+)$ and $P(E_-)$ fail.
-> The proofs of the main results would work after modifying Lemma 1 as suggested by the authors.
questions: questions: - Is it possible to prove Lemma 1 with additional assumptions that are suitable to the current setting?
- In the proof of Lemma 1, there are other minor problems listed below.
1) In line 618, $\xi_i \in [0, 1]$ is wrong since the mean $\bar{x}$ is subtracted.
2) In the equation below line 621, why $\| \pi_H(x)\|^2 = \| \pi_H(\bar{x}) \|^2 + \| \pi_H(\xi) \|^2$?
3) In the equation below line 621 and several other places, $X$ should be $x$. Also, $\bar{\xi}$ should be $\xi$.
limitations: limitations: The work does not seem to have potential negative societal impact.
paper_summary: paper_summary: The paper focuses on deriving entrywise error bounds for low-rank approximations of kernel matrices using truncated eigen-decomposition. It addresses the statistical behavior of individual entries in such approximations under assumptions of polynomial eigenvalue decay or exponential decay. The authors also provide empirical studies on synthetic and real-world datasets.
strength_weakness: strength_weakness: 1. The assumptions on the eigenfunctions corresponding to the assumptions of eigenvalue decay are hard to verify for general kernels, especially the part on the rate of decay ($\alpha >2r+1,\beta> 2s$). Moreover, I wonder if these inequalities are required to guanrantee the uniform convergence of the kernel (I note that $k(x,y)=\sum_{i=1}^{\infty}\lambda_i u_i(x)u_i(y)$ converges uniformly under these assumptions).  But in the proof I see these assumptions are used in a way like $\beta-s\ge \beta/2$ (e.g., Line 590). Thus, I am not sure if these asssumptions are necessary for derivation.
2. Assumption (R) seems not natural (why is $1\le a < b/16$ is needed?) and also I do not know how to verify this. Could you provide some examples with $\Gamma_i \neq 0$ under Assumption (R)?
3. The contributions are undetermined. The proof of the main theorem seems to heavily rely on past random matrix theory works (Tao and Vu [2011], Erdős et al. [2009 a,b]). With assumptions (E)/(P) and (R) and the previous works, the proof is straightfoward. And I am not sure about the importance of entrywise error bound.

Minor typos: 
1. Line 578/588 hypotheses-> hypothesis
2. Line 539/581 miss a period
questions: questions: 1. (Line 82) What do you mean by "infinite sample limit of $\frac{1}{n}K$"?
2. Could you provide more general examples that completely follow the assumption (E)/(P)?
3. Is this error bound optimal? Are there any lower bound results?
4. Is it possible (or are there any hardness results) to compute or approximate $\text{argmin}_{K':\text{rank}(K')=d}$ $ \||K-K'\||$ w.r.t. the sup norm?
5. Regarding the importance of entrywise error bound, could you provide more concrete examples?
limitations: limitations: There is no negative societal impact of their work.
paper_summary: paper_summary: This paper is first to establish entrywise guarantees for low rank approximation of kernel matrices when kernel eigenvalues satisfy either polynomial or exponential decay. More specifically, in the $\alpha$-polynomial decay setting, entrywise error scales as $O(n^{-\\frac{\alpha-1}{\\alpha}} \\log n)$ for rank $d = \Omega(n^{1/\\alpha})$, while for $(\\beta,\\gamma)$-exponential decay error scales like $O(1/n)$ for $d > \\log^{1/\\gamma}(n^{1/\\beta})$. In order to establish such results, authors prove that eigenvectors corresponding to small eigenvalues are completely incoherent/delocalized i.e. have bounded entries of size $O(1/\\sqrt{n})$. Technical novelty stems from the fact that entries of the kernel matrix are dependent and have non-zero mean.
strength_weakness: strength_weakness: 1) Although authors claim that Lemma 1 is a novel concentration result, it seems to be only a slight generalization of Lemma 68 in Tao and Vu [2011], and is proved essentially using the same argument as that in the proof of Lemma 68. 

2) Although I appreciate proof sketches of Theorems 1 and 2 in the main text, I believe it would be more useful to add more information about the proof deferred to Appendix D since this is the most novel and interesting part of the proof.

3) It is not clear whether assumption (R) is necessary and how general it is apart from the two special cases given in Section 3.1.
questions: questions: 1) Could you elaborate more on tightness of your results? How do they compare with already established results for Frobenius and spectral norm? Are there any known lower bounds for entrywise estimation?

2) Although assumptions (E) and (P) seem to be very natural, I am not sure about assumption (R). Do results hold for any $a$ and $b$ such that $1\\leq a < b/16$? Since the final error bound does not depend on $a$ and $b$, do you think this assumption can be relaxed?   

3) Although I think that double descent observation is interesting on its own, the evidence for it is vague. Is this behavior observed for a range of percentile values or does it happen only around 99.95 percentile? Also from figures in the paper seem like it appears only for not very smooth kernel functions. It would be beneficial to have more convincing evidence whether this phenomenon occurs because of your choice of 1) kernels, 2) percentiles, 3) entrywise errors or something else.


Typos and other comments

(106) maximum entrywise "error" (missing)

(186) should be $ \\hat{u}_i(1)$, instead of $ \\hat{u}_l(1) $

(647) later on

I would prefer if you do not use $(a,b)$ both for constants in assumption (R) and for vectors in the proof of Theorem 2.

In introduction you cite [Lei, 2019] for establishing entrywise error bounds for reinforcement learning - but I could not find any references to RL in that paper. Is this a typo? For example, I believe the following papers are more suitable for that particular reference: 

- Pananjady, Ashwin, and Martin J. Wainwright. "Instance-dependent ℓ∞-bounds for policy evaluation in tabular reinforcement learning." IEEE Transactions on Information Theory 67.1 (2020): 566-585.
- Shah, Devavrat, et al. "Sample efficient reinforcement learning via low-rank matrix estimation." Advances in Neural Information Processing Systems 33 (2020): 12092-12103.
- Stojanovic, Stefan, Yassir Jedra, and Alexandre Proutiere. "Spectral entry-wise matrix estimation for low-rank reinforcement learning." Advances in Neural Information Processing Systems 36 (2023): 77056-77070.
limitations: limitations: The authors have addressed limitations adequately.

Comments: title: Reponse
comment: I thank the reviewer for taking the time to go through the appendix, and I am happy to see their recognition of the complexity of some of the technical contributions there.

I would argue that the correction to Lemma 1 is only minor, does not affect any other areas of the proofs and is now resolved. 

With regards to the difficultly in verifying the assumptions, this is a widespread limitation of *all* theoretical works on kernel methods which require knowledge of the spectral properties of the kernel, and I refer the reviewer to Section 2.2 of Barzilai and Shamir (2023) for an extended discussion of this point. Given this, I believe I take the best possible approach to making the assumptions interpretable to the reader. In Proposition 2, I show that in the special case of dot product kernels on the sphere (for which the spectral properties of the kernel *can* be easily computed), the assumptions can be replaced with a simple, highly-interpretable smoothness assumption on the kernel. I then show  experimentally that these results generalise to other data-generating measures using simulations and real datasets (using 4 Matérn kernels of differing smoothness). This is a standard approach, for example in the theoretical deep learning literature (e.g. Jacob et al. (2018), Bietti and Mairal (2019), Bietti and Bach (2020)), and I don't see that there is a better way of doing it.



*References:*

- Daniel Barzilai and Ohad Shamir. Generalization in kernel regression under realistic assumptions. *arXiv preprint arXiv:2312.15995, 2023*.

- Bietti, A., & Bach, F. (2020). Deep equals shallow for ReLU networks in kernel regimes. *arXiv preprint arXiv:2009.14397*.

- Bietti, A., & Mairal, J. (2019). On the inductive bias of neural tangent kernels. *Advances in Neural Information Processing Systems*, *32*

- Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. *Advances in neural information processing systems*, *31*.
I am glad to see that the reviewer is satisfied with my proposed modification to Lemma 1 and I thank them for updating their score. In response to their comment about the significance of the new lemma, I would argue that the new lemma is no less significant compared to the original one, especially in the asymptotic analysis considered in this paper. 

So far, the reviewer has only commented on Lemma 1 in the paper, which is only a small (but necessary) part of this work and is not the main contribution of the paper. I would be interested to know their opinion of the paper as a whole, now that the potential problem has been resolved.
Thank you for your reply. I will maintain my score.
Thank you for your response. After the rebuttal, I go through the Appendix and believe the author has make great efforts in the proof, not as easy as we reviewers thought. But considering the fact that Lemma 1 should be corrected and the assumptions still lack some intuition (since it is hard to give some general examples), my score remain the same.
Thank you for your answers. It seems that the main result can be proved with the modified version of Lemma 1. (However, the modified version of Lemma 1 is less significant than the original one, since the new assumption $|\pi_H(\bar a)| \leq 2(\sigma^2 q)^{1/4}$ is stronger.) I will adjust my rating accordingly.