Entrywise error bounds for low-rank approximations of kernel matrices
Authors: Alexander Modell
Venue: NeurIPS 2024 poster (2024)
Keywords: low-rank approximation
kernel methods
SVD
theory
error bounds
Primary area: learning_theory
TL;DR: This paper proves an entrywise error bound on the low-rank approximation of a kernel matrix, obtained using the truncated eigen-decomposition (or singular value decomposition).

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.

Entrywise error bounds for low-rank approximations of kernel matrices
Alexander Modell Department of Mathematics Imperial College London, U.K.
wmm.elllllmma .mooell@imperialll aac. uk
Abstract
In this paper, 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 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 collection of synthetic and real-world datasets.
Introduction
Low-rank approximations of kernel matrices play a central role many areas 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 [000 Belkin and
Niyogi Coifman and Lafon [2006]. where they serve core component of the algorithms,
and support vector machines [Coortes and Vapnik, 1995 Fine and Scheinberg 2001] and Gaussian
process regression [Williams and Rasmussen 1995 Ferrari-Trecate al. 1998 where they serve
dramatically speed up computation times.
In this paper, we derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated agge-ddccomposition (or singular value decomposition). Entrywise error bounds are important for 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 al. 2018 Abbe al. 2022]]
matrix completion [Candes and Recht. 2012 Chi et al. 2019], phase synchronisation [Zhong and
Boumal 2018 Ma et 20.1 reinforcement learning [Stojanovic et al.
2023], community detection
[Balakrishnan et al. 201 L et al. 2014 Eldridge et al. 2018
Lei 2019 Mao et al. 202 to name a few.
and graph inference
Cape et al. 2019 DelancDylanchy et al. 2022
1.1
Contributions
Our main result (Theorem 1) is an entrywise error bound for the low-rank approximation of kernel matrix. Under regularity conditions, we find that for kernels with polynomial eigenvalue decay, X; O(i-a), we we require a polynomial-rank approximation, d ((n-/a).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to achieve entrywise consistency. For kernels with exponential eigenvalue decay, A O(e require (poly)log-rank approximation, d d> log!/(n21/8)
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 the proof of which draws on ideas from the Random Matrix Theory literature. To knowledge, this is the first such result for random matrix with non-zero mean and dependent entries.
Along the way, we prove novel concentration inequality for the distance between random vector (with potentially non-zero mean) and a subspace (Lemma I 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 collection of synthetic and real datasets.
1.2
Related work
lemma [Johnson and Linden strauss 1982 to bound the entrywise eтror of low-rank matrix approximations obtained via random
Some complementary results to ours use the
projections Srebro and Shraibman 2005 Alon et al. 2013 [dell 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 ideas from the Random Matrix Theory literature, where de- localisation results have been established for certain classes of zero-mean random matrices with independent entries [Erdös al. 2009b 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 im-
prove upon classical absolute concentration bounds Rosasco et al. 2010 which would not provide sufficient control for our purposes.
1.3 Big-O notation and frequent events
We use the standard big- O notation where a, = (b,,) (resp. a,, = (?(b,,)) means that for sufficiently large n. a, I Cb2 (resp. a, 2 Cb2,) for some constant C which doesn't depend on the parameters of the problem. We will occasionally write on, I b, to mean that a, = Ob,,).
In addition, we say that event En holds with overwhelming probability if for every e ((E.) 2 - (nn where the hidden constant is allowed to depend on c.
2 Setup
begin by describing the setup our problem. We suppose that we observe n, p-dimensional data points {x,) which assume were drawn i..d. from some probability distribution p. supported on a set X. Given a symmetric kernel x X + R, we construct the n X n kernel matrix K, with entries
K (i,j) = IT)
will assume throughout that the kernel is positive-definite, continuous and bounded. Let Ra denote the "best" rank-d approximation of K, in the sense that R₂ satisfies
Ka arg min
||K
K'llg;
K K'rank(KK))=
where I1-1lg is rotation-invarian norm, such as the spectral or Frobenius norm. Then by the Eckart-
Young-Mirsky theorem |Eckart and Young. 1936 eigen-decomposition of K, i.e.
Mirsky 1960). Ra is given by the truncated
Ra = Σ Aaja
where (2,)2 are the eigenvalues K (counting multiplicities) in decreasing order, and (ū,) corresponding cigenvectors.

---

We now introduce some population quantities which will form the basis of our theory. Let L denote the Hilbert space of real-valued square integrable functions with respect to p. with the inner product defined as ( = (()))())d)(())) We define the integral operator K. 1.2 1 by
(Kf)) (z) = J k(z, ((zz))f(y)dp))
which is the infinite sample limit of , K. The operator IC is self-adjoint and compact (Hirsch and Lacombe| 1999), so by the spectral theorem for compact operators, there exists sequence of eigenvalues (Ai (counting multiplicities) in decreasing order, with corresponding eigenfunctions 0o which are orthonormal in L such that {u
Ku; A,
Moreover, by the classical Mercer's theorem [Mercer 1909 Steinwart and Scovel 2012), the kernel can be decomposed into
k( = (
(2)
where the series converges absolutely and uniformly in y,
3 Entrywise error bounds
This section is devoted our main theoretical result. We begin by discussing assumptions, before presenting our main theorem and giving some special cases of kernels which fit within our framework.
In our asymptoties, we will assume that and p 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.c. A = =
for some a > 1, or (nearly) exponential decay, i.c. A; O(e-Bi)) for some 3 > 0 and 0 < S 1. We will refer these two hypotheses as (P) and (E) respectively. We also assume a corresponding hypothesis on the supremum supremum-norm norm growth of the eigenfunctions. Under (P), we assume that || ||u:
(it)) with
2r + 1, and under (E), we assume that ||u,|loo = O(e*t)) with 3 > 28.
Our eigenvalue decay hypothesis commonplace in the kernel literature [Braun 2006 Ostrovski and
Rudi 2019 Xu 2018 Lei [02T]. and can be related to the smoothness of the kernel. For example, the decay of the eigenvalues directly implied by Hölder or Soboley-type smoothness hypothesis
on the kernel (see, for example, Nicaise [2000). Belkin (2018). Section 2.2 of Xu (2018), Section 5 of
Valdivia (2088. |Seetbon and Harchaoui [202] and Proposition in this paper). We don't It consider
a tinite-rank (say, D) hypothesis, since in this case the maximum entrywise error is trivially zero whenever 2 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 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 al. 2005 Braun 2006), which do not hold for many commonly-usee 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 (012) 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 [Cndèè and Tao
2010 Keshavan et al. 2010 Chi et al. 2019 Abbe et al. 2020 Chen al.. 2021
In addition, we introduce regularity hypothesis, which we will refer to as (R), which relates to the
following two quantities:
A = max tA - A1+1} J21
which measures the largest eigengap after a certain point in the spectrum, and
(fus ((ste)dp(a) )
r
Σ j=
3

---

1 ll
A
(P)
9)
(i))
a > 2r +1
(R)
O(A9)
15 a < 6/16
O
(e-
① (E#P)
8> 2s, 0
<1
Table 1: Summary of the hypotheses (P), (E) and (R).
which measures the squared residual after projecting the unit-norm constant function onto the first eigenfunctions. Under (R), we assume that A; 22 (Xş) and r, O (XP) with S < 6/16 S co.
sufficient condition for (R) to hold, is that the first eigenfunction is constant. This holds, for example, when k is dot-product kernel and is a uniform distribution on hypersphere. In such scenarios, r,- = for all
and it is not necessary to make any assumptions on the eigengap quantity A, We remark that (R) permits repeated eigenvalues in the spectrum of XC, 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) summarised in Table 1 We now ready state main theorem.
Theorem 1. Suppose that k is symmetric, positive-defiitte continuous and bounded kernel and p a probability measure which satisfy (R) and one of either (P) or (E). If the hypothesis (P) holds and d = Ω (n')),, then
Ra- K
-0
log(n))
maxx
with overwhelming probability. If the hypothesis (E) holds and d > log (n/ then
Ra
K max =0 (n
with overwhelming probability.
3.1
Special cases
In this section, provide some examples of kernels which satisfy the assumptions of Theorem [ Proofs of the propositions in this section are given in Section A of the appendix. We start with canonical example of radial basis kernel.
Proposition Suppose k(x,y) y) = exp (- u112 /2w²) is a radial basis kernel, and p ~ (0, 1p) is a isotropic Gaussian distribution on 12,. Then the hypotheses (E) and (R) are satisfied with
log 1 2
==1
where 20 //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. 22099), 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 able replace assumptions with
SP-1, and is dot-product kernel. In this setting, a smoothness hypothesis on the kerne.. Note that this class kernels includes those which are functions of Euclidean distance, since on the sphere we have the identity | - y/12 (x, v). Proposition 2. Suppose that
k(z,y)= =
Σ by ((a, vi)
a dot-producc kernel and p is the uniform distribution on the hypersphere S with p 2 3. If there exists > (p² 4p 5)/2 such that b; O(i-a), then (P) and (R) are satisfied with
2a +
D-2

---

Alternativll, if there exists 0 < < such that b; O(r"), then (E) and (R) are satisfied with
B (p 1)!
(og(1/r),
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 |Seetbon and Harchaoui [021]] and we make use of a supremum norm bound for spherical harmonics in Minh al. 2006].
3.2
Comparison with random projections and the Johnson-Lindenstrann lemma
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 bb]
For an x 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 rank-d approximation Ma whose entrywise error is bounded by e when d = (0===((o(n)) log(n)).
The proof is via probabilistic construction. Let X be for some I n, let R be an n x d matrix with i..dd entries from (0, 1/d). Then, the randomised low-rank approximation
matrix such that M = XX",, and
Ma = XRR
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 positive semi-definite matrix with bounded entries, and Ma be randomised rank-d approximation of M described in (4). Then
log(n) d
Ma
M
=0
max
with overwhelming probability.
To obtain polynomial entrywise error rate, i.e. ((n=c) for >>>> with Theorem 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 entrywise error bounds o(n 1/2) for the cases consider, this rate can never be achieved, regardless 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
4 Proof of Theorem
In this section, we outline the proof of Theorem Without loss of generality, we will assume that 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 that
K2 K max
Rali.)) k(,5))=
Σ (()(()) 1=d+1
max 15if5n
ISNJER
X
| detisn
max
|
I=d+1
Using concentration bound due to Valdivia (2018), we are able show that
O (m log(n)) under (P) with d = Ω (n²/a) under (E) with d log (n 1/8).
(5)
(1)
1=d+1
5

---

with overwhelming probability, the details of which are given in Section B of the appendix. Then, the proof boils down showing the following result, which we state as an independent theorem.
Theorem 3. Assume the setting of Theorem L then simultaneously for all d + 1 S SIS n,
@ = O (n
(6)
with overwhelming probability.
When unit eigenvector satisfies (6) (up to log factors), it is said to be completely delocalised. There a now expansive literature in the field of Random Matrix Theory proving the delocalisation the
eigenvectors of certain mean-zero random matrices with independent entries (Erdös et al. 2009b
Tao and Vul 2011] Rudelson and Vershynin 2015, Vu and Wang [2055) Theorem ] may be of independent interest since to knowledge, it is the first eigenvector delocalisation result for
random matrix with non-zero mean and dependent entries.
To prove Theorem 3 we take inspiration from proof strategy employed in Tao and Vul [201T] (see also Erdōs et al. (2009b]) which makes use of an identity relating the eigenvalues and eigenvectors of 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.
By symmetry and a union bound, to prove Theorem B it suffices to establish the bound for the first coordinate ún for some an arbitrary index 1 n. We shall let K denote the bottom right principal minor of K that is the 1 matrix such that
Proof of Theorem 3
y K
K
where = = k(x1,21) and = (k(11, k(æ,, (n)) xn))) We will denote the ordered eigenvalues
and corresponding eigenvectors of K by { and ( respectively. By Lemma 41 of Tao and Vu 2001]] we have the following remarkable identity:
ix(1)²
1+ E+ (2, Xx) (4]
In addition, Cauchy's interlacing theorem tells that the eigenvalues of K and K interlace, i.e. X; S X, S Set1 for all 1 < S 1. By (5) we have that [A1] = ((1) for all d + < S with overwhelming probability and so by Cauchy's 's interlacing theorem, we can find a set of indices
{d 1, ,........... 1} with [J] 2 (n - d2/2 such that Xo d O (1) for all J. Combining this observation with (7). we have that
Σ 0
12 v) ),,
2a 21) -
"a],v) vu) R 1T))1
(8)
JEJ
where nт denotes the orthogonal projection onto the subspace spanned by {ūz}eeJ- So, establish (6) suffices to show that
[ = 1())
with overwhelming probability. We condition on 11, so that is a vector of independent random variables and denote its conditional mean by J. 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 ² Ez-r (K2 x))
To obtain the lower bound 9 we prove novel concentration inequality for the distance between random vector and a subspace, which may be of independent interest. Our lemma generalises 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 E R" be random vector with mean y := Ey whose entries are independent, have
common variance o² and are bounded in [0. 1] almost surely. Let be subspace of dimension
q 22 64/o² and лh the orthogonal projection onto H. If H is such that 1 [m) S 2 1/4, then for any t 2 8
P P(IITH (v)ll - oq 2)) - exx (-12/3))
In particular, one has
Nh (v)ll - 02 O 0 (m))
(10)
with overwhelming probability.
Returning to the main thread, we claim for the moment that ||) S 2/ Then, by Lemma we have that, conditional on 21,
[ 2 J 2 (n - d)/2 = 2(n)
with overwhelming probability. This holds for all #1 X and therefore establishes ( complete the proof, then, it remains to prove claim, and it is here where require the regularity hypothesis (R). The proof of the claim is quite involved, so we defer the details to Section DJ the appendix, given which, the proof of Theorem 3 complete.
Experiments
5.1
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 synthetic dataset and collection of five real-world data sets, which are summarised in the following table"
Dataset
Description
# Instances
# Dimensions
GMM
simulated data from a Gaussian mixture model
1,000
10
Abalone
physical measurements of Abalone trees
4,177
7
Wine Quality
physicochemical measurements of wines handwritten digits
6,497
11
MNIST
10,000
784
20 Newsgroups
if-idf vectors from newsgroup messages
11,314
21,108
Zebrafish
gene expression in zebrafish embryo cells
6,346
5,434
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 form 120 | wll
21-v T(v)
K, /22 1| y/
(o,
where I 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 differentiable exponential kernel, and in the v + oc limit, we obtain the infinitely infinitely-diffcrennte differrrtiii radial basis kernel. For the intermediate values 3/2 and 5/2, obtain, respectively, once and difeediifferentiable functions.
1/2. obtain the non-
The optimal choice of the bandwidth parameter is problem- -deeedd-de and in supervised settings is typically chosen using tross-validation. In unsupervised settings, it is necessary to rely on heuristics,
'Code to reproduce the experiments in this section can be found at https://gist. gittiiggittuu..... wwt.ta.coom/allaaaaaaaaccoccccae http:///eeceoeooooooo//o///////a

---

GMM
Abalone
Wine Quality
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
200
400
600
800
1000
1000
2000
3000
4000
2000
4000
6000
MNIST
20 Newsgroups
Zebrafish
1.0
1.0
1.0
0.8
0.8
0.8
maximum
0.6
0.6
0.6
0.4
0.4
0.2
0.0
2000
4000
6000
8000
10000
2500
5000
7500
10000
2000
4000
6000
rank
rank
rank
== 1/2
P= 3/2
5/2
v=
Figure 1: The maximum entrywise 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 range of smoothness parameters, each of which is represented by line in each plot. Details of the experiment are provided in Section 5
and for this experiment, we use the popular median heuristic [Flaxman al.) 2016 Mooij et al. 2016 Mu et al. 2016 Garreau et al. 2017]. which has been shown to perform well in practice.
construct four kernel matrices using Matérn kernels with smoothness parameters v = 2: 2: 2 D0, 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 SeiPy library for Python (Virtanen et al. 2020]. We do this for range of ranks d from to n, where is the number of instances in the dataset, and record the entrywise errors.
For each dataset, 3
5.2 Interpretation of the results
Figure shows the maximum entrywise errors for each dataset and kernel. For comparison, the Frobenius errors are plotted in Figure
2 in Section of the appendix.
As predicted by our theory, for the four "iw-dimensiooal" datasets, GMM, Abalone, Wine Quality and MNIST, the maximum entrywise decays rapidly we increase the rank of the approximation, with the exception of the highly non-smooth v kernel, for which the maximum entrywise error decays much more slowly. In addition, the decay rates of the maximum entrywise error in order of the smoothness of the kernels.
For the "high-dimensional" datasets, 20 Newsgroups and Zebrafish, different story emerges. Even for the smooth radial basis kernel (v oo), 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 sharp drop in maximum entrywise error between = 2500 and 3000 which not seen in the decay the Frobenius norm error (Figure in Section
6 Limitations and open problems
To conclude, discuss some of the limitations of our theory, well some of the open problems.

---

6.1 Limitations of our theory
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 kemel (2) converges uniformly. however we don't actually require such 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. [010] 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 asymptoties, 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 nigh-dimensional setting, however our empirical experiments suggest that our conclusions may not carry over.
Verification of the assumptions. While there is established literature studying the eigenvalue decay of kernels under general probability measures Kühh 1987, Cobos and Kühn 1990, Ferreira and Menegatto [013 Belkin 2018 Li al.) 2024], except in very specialised settings (such as Propositions I and 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, refer the reader to Barzilai and Shamir 2023
6.2 Open problems
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 pro- hibitive 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 J. have emerged efficient alternatives, and
there is an extensive body of literature examining their statistical performance [Drineas et al.) 22055
Rahimi and Recht 2007, Belabbas and Wolfe, 2009 Boutsidis 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 classical error metrics such 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 al. 22020)
Lower bounds. At present, 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.
Acknowledgements
The author thanks Nick Whiteley, Yanbo Tang and Mahmoud Khabou for helpful discussions and Annie Gray for providing code to preprocess the 20 Newsgroups and Zebrafish datasets.
This work was supported by the Engineering and Physical Sciences Research Council [grant EP/X002195/1J.
References
Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong, Entrywise eigenvector analysis of random matrices with low expected rank. The Annals of Statistics, 48(3):1452, 2020.
Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang. An lp theory of pea and spectral clustering. The Annals of Statistics, 50(4):2359-233) 2285,,223,,222 2022.

---

Noga Alon, Troy Lee. Adi Shraibman, and Santosh Vempala. The approximate rank of a matrix and its algorithmic applications: approximate rank. In Proceedings of the forty-fifth annual ACM Symposium Theory of Computing, pages 675-684, 2013.
Jason Altschuler, Aditya Bhaskara, Gang Fu, Vahab Mirrokni, Afshin Rostamizadeh, and Morteza Zadimoghaddam. Greedy column subset selection: New bounds and distributed algorithms. In International Conference on Machine Learning, pages 2539-2548. PMLR, 2016.
Sivaraman Balakrishnan, Min Xu, Akshay Krishnamurthy, and Aarti Singh. Noise thresholds for
spectral clustering, Advances Neural Information Processing Systems, 24, 2011.
Daniel Barzilai and Ohad Shamir. Generalization in kernel regression under realistic assumptions. arXiv preprini arXiv:2312.15995 2023.
Mohamed-All Belabbas and Patrick Wolfe. Spectral methods in machine learning and new strategies for very large datasets. Proceedings of the National Academy of Sciences, 106(2):369-3) 374, 2009.
Mikhail Belkin. Approximation beats concentration? an approximation view on inference with smooth radial kernels. In Conference On Learning Theory, pages 1348-1361. PMLR, 2018.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in Neural Information Processing Systems, 14, 2001.
Christos Boutsidis, Michael W Mahoney, and Petros Drineas. An improved approximation algorithm for the column subset selection problem. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 968-977. SIAM, 2009.
Mikio L Braun. Accurate error bounds for the eigenvalues of the kernel matrix. The Journal of Machine Learning Research, 7:2303-2325 2006.
Stanislav Budzinskiy. On the distance to low-rank matrices in the maximum norm. Linear Algebra and its Applications, 688:44-58, 2024a.
Stanislav Budzinskiy. Entrywise tensor-train train approximation of large tensors via random embeddings. arXiv preprint 11Xi: 2024b.
Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Commu- nications of the ACM, 55(6):1 119, 2012.
Emmanuel Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix
completion. IEEE transactions information theory, 5665):2053-2080 2010.
Joshua Cape, Minh Tang, and Carey Priebe. The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics. The Annals of Statistics, 2019.
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, et al. Spectral methods for data science; statistical perspective. Foundations and Trends@ in Machine Learning, 14(5):566-800) 2021.
Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimizationn meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing, 67(20))5239-5266 2019.
Fernando Cobos and Thomas Kühn.. Figenvalues of integral operators with positive definite kemnlss satisfying integrated hölder conditions over metric compacta. Journal of Approximation Theory, 63(1):39-55, 1990.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
Corinna Cortes and Vladimir Vapnik. Support networks. Machine learning, 20:273-297, 1995.
Paulo Cortez, A. Cerdeira, F. Almeida, T. Matos, and J. Reis. Wine Quality. UCI Machine Learning Repository, 2009. DOI: http:///o..oy///22233//555
10

