The GaussianSketch for Almost Relative Error Kernel Distance
This work provides incremental improvements in kernel methods for machine learning by offering more efficient sketches for high-dimensional data, though it builds on existing techniques like RecursiveTensorSketch.
The authors tackled the problem of approximating Gaussian kernel distances between point sets by introducing two new sketches that embed the Gaussian kernel into Euclidean space with almost (1+ε)-relative error and a small additive term α, achieving poly-logarithmic dependence on 1/α and either higher polynomial or linear dependence on dimension d.
We introduce two versions of a new sketch for approximately embedding the Gaussian kernel into Euclidean inner product space. These work by truncating infinite expansions of the Gaussian kernel, and carefully invoking the RecursiveTensorSketch [Ahle et al. SODA 2020]. After providing concentration and approximation properties of these sketches, we use them to approximate the kernel distance between points sets. These sketches yield almost $(1+\varepsilon)$-relative error, but with a small additive $α$ term. In the first variants the dependence on $1/α$ is poly-logarithmic, but has higher degree of polynomial dependence on the original dimension $d$. In the second variant, the dependence on $1/α$ is still poly-logarithmic, but the dependence on $d$ is linear.