Kernelized Cumulants: Beyond Kernel Mean Embeddings

Summary

This paper proposes kernelized cumulants to extend classical cumulants in $\mathbb{R}^d$ and shows that the kernelized cumulants provide a new set of all-purpose statistics and are computationally tractable. This paper also show advantages of kernelized cumulants both theoretically and empirically.

Strengths

* The paper is well-written and easy to follow. * The method, that is, kernelized cumulant, proposed in this paper is novel and might be useful in real-world applications. For example, this method can be used to provide metrics for distributions and measure independence. Moreover, this method includes traditional MMD and HSIC as its special case and can even outperform the traditional ones.

Weaknesses

* In the experiments, more kernels, such as the neural tangent kernel, could be considered. * It would be better if the authors provide theoretical guarantees of the effectiveness of kernelized cumulants, such as consistency.

Questions

1. In the experiments, what is the criteria of the 'optimal value' of $\sigma$ (Line 265)?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors have adequately addressed the limitations.

Summary

This paper generalizes the notion of cumulants to Hilbert-space-valued random variables. When these Hilbert spaces are RKHSs, the kernel trick applies so that computations can be performed with the kernel function. It leads to higher-order two-sample and independence tests, which generalizes MMD and HSIC. The efficiency of these tests is demonstrated numerically on both synthetic and real data. EDIT: I have read the author's rebuttal, which partially addressed my concerns.

Strengths

The paper is well written and clear, despite the fact that the notation is heavy due to the complexity of the considered objects. I appreciated that equivalent definitions of the kernelized cumulants are given, as well as special cases to build intuition and relate it to classical notions. Because of this, I think the paper should be accepted.

Weaknesses

A first weakness in my opinion is that the main contribution of the paper is a straightforward combination of two known concepts: (i) cumulants and (ii) the use of the kernel methods in statistical testing. Also, rather than using the tensor algebra framework used by the authors in Section 3 and Appendix C.2, it seems to me that the simpler route would be to use the generating function $K(\theta_1, \dots, \theta_d) = \log \mathbb E[ \exp(\sum_{i=1}^d \langle \theta_i, X_i \rangle ) ]$ and define the cumulants from its series expansion, or equivalently derivatives at zero (which would be the correct equivalent of item 1. in Appendix C.1, rather than eq. (11)) . The definitions are of course equivalent, but it would lighten the formalism in the main text. The second main weakness is that the relationship between MMD/HSIC and the higher-order versions *when one is allowed to change the kernel* is not discussed. If I'm not mistaken, the second-moment embedding of a probability distribution with kernel $k$ coincides with the mean embedding with the squared kernel $k^2$. So one should expect a relationship between $d^{(2)}$ with kernel $k$ and MMD with some combination of $k$ and $k^2$ as kernel. If that is the case, then the use of higher-order cumulants can be equivalently rephrased as the use of different kernels. In particular, it is not clear whether one could be better off by sticking to MMD/HSIC but with well-designed kernels, as the estimation of higher-order moments has a higher variance. I think this point should be discussed in the text. Two additional minor remarks: - Repetition of "energy distance" in lines 37-38, which I'm guessing is a typo. - Missing related work: [1] considers a second-moment kernel embedding and defines kernel information-theoretic quantities. [1] Bach, Francis. "Information theory with kernel methods." IEEE Transactions on Information Theory 69.2 (2022): 752-775.

Questions

- I am suspicious of the fact that the computational complexity of MMD/HSIC and the higher-order extensions are the same, and are bottlenecked by the computation of the kernel matrix. Surely the complexity must increase with $m = \mathrm{deg}(\mathbf{i})$, even if it remains quadratic in the sample size? - Is there a relationship between going to higher-order cumulants and changing the kernel? Can we achieve the same performance than the higher-order cumulants by adapting the kernel? - Isn't the the $V$ statistic estimator a straightforward replacement of the expectation with empirical averages over the sample? I think this could be mentioned in the text.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors mentioned the two main limitations of their approach: - It is not clear how to design the kernels to maximize the performance of the statistical tests. - There is no theoretical analysis of the introduced tests. I agree that a complete resolution of these issues should be left to future work. However, I think the second weakness above, which is related to the first limitation, should be at least acknowledged. There is no foreseeable negative societal impact.

Summary

The authors introduce the kernelized cumulant and show that it can characterize distributions and statistical (in)dependence.

Strengths

