Faster Gaussian Summation: Theory and Experiment
This work addresses a computational bottleneck in Gaussian summation for machine learning practitioners, but it is incremental as it builds on existing algorithmic frameworks.
The paper tackled the problem of Gaussian summation, a bottleneck in many machine learning methods, by developing two new algorithmic extensions: an O(Dp) Taylor expansion with error bounds and a novel error control scheme. The results showed that the error control scheme improved performance, while the series expansion was only effective in low dimensions (five or less).
We provide faster algorithms for the problem of Gaussian summation, which occurs in many machine learning methods. We develop two new extensions - an O(Dp) Taylor expansion for the Gaussian kernel with rigorous error bounds and a new error control scheme integrating any arbitrary approximation method - within the best discretealgorithmic framework using adaptive hierarchical data structures. We rigorously evaluate these techniques empirically in the context of optimal bandwidth selection in kernel density estimation, revealing the strengths and weaknesses of current state-of-the-art approaches for the first time. Our results demonstrate that the new error control scheme yields improved performance, whereas the series expansion approach is only effective in low dimensions (five or less).