Learning Representations for Independence Testing

Thank you for your constructive feedback and your review of our paper.

One limitation could be the lack of evaluation on real-world datasets [...]

Thanks for bringing these datasets to our attention, and we appreciate this open-minded comment.

In general, the challenge is that many of the existing real-world datasets are just "too simple," because they are designed to be approachable for classification or regression tasks. If a classifier or regressor gets any non-trivial performance, then the variables are clearly dependent (this is the basis of C2STs). On many of these datasets, median heuristic-based kernel tests achieve perfect power with only a few hundred samples. Our optimization-based methods, on the other hand, shine in problems with subtle dependencies, for which these simpler kernels are barely able to detect any dependence at all – not the kinds of datasets which tend to be available in machine learning repositories. We believe that such questions do arise in real scientific and engineering tasks, but lacking the tools to address them, people usually don't think to ask or publicize such problems.

One real dataset where dependence is present but subtle is the Wine Quality dataset [Paulo et al., 2009], which details physicochemical properties (e.g., sugar, pH, chlorides) of different types of red and white wines, along with their perceived quality as an integer value from 1 to 10. We test dependency between residual sugar levels and quality, and plot our results in Figure 11 (Appendix D.3.1); our method outperforms all competitors for a range of dataset sizes, although the median heuristic is better at very small sizes and for large enough datasets all methods work well.

We would be happy to hear any suggestions of other real datasets that we should try (without taking too much domain-knowledge effort for one application of an ICLR paper).

Another limitation, which is also discussed by the authors, is the scope only focusing on the independence test, which is considerably easier compared with the conditional independence test. Can you provide more details on what specific challenges you foresee in adapting the current method for conditional independence?

Thanks for your comment. This is true; conditional independence (unless there are many samples per condition) is a more difficult problem and requires very different techniques, because we need to find the relationship between the condition variable and interested variables. The fundamental idea of optimizing the asymptotic test power could apply to conditional testing approaches like KCI [Zhang et al., 2011] and CIRCE [Pogodin et al. 2023], but the performance might largely depend on how well we model the relation between the conditioning variable and interested variables, which brings many challenges of its own beyond the setting of marginal independence. We will discuss this relationship in our revision.

A minor piece of advice: A paragraph or several sentences to highlight the difference between the traditional independence test and the independence test in high dimensions will be appreciated and suitable for readers from different levels.

Thank you for your suggestion. We will expand on this difference in our revision.

What is the definition of K in Line 130?

Thanks for bringing this to our attention. K is basically the test/batch size; we will clarify this.

Thank you for your constructive feedback and your review of our paper.

(A note for the authors - this can be also seen from the proof of the DV formula)

That's quite interesting, thanks for pointing this out! We'll add a footnote about this in the revision.

I feel that the paper could benefit from better representation, which makes it harder for the reader to understand the contributions in a bird's view, e.g., some crucial parts are migrated to the appendix, such as the assumptions of the main theorem of the paper, while some parts do not benefit the presentation in my opinion, such as some of the very specific and technical details in Section 5.

Thanks for bringing this to our attention. Certain parts of the theory, particularly the assumptions, were moved to the appendix in the process of editing our paper mainly to fit in the page limits. We also believe that the assumptions are relatively benign, and hold for many problems and the particular deep kernels we use in practice; see Propositions 7 and 9 of [Liu et al., 2020]. We agree that we should at least discuss this in the main body; we will add at least some discussion, and hopefully statements of the assumptions if we can make them fit, to the main body in revision.

As the authors utilize 'heavy' machinery such as NN optimization, I would expect at least one experimental results on real world high dimensional data.

Our experiments are indeed synthetic, but we want to emphasize that RatInABox was designed by neuroscientists as a potential replacement for running real neural experiments with live animals; it was designed to be as realistic as possible. Thus, while synthetic, we think it is not entirely not "real world data." If we recorded real rats running around a maze for several months, and applied standard neural processing pipelines, the dataset should look quite similar (at the cost of grad students' time and rats' lives).

