Fourier Sparse Leverage Scores and Approximate Kernel Learning
  We prove new explicit upper bounds on the leverage scores of Fourier sparse
functions under both the Gaussian and Laplace measures. In particular, we study
$s$-sparse functions of the form $f(x) = \sum_{j=1}^s a_j e^{i \lambda_j x}$
for coefficients $a_j \in \mathbb{C}$ and frequencies $\lambda_j \in
\mathbb{R}$. Bounding Fourier sparse leverage scores under various measures is
of pure mathematical interest in approximation theory, and our work extends
existing results for the uniform measure [Erd17,CP19a]. Practically, our bounds
are motivated by two important applications in machine learning:
  1. Kernel Approximation. They yield a new random Fourier features algorithm
for approximating Gaussian and Cauchy (rational quadratic) kernel matrices. For
low-dimensional data, our method uses a near optimal number of features, and
its runtime is polynomial in the $statistical\ dimension$ of the approximated
kernel matrix. It is the first "oblivious sketching method" with this property
for any kernel besides the polynomial kernel, resolving an open question of
[AKM+17,AKK+20b].
  2. Active Learning. They can be used as non-uniform sampling distributions
for robust active learning when data follows a Gaussian or Laplace
distribution. Using the framework of [AKM+19], we provide essentially optimal
results for bandlimited and multiband interpolation, and Gaussian process
regression. These results generalize existing work that only applies to
uniformly distributed data.
