Consistent Kernel Mean Estimation for Functions of Random Variables
We provide a theoretical foundation for non-parametric estimation of functions of random variables using kernel mean embeddings. We show that for any continuous function f , consistent estimators of the mean embedding of a random variable X lead to consistent estimators of the mean embedding of f (X). For Matérn kernels and sufficiently smooth functions we also provide rates of convergence. Our results extend to functions of multiple random variables. If the variables are dependent, we require an estimator of the mean embedding of their joint distribution as a starting point; if they are independent, it is sufficient to have separate estimators of the mean embeddings of their marginal distributions. In either case, our results cover both mean embeddings based on i.i.d. samples as well as "reduced set" expansions in terms of dependent expansion points. The latter serves as a justification for using such expansions to limit memory resources when applying the approach as a basis for probabilistic programming.
This paper quantifies the price of estimating the distribution of $f(X)$, when {\em dependent} Kernel mean embedding is used. As shown in Eq. (2), O(1/n) of parametric rate is achievable with KME based on i.i.d. samples. However, when "expansion-points" are dependent, the rate is not known and possibly worse. The authors quantify this gap precisely in Theorem 2. The take-home message is that when f is smooth, there is no loss, but for non-smooth f, you pay the price in sample complexity. Hence, for practitioners, this gives a guideline for deciding when to use techniques such as reduced set expansions.   The paper is very well written, and I really appreciate the fact that the authors took the effort in Sections 1.1, 1.2, 1.3, and 1.4 to motivate when dependency naturally arises in KME and how memory trades off with accuracy. I learned something non-trivial that I did not know before I read this paper.   
Quantifying the price of dependent expansion points is an interesting mathematical question. However, this paper could improve in motivating the general readers from machine learning community to get interested in a broader topic of Kernel Mean Embedding. The authors attempt to do this in the last paragraph in Section 4, relating it to Probabilistic Programming Systems, which seems to be a weak connection. AS a reader, I was curious as to where such techniques of KME and reduced set expansions can be potentially used, or are used currently in solving some application specific problems.   Another disappointing aspect of the paper is that the authors did not delve deeper into the question Multiple arguments in Section 3. What is currently provided is a direct corollary of the Theorem 2, and the paper assigns too much space for something that has little information over what is already said. However, it is an interesting question to ask: given i.i.d. samples from joint distribution $(X,Y)$, what is the sample-efficient way to construct KME? (although this is outside the scope of this paper)  Overall, the questions addressed in this paper is theoretically very interesting, but mainly theoretical since there is no algorithmic innovation. Further, the techniques necessary to prove the main results seem to be largely available from existing literature e.g. [Kanagawa and Fukumizu 2014] as the authors point out, which I appreciate since I could not have made the connection if the authors did not state it so clearly. Hence, this paper addresses an interesting question and gives a clean answer, but the solution ended up being simple that it lost in Novelty/originality.   Typos:  - On page 2, $\{(x'_j,w'_j)\}_{i=1}^n$ should be $\{(x'_j,w'_j)\}_{j=1}^N$. - On page 2, $\{(f(x'_j),w'_j)\}_{i=1}^n$ should be $\{(f(x'_j),w'_j)\}_{j=1}^N$.