In general, one major challenge with real-world datasets for independence testing is that many of the easily usable real-world datasets are just "too simple," because they are designed to be approachable for classification or regression tasks. If a classifier or regressor gets any non-trivial performance, then the variables are clearly dependent (this is the basis of C2STs). On many of these datasets, median heuristic-based kernel tests achieve perfect power with only a few hundred samples. Our optimization-based methods, on the other hand, shine in problems with subtle dependencies, for which these simpler kernels are barely able to detect any dependence at all – not the kinds of datasets which tend to be available in machine learning repositories. We believe that such questions do arise in real scientific and engineering tasks, but lacking the tools to address them, people usually don't think to ask or publicize such problems.

One real dataset where dependence is present but subtle is the Wine Quality dataset [Paulo et al., 2009], which details physicochemical properties (e.g., sugar, pH, chlorides) of different types of red and white wines, along with their perceived quality as an integer value from 1 to 10. We test dependency between residual sugar levels and quality, and plot our results in Figure 11 (Appendix E.1); our method outperforms all competitors for a range of dataset sizes, although the median heuristic is better at very small sizes and for large enough datasets all methods work well.

We would be happy to hear any suggestions of other real datasets that we should try (without taking too much domain-knowledge effort for one application of an ICLR paper).

Literature review: Independence testing has been previously explored in the form of optimization of families of functions. Specifically, classical methods such as canonical correlation analysis (Hoteling 67) and its many extensions tackle the problem of independence testing. In an information theoretic setting there are the Hirschfeld-Gebelein-Renyi coefficient. More recently, max-sliced mutual information (Tsur 24), which was shown useful for independence testing and was connected to constrained variational mutual information estimation.

Thanks for highlighting these works, some of which we were unaware of. We'll add a discussion of them to the related work section, but as far as we can tell, none seem to address our fundamental problem of learning an appropriate representation to test with. In particular, when optimizing over RKHS functions, HGR is closely related to a normalized version of HSIC; choosing the RKHS to use becomes very similar to the problem of choosing the RKHS to use in an HSIC test.

The max-sliced mutual information is quite relevant, but the form of representation they consider (slicing) is extremely limited; we will discuss this further in revision.

Dear Reviewer WLby,

Thank you for taking the time and effort to review our manuscript.

We have carefully addressed all your comments and prepared detailed responses. Could you kindly review them at your earliest convenience?

We hope our responses have satisfactorily addressed your key concerns. If anything remains unclear or requires further clarification, please do not hesitate to let us know, and we will address it promptly.

We look forward to your feedback.

Best regards,

Authors of Submission 11733

Dear Reviewer WLby,

Thank you for taking the time and effort to review our manuscript.

We have carefully addressed all your comments and prepared detailed responses. Could you kindly review them at your earliest convenience?

We hope our responses have satisfactorily addressed your key concerns. If anything remains unclear or requires further clarification, please do not hesitate to let us know, and we will address it promptly.

We look forward to your feedback.

Best regards,

Authors of Submission 11733

Thank you for your constructive feedback and your review of our paper.

A notable issue is the lack of clarity regarding the aims and achievements of the paper. For instance, while it claims to present two approaches for independence testing, the conclusion suggests that it only studies one approach, leading to confusion about the overall contribution and focus of the work.

Thank you for bringing this to our attention. We indeed present two related approaches to independence testing: one based on maximizing the asymptotic power of a HSIC test, and one family based on maximizing variational mutual information bounds. We will be sure to make both contributions more explicit in the conclusion.

The performance of HSIC-based tests is significantly influenced by the choice of kernel. While the paper proposes methods to optimize kernel selection, identifying the appropriate kernel for specific data types or distributions remains challenging and may not generalize well across diverse datasets.

