Kernel-Based Tests for Likelihood-Free Hypothesis Testing

Summary

This paper studies a problem in the area of likelihood-free testing, where one is given black-box access to samples $X\sim P_X$, $Y \sim P_Y$ of size n, as well as "real-world data" $Z \sim P_Z$ of size m. The authors propose a new model ("Mixed likelihood-free testing") where it is known that $P_Z = (1 - \nu) P_X + \nu P_Y$ for rate parameter $\nu$, and the goal is to determine whether $\nu = 0$ or $\nu \ge \delta$. They propose a kernel based test statistic for this problem, and analyze its performance theoretically, and also provide lower bounds. They also perform experiments based on Higgs Boson detection and detecting images produced by a diffusion model to support their theoretical claims.

Strengths

This paper is well written, and the problem is well motivated from the point of view of practical applications (Higgs Boson detection, diffusion image detection). The paper has an extensive set of experiments on real data, and there is an interesting theory to support empirical findings. Overall, I think this is an interesting paper.

Weaknesses

The upper and lower bounds in the theory are a little difficult to interpret, especially the dependence on the eigenvalues of the kernel - it would be useful if the authors could provide some examples with simple kernels to illustrate better what the bounds are saying. Some of the things done in the experiments, such as training a kernel on the test data (especially overlap between training and evaluation data), are not captured/explained by the theory. Also, while Figure 1 seems like it agrees with the theory, it includes all the samples, including ones used for training, calibration, and evaluation. On the other hand, the plot involving only the evaluation samples (Figure 8 in appendix) seems like it agrees more with the naive expectation of $\min\{n, m\} \gtrsim n_{TS}(\alpha, \epsilon, \mathcal P)$. Since the theory is supposed to reflect performance relative to evaluation samples for a fixed kernel, it would be useful if the authors could provide a more detailed explanation of both these plots. It would also be useful if the authors could provide a simple synthetic experiment to illustrate the theoretical bounds for the setting that it is supposed to explain (with a fixed kernel) The dependence on mis-specification parameter $R$ is not captured by the lower bounds, and Proposition 4.1 (which is about the calibration of the test statistic) assumes that $R=0$. I would be curious to know if proposition 4.1 can be made stronger. In particular, can anything be said about the empirical settings where presumably $R > 0$? One very interesting thing the authors do in experiments is to use a fraction of the samples from $P_X$ and $P_Y$ to train a kernel that maximizes the (normalized) expectation gap of the statistic. While this seems to work well, there doesn't seem to be a theoretical explanation for why this is a good idea. Of course, while it may not currently be possible to make theoretical claims about a neural net based kernel, is it possible to make a theoretical claim about some simpler model? Or make some abstract claim given black box access to an algorithm that can take samples and generate a kernel with some good properties?

Questions

1) What is the relationship between this problem/likelihood-free testing more generally, and the distribution testing literature in theoretical CS? Can you include a brief comparison? 2) While Proposition 4.1 says that the p-value estimate is good as n_cal-> infty, what is the finite-sample relationship between n_cal, n_eval and the test statistic? Is there something quantitative that can be said here? What happens if $R > 0$? 3) Is it possible to say anything about the kernel training phase theoretically?

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

4 excellent

Contribution

3 good

Limitations

Yes

Summary

This paper introduces a new framework for likelihood-free hypothesis testing (LFHT), denotes as Mixed-LFHT or mLFHT. The setting of mLFHT is as follows: assume $n$ i.i.d. samples from a background disttribution $P_X$, and the same number of samples from a signal distribution $P_Y$. Also, assume we are given another $m$ i.i.d. samples from a mixed distribution $P_Z=\nu P_Y + \left(1-\nu\right)P_X$, and the aim is to "test" and see if $\nu$ is greater than some positive threshold $\delta$. Paper proposes a new kernel-based test statistic for this problem and then analyzes it from both theoretical and experimental perspectives. The main idea is to somehow "map" the empirical distributions of observed data into an RKHS (for some kernel of choice) and then measure the discrepancies of the observed data from both $P_X$ and $P_Y$. From a theoretical POV, authors claim to acheieve non-trivial sample complexity bounds for the non-asymptotic regime. Both upper and lower-bounds on the error have been established in Thms 3.2 and 3.3, respectively. From an experimental side, authors propose a new algorithm to learn the kernel from data, and also showcase the applicability of their test statistic and algorithm on a number of real-world tasks. I am not an expert in this particular field and therefore not much aware of other similar works. However, paper is not well-written and seems a little rushed. Regarding the technical contribution, I have a number of questions (please see questions section) before reaching a final conclusion. For now, my vote is borderline reject, with a relatively low confidence.

