Even Faster Kernel Matrix Linear Algebra via Density Estimation
This work addresses computational bottlenecks in machine learning and data analysis for researchers and practitioners dealing with large-scale kernel methods, though it is incremental as it builds on existing algorithms with specific improvements.
The paper tackles the problem of accelerating linear algebraic tasks on kernel matrices, such as matrix-vector products and spectral norm computation, by using kernel density estimation (KDE) queries, achieving improved runtimes with reduced polynomial dependence on error ε and lower dependence on the number of points n compared to prior methods.
This paper studies the use of kernel density estimation (KDE) for linear algebraic tasks involving the kernel matrix of a collection of $n$ data points in $\mathbb R^d$. In particular, we improve upon existing algorithms for computing the following up to $(1+\varepsilon)$ relative error: matrix-vector products, matrix-matrix products, the spectral norm, and sum of all entries. The runtimes of our algorithms depend on the dimension $d$, the number of points $n$, and the target error $\varepsilon$. Importantly, the dependence on $n$ in each case is far lower when accessing the kernel matrix through KDE queries as opposed to reading individual entries. Our improvements over existing best algorithms (particularly those of Backurs, Indyk, Musco, and Wagner '21) for these tasks reduce the polynomial dependence on $\varepsilon$, and additionally decreases the dependence on $n$ in the case of computing the sum of all entries of the kernel matrix. We complement our upper bounds with several lower bounds for related problems, which provide (conditional) quadratic time hardness results and additionally hint at the limits of KDE based approaches for the problems we study.