It is true that the choice of kernel significantly impacts the test performance. Using a fixed test may not work well on any given problem, which is indeed the entire purpose of our paper. Using a particular kernel architecture to optimize for a given problem may not help, if the kernel architecture is inappropriate; this is exactly analogous to the same concern in supervised learning, however, and we can choose between different options of kernel architecture in the same way that we choose between different options of classifier architecture when training a classifier. Our experiments confirm that a general MLP-type architecture feeding into a Gaussian kernel gives a good tradeoff between expressivity and ability to learn in the class; note in particular that HSIC-D, using a deep kernel, always outperforms HSIC-O, choosing the bandwidth of a Gaussian kernel.

Although the proposed methods enhance sample efficiency compared to traditional tests, they still necessitate a considerable number of samples to effectively detect subtle dependencies in very high-dimensional data, which could limit their practicality in scenarios with restricted data availability.

It is true that learning a kernel requires more data than just using an off-the-shelf kernel; this is an instance of the tradeoff mentioned in the previous answer. For very small sample sizes, we should choose a simpler kernel architecture; for very small sizes, not optimizing will be better than trying to optimize. The experiments on Sinusoid and RatInABox show that even for fairly complex forms of dependence with fairly general kernel architectures, the total number of training samples needed to identify a good kernel need not be exorbitant (<2,000 here).

As our experiments show, our method is better than many alternatives for several problems across a wide range of total available samples. For instance, although HSICAgg does not need a separate training set, our train+test split method typically outperforms it.

Additionally, the paper does not provide theoretical rates for the convergence of test statistics and lacks a discussion on the asymptotic validity of power in its main content.

We briefly mentioned the already-known asymptotics/convergence rate for these statistics around line 220; we used these results to derive our HSIC-D method in line 308. Detailed theorems regarding HSIC asymptotics are given in Appendix A, as a direct result of the asymptotic normality of U-statistics [e.g. Serfling 1980, Theorem B, p.193]. For the revision, we will try to bring more details around this into the main body to provide more context for the reader; thanks for bringing this to our attention

Furthermore, regarding Algorithm 1, the choice of $n_\text{perm}$ is required; what are the best empirical strategies for selecting this parameter, and how does the choice impact the convergence rate?

$n_\text{perm}$ is the number of shuffles used in the permutation test, and does not affect the convergence rate; it is totally independent of the choice of test statistic/kernel leading into the permutation test, and the choice does not affect the training procedure. As long as we include the original alignment in the permutation procedure, the permutation test is guaranteed to be finite-sample valid [Hemerik & Goeman 2018, Theorem 2]. The conservatism of the $p$-value is determined by the number of permutations; a one-permutation test is extremely conservative, while using all $n!$ permutations when $n \alpha$ is also an integer would yield an exact $p$-value. Larger $n_\text{perm}$ will give a slightly less conservative test, but the difference beyond using a few hundred permutations is minimal for typical values of $\alpha$. We also emphasize that we do not need to permute during training, only once at the very end, and so using a few hundred permutations (each of which only requires taking a quadratic form of the kernel matrix) is not a substantial portion of our runtime.

Dear Reviewer WsaA,

Thank you for taking the time and effort to review our manuscript.

We have carefully addressed all your comments and prepared detailed responses. Could you kindly review them at your earliest convenience?

We hope our responses have satisfactorily addressed your key concerns. If anything remains unclear or requires further clarification, please do not hesitate to let us know, and we will address it promptly.

We look forward to your feedback.

Best regards,

Authors of Submission 11733

Dear Reviewer WsaA,

Thank you for taking the time and effort to review our manuscript.

We have carefully addressed all your comments and prepared detailed responses. Could you kindly review them at your earliest convenience?

We hope our responses have satisfactorily addressed your key concerns. If anything remains unclear or requires further clarification, please do not hesitate to let us know, and we will address it promptly.

We look forward to your feedback.

Best regards,

Authors of Submission 11733

Thank you for your constructive feedback and your review of our paper.