Strengths

- Paper investigates an important problem for the ML community in general. - The mathematical tools (specially those from functional analysis and RKHS-related areas) used for the theoretical parts are sufficiently sophisticated and might be interesting for many researchers in this field. - Paper attempts to propose a new setting which comes with both a) theoretical guarantees and b) applicability on real-world data, - I did not completely checked the proofs, however, so far I have not found any miscalculations or mathematical flaws.

Weaknesses

- IMO paper is not well-written, and this might be the biggest weakness of this work. Introduction seems short and not that much informative. Also, transitions from one part or section to another do not seem to be smooth enough. There are some cases where an equation or formula is referred to, but in fact it appears (for the first time) at least two pages later which makes the paper a little confusing for a general reader. Positioning of the work w.r.t prior papers is lacking in some ways, and some assumptions are not sufficiently justified. Overall, it seems that authors have tried to compress too much information into a 9-page limited manuscript which has degraded its readability. I suggest a major reconsideration in the writing, or even maybe considering this work for a journal paper instead of a conference. - One of the main theoretical contributions, as far as I have understood, is the claimed "non-trivial" behavior of the sample complexity bound which is outlined in Theorem 3.2, where authors show a non-symmetic behaviour between $m$ and $n$. However, in L.79 authors mention a similar relation in an existing work (Ref. [18]), which I assume is achieved for a slightly different problem. If this non-symmetric relation has been already discovered, it might affect the contribution level of this paper (please correct me if I am wrong). - In Thm. 3.3 authors claim to achieve an error lower-bound for mLFHT which matches (more or less) the error upper-bound in Thm 3.2. However, my understanding is that the bound in Thm 3.3 is mainly for the particular kernel-based solution of this paper, and not for mLFHT in general. The actual error lower-bound might be a lot smaller (or not). Again, please correct me if I am wrong. - I have some questions regarding a number of assumptions and derivation in the paper to see how they might limit the applicability of this solution (please see Questions section). ----------------------------------------------------------------- Minor comments: - Caption of Fig. 1: Eq. (4) appears on page 4, but figures is on page 2. - L.82 to L.89: explanations are vague, please consider some improvements. - Section 1.2 is a key part of the technical contribution (introducing mLFHT), but there are no prior announcements or motivations for it. Please highlight it more. - L.105 to L.109: Explanations seem to be non-informative, and can be removed. - Transition from Section 1.2 to 2.1 is not smooth at all. Also, the math that comes afterwards is unncessarily intense and some of it can be moved to appendix (Specially the "Removing the Bias" part, I guess it won't hurt the paper it this part is moved). - Again, section 2.2 needs more prior advertisement and explanations. - L.140 to L.151: explanations seem vague. - L.154: please consider citing some ref. paper for the theorem, otherwise it might look like it is your contribution. - L.179: Authors claim that this paper imposes less restrictions on the class of distributions for $P_X$ and $P_Y$ compared to other works. I am not completely sure about this claim (see questions), however, it might be a good idea to advertise it more. For example, authors can bring it up in the Introduction section.

Questions

- Please position your work w.r.t Ref. [18], since they also have achieved a similar non-symmetric and non-aasymptotic relation between $m$ and $n$. - Please justify the assumptions (i) and (iii) in L.165 and L.167, respectively. Assumption (ii) makes sense, but I assume (i) and (iii) might be limiting. Are they necessary in general (are they fundamentally required)? If yes, then please elaborate. If not, please explain how this will affect the applicability of this method in real-workd tasks. - In Theorem 3.2, how can we deal with $R$? While reading Section 3.5, I noticed $R$ automatically becomes zero in other existing works since they assume $P_Z=P_X$ or $P_Z=P_Y$. This makes the comparison a little troublesome. Again, is the appearance of $R$ inevitable in your equations? or is it a limitation of this work? - Related to previous question: In L.101 it has been said that $P_Z\triangleq (1-\nu)P_X+\nu P_Y$. Then, in L.163 we have $\nu=\arg \min_{\nu'} \mathrm{MMD}(P_Z,(1-\nu')P_X+\nu' P_Y)$. Does this mean $R$ is always zero, since $P_Z$ is already assumed to be a convex combination of $P_X$ and $P_Y$? This part is confusing, please clarify.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

2 fair

Contribution

2 fair

Limitations

-

Summary

The paper addresses a likelihood-free hypothesis testing (LFHT) scheme, where the data distribution is a mixture of two distributions. The null hypothesis is given by one of these distributions, whereas the alternative hypothesis is that the mixture coefficient is lower-bounded by some delta. The motivation for such a scheme is that it is tied to some applications in particle physics, for example, the Higgs boson discovery. This is a generalization of the original LFHT scheme, which is recovered if delta=1. Goal of the paper is to characterize the tradeoff between n, i.e., the size of the dataset and m, the number of samples available from the mixture data distribution available at test time. Specifically, the authors derive lower and upper bounds on the minimal sample complexity. They also empirically verify this trade-off for kernel based hypothesis testing, where the kernels are parameterized via neural networks.

Strengths

An interesting result is the dependency between n and m for which the authors derive lower and upper bounds, with a non-trivial trade-off between these quantities. It seems though that this was already addressed in prior work, but this is not my research area and I may be missing other contributions.

Weaknesses

It seems that the applications for the proposed mixture LFHT are quite limited. In particular, the Higgs boson discovery is a very specific application, and therefore it is unclear whether this work extends to other key applications. The authors mention in Section 4 that the results from Theorem 3.2 cannot be directly applied because of the dependency of data and kernel. This is not clear to me. Isn’t the main idea of a kernel that it is learned from the data? It also seems to be the reason why their proposed generalization bounds cannot be included in Fig. 1 as a reference, which questions the usefulness of these bounds as fundamental limits of the scenario at hand. The statement in line 274 seems like a trivial observation, typically the validation set is always chosen much smaller than the training set.

Questions

See weaknesses.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

Does not apply.

Summary

This paper proposes a test statistic that can be used for likelihood-free hypothesis testing [LFHT] (for distributions $P_X, P_Y$, given a sample from $P_Z$, decide if $P_Z = P_X$ versus $P_Z = P_Y$) and mixed likelihood-free hypothesis testing [MLFHT] (for $P_Z = (1 - \nu) P_X + \nu P_Y$, decide if $ \nu = 0 $ versus $ \nu \ge \delta$). The test statistic is defined as the MMD distance between $P_Y$ and $P_X$ for an appropriately chosen kernel $K$. The paper then shows an upper and lower bound for these two testing problems. These depend on a base measure $\mu$ and a kernel $K$, both of which can be chosen, such that if $e_j$ are eigenfunctions of $\mu$, then $K(x, y) = \sum_j \lambda_j e_j(x) e_j(y) $. The bounds are then stated in terms of $\lambda$ (either $\mid\mid \lambda \mid \mid_\infty $ or $ \mid \mid \lambda \mid\mid_2$).

Strengths

- The results are very general with reasonable assumptions. The authors assume that the distributions $P_x, P_y, P_z$ have bounded densities wrt the base measure $\mu$, and the sample complexity scales linearly with this bound on the density. This is in contrast to existing work, which assumes more descriptive assumptions on these distributions. - There is empirical support for the asymmetric sample complexity between the train sample $n$ and the test sample $m$. - The lower bounds are general, in that although they are minimax, they apply for any choice of $\mu, K$. - The upper bound allows for distribution mismatch, i.e., the test sample need not be a perfect mixture of $P_X, P_Y$. The bound holds as long as the true distribution is close in MMD to some mixture of $P_x, P_y$. - This approach also allows for learning a kernel from the data, although the theory bounds don't hold in this case as it violates independence between choice of the kernel and the training samples.

Weaknesses

- The bounds are a little non-intuitive / roundabout, as they depend only on the base measure $\mu$ and the kernel $K$, both of which do not directly depend on the hypothesis class containing $P_x, P_y$. From my understanding, the only place the hypothesis class shows up is that it must have bounded density with respect to the measure $\mu$. - The novelty of the results over existing work is not explained fully. Is the main contribution of the work bounds for the mixed-distribution testing? Or is the test statistic and the analysis also entirely new? - As mentioned by the authors, there is gap between the upper and lower bounds for the training set size $n$ and its dependence on the mixture coefficient $\delta$. However, I think this is acceptable and a good open question.

Questions

See weaknesses section.

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 discuss differences between the upper and lower bounds, but apart from that, there's no discussion of limitations. There should be more discussion about drawbacks of this approach wrt existing approaches -- surely there must be some based on how general these results are in comparison to existing work.