1. The kernelized cumulant provides a natural generalization of the popular maximum mean discrepancy (MMD) as well as the Hilbert-Schmidt independence criterion (HSIC). 2. The authors illustrate several interesting properties of the kernelized cumulants and provide a two-sample test for non-characteristic feature maps as well as an independence test. 3. The authors demonstrate the utility of the proposed method on a variety of datasets with competitive results.

Weaknesses

1. Estimating the kernelized cumulant may require a large sample. Convergence rate of the estimator is not discussed, but the empirical results suggest comparable performance as the HSIC. 2. The proposed method could potentially be vulnerable to kernel misspecification.

Questions

1. Is the independence criterion kernel dependent? What happens if the kernel is misspecified? 2. What are the convergence rates for the finite-sample estimators?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This papers revisits advances in cumulants on real data, by extending them to provide cumulants for random variables in an RKHS.

Strengths

The idea of this work is interesting, as the paper proposed to go beyond conventional kernel mean and kernel covariance. Moreover, a proposed kernel trick allow to obtain efficiently the kernelized cumulants. The paper well describes the contributions. The derivations seem to be good, and some experiments on synthetic and real datasets allow to understand the relevance of the proposed approach

Weaknesses

While the paper includes some experimental results, there are only two settings : independence test and two-sample test (MMD-like). Is there any other tests (or beyond test) where the proposed kernelized cumulants would be relevant ?

Questions

see question in weaknesses

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

OK

Summary

The paper generalises the notion of kernel mean embeddings to higher-order cumulants. It proposes kernelled cumulants in the RKHS. While kernelled cumulants reside in tensor product space of the RKHS, the paper shows that Hilbert space metric between cumulants can be exactly computed using the kernel trick. Based on this construction, the paper proposes: (1) a two-sample test statistics, that generalises MMD test statistics by considering distance between cumulants, and (2) a generalisation of HSIC statistic for independence testing, again by considering distant between cumulants of joint distribution and product of marginals. The advantages of the construction and proposed tests include: (i) the test are applicable for a broader class of "point-separating" kernels (unlike MMD/HSIC that can only useful for characteristic kernels); (ii) the new statistics can be computed in quadratic time (same as MMD); and (iii) empirically achieve higher power that classical MMD/HSIC statistics (both on synthetic and real data).

Strengths

- The idea of considering higher order moments/cumulants in RKHS is quite natural, and yet unexplored in the literature (apart from the recent work of Makigusa (2020) that consider only 2nd order moments). Hence, the contribution is novel and quite timely - The main strength of the paper is that the computational cost of the proposed statistics is still quadratic in sample size (same as MMD), which implies the advantages of higher order moments does not come at significant additional cost - The work is technically sound, and the construction of cumulant and use of kernel trick is reasonably involved.

Weaknesses

- While it is easy to imagine in general that higher-order cumulants can distinguish between more distributions, the advantage of kernelled cumulants is difficult to grasp. If a characteristic kernel is used wouldn't mean embedding (MMD) suffice? - The line of argument used in the paper to demonstrate advantage of kernel cumulants is that (empirically) they have show higher power (can detect small differences better). Is there a theoretical justification for this? It would be sufficient if the authors provide a justification / reference that standard (non-kernel) cumulants are more sample efficient in some cases, where means already show separation - For the synthetic experiments, the null rejection rate should also be plotted to show that cumulants do not have higher tendency to reject than MMD/HSIC. While this is true for the real data, unfortunately both 1st order and higher order terms reject at a rate higher than significance level - Overall, it is not clear when tests based on higher-order cumulants are indeed needed in practice. I still feel the work is relevant, but some discussions on this would certainly increase the significance of the work for the broader community - The paper, although well-written, is quite dense and at times bit difficult to follow, but this can be attributed to the content of the paper

Questions

- see weakness - in addition, a precise statement on computational complexity (at least for d2, d3) would be useful Minor remarks: H in Lemma 3 is not defined in main paper (but in appendix), and E et al citation seems incorrect (there is a full name for E)

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

the paper does not have immediate negative societal impact (although conclusions from hypothesis tests can always have). Hence, the work could benefit from: - consistency results (similar to kernel two-sample tests) - characterisation of whether higher-order cumulant based statistics typically tend to be larger than MMD (even under null). The comment is about sample estimates and not expected value (hence, more tied to concentration/consistency of test statistics)

Thank you

I thank the authors for the responses, and clarifying the relevance of looking at higher order cumulants. In future, it would help to further investigate practical implications of kernel cumulants. It feels like there is more potential than what is claimed in the paper/rebuttal.