Random Gegenbauer Features for Scalable Kernel Methods
  We propose efficient random features for approximating a new and rich class
of kernel functions that we refer to as Generalized Zonal Kernels (GZK). Our
proposed GZK family, generalizes the zonal kernels (i.e., dot-product kernels
on the unit sphere) by introducing radial factors in their Gegenbauer series
expansion, and includes a wide range of ubiquitous kernel functions such as the
entirety of dot-product kernels as well as the Gaussian and the recently
introduced Neural Tangent kernels. Interestingly, by exploiting the reproducing
property of the Gegenbauer polynomials, we can construct efficient random
features for the GZK family based on randomly oriented Gegenbauer kernels. We
prove subspace embedding guarantees for our Gegenbauer features which ensures
that our features can be used for approximately solving learning problems such
as kernel k-means clustering, kernel ridge regression, etc. Empirical results
show that our proposed features outperform recent kernel approximation methods.
