Efficient Nonparametric Smoothness Estimation
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, 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.
The paper proposed a non-parametric estimator for Sobolev quantities (norms, inner products, and distances) of probability density. The estimator operates in the Fourier (frequency) domain, and it unbiasedly estimates the related quantities that are truncated to a certain frequency.   For the theoretical aspect, the convergence rate of the mean square error is provided, which matches several previous results. Moreover, the asymptotic distributions are derived for the inner product estimator and the distance estimator when $p=q$.   For the practical aspect, the computational complexity is emphasized which in linear w.r.t. the sample size $n$. This makes the proposed estimator more computationally tractable than previous estimator. Also, simulations are provided that validates the theory.  
Sobolev quantities (norms, inner products, and distances) of probability density are important to a lot of applications in machine learning and signal processing. This paper proposed a non-parametric estimator for such quantities with the computational complexity linear in the sample size $n$. The convergence rate of the mean square error, and the asymptotic distributions are provided for such estimator. Moreover, a few simulations are provided that validates the theory.  Generally speaking, I think this is a pretty nice theoretical paper. The idea is simple and well presented: the estimator looks at the probability distribution in its Fourier domain, and provides an unbiased estimate of the desired quantities that are truncated to a certain frequency. Here are a few suggestions & comments.   1. My biggest concern is the usefulness of the proposed estimator. Choosing to estimate the frequency-truncated version of the Sobolev quantities seems a natural idea to me. However, I am a little less convinced why we should use the proposed estimator in practice instead of using some other methods. For example, we can look the quantity in some other domain rather than the Fourier domain.   The only reason that convinces me is its linear computational complexity. I would be better convinced if some optimality guarantees are presented. For example, some converse results that show the estimator is indeed rate optimal. Or some real world data experiments that show the proposed estimator is robust in practice. Some intuitions suggesting the Fourier domain is reasonable to look at will also help.   Also, I admit I am not an expert in the non-linear functional estimation of continuous distributions. It would be helpful if the authors can clarify a little more why estimating the Sobolev quantities, especially higher order Sobolev quantities, are very useful. A few examples will work here.   2. The paper uses Gaussian distribution and uniform distribution for simulation. It seems a little weird to me to use the Gaussian distribution, which violates the bounded support assumption. Also, it would be better to use some less smooth distributions. Of course, the paper would be much stronger if there were some real-world data experiments presented.  3. There are a few typos in section 7, which, of course, are just some minor issues. For example, line 195 and line 196, I believe it is equation (13) that we should look at instead of (14). Also, line 196 and 199, I think in the expression of $Z_n$, the exponent should be positive instead of negative.