  Sobolev quantities (norms, inner products, and distances) of probability
density functions are important in the theory of nonparametric statistics, but
have rarely been used in practice, partly due to a lack of practical
estimators. They also include, as special cases, $L^2$ quantities which are
used in many applications. We propose and analyze a family of estimators for
Sobolev quantities of unknown probability density functions. We bound the bias
and variance of our estimators over finite samples, finding that they are
generally minimax rate-optimal. Our estimators are significantly more
computationally tractable than previous estimators, and exhibit a
statistical/computational trade-off allowing them to adapt to computational
constraints. We also draw theoretical connections to recent work on fast
two-sample testing. Finally, we empirically validate our estimators on
synthetic data.
