A Dynamic Low-Rank Fast Gaussian Transform

We express our deepest gratitude to the reviewer for the time and effort in reviewing our work. We appreciate that you evaluate our work as well-motivated. Below, we want to address your concerns.

We respectfully disagree that this paper has no novelty or is merely an incremental combination of existing techniques. While it builds on prior work on FGT, we introduce several key technical innovations that enable the design of an efficient, fully dynamic data structure for the Fast Gaussian Transform problem. Our first contribution is the novel "decoupling" technique to disentangle the source points from target box centers in the FGT coefficients. This allows updating the coefficients in polylogarithmic time when adding/removing sources instead of the prohibitive linear scan. Second, generalizing the data structure to handle points from an unknown, dynamically changing low-dimensional subspace via efficient basis updates. To the best of our knowledge, this is the first result showing that FGT can bypass the curse of dimensionality for kernel density queries. Furthermore, an efficient dynamic FGT data structure has important practical implications in scaling up kernel methods and Gaussian process regression to massive streaming data. As evident from recent works on continually learning systems and online optimization, handling concept drift and covariate shifts in real-world datasets necessitates dynamic algorithms.

We again thank you for your time and for giving us your insightful comments, and we hope that our rebuttal may address your concerns.

We express our deepest gratitude to the reviewer for the time and effort in reviewing our work. We really appreciate for your invaluable comments, and we are very excited to see that our work is evaluated as well-written and technically sound. Besides these, the problem we study is also thought to be important. Below, we want to address your concerns.

You raise a very important concern about the lack of experimental results, which is similar to Reviewer 1GBM and Reviewer pkC2. We regretfully do not have more experimental results at this point. However, we also want to highlight that the works we build upon [1, 2] 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.

We thank you again for your insightful comments, and 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] Yeshwanth Cherapanamjeri, and Jelani Nelson. "Uniform approximations for randomized hadamard transforms with applications." STOC’22.

[2] Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. "Algorithms and hardness for linear algebra on geometric graphs." FOCS’20.

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.

We express our deepest gratitude to the reviewer for the time and effort in reviewing our work. It is very encouraging for us to see the evaluation of our work as having a “strong theoretical contribution by solving an open problem of dynamizing the FGT algorithm”, being applicable to other machine learning and data analysis fields, and possessing novel theoretical approaches. Below, we want to address your concerns about our work.

Thank you for raising important points about the numerical stability and the experimental evaluations. We regretfully do not have more experimental results at this point. However, we also want to highlight that the works we build upon [1, 2] are completely theoretical works. Our focus in this paper remains on developing the theoretical side of this line of work, extending the landscape of the 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.

Regarding the assumptions that data points lie in a low-dimensional subspace, we first thank you for pointing this out. We agree that the dimension of many data points is usually high, especially in our big data era. However, we believe that there are many modern deep learning architectures, used in various fields, that explicitly project high-dimensional data into lower-dimensional spaces, which may alleviate the assumption we have. Dimension reduction involves two main strategies: feature selection which focuses on selecting a subset of the most relevant features from the original dataset to lower dimensionality while preserving interpretability; and feature extraction which creates new, lower-dimensional features from the original data to encapsulate key patterns and relationships. For example,

$\bullet$ Autoencoders consist of an encoder and a decoder, where the encoder maps high dimensional data points to low dimensional and the decoder may reconstruct the original high dimensional data [3].

$\bullet$ Principal component analysis projects data into a lower-dimensional space by maximizing variance along new axes [4].

There are numerous other dimension reduction techniques which can be used, and we believe that these methods may make our method more applicable.

We thank you again for your insightful comments. 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. Regarding the assumption we use, we hope that the use of the dimension reduction techniques may address your concerns.

[1] Yeshwanth Cherapanamjeri, and Jelani Nelson. "Uniform approximations for randomized hadamard transforms with applications." STOC’22.

[2] Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. "Algorithms and hardness for linear algebra on geometric graphs." FOCS’20.

[3] Kamal Berahmand, Fatemeh Daneshfar, Elaheh Sadat Salehi, Yuefeng Li, and Yue Xu. "Autoencoders and their applications in machine learning: a survey." Artificial Intelligence Review 57, no. 2 (2024): 28.

[4] Feiping Nie, Jianjun Yuan, and Heng Huang. "Optimal mean robust principal component analysis." ICML’14.

Thank you for your considerate reply to my feedback. Your intention to include findings and deeper analysis in the iteration is encouraging. I am excited to witness these enhancements as they are sure to bolster the quality of the project. I prefer keeping the current evaluation until the results from the experiments are included.