Interpretable Distribution Features with Maximum Testing Power
Two semimetrics on probability distributions are proposed, given as the sum of differences of expectations of analytic functions evaluated at spatial or frequency locations (i.e, features). The features are chosen so as to maximize the distinguishability of the distributions, by optimizing a lower bound on test power for a statistical test using these features. The result is a parsimonious and interpretable indication of how and where two distributions differ locally. We show that the empirical estimate of the test power criterion converges with increasing sample size, ensuring the quality of the returned features. In real-world benchmarks on highdimensional text and image data, linear-time tests using the proposed semimetrics achieve comparable performance to the state-of-the-art quadratic-time maximum mean discrepancy test, while returning human-interpretable features that explain the test results.
The paper considers the classical two sample problem where one wants, from the observation of two independent samples in R^d, X_1^n and Y_1^n with respective distribution P and Q, be able to test whether P = Q or P \neq Q. The solution investigated in the paper, which is due to Chwialkowski et al., is very interesting. It is based on a kernel k : (R^d)^2 → R and a set of J test locations (v_j)^J_{j=1}. For any i = 1,...,n, one builds the vectors z_i with coordinates k(x_i,v_j) − k(y_i,v_j), j = 1,...,J and measure the discrepancy between P and Q with the T-statistic \hat{\lambda}_n=n\bar{z}_n(S_n+\gamma_nI)^{-1}\bar{z}_n, where \bar{z}_n=\frac1n\sum_{i=1}^nz_i, S_n=\frac1{n-1}\sum_{i=1}^n(z_i-\bar{z}_n)(z_i-\bar{z}_n)^T. The authors Chwialkowski et al. proved in particular that the asymptotic distribution of \hat{\lambda}_n, when n → ∞ and the other parameters are fixed, is \chi^2(J). The present paper also consider an associated test, called SCF-test which relies on the same ideas. The main question is how should we choose the test locations (vj)_{j=1}^J to optimize the performance of this test (the choice of the kernel k or of some scaling parameters is also relevant). This is precisely the question considered by the author, who proceed as follows. First, they prove a lower bound on the power of the test that is increasing with the limit \lambda = \mu^T \Sigma^{−1}\mu of \hat{\lambda}_n/n as n → ∞. Then, as \lambda is unknown, they cut the sample in two halves, the first one is used to estimate the parameters \mu and \Sigma and therefore estimate the function \lambda of the parameters of interest (v_j)_{j=1}^J. The second is used to select the parameters maximizing this estimator of \lambda. The author proves the consistency of the estimator of \lambda and test its procedure on both toy Gaussian regression models and in two real data-sets in a simulation study concluding the paper.
I found the approach of the problem very interesting and the solution quite elegant and, even if I did not check the details of all proofs, they seem correct. This is why I would like to see the paper published. However, and this is my main concern, I really think that the author should make a strong effort of presentation of their results. In the present state, I think that it is quite hard to read due to the lack of many details, not completely honest on some aspects and both theorems are unnecessarily way too technical. I will now detail some of these points.  You should improve the presentation of the paper. Some important formulas, like the definition of your main quantities (for example zi p3 l98) should be isolated in an equation to ease the reading. Moreover, please define the quantities in the text when you use them in your main results, for example the Frobenius norm used p3 l121 in your first result is only defined in Section C1 of the supplementary material. These are really not details, as I said it makes the paper very hard to understand. To improve the presentation, I also suggest that you avoid the sketchs of proofs that I found quite obscur and not really informative. The same holds for the comment after Proposition 1 giving another intuition that maximizing \lambda would lead to better performances, as you said, Proposition 1 does it and better. Also, p4 at the beginning of the Section Contribution, you briefly change from a parameter k to designate the kernel to \sigma before going back to k and use \sigma as a tuning parameter.  You refer several times to the fact that your procedure is adapted to the large dimension setting. You should be more precise here. I believed that it meant that d or J can be large compared to the number n of observations. However, it looks like your test has only confidence level \alpha in an asymptotic framework where n → ∞ while the other parameters remain fixed? Also, in your comment after Theorem 2, you get the rate O(n^{−1/4}) only if the VC dimension of your class of kernels is not allowed to grow with n. Finally, in your simulations study, I think that, in all toy models, n is larger than d and much larger than J, and, for example on Fig 3, it is not clear that your procedure remain effective when d gets closer to n.  You should finally improve the presentation of your theorems. For example, since you introduce some ”constants” in Proposition 1 depending on B, J to express L(\lambda_n), why do these parameters and meaningless absolute constants still appear in the expression of L(\lambda_n)? You should really write a more synthetic and comprehensive result in the main text, and probably keep this result for the supplementary material. The same comments hold for Theorem 2.