---

Ernesto De Vito, Lorenzo Rosasco, Andrea Caponnetto, Umberto De Giovannini, Francesca Odone, and Peter Bartlett. Learning from examples as inverse problem. Journal of Machine Learning Research, 6(5), 2005.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, (966):41-1422 2012.
Michal Derezinski, Rajiv Khanna, and Michael W Mahoney. Improved guarantees and multiple- descent curve for column subset selection and the nystrom method. Advances in Neural Information Processing Systems, 33:4953-4964 2020.
Petros Drineas, Michael W Mahoney, and Nello Cristianini. On the nyström method for approximating a gram matrix for improved kernel-based learning. Journal of Machine Learning Research, 6(12), 2005.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- trika, (13::21-2118 1936.
Justin Eldridge, Mikhail Belkin, and Yusu Wang. Unperturhed: spectral analysis beyond davis-kahan. In Algorithmic learning theory, pages 321-358. PMLR, 2018.
László Erdós, Benjamin Schlein, and Horng-Tze Tzer Yau. Local semicirele law and complete delocal- ization for wigner random matrices. Communications in Mathematical Physics, 284(2))
2009a.
László Erdós, Benjamin Schlein, and Homn- Tzer Yau. Semicirele law short scales and delocaliza- tion of eigenvectors for wigner random matrices. 2009b.
Jianqing Fan, Weichen Wang, and Yiqiao Zhong. An foe eigenvector perturbation bound and its application. Journal of Machine Learning Research, 18(207): 42, 2018.
Gregory E Fasshauer and Michael J McCourt. Stable evaluation of gaussian radial basis function interpolants. SIAM Journal on Scientific Computing, 3412):A737-A76,, 2012.
Giancarlo Ferrari-Trecate, Christopher Williams, and Manfred Opper. Finite-dimensional approxima- tion of gaussian processes. Advances in Neural Information Processing Systems, 11, 1998.
JC Ferreira and VA3128739 Menegatto. Eigenvalue decay rates for positive integral operators. Annali di Matematica Pura ed Applicata, 192(6):1025-1048 1041, 2013.
Shai Fine and Katya Scheinberg. Efficient svm training using low-rank kernel representations. Journal of Machine Learning Research, 24De4):243-26,, 2001.
Seth Flaxman, Dino Sejdinovic, John P Cunningham, and Sarah Filippi. Bayesian learning of kernel embeddings. arXiv preprint arXiv:1603.0211 02060, 2016.
Damien Garreau, Wittawat Jitkrittum, and Motonobu Kanagawa. Large sample analysis of the median heuristic. arXiv preprint arXiv:1707.07266 2017.
Alex Gittens. The spectral norm error of the naive nystrom extension. arXiv preprint arXiv: | 1100.5305 2011.
Alex Gittens and Michael Mahoney. Revisiting the nystrom method for improved large-scale machine learning. In International Conference on Machine Learning, pages 567-575. PMLR, 2013.
I.S. Gradshteyn and I.M. Ryzhik. Table of Integrals, Series, and Products. Academic Press, edition, 2014. ISBN 978-0123849335.
Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2): 217-288, 2011.
Peter Hall and Joel Horowitz. Methodology and convergence rates for functional linear regression. The Annals of Statistics, 2007.

