Skip to yearly menu bar Skip to main content


Efficient Nonparametric Smoothness Estimation

Shashank Singh · Simon Du · Barnabas Poczos

Area 5+6+7+8 #9

Keywords: [ Learning Theory ] [ (Other) Statistics ] [ Information Theory ]


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 finite-sample bias and variance of our estimators, 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 and empirically validate our estimators on synthetic data.

Live content is unavailable. Log in and register to view live content