It seems to me that the authors didn't highlight their core contribution enough. The InfoNCE approach already exists in the literature and making an independence test out of it based on permutation is not very interesting; applying this trick to HSIC either. The interesting part to me is they propose to minimize the SNR -- a quantity that characterizes the statistical power -- instead of the test statistics themselves. However, this contribution is not supported in the experiments (or is not conveyed clearly). I would like to see a comparison between the InfoNCE (HSIC as well) that minimizes the lower bound (test statistic) versus the one that minimizes the SNR. If the latter shows significant improvement upon the former, I would then say the contribution is solid.

Thank you for your interest in our work. To summarize, we present two (related) approaches: one based on maximizing the asymptotic power of a HSIC test, and one based on maximizing variational mutual information bounds.

Regarding the mutual information bound-based test, as in InfoNCE:

We agree that constructing a permutation test from this bound is not a surprising technical contribution, but to our knowledge it has not been considered before in the literature, despite the ease of doing so; we think making this explicit for practitioners unfamiliar with one or the other set of tools is valuable in itself. We also think that the observation of the equivalence of essentially all of these bounds at test time, based on $\hat T$, is novel and interesting.

As for maximizing the SNR:

For HSIC, this is exactly what we do in all of our experiments: HSIC-D/Dx/O are all based on maximizing the $J$ objective, which is HSIC divided by its asymptotic standard deviation. As an ablation, we included tests where we just trained the HSIC statistic (rather than its SNR) in Figure 8 (Appendix C.5); while this approach is reasonably comparable to (but worse than) our method for HDGM-10, it is far far worse than maximizing the SNR for HDGM-30, -50, and RatInABox.

For the $\hat T$-based tests corresponding to MI estimators, as you noticed, we did not originally explore maximizing the SNR in our experiments. In the last week since seeing the reviews, we have explored this idea in practice. Implementing this procedure yields a valid test, with empirical results in the new Appendix E.1. On Sinusoid, it performs in between InfoNCE and NWJ (which are all close); on RatInABox, it performs slightly worse than NWJ, which is notably worse than InfoNCE; on HDGM-4, its performance is poor; on HDGM-10, it performs abysmally, with trivial power. Throughout, it is consistently worse than our HSIC-based tests.

Why did this happen? Appendix E.2.2 explores this question on RatInABox. Here, the $\hat T$-SNR test does obtain better SNRs than InfoNCE (by a factor of 2-3). In fact, the $\hat T$-SNR test follows the asymptotics quite closely, with observed powers very close to those predicted by our asymptotic formula $\Phi\left( \sqrt{m} \, \mathrm{SNR} - \frac{\sigma\_{\mathfrak{H}_0}}{ \sigma\_{\mathfrak{H}_1}} \Phi^{-1}(1-\alpha) \right)$.

InfoNCE tests, though, do much, much better than predicted by these asymptotics. This is due to a strange phenomenon: as shown in Figure 15, the InfoNCE estimate and permutation-based rejection threshold are 99% correlated across different observed test sets for the same problem. This strange behavior is totally outside of our asymptotic analysis, which assumes the threshold is approximately a constant independent of the particular test sample.

This can also partially explain why $\hat T$-SNR tests are so much worse than HSIC ones. In this case, the ratio of standard deviations is approximately one; thus the power is about $\Phi\left( \sqrt{m} \, \mathrm{SNR} - 1.6 \right)$, for $\alpha = 0.05$. When $m = 2,000$, $\sqrt m$ is about $45$, and we obtain SNRs around $0.02$, giving a product around $0.9$. Thus subtracting $1.6$ from the probit of the power is highly significant until $m$ is much larger. By contrast, the asymptotic power of the HSIC test is $\Phi\left( \sqrt{m} J - \frac{r}{ \sigma\_{\mathfrak{H}_1} \sqrt{m}} \right)$; this additional $1/\sqrt{m}$ on the second term means that its relevance diminishes faster as $m$ grows, avoiding this weight which holds back $\hat T$-SNR tests.