Entrywise error bounds for low-rank approximations of kernel matrices

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.

Strengths

1) This is a first result showing entrywise error guarantees for low rank approximation of kernel matrices. 2) Proof sketches of two main theorems are clear and easy to follow. 3) 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. 4) 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. 2) Although I appreciate proof sketches of Theorems 1 and 2 in the main text, I believe it would be more useful to add more information about the proof deferred to Appendix D since this is the most novel and interesting part of the proof. 3) It is not clear whether assumption (R) is necessary and how general it is apart from the two special cases given in Section 3.1.

Questions

1) Could you elaborate more on tightness of your results? How do they compare with already established results for Frobenius and spectral norm? Are there any known lower bounds for entrywise estimation? 2) Although assumptions (E) and (P) seem to be very natural, I am not sure about assumption (R). Do results hold for any $a$ and $b$ such that $1\\leq a < b/16$? Since the final error bound does not depend on $a$ and $b$, do you think this assumption can be relaxed? 3) Although I think that double descent observation is interesting on its own, the evidence for it is vague. Is this behavior observed for a range of percentile values or does it happen only around 99.95 percentile? Also from figures in the paper seem like it appears only for not very smooth kernel functions. It would be beneficial to have more convincing evidence whether this phenomenon occurs because of your choice of 1) kernels, 2) percentiles, 3) entrywise errors or something else. Typos and other comments (106) maximum entrywise "error" (missing) (186) should be $ \\hat{u}_i(1)$, instead of $ \\hat{u}_l(1) $ (647) later on I would prefer if you do not use $(a,b)$ both for constants in assumption (R) and for vectors in the proof of Theorem 2. In introduction you cite [Lei, 2019] for establishing entrywise error bounds for reinforcement learning - but I could not find any references to RL in that paper. Is this a typo? For example, I believe the following papers are more suitable for that particular reference: - Pananjady, Ashwin, and Martin J. Wainwright. "Instance-dependent ℓ∞-bounds for policy evaluation in tabular reinforcement learning." IEEE Transactions on Information Theory 67.1 (2020): 566-585. - Shah, Devavrat, et al. "Sample efficient reinforcement learning via low-rank matrix estimation." Advances in Neural Information Processing Systems 33 (2020): 12092-12103. - Stojanovic, Stefan, Yassir Jedra, and Alexandre Proutiere. "Spectral entry-wise matrix estimation for low-rank reinforcement learning." Advances in Neural Information Processing Systems 36 (2023): 77056-77070.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have addressed limitations adequately.

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.

Strengths

1. The paper is clear and well written. The proof seems to be solid. 2. The entrywise error bound is new to the community. 3. The assumptions on polynomial/exponential eigenvalue decay seem general and cover lots of common kernels. 4. 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. 2. Assumption (R) seems not natural (why is $1\le a < b/16$ is needed?) and also I do not know how to verify this. Could you provide some examples with $\Gamma_i \neq 0$ under Assumption (R)? 3. The contributions are undetermined. The proof of the main theorem seems to heavily rely on past random matrix theory works (Tao and Vu [2011], Erdős et al. [2009 a,b]). With assumptions (E)/(P) and (R) and the previous works, the proof is straightfoward. And I am not sure about the importance of entrywise error bound. Minor typos: 1. Line 578/588 hypotheses-> hypothesis 2. Line 539/581 miss a period

Questions

1. (Line 82) What do you mean by "infinite sample limit of $\frac{1}{n}K$"? 2. Could you provide more general examples that completely follow the assumption (E)/(P)? 3. Is this error bound optimal? Are there any lower bound results? 4. Is it possible (or are there any hardness results) to compute or approximate $\text{argmin}_{K':\text{rank}(K')=d}$ $ \||K-K'\||$ w.r.t. the sup norm? 5. Regarding the importance of entrywise error bound, could you provide more concrete examples?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

There is no negative societal impact of their work.

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.

Strengths

- The problem is a very fundamental one and it is considered both analytically and numerically. - 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. Consider an extreme case where $a=0$ with probability $1$. Then, since $\pi$ is an orthogonal projection, $\| \pi_H(a) \| = 0$ and thus Lemma 1 fails. The main issue is that in the proof of Lemma 1, if $S_1 = \sum p_{ii} (\xi_i^2 - 1)$, then $E[S_1^2] = \sum_{i, j} p_{ii} p_{jj} E[\xi_i^2 - 1] E[\xi_j^2 - 1]$, which is different from $\sum_i p_{ii}^2 E[(\xi_i^2 - 1)^2]$ in (17), unless $E[\xi^2]=1$. As a result, (17) and the estimates on $P(E_+)$ and $P(E_-)$ fail. -> The proofs of the main results would work after modifying Lemma 1 as suggested by the authors.

Questions

- Is it possible to prove Lemma 1 with additional assumptions that are suitable to the current setting? - In the proof of Lemma 1, there are other minor problems listed below. 1) In line 618, $\xi_i \in [0, 1]$ is wrong since the mean $\bar{x}$ is subtracted. 2) In the equation below line 621, why $\| \pi_H(x)\|^2 = \| \pi_H(\bar{x}) \|^2 + \| \pi_H(\xi) \|^2$? 3) In the equation below line 621 and several other places, $X$ should be $x$. Also, $\bar{\xi}$ should be $\xi$.

Rating

5

Confidence

4

Soundness

2

Presentation

4

Contribution

3

Limitations

The work does not seem to have potential negative societal impact.

Reponse

Thank you for your response. After the rebuttal, I go through the Appendix and believe the author has make great efforts in the proof, not as easy as we reviewers thought. But considering the fact that Lemma 1 should be corrected and the assumptions still lack some intuition (since it is hard to give some general examples), my score remain the same.