---

Francis Hirsch and Gilles Lacombe. Elements of Functional Analysis. Springer, 1999.
Jack Indritz. An inequality for hermite polynomials. Proceedings of the American Mathematical Society, 12(6))981-9)) 1-883, 1961.
William Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into hilbert space. Confer- ence in Modern Analysis and Probability, 26: 26:189-206, 01 1982.
Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from few entries. IEEE transactions on information theory, (6(1)))))6): 2010.
Thomas Kühn. Eigenvalues of integral operators with smooth positive definite kernels. Archiv der Mathematik, 49:525-534, 1987.
Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar. Ensemble nystrom method. Advances in Neural Information Processing Systems, 22, 2009a.
Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar. On sampling-based approximate spectral decomposition. Proceedings of the 26th annual International Conference on Machine Learning, pages 553-560, 2009b.
John Lafferty, Guy Lebanon, and Tommi Jaakkola. Diffusion kernels statistical manifolds. Journal of Machine Learning Research, 6(1) 6(1), 2005.
Ken Lang. Newsweeder: Learning to filter netnews. In Machine Learning Proceedings 1995, pages 331-339. Elsevier, 1995.
Michel Ledoux. The Concentration of Measure Phenomenon, Mathematical Surveys and Monographs. Number 89, American Mathematical Soc., 2001.
Jing Lei. Adaptive global testing for functional linear models. Journal of the American Statistical Association, 109(506):624-60) 634, 2014.
Jing Lei. Network representation using graph root distributions. The Annals of Statisties, 2021.
Lihua Lei. Unified + eigenspace perturbation theory for symmetric random matrices. arXiv preprint arXiv: NXXX::199990479: 2019.
Yicheng Li, Zixiong Yu, Guhan Chen, and Qian Lin. On the eigenvalue decay rates of class of neural-network related kernel functions defined on general domains. Journal of Machine Learning Research, 25(82):1 2024.
Vince Lyzinski, Daniel L Sussman, Minh Tang, Avanti Athreya, and Carey E Pricbe. Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding. Electron. J. Statist., 2014.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pages 3345-3354. PMLR, 2018.
Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti. Estimating mixed memberships with sharp eigenvector deviations. Journal of the American Statistical Association, 196553)):1288-144 2021.
Alexander Meister. Asymptotic equivalence of functional linear regression and white noise inverse problem. The Annals of Statistics, pages 1471-1495, 2011.
Shahar Mendelson and Joseph Neeman. Regularization in kernel learning. The Annals of Statistics, 2010.
James Mercer. Xvi. functions of positive and negative type, and their connection the theory of integral equations. Philosophical Transactions of the Royal Society of London. Series A, 209(4114458) 415 446, 1909.
Ha Quang Minh, Partha Niyogi, and Yuan Yao. Mercer's theorem, feature maps, and smoothing. In International Conference Computational Learning Theory, pages 154-168. Springer, 2006.
12

