Thank you very much for your insightful comments!
We express our deepest gratitude to the reviewer for the time and effort in reviewing our work. We sincerely thank you for evaluating our work as having novel techniques in efficiently handling changing datasets in KDE and matrix-vector multiplication in a dynamic setting, having good time complexity, and the problem we study is very important in practice. Below, we want to address your concerns about our work.
Regarding the first weakness, our method indeed can be generalized to a very broad class of "fast-decaying kernels". We formally present the specific properties, derived from [1], of this class of the kernel in Appendix B, Definition B.1, which includes:
$\bullet$ The kernel function $f$ is non-increasing, i.e., $f(x)\leq f(y)$ when $x\geq y$.
$\bullet$ $f$ is decreasing fast, i.e., $f(\Theta(\log(1/\epsilon)))\leq \epsilon$.
$\bullet$ $f$’s Hermite expansion and Taylor expansion are truncatable: the truncation error of the first $(\log^d(1/\epsilon))$ terms in the Hermite and Taylor expansion of $\mathsf{K}$ is at most $\epsilon$.
The specific examples of the kernel function $f$ satisfying these three properties include:
$\bullet$ inverse polynomial kernels: $K(x,y) = 1 / \|| x - y \||_2^c$ for constant c > 0,
$\bullet$ exponential kernel: $K(x,y) = \exp(-\|| x - y \||_2)$,
$\bullet$ inverse multiquadric kernel $K(x,y) = 1/\sqrt{\|| x - y \||_2^2 + c}$ [2, 3],
$\bullet$ rational quadratic kernel $K(x,y) = 1/(1 + \||x - y\||_2^2/\alpha)$ where $\alpha > 0$,
$\bullet$ piecewise exponential kernel [1], and
$\bullet$ more can be found in [1].
All of these kernels are widely used in the literature (see [1]). Thank you for pointing this out, and we hope that these examples may make our claim more clear.
Regarding the second weakness, the kernel bandwidth $\delta > 0$ can be set using standard rules like median heuristic or cross-validation. For the box length $L = r \sqrt{2 \delta}$, we have that $r$ controls the tradeoff between computational cost and accuracy. We recommend $r = 1/2$ as it provides a good balance, and the error bound (see Eq. (1) in Line 243-244) scales as $\exp(-2 r^2 k^2)$ where $k$ is a parameter that controls the number of neighboring boxes. For the truncation parameter $p$, we set it to $p=\log(\|| q \||_1/\epsilon)$ to achieve desired accuracy $\epsilon$ (see Lemma E.6). It can be adjusted dynamically based on observed errors. Thank you for pointing out this issue! We hope that our response may address your concern.
Regarding the third weakness, we regretfully do not have more experimental results at this point. However, we also want to highlight that the works we build upon [1, 4] are completely theoretical works. Our focus in this paper remains on developing the theoretical side of this line of work, extending the landscape of fast Multipole method in a dynamic setting to support data insertion and deletion and to support data in a low-dimensional subspace. We admit that the lack of experimental results is a weakness of this series of works, including ours. We will try to include more experimental results in the revised version, but we believe that to fully fill in the lack of experimental results in this line of work would require more substantial effort in the future. Thank you for pointing this out.
We once again provide our sincere thanks for your insightful comments. For the first and the second weaknesses, we have adjusted our manuscript accordingly to make them more clear. We uploaded a new version of our paper and marked our changes in red. For the third weakness, we agree with the general lack of experimental results in the line of works related to ours and will try to include more experimental results in the final version of our paper to fill this gap.
[1] Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. "Algorithms and hardness for linear algebra on geometric graphs." FOCS’20.
[2] Charles A Micchelli. “Interpolation of scattered data: distance matrices and conditionally positive definite functions.” Springer Netherlands, 1984.
[3] Per-Gunnar Martinsson. Encyclopedia entry on fast multipole methods. In University of Colorado at Boulder, 2012.
[4] Yeshwanth Cherapanamjeri, and Jelani Nelson. "Uniform approximations for randomized hadamard transforms with applications." STOC’22.