Minimax Estimation of Kernel Mean Embeddings

By Ilya O. Tolstikhin, Bharath K. Sriperumbudur, Krikamol Muandet. 2016

96 citations recorded by the source corpus.

In this paper, we study the minimax estimation of the Bochner integral $$\mu_k(P):=\int_{\mathcal{X}} k(\cdot,x)\,dP(x),$$ also called as the kernel mean embedding, based on random samples drawn i.i.d.~from $P$, where $k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ is a positive definite kernel. Various estimators (including the empirical estimator), $\hat{\theta}_n$ of $\mu_k(P)$ are studied in the literature wherein all of them satisfy $\bigl\| \hat{\theta}_n-\mu_k(P)\bigr\|_{\mathcal{H}_k}=O_P(n^{-1/2})$ with $\mathcal{H}_k$ being the reproducing kernel Hilbert space induced by $k$. The main contribution of the paper is in showing that the above mentioned rate of $n^{-1/2}$ is minimax in $\|\cdot\|_{\mathcal{H}_k}$ and $\|\cdot\|_{L^2(\mathbb{R}^d)}$-norms over the class of discrete measures and the class of measures that has an infinitely differentiable density, with $k$ being a continuous translation-invariant kernel on $\mathbb{R}^d$. The interesting aspect of this result is that the minimax rate is independent of the smoothness of the kernel and the density of $P$ (if it exists). This result has practical consequences in statistical applications as the mean embedding has been widely employed in non-parametric hypothesis testing, density estimation, causal inference and feature selection, through its relation to energy distance (and distance covariance).

Subfields: Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “While various estimators have been studied for µP (Muandet et al. 2016, Sriperumbudur 2016), Tolstikhin et al. (2016) recently showed that this rate is minimax optimal and so the empirical estimator µ̂P is a minimax optimal estimator of µP.”
Consistent Kernel Mean Estimation for Functions of Random Variables (2016, background): “observations from X and ˆ X = {(xi, 1/n)}n i=1, we get kμ̂ f(X) μf(X)k(2) = OP (n 1), which was recently shown to be a minimax optimal rate (Tolstikhin et al., 2016).”
From Dependence to Causation (2016, background): “For a minimax lower bound on the set of all kernel mean embedding estimators, see (Tolstikhin et al., 2016).”
Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences (2018, result): “d. sample x1;:::;xn˘P, an empirical estimator of the kernel mean (67) is dened as ^P := 1 n Xn i=1 k(;xi); (78) which satises E[k^P PkH k ] = O(n 1=2) as n_1, if kis bounded [Smola et al., 2007, Tolstikhin et al., 2017]. One way to compute MMD empirically is to substitute this estimate (and that for”