---

Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The Quarterly Journal of Mathematics, 11(1):00-59, 1960.
Joris M Mooij, Jonas Peters, Dominik Janzing, Jakob Zscheischler, and Berhhard Schölkopf. Distin- guishing cause from effect using observational data: methods and benchmarks. Journal of Machine Learning Rexearch, 17(32): 2016.
Krikamol Mu, Bharath Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, et al.
Kernel mean shrinkage estimators. Journal of Machine Learning Research, 17(48):1-41, 2016.
Warwick Nash, Tracy Sellers, Simon Talbot, Andrew Cawthorn, and Wes Ford. Abalone. UCI
Machine Learning Repository, 1995. DOE:
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems, 14, 2001.
Serge Nicaise. Jacobi polynomials, weighted sobolev spaces and approximation results of some singularities. Mathematische Nachrichten, 213(():117-140) 2000.
Cheng Soon Ong, Xavier Mary, Stéphane Canu, and Alexander Smola. Learning with non-positive kernels. In Proceedings of the twenty-first International Conference on Machine Learning, page 81, 2004.
Dmitrii M Ostrovskii and Alessandro Rudi. Affine invariant covariance estimation for heavy-tailed distributions. In Conference on Learning Theory, pages 2531 2531-2550. PMLR, 2019.
David Pollard. Empirical processes: theory and applications. IMS, 1990.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, 20, 2007.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. Advances in Neural Information Processing Systems, 21, 2008
Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11(2), 2010.
Sam Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500) 23222336,,, 2000.
Patrick Kubin-Delanchy Joshua Cape, Minh Tang, and Carey E Priebe. A statistical interpretation of spectral embedding: the generalised random dot product graph. Journal of the Royal Statistical Sociity Series B: Statistical Methodology, (4(4)::446-1474) 2022.
Mark Rudelson and Roman Vershynin. Delocalization of eigenvectors of random matrices with independent entries. Duke Math. J., 2015.
Meyer Scetbon and Zaid Harchaoui. A spectral analysis of dot-product kernels. In International Conference on Artificial Intelligence and Statistics, pages 3394 34022 PMLR, 2021.
Bernhard Schölkopf, Alexander Smola, and Klaus-Robers Müller. Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, (0(5):129--1199 1998.
Tao Shi, Mikhail Belkin, and Bin Yu. Data spectroscopy: Learning mixture models using eigenspaces of convolution operators. In Proceedings of the 25th International Conference on Machine Learning, pages 933-943, 2008
Tao Shi, Mikhail Belkin, and Bin Yu. Data spectroscopy: Eigenspaces of convolution operators and clustering. The Annals of Statistics, pages 3960-3984, 2009.
Alex Smola, Zoltán Ovári, and Robert C Williamson. Regularization with dot-product kernels. Advances in Neural Information Processing Systems, 13, 2000.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. International Conference on Computational Learning Theory, pages 545-560. Springer, 2005.
13

---

Ingo Steinwart and Clint Scovel. Mercer's ' theorem general domains: On the interaction between measures, kernels, and rkhss. Constructive Approximation, 55:363-417, 2012.
Stefan Stojanovic, Yassir Jedra, and Alexandre Proutiere. Spectral entry-wise matrix estimation for low-rank reinforcement learning. Advances in Neural Information Processing Systems, 36: 77056-77070, 2023.
Michel Talagrand. A new look at independence. The Annals of Probability, 24(1):1 - 334, 1996.
Minh Tang, Daniel I.. Sussman, and Carey F., Priehe. Universally consistent vertex classification for latent positions graphs. The Annals of Statistics, 41(3):1406 1430, 2013.
Terence Tao and Van Vu. Random matrices: Universality of local eigenvalue statistics. Acta Mathematica, 106(1):127 - 204, 2011. doi: 10.1007/111511-011-0000
Madeleine Udell and Alex Townsend. Why are big data matrices approximately low rank? SIAM
Journal on Mathematics of Data Science, 1(1):144-160, 2019.
Ernesto Araya Valdivia. Relative concentration bounds for the spectrum of kernel matrices. arXiv preprint arXiv: 11/2::::1/2.02100 2018
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, ilhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. Quintero, Charles R. Harris, Anne M. Archibald, Antonio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272 2020. doi: 10. 192-001-0086--2
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17:395-416, 2007.
Van Vu and Ke Wang. Random weighted projections, random quadratic forms and random eigenvec- tors. Random Structures & Algorithms, 47(4):792-821, 2015.
Daniel E Wagner, Caleb Weinreb, Zach M Collins, James A Briggs, Sean G Megason, and Allon M Klein. Single-cell mapping of gene expression landscapes and lineage in the zebrafish embryo. Science, 360(6392)9811-987, 2018.
Christopher Williams and Carl Rasmussen. Gaussian processes for regression. Advances in Neural Information Processing Systems, 8, 1995.
Christopher Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. Advances in Neural Information Processing Systems, 13, 2000.
Robert C Williamson, Alexander J Smola, and Bernhard Scholkopf. Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators. IEEE transactions Information Theory, 47(6):2516-2555 2001.
Jiaming Xu. Rates of convergence of spectral methods for graphon estimation. In International Conference on Machine Learning, pages 5433-5442. PMLR, 2018
Yiqiao Zhong and Nicolas Boumal, Near-optimal bounds for phase synchronization. SIAM Journal on Optimization, 28(2):989-1066, 2018.
Ding-Xuar Junn Zhou. The covering number learning theory. Journal of Complexity, 18(3)739-767, 2002.
Huaiyu Zhu, Christopher KI Williams, Richard Rohwer, and Michal Morciniec. Gaussian regression and optimal finite dimensional linear models. 1997.
14

---

Appendix
A Proof of Propositions I and 2
For notational simplicity, in this section we will assume in this section that the eigenvalues and eigenfunctions are indexed from rather than
A.1 Proof of Proposition
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 (0,, o²), which we will denote by μ..
Let K. L3 - L2 denote the integral operator associated with the kernel and the measure and let } denote its eigenvalues, arranged in descending order, and {u,} denote their corresponding eigenfunctions. By the rotation invariance of both and p. the operator IC may be written as the p-fold tensor product
K K ② & IC
where K. 12 - F denotes the integral operator associated with the kernel & and the univariate Gaussian measure μr. Let (A:} denote its eigenvalues, arranged in descending order, and {ui} denote their corresponding eigenfunctions. Then, the eigenvalues and eigenfunctions of IC and K. are related in the following way (see (Shi al. [2008] or Fasshauer and McCourt (0012). For every i, there exists i1,..., 8p satisfying 2 1 = such that
A
II
X
and
(x)x)
Wiy (x*) j=1
II
(1I)
f=1
for all x (at ,...,, T TRP. Now suppose that X; = 0 (e- then
Big c -BE, E,
j=l
j=1
and suppose that ||u/|oo Oe)*) for some
3/2, Then
M II 2=1
S II e ei 1=1
Therefore to prove that (E) hold under p. 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 u : 20 /w2 and let (.(x) be the ith order Hermite polynomial. Then the eigenvalues and eigenfunctions of K. are given by
V
A
1
V1+ 2v
(1 /1 +
20
u(xx) (1 1// 1/8
x² 2 20
Hi ((
8 1/4 +
x
exp
2
0
Therefore, we have X; = -Be where
1 1+ VI 2u
B = log
We will now show that each u; is uniformly bounded. By a change of variables, we can write u; as
C2
U4 (x(x) =
22-1! e H.(y)
15

---

for some R. On the other hand, we have the following inequality due to Indritz [961]. For all R,
H2(x) S 1.09
Therefore (.( S 1.09C2 for x. We can use fact that H; (xx) is either odd or even to obtain an analogous lower bound. Therefore ||u/|lso I 1.09C² for all so 0 and (E) holds.
We will now show that P, for all so that (R) holds with b +oo and there no requirement on the eigengaps A,
Expanding J u; (z))d((z)) collecting exponential terms and applying change-of-variables, calculate that
/ ux(x)dp(z) = C3 e e-v Hyyy)
It is standard result that e- Hy) 0 long as i + 0 Gradshteyn and Ryzhik 2014]. and therefore |f (x())d(())) = 0 for all i 2 1. and by 11 we have that I'; for all 2 1.
A.2 Proof of Proposition
For any p 2 3, dot-product kernels with respect to the uniform measure the sphere exhibit the spectral decomposition
k(1, v)
u (1)mi, (3)
1=0
m=1
where the eigenfunctions (uī,m) are the ruth spherical harmonic of degree Nr 2-pp-2 (1+p-3))
p-2
( 22 is the number of harmonics of each degree, and {A') are the distinct eigenvalues [Smola
al. 2000].
The first spherical harmonic is constant function, and therefore by the orthogonality of the eigen- functions in 1. "m.m (x))p((()))))))))))))))))))))))) for all / 2 1, and therefore r; = 0 for all i 1. Therefore (R) holds with +oc, and there requirements the eigengaps.
In addition, Lemma of Minh al. [2006] shows that the supremum-norm spherical harmonic is upper bounded by
[ box
o (1
(12)
SP-11
The eigenvalue decay rates are obtained from Propositions 2.3 and 2.4 Scetbon and Harchaoui 2021 and given (12), the condition > (p² -4p + 5)/2 ensures that the conditions for (P) are met.
B Proof of Equation (5)
We begin this section with two upper bounds on polynomial and exponential series, which we prove in Section B.I. and which we will use throughout this proof.
Lemma 2. Let a > 1, B > 0 and 0 < S 1 for fixed constants. Then the following upper bounds hold:
-- O (d=at),
Σ d=1+
e - = =0 (6 (c-00 (d0dd-1).
1=d+1
even within lines. Throughout this proof, & 0 will denote some constant which may change from line to line, and
To show equation
5
we first note that under (P) with d 1(n
Σ ra aasd 0 ( --1
1=d+1
i=d=1
16

---

where we have used Lemma
In addition, under (E) with d > log (n we have that
Σ
A
e pr S E 3d 7' = -(+e)
(1+c) log (1 (1111// (n 1/9 - On
1=++1
1=++1
where we have again used Lemma 2 Now, by the triangle inequality have that
x
1=d+1
1=++1
1=d+1
and therefore we are left to show that
Σ N Σ
o (n-(o-1)/ log(n)) (n-))
under (P) with d = 52 (2n1//n)
A
(13)
under (E) with d loog 10gg//11 (n (1))
(=d+1
To bound (33, we employ a fine-grained concentration bound due to Valdivia 2018 We begin with the polynomial hypothesis. The authors only consider the cases that o, are natural numbers, since they draw a comparison between between these values and Sobolev-type notion of regularity. Inspecting their proofs, they treat the cases r = 0 and 2 separately, however their proofs follow through in exactly the same way when the r 2 case is replaced with r > 0, in order to cover all values of a > 2r + 1, 2 O. For the > 0 case, they derive the following result.
Lemma 3. Suppose that the hypothesis (P) holds with r > O. Then, with overwhelming probability
X
A 2 B(t,n) log(n)
where
j -- (r+)))
filiin 5t;
n) =
g 2 (1+3) 1/2
if कका sis in sism;
j-atrtIn-1 1/2
Via some rearrangement we can show that
if
and by Lemma we have that
[n2/2r]
[nt/2rj
Σ
I log(n)
Σ
a
S
log(n).
(14)
n
t=d+1
1=0+1
In addition, we have that
X
Σ
A
S n2 1/2 (/1g(())
Σ
i a-++ti
1= [2(2m/2
1=(nt/2r
-at++2
3 12 1/2 log(n):
(15)
17
5 n log(n)
S n
where we have used that 0 < r < (a- 1)/2. Combining (4) with (15) establishes (13 under (P) omit the details.
assuming > 0. The case with = 0 follows analogous fashion
We now turn to the hypothesis (E). The authors only explicitly derive a result for the case that 7 1, however following through their proof with Lemma 2 to hand, we obtain the following for the general case that < 1.
Lemma 4. Suppose that the hypothesis (E) holds with > 0. Then, with overwhelming probability
X;
A S (-
;1-7n 1/2 log(n)
for all 1 isis
17

---

Therefore we have that
2 1/2 log(n)
Σ
el-
n
imd-l
S 1/2 log(n)
(8/2+e)1 8
id+11
X 1/2 log(n)
(-6 /2+c)
$ 1/2 1og(n)m (11/2e))
where in the second inequality have used the assumption that 8 3/2 and in the fourth have The case for follows similarly, so we omit the details. Then Equation (5) is
used Lemma 2 established.
B.1 Proof of Lemma 2
To bound the polynomial series, we upper bound it by an integral as
d a++1
O (d-att).
d
+1
To bound the exponential series, again employ an integral approximation, and upper bound it
BF7
e 352 dt.
1od+1
We then apply the substitution
B8 to obtain
di
/ B8
e --
1r
(2.0ar)
where I' denotes the incomplete Gamma function. We can then use the fact that I(s, 2) S 22-- for 0 to obtain the upper bound
1 (
3d
1 -
-ad ad
(Bd7)
B ad d'-y
7
7
from which we can conclude that
= 0 (c2
e
1=d+1
required.
C Proof of Lemma 1
The proof of Lemma generalises the proof of Lemma 43 of Tao and Vu [211]]. We will make of the following theorem due to Ledoux 2001 which is corollary of Talagrand's inequality Talagrand] 1996).
Theorem 4 (Talagrand's inequality). Let = (y1....,yhh) be a vector of independent random variables, and let f I - R be convex 1- Lisiiiitttttuuccti function. Then, for all t 2 0,
(If(vv) - M(F) t) < 4 exp (-t/16)
where M (f) denotes the median of f.
18

---

It is easy to verify that the map y - (v)ll is convex and 1-Lipschitz, and so by Talagrand's inequality we have that
PP (II - M(I (v) 2 s 4exp (-f/16).
(16)
For 2 8, we have that so to conclude the proof, it suffices to show that
4 exp (-(t - 4)6/16) - exp (-t2/2)..
(x) 0 / 4.
(17)
Let E denote the event that | 2 / + and let ع_ denote the event that || -
0/9- 4. By the definition of median, (T7) established if we can show that P(E+) < 1/2 and P(E-) 1/2..
Let be the mean-zero random vector such that y = E+ and let P = (pis) igi,sn be the orthogonal projection matrix onto H. We have that tr pa = tr P = Σ, Pis = q and pal I 1. Furthermore
[[][()]] - 0²q = Σ
PijeiE; - o² = S + S2.
15655h
where S = P and S2 Eisigjen PigEiEj. We now upper bound the expectations of S? and S3 which will use later on for bounding the probabilities of & and E- using Markov's inequality. Before we do, note that since E [-ø.1 1 ø] almost surely, Popoviciu's 's inequality implies that 0² $ 1/4 Therefore, we also have that E(e,) S o², and so
E (S?)
Σ
PaPjj E (Ee - -f) (5) - = Σ
PI -
1
i=1
(18)
2 Pis
Re - 20 (57) + (09) <
2
10² - -( + (0-)3) S so²q
Pi
1=1
where the second inequality follows from the independence of (s? - - and (c} o²) for all í + j. In addition, we have that
= Σ EEEE < (03) o²9
E
($
E
Σ (Fj
PiySiEj
(19)
4
To upper bound the probability of E., we first observe that by assumption
[ || + [| < ||
and therefore we have that
P(EE)) = IP (v)l 2 o / < P (1 8o S (P(Tn(())) 2 و²g + 40 vo)
Using the definitions of S₁ and S2, it follows that
IP(E+) < P (S1 + S₂ 2 4a ( PP > 20 ② + (S2 2 20 /
By Markov's inequality, we have that
E ES 1
P > 20 P
40
402g 4
and similarly that
E E
TP (S2 2 20 /g) = P 2 40 4)
<
<
402g
16'
therefore follows that (P(()) < 1/2. We upper bound IPEE) in similar fashion. Since T (=) we have that
||TH( >
P (E_) (([THH())] S / < {([]TH()))
So = ((I==(())1 00'q-80
19

---

Again, recalling the definitions of S1 and S2 we have that P ((E-) S P (Si + S2 v - + 16) I P(Si - 4) P(S2 S - 40 V
As before, applying Markov's inequality we have that
E E(
P(SI < 8 -
4/ -
s P( 2 64 - 64o 160 S IP (5 2 80
5 8
80
where we have twice used the assumption that 64/0². Similarly
E
(5
1 -
P(S₂ - 8 40 - P
($2 2 80
8
32
It therefore follows that P PE-_) < 1/2,, thereby establishing
and concluding the proof.
D Proof of the claim that ||
[,)
S 2|
In this section, we prove the claim made in the proof of Theorem Ithat
| S 2/
(20)
with overwhelming probability, which require in order to invoke Lemma 1 convenience, we shall assume we are working in an n-dimensional space, rather than an (n1 - 1)- dimensional space this is immaterial in our big-O bounds.
For notational
Recall that ÿ is 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
Ax+1= (n-
This implies that under (P), d' = O (n>/5a), and under (B), d' < log (n2/5)). Clearly d' S d and so J C {d' + +I,..., n2, and therefore
[ ([
In addition, we observe that
( (1)] =n |T (1)11²
Since |J] (n). it will suffice to show that
| (1) = 12 (11111112-11)
(21)
with overwhelming probability.
Let Ux and Us denote the n x d' matrices with entries
(21(1,) (t = 1/2
(i.j) = (1),
respectively. Then we have
1 ||
1 10 1
00 1| = 16 W) _1|
where Win is orthogonal matrix which will define later By the triangle inequality, we have that
2
| 2 - 1a - U
||11 = |0 |1 &.a - UJ 2
and therefore show
21 we need to show that
| 111 1 0 (0 (1/2--0)001)
(22)
and
Do - -UT 0 -0''n"
(n-
(23)
with overwhelming probability.
20

---

D.1 Bounding (2
To bound (22 we begin by using the the inequality (c1 + o2)² 2(c + c
write
u (x,)
U
n
n2
1=1
2
( (u(o))p(()))
ux(x;)
-f fm(o)dptt))
n
To bound the first term, we observe that since {ush== forms an orthonormal basis for L (2)) we have that
( (u(w)do(s))
Σ
E=
and therefore
Σ ( (u())d((z))
Σ (fulerdptes) 1 T
=1
1dd'11
By assumption,
Fø+1 = O (A 0 (n" b/c))( 0 -000)-200000pp
where we have used the assumption that b > 5/2, and therefore
Σ (f (u(e)do(ss) =1 (n b/6 (n- 1 -0 (1-1/2-a(())
as required.
Now to bound the second term, use Hoeffding's inequality to obtain that
(1:)))
fu((edp(()) = =o -Olllllo log (ggl/((n) n2/22
n
Under (P), we have that for all d'
||11//5 d S n/n =0
(1(1/22) 0 On ((12116-00))
where we have used that r < (a <a S a/2, and that { {>> 8, and under (E)
|| S 0d < slgg(n/)E o (n 1/E))) = O(n On
1/10 (116))((1))
where we have used that < 3/2, Therefore, since d' = (n2/b), we have that
(x:)
f mu(o)do(t) S (n1/16-1/2) 0 ((n (n-3/4
n
which is O (z (1211/2-01)) as required.
D.2 Bounding 23
To bound
23 we begin by defining the x d' diagonal matrices Arr and Axr with diagonal entries
(i, As.
respectively, and the n x matrices Ter and o with entries
(i.5) x3/22 (i),
(r 22/22,(0)
21

---

respectively. Then in matrix notation we have that
Dx =n2 N/222
Dx UZ
Now, we decompose Ug Wa Up as
Wa 1// { 1112/2 De - (s)) + Üw (W - -yd } A-1/2 and so we have that
La - Un| S Xx 1/2 111 a. 1 We - -D - + W 1/2 / Wx |
1/2
By the construction of we have that Ay = Q(n 1/5) = 1/8) and therefore 1/22 A
O (n1/1e). Therefore to show (23. it will suffice to show that
Te. We T2
o ((C))
(24)
and
W 22/ O (n fe- (n-
(25)
To obtain the bound 24 make of the following result which is Equation 3.8 of Tang al. 2013]. Lemma 5. The exists an orthogonal matrix Wa (constructed as in 29 such that
TaWW. $2 =0 ( log logg/²(n)
Ad Ad+1
with overwhelming probability.
Now, let
d' = arg max the A1413.
(26)
'2
then by the assumption (R), we have that
Ad- A 0(22))) = 1nn = St (1-1/8+R(V).
(27)
Using Lemma obtain that
< T Wa - Da - log log'/2 (2
T Wer 2x
O =
(nt/8-ac1)
Xx. Ao
which establishes
24 Obtaining the bound (25) requires some new concepts, so dedicate its
own section.
D.3 Bounding
25
We now turn attention to the bound (25). We begin by defining H. the reproducing kernel Hilbert space associated with the kernel k, and define the operators KH KH,Kx H H. given by
KHf= = f (f. ko) kodp()))
(28)
Rx Σ (u,kni kaz
where (-) = x(),z)) and (1,)) is the inner product in H. These operators are known as the "extension operators" of IC and K, respectively, and it may be shown that each has the same eigenvalues as its corresponding operator, possibly up zeros (see e.g. Propositions and 9 of Rosasco al. 2010).. We will make use of the following concentration inequality for Kx Kx which is due to De Vito et al. 2005 and appears Theorem 7 of Rosasco et al. (2110).
22

---

Lemma 6 (Theorem 7 of Rosasco et al. (2010)). The operators Kn and Ru are Hilbert- Sehbbrr-Schmidt, and
(
logg/((n))
|Ru Kn
=0
n2//2
with overwhelming probability.
Let (ux,a denote the eigenfunctions of K' corresponding to the eigenvalues (Aitiga and let (ūn,))iee denote the cigenfunctions of K corresponding to the eigenvalues {A//niia. We define the infinite-dimensionaa "matrices" Un.d and Un.d whose columns contain the eigenfunctions (ux,aliga and {ūH,,)iga* respectively. These "matrices" are well-defined with matrix multipiccation is defined usual with inner products taken in H. We will refer to Un,d: UH,d and the subspaces spanned by their columns interchangably.
Let Ha = UH, with entries Ha(i,j) = (uH,i, "H.)H and denote its singular values by Ei,...,
,.....,,a. Sa. Then the principal angles between the subspaces Un. and Ün which we will denote by .i...., Os, are define as via & cos(O:). Define the matrix
sin θ (Ur.dd UH.a)) diag (sin
Let d' be as in (26 so that Ad- - Aa = (n-118+2()). Since d' 2 d', by the Davin-Kahan theorem, have that
V2 Rx -
Kne
sin θ (Uxaar, Ureal) )1 sin Q (Uzir Un,,a)
Aa Ad
V2 Ru KN KH||IS O - (n-3/882(1)
Aa- Aa++1
where the second inequality comes from the relationship from Lemma 6 and (27).
||-|l S II and the final inequality follows
We now come to constructing the matrix Wa. We denote the singular value decomposition of as H Wa T. T and define the matrix Wa by
d,2
W = W..
(29)
which is known as the "matrix sign" of H. Let Pa and Pa to be the projections onto the subspaces Undd and Un.d, respectively. Then we have the following decomposition.
Wx N1/2Wa (Wv - Ha -H + Aa (Ha WWr)
(R# KH)(P -Pa)UH
(30)
UF (RoH KKH Har
We first observe that Hæ S 110 [|||UH, 1. and by
5
Aa
||A
0(1). In addition,
following the same steps as in the proof Lemma 6.7 of Cape et al. (in)equalities for dinee-aimensional matrices) we have that
2019 (who prove similar
PPx Par = sin (Ün.er Un,er
0 (n 3/8 3/8--((1)
[H -ii--Wall = |sin θ (Uze,v Une.
11
O n -//44-111)
We now turn to bounding | (RH - KH)UH To condense notation, let Q = (K Kz)U We will bound |[Q] using classical e-net argument. Let S be e-net of the (d - 1)- dimensional unit sphere gd-1 := (v. ||l|| 1}. that is, a subset of gd-1 such that for any gd-1
23

---

there exists some Wy E s such that || - -wwll <. Then, we have that
||||
max
v0" Qui
w:|| 1s1
max
(2 - we + we) Q wo + we)
w:|| 151
- (s² + 2c) || + max
w [TTQul
WESt
With E = 1/3, we have
1Q1 S 9
| Qul
max
2
wEs
Using the definitions (28
its (1, m)th entry can be calculated as
n k( (t) (11z) - // Kor.,)uuoooommoooooo000o0o
@).m)
(31)
and for given S have that
w Qui
Q m))(())m(m)
1i==1
n k(r, (5) -f
lf k(,,, hic.:))lleeo
Σ
(()((m)
n
[m((i)) n -
max
Lu llo
Σ
(())
(m==1
where we have used that k( y) S 1 for x, y E X. This is sum of independent random variables, so by Hoeffding's inequality, we that that
2nt
TP
(1 (I T Quel 21) S exx
maxi ||u
where we have used that Ed Eim= w())w(()) is no greater than 18d (see, for example, Pollard 1990 ). using union bound we have that
The set s can be selected that its cardinality
w Tw@ 2 g
P [IQ 2 f) S IP
max w
N
s Σ w / [ [ww|
2
N
8nt2
< 18 exp
81 $l.maxisisa
| llc
8nt2
d' d'loo((1))
< 2exp
81 maxi |ullls
< 2cxp (2(121/8011)) n3/442)
where we have used that d' 0n2118-2(1)) and maxisise |1 O112/16), Choosing è 2n ((16))((() we have that
IP (I인11 2n -/16--1-)))) < 2exp (-nd18) S -c
for any e 0 for large enough n. Therefore
||Q|| = 0 0n (1-5/10-2(1))
24

---

GMM
Abalone
Wine Quality
1000
800
100
600
Rrabemius
75
400
25
200
0
200
400
600
800
1000
0
1000
2000
3000
4000
2000
4000
6000
MNIST
20 Newsgroups
Zebrafish
80
Froberius
400
60
40
200
2000
4000
6000
8000
10000
2500
5000
7500
10000
2000
4000
6000
rank
rank
rank
== 1/2
P= 3/2
= 5/2
v=
Figure 2: The Frobenius-nome norm eπror 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 range of smoothness parameters, each of which is represented by line in each plot. Details of the experiment are provided in Section 5
with overwhelming probability. Combining the above bounds with 30 we obtain that
W A/2
X W =
(1-1111--11)))
which establishes 25 and therefore completes the proof.
E
Additional details about the experiments
In this section, we provide some additional details and plots relating to the experiments in Section
E.1 Details about the datasets
GMM is synthetic dataset of 1,000 simulated data points from 10-component Gaussian mixture model with unit isotropic covariances and means of size ten on the axes. Abalone [Nash al. [995] and Wine Quality [Cortez 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 Abulone dataset to retain only the continuous features. MNIST (Deng] 2012 is dataset 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 the theory we present in Section
In addition, we consider two "high- dinenniimmnsional" datasets. 20 Newsgroups Lang 1995 is 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-invers document frequency (tf-idf) features for each word. Zebrafish [Wagner et al. 2018 is dataset of single-cell gene expression in zebrafish embryo taken during their first day development. We subsample 10% of the cells, and process the data following the steps in Wagner et al. 20188
25

---

E.2 Frobenius norm errors
Figure shows the Frobenius norm error the low-rank approximations. For the -iwddiinnsional datasets GMM, Abalone, Wine Quality and MNIST, the Frobenius norm eтrоr 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 3000 that the maximum entrywise error exhibits.
E.3 Implementation details
The experiments were performed on the HPC cluster at Imperial College London with cores and 16GB of RAM. The GMM experiment took less than minute; the Abalone, Wine Quality, MNIST and Zebrafish experiments took less than hours; and the 20 Newsgroups experiment took less than 24 hours.
26

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See Section Contributions
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of our theory discussed extensively in Section 6.
27

---

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 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 few datasets with 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, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or 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, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and 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 [ The full proof is provided in Section 4 and additonal
technical details are provided in Sections B and D Proofs of Propositions and 2 are
provided Section
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 cross- referenced.
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 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.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Code reproduce the experiments is provided with the submission.
Guidelines:
28

---

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 novel architecture, describing the architecture fully might suffice, or if the contribution 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 accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions 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
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.ccppullc//guus httpbb/ii/ggiiide/d//eebbbb//aae
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
29

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Preprocessing of data is explained and code provided. There are no hyperpa- rameters to tune or data splits in our experiment.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
Our experiments are deterministic, so there are no error bars to show.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Details are provided Section
E
Guidelines:
The answer NA means that the paper does not include experiments.
30

---

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 compute required for each of the individual experimental runs well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http::://ppprrss.cccoooo////ccca
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. 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 high cost. Our work foundational theory, and we don't foresee any negative societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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 tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it 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, 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 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 unintentional) misuse of the technology.
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).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
31

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Licenses for the datasets used the experiments are described with the provided code.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the bataasets.ppprsstttt paperswi theode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
32

---

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 research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the 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.
33


Reviews:
[{"review_id": "oQ1pMXZdQV", "reviewer": "Reviewer_tJPJ", "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.", "questions": "- Is it possible to prove Lemma 1 with additional assumptions that are suitable to the current setting?\n- In the proof of Lemma 1, there are other minor problems listed below.\n1) In line 618, $\\xi_i \\in [0, 1]$ is wrong since the mean $\\bar{x}$ is subtracted.\n2) In the equation below line 621, why $\\| \\pi_H(x)\\|^2 = \\| \\pi_H(\\bar{x}) \\|^2 + \\| \\pi_H(\\xi) \\|^2$?\n3) In the equation below line 621 and several other places, $X$ should be $x$. Also, $\\bar{\\xi}$ should be $\\xi$.", "limitations": "The work does not seem to have potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "- The problem is a very fundamental one and it is considered both analytically and numerically.\n- The writing is very clear and easy to read.", "weaknesses": "- Lemma 1 is wrong, and thus the proofs of the main results do not work. \nConsider 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.\n-> The proofs of the main results would work after modifying Lemma 1 as suggested by the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "I would like to start by thanking the reviewer for taking the time to work through my paper, in particular for working through the proofs in the appendix and for noticing a mistake in Lemma 1 which I address below. I was happy to read that they consider the problem to be very fundamental and that they found the writing to be very clear and easy to read.\n\nThe reviewer is correct that there is indeed a mistake in Lemma 1, although this can be rectified with a simple modification of the lemma statement, which does not materially change the proof of the main result. As mentioned by the reviewer, in the proof of Lemma 1, I have implicitly assumed that the variance of each element of $a$ is one (which, in fact, by Popoviciu's inequality is not compatible with the assumption that each element of $a$ is uniformly bounded in $[0,1]$). This can be rectified by simply assuming that each element of $a$ has variance $\\sigma^2$ and replacing each $q$ with $\\sigma^2 q$ in the lemma. The lemma statement would then read:\n\nIf $H$ is such that $\\|\\pi_H(\\bar a)\\| \\leq 2(\\sigma^2 q)^{1/4}$, then for any $t \\geq 8$\n\n$$\n\\mathbb{P} \\left( \\left| \\|\\pi_H(a)\\| - \\sigma q^{1/2} \\right| \\geq t \\right) \\leq 4 \\exp(-t^2/32).\n$$\n\nFollowing this modification through in the proofs, $S_1$ defined in line 616 would become $S_1 = \\sum_{i=1}^n p_{ii} (\\xi_i^2 - \\sigma^2)$ and therefore $S_1^2 = \\sum_{i,j=1}^n  p_{ii} p_{jj}(\\xi_i^2 - \\sigma^2)(\\xi_j^2 - \\sigma^2)$. Now for each $i \\in \\{1,\\ldots,n\\}$, $(\\xi_i^2 - \\sigma^2)$ are independent mean zero random variables and therefore for $i \\neq j$, we have that $\\mathbb{E}\\{(\\xi_i^2 - \\sigma^2)(\\xi_j^2 - \\sigma^2)\\} = 0$. Therefore\n\n$$\n\\mathbb{E}(S_1^2) = \\sum_{i,j=1}^n  p_{ii} p_{jj}\\mathbb{E}\\{(\\xi_i^2 - \\sigma^2)(\\xi_j^2 - \\sigma^2)\\} = \\sum_{i=1}^n p_{ii}^2 \\mathbb{E}\\{ (\\xi_i^2 - \\sigma^2)^2 \\}\n$$\n\nas required. From hereon, the proof of Lemma 1 follows through. \n\nIn the main thread of the proof of Theorem 2 from line 206, we can set $\\sigma^2$ equal to the variance of $k(x_1, y)$ where $y \\sim \\rho$. Provided that for all $x_1 \\in \\mathcal{X}$ we have that $\\sigma^2$ is bounded away from zero, then the rest of the proof holds. I will add this non-degeneracy condition as an assumption to the theorem.\n\nAdditionally, I thank the reviewer for pointing out two more typos. The equation below line 621 should contain an inequality $\\leq$ rather than an equality. I will correct the typos relating to $x$ and $\\xi$​.\n\nI will be interested to hear whether the reviewer is satisfied with this correction and if they are, their view of the paper as a whole.", "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": "", "extra_scores": {}}, {"review_id": "0uHjWUaUsG", "reviewer": "Reviewer_3p4Z", "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.", "questions": "1. (Line 82) What do you mean by \"infinite sample limit of $\\frac{1}{n}K$\"?\n2. Could you provide more general examples that completely follow the assumption (E)/(P)?\n3. Is this error bound optimal? Are there any lower bound results?\n4. 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?\n5. Regarding the importance of entrywise error bound, could you provide more concrete examples?", "limitations": "There is no negative societal impact of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clear and well written. The proof seems to be solid.\n2. The entrywise error bound is new to the community. \n3. The assumptions on polynomial/exponential eigenvalue decay seem general and cover lots of common kernels.\n4. Some statements about random matrix theory and concentration inequalities are provided (e.g., Lemma 1), which could be independently useful to the community.", "weaknesses": "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.\n2. 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)?\n3. 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.\n\nMinor typos: \n1. Line 578/588 hypotheses-> hypothesis\n2. Line 539/581 miss a period", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To begin, I would like to thank the reviewer for taking the time to review my paper. They considered the writing and proofs to be clear and accurate, and the theoretical result to be new to the community. \n\nThe reviewer mentions that the assumptions on the eigenvalue decay and the eigenfunction growth (assumptions (P) and (E)) are hard to verify for general kernels. Indeed, this is a general shortcoming of many theoretical works on kernel methods which I discuss in the limitations section of the paper, but I will provide some additional context here. As noted by the reviewer, each of these assumptions imply the convergence of the eigendecomposition. Firstly, given the eigenvalue decay condition (either polynomial of exponential), the eigenfunction growth condition is the weakest possible which ensures the convergence of the eigendecomposition. We need explicit decay/growth conditions on the eigenvalues and eigenfunctions for two reasons: firstly, our results rely on a state-of-the-art eigenvalue concentration inequality due to Valdivia (2018, Theorem 2) which we use to prove equation (4), which explicitly require these assumptions. I am not aware of any other such results in the literature which are sufficiently tight for the purposes of this proof. Secondly, our result relies on explicitly bounding $\\sum_{j>d} \\lambda_j$​ for which we use the eigenvalue decay assumption and the proof of the claim proved in Section D repeatedly employs Hoeffding's inequality for which we require the explicit eigenfunction growth assumption (for example, in line 590). \n\nThe reviewer also mentions that they believe that assumption (R) does not seem natural. A similar comment was made by reviewer 2JjA, so I respond to this in the global response.\n\nI also respond to the reviewer's comment that the contributions are undetermined given previous work in the global response.\n\nIn view of the importance of the entrywise error bound, fairness is one important reason and another is that such bounds can be used to show improved bounds for other algorithms which use these approximations (see response to Q5).\n\nI thank the reviewer for pointing out some minor typos, they will be corrected in the revision.\n\nIn response to the reviewers questions:\n\n1. Viewing the matrix $\\tfrac{1}{n}K$ as a operator which acts on vectors $y\\in\\R^n$ (which we also view as a function from $\\mathcal X$ to $\\R$, associating each $i$ to $x_i$) with matrix multiplication, i.e.\n\n   $$\n   [\\tfrac{1}{n}Ky]_i = \\tfrac{1}{n}\\sum_{j=1}^n K(i,j)y(j) = \\tfrac{1}{n}\\sum_{j=1}^n k(x_i,x_j)y(j)\n   $$\n\n    and taking the $n\\to\\infty$​ limit we have \n\n   $$\n   [\\tfrac{1}{n}Ky]_i \\to \\int k(x_i,z) y(z) \\:\\text{d}\\rho(z) = \\mathcal K y.\n   $$\n\n2. E.g. smooth radial kernels follow the eigenvalue decay assumption in (E) (see Belkin (2018)) regardless of the data generating measure. The exponential eigenfunction growth condition is then very mild.\n\n3. I'm not aware of any lower bounds for the max-norm, although this would be an interesting direction for future research.\n\n4. This optimisation problem is likely highly non-convex, but this would be an interesting avenue for future research.\n\n5. Beyond fairness, for example, this max-norm bound could be used to show stability bounds for algorithms which use this low-rank approximation in place of the true kernel matrix. For example, Proposition 2 of Cortes et al. (2010) derives a stability bound for a SVM trained with a kernel approximation in terms of a spectral norm bound on the kernel approximation. For the values of $d$ allowed in our Theorem 1, this bound would not show consistency of the estimator learned with the kernel approximation, however a napkin calculation suggests that one could show consistency using our entrywise bound, although this is beyond the scope of this paper.\n\n*References:*\n- Mikhail Belkin. Approximation beats concentration? an approximation view on inference with smooth radial kernels. In Conference On Learning Theory, pages 1348–1361. PMLR, 2018.\n- Cortes, C., Mohri, M., & Talwalkar, A. (2010, March). On the impact of kernel approximation on learning accuracy. In *Proceedings of the thirteenth international conference on artificial intelligence and statistics* (pp. 113-120). JMLR Workshop and Conference Proceedings.", "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": "", "extra_scores": {}}, {"review_id": "M8RohoUDnU", "reviewer": "Reviewer_2JjA", "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.", "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?\n\n2) 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?   \n\n3) 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.\n\n\nTypos and other comments\n\n(106) maximum entrywise \"error\" (missing)\n\n(186) should be $ \\\\hat{u}_i(1)$, instead of $ \\\\hat{u}_l(1) $\n\n(647) later on\n\nI would prefer if you do not use $(a,b)$ both for constants in assumption (R) and for vectors in the proof of Theorem 2.\n\nIn 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: \n\n- 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.\n- Shah, Devavrat, et al. \"Sample efficient reinforcement learning via low-rank matrix estimation.\" Advances in Neural Information Processing Systems 33 (2020): 12092-12103.\n- 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": "The authors have addressed limitations adequately.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) This is a first result showing entrywise error guarantees for low rank approximation of kernel matrices. \n\n2) Proof sketches of two main theorems are clear and easy to follow.\n\n3) Strongest technical contribution of this paper is proof given in Appendix D that, simply speaking, shows that the norm of projection of vector 1 on the subspace spanned by $n-d'$ eigenvectors with smallest eigenvalues is vanishing sufficiently fast.\n\n4) Experiments are complementing theoretical results well.", "weaknesses": "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. \n\n2) 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.\n\n3) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "I thank the reviewer for their time and effort reviewing my paper. \n\nThe reviewer argues that Lemma 1 is only a slight generalisation of Lemma 68 in Tao and Vu (2011), although understanding the conditions which one must place on the mean vector when it is non-zero for the lemma to work required some technical innovation, and could not simply be guessed without working through the mathematical details. I provide more details in the global response.\n\nI was happy to read that the reviewer found the proofs in Section D to represent a strong technical contribution and I agree that it deserves more space in the main paper. The main reason that it did not receive it was simply space limitations. If space allows, I will include a sketch of Section D in the main paper in the revision.\n\nIn response to the concern about assumption (R), I provide additional details and discussion in the global response.\n\nI included the double descent observation as a curiosity for readers and other researchers, in the hope it may encourage additional investigation into the phenomenon. The phenomenon does occur at lower quantiles albeit less extremely (even at the median in some cases), and I can include some additional plots in the appendix, however I don't plan to investigate this further in this paper.\n\nI thank the reviewer for pointing out some typos which I will correct, and I agree with the comment about using the constants $a$ and $b$ in multiple settings. I will use different letters for the vectors in the proof of Theorem 2. I also thank the reviewer for noticing the incorrect citation in the introduction - it is a typo! I had meant to cite the mentioned Stojanovic et al. paper.\n\nComing to Question 1, I am not aware of any lower bounds for entrywise estimation in this setting, although this would be an interesting direction for future research. The question about how the bounds compare to naive spectral and Frobenius norm bounds is an interesting question. Indeed, one can naively upper bound the entrywise norm $\\|\\hat K - K\\|_\\max$ by the spectral norm $\\|\\hat K - K\\|_2 = \\hat \\lambda_{d+1}$ (or worse, the Frobenius norm). There are two reasons that this approach does not lead to satisfactory bounds. First if one has a bound of the form\n\n$$\n\\hat \\lambda_{d+1} = n \\lambda_{d+1} + \\textsf{approximation error}\n$$\n\nwhere the approximation error is of the order $O(n\\lambda_{d+1})$, then to obtain the same rates as Theorem 1, one would require that $d \\geq \\log^{1/\\gamma}(n^{2/\\beta})$ under (E), and $d = \\Omega(n^{2/\\alpha})$ under (P), which are much larger than the $d$ required in Theorem 1. The second stumbling block is that when $d$ is this large, using the best available concentration inequalities (i.e. Theorem 2 of Valdivia (2018)), the approximation error will in fact dominate $n\\lambda_{d+1}$ and in this case it may not even be possible to obtain a shrinking error rate for any $d$​!\n\n*References:*\n- Terence Tao and Van Vu. Random matrices: Universality of local eigenvalue statistics. Acta Mathematica, 206(1):127 – 204, 2011.\n- Ernesto Araya Valdivia. Relative concentration bounds for the spectrum of kernel matrices. arXiv preprint arXiv:1812.02108, 2018.", "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": "", "extra_scores": {}}]

Author rebuttal:
I would like to start by thanking all the reviewers for taking the time to work through my paper and to write their reviews. I was happy to read that the reviewers consider the problem to be a very fundamental one, that the main results in the paper are new to the community, that the paper is clear, well-written and easy to follow, and that the experiments complement the theoretical results well.

I am grateful to reviewer tJPJ for pointing out a mistake in Lemma 1, which can be rectified with a simple modification of the lemma statement, and which does not materially change the proof of the main result. I outline this in the direct response to their review, and if they are satisfied with the change, I will be interested to hear their opinion of the paper overall.

Both reviewers 3p4Z and 2JjA mention that the assumptions (P) and (E) seem very natural and cover many common kernels, however both questioned how natural the assumption (R) is. In this global response, I will provide some high-level intuition as to where this assumption comes from, and why it is necessary. Reviewer 2JjA argues that Lemma 1 is only a slight generalisation of Lemma 68 in Tao and Vu (2011), and therefore does not represent a significant novel contribution, and reviewer 3p4Z argues that with previous works on random matrix theory, the proofs are straightforward. In this global response, I will emphasise why I do not believe this to be the case, and clarify where new technical insights were required to prove the results in the paper.

**On the assumption (R).** To employ Lemma 1, we require that the projection of a constant vector onto a subspace spanned by the eigenvectors of $K$, corresponding to a subset of the eigenvalues with index $i > d$, is sufficiently small. The natural population analog of this is to assume that the projection of a constant function onto the subspace spanned by the population eigenfunctions with index $i > j$, which I denote $\Gamma_j$, decays sufficiently quickly with $j$. This assumption aligns with the intuition that the frequency of each eigenfunction increases as its corresponding eigenvalue decreases. If the first eigenfunction is constant, as is the case in Special Case 2, all the remaining eigenfunctions are orthogonal to it, and so $\Gamma_j$ is zero whenever $j\geq 1$.  Reviewer 3p4Z asks if I can provide some examples where this isn't the case. Unfortunately, it is only possible to explicitly compute the eigenvalues and eigenfunctions of very special kernels with respect to very special measures. Typically, it is certain symmetries which allow them to be calculated, and in all the cases I am aware of, $\Gamma_j = 0$ for all $j\geq 1$. The assumption $a < b/16$ in (R) can be seen as a relaxation of this case, and the constant $16$ just pops out of what is possible with the proof technique I am using. I considered simply replacing (R) with the assumption that $\Gamma_j = 0$ for sufficiently large $j$, which is more restrictive but perhaps more natural seeming, however I preferred to stick with the slightly more involved and more general assumption. 

**On the novelty of Lemma 1.** Reviewer 2JjA argues that Lemma 1 is only a slight generalisation of Lemma 68 in Tao and Vu (2011), and that since it follows a similar proof technique, does not represent a significant novel contribution. My Lemma 1 generalises Lemma 68 of Tao and Vu (2011) by allowing the mean $\bar a$ of the random vector $a$ to be non-zero. Establishing the condition on the relationship between subspace $H$ and the mean vector $\bar a$ for which such a concentration inequality can be derived was non-trivial and could not simply be guessed without working through the mathematical details. It is this innovation which represents the novelty of the lemma.

**On the novelty of the main proof.** Reviewer 3p4Z argues that with previous works on random matrix theory, the proofs of the main theorems are straightforward. I do not believe this to be the case and I will provide a summary of some of the technical challenges which arose in each part of this proof. Firstly, the core proof technique for the delocalisation bound (Theorem 2) follows a technique used in Tao and Vu (2011) which reduces the problem to (i) controlling the eigenvalues $\hat \lambda_i$ for $i$ in a constructed set $J$, and (ii) proving that the size of the orthogonal projection of a row of $K$ onto the subspace spanned by the eigenvectors $u_i$ for $i \in J$ is sufficiently large. The matrices considered in the paper of Tao and Vu (2011) and this paper are very different. Tao and Vu (2011) consider Wigner random matrices with independent mean-zero, unit variance entries, while we consider kernel matrices which have neither mean-zero nor independent entries, the randomness stemming from sampling the data points used to construct it. For this reason, (i) requires very different techniques - we use a concentration due to Valdivia (2018). (ii) also requires the new concentration inequality (Lemma 1) since our matrix does not have mean-zero entries. This new concentration inequality requires a condition on the mean of a row of the matrix and the aforementioned subspace. Proving that this condition holds in our setting (Section D) requires 7 pages of novel technical derivations. Additionally, understanding the necessary assumptions to make everything fit together is entirely non-trivial. For these reasons, I don't believe that this work can be reasonably described as "straightforward" application of previous work.

*References:*
- Terence Tao and Van Vu. Random matrices: Universality of local eigenvalue statistics. Acta Mathematica, 206(1):127 – 204, 2011.
- Ernesto Araya Valdivia. Relative concentration bounds for the spectrum of kernel matrices. arXiv preprint arXiv:1812.02108, 2018.

Meta-review: 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.
Decision: Accept (poster)