High dimensional consistent independence testing with maxima of rank correlations

Mathias Drton, Fang Han, Hongjian ShiThe Annals of Statistics 2018 · arXiv

Abstract

Testing mutual independence for high-dimensional observations is a fundamental statistical challenge. Popular tests based on linear and simple rank correlations are known to be incapable of detecting non-linear, non-monotone relationships, calling for methods that can account for such dependences. To address this challenge, we propose a family of tests that are constructed using maxima of pairwise rank correlations that permit consistent assessment of pairwise independence. Built upon a newly developed Cramér-type moderate deviation theorem for degenerate U-statistics, our results cover a variety of rank correlations including Hoeffding's $D$, Blum-Kiefer-Rosenblatt's $R$, and Bergsma-Dassios-Yanagimoto's $\tau^*$. The proposed tests are distribution-free in the class of multivariate distributions with continuous margins, implementable without the need for permutation, and are shown to be rate-optimal against sparse alternatives under the Gaussian copula model. As a by-product of the study, we reveal an identity between the aforementioned three rank correlation statistics, and hence make a step towards proving a conjecture of Bergsma and Dassios.

Introduction

In the era of big data, researchers frequently encounter datasets where the number of variables ($p$) significantly exceeds the number of observations ($n$). A core task in analyzing such data is determining whether the variables are mutually independent. While classical methods like Pearson’s correlation or Spearman’s rho are computationally efficient, they are fundamentally limited to detecting linear or monotone relationships. In complex systems, dependencies often manifest in non-linear or non-monotone patterns—such as circular or sinusoidal relationships—which these traditional metrics fail to capture.

To bridge this gap, "consistent" rank correlations like Hoeffding’s $D$ have been developed. However, their application in high-dimensional settings has been hindered by a lack of theoretical understanding regarding their behavior as $p \to \infty$. This paper introduces a family of tests based on the maxima of pairwise rank correlations, providing a robust and computationally efficient framework for high-dimensional independence testing.

Methodology: Maximum-Type Tests and Degenerate U-Statistics

The authors propose a maximum-type testing statistic. Rather than aggregating all pairwise dependencies (an $L_2$-type approach), which can dilute the signal in sparse settings, the proposed method focuses on the maximum observed pairwise dependency ($L_\infty$-type). This is particularly effective for "needle in a haystack" scenarios where only a few variables are dependent.

The primary challenge in analyzing these statistics lies in their "degeneracy." Under the null hypothesis of independence, the first-order terms of the U-statistics (like Hoeffding’s $D$, Blum-Kiefer-Rosenblatt’s $R$, and Bergsma-Dassios-Yanagimoto’s $\tau^*$) vanish. This degeneracy means the statistics do not follow a standard normal distribution, making traditional asymptotic analysis inapplicable.

To resolve this, the authors develop a novel Cramér-type moderate deviation theorem for degenerate U-statistics. This theorem allows for the characterization of the tail probabilities of these statistics. Specifically, it is shown that the maximum of these pairwise correlations converges to a Gumbel distribution (an extreme value distribution). This theoretical breakthrough is significant because it allows for the calculation of p-values and critical thresholds analytically using explicit formulas, eliminating the need for computationally intensive permutation tests.

Theoretical Contributions and the Rank Identity

A notable byproduct of this research is the discovery of a mathematical identity linking three prominent rank correlations. Under the assumption of no ties in the data, the authors demonstrate that:

$$3D + 2R = 5\tau^*$$

This identity not only simplifies the theoretical landscape of rank-based dependence measures but also provides a key step toward proving a long-standing conjecture by Bergsma and Dassios regarding the consistency of the $\tau^*$ statistic.

Furthermore, the proposed tests are "distribution-free" for multivariate distributions with continuous margins. This means the test's validity does not depend on the underlying distribution of the data (e.g., it does not require Gaussianity), making it highly versatile for real-world applications where the data distribution is unknown.

Simulation Results and Performance

The authors evaluated the proposed "Extreme D," "Extreme R," and "Extreme $\tau^*$" tests through extensive Monte Carlo simulations. The tests were compared against traditional maximum-type tests based on Pearson and Spearman correlations across several scenarios:

  • Type I Error Control: The tests accurately maintained the nominal significance level even when the dimension $p$ was exponentially larger than the sample size $n$ (specifically, $\log p = o(n^\theta)$).
  • Power Against Non-linear Dependencies: In scenarios involving complex non-linear transformations (e.g., sine and cosine dependencies), the proposed tests achieved a power of 1.000, whereas traditional linear/monotone tests performed no better than random chance (power $\approx$ 0.05).
  • Sparse vs. Dense Alternatives: The maximum-type tests proved to be "rate-optimal" for sparse alternatives. In these cases, the $L_\infty$ approach significantly outperformed sum-type ($L_2$) tests, which often wash out sparse signals.

Discussion and Limitations

While the proposed tests offer significant advantages in high-dimensional, sparse, and non-linear settings, there are inherent trade-offs. In "dense" scenarios, where many variables share weak dependencies, sum-type tests may still be more powerful than maximum-type tests.

Additionally, the current theory assumes continuous distributions. While practical workarounds like random tie-breaking exist, a formal theoretical extension to discrete data remains a subject for future research. Finally, the authors suggest that the range of the moderate deviation theorem ($o(n^\theta)$) might be further refined for cases with infinitely many nonzero eigenvalues, pointing toward ongoing developments in the probability theory of U-statistics.

Conclusion

This work provides a rigorous and practical solution for testing independence in high-dimensional data. By leveraging the maxima of consistent rank correlations and providing a new theoretical foundation via moderate deviation theorems, the authors have created a tool that is both mathematically optimal and computationally accessible for modern data science challenges.

Summary updated

Abstract

Testing mutual independence for high-dimensional observations is a fundamental statistical challenge. Popular tests based on linear and simple rank correlations are known to be incapable of detecting non-linear, non-monotone relationships, calling for methods that can account for such dependences. To address this challenge, we propose a family of tests that are constructed using maxima of pairwise rank correlations that permit consistent assessment of pairwise independence. Built upon a newly developed Cramér-type moderate deviation theorem for degenerate U-statistics, our results cover a variety of rank correlations including Hoeffding's $D$, Blum-Kiefer-Rosenblatt's $R$, and Bergsma-Dassios-Yanagimoto's $τ^*$. The proposed tests are distribution-free in the class of multivariate distributions with continuous margins, implementable without the need for permutation, and are shown to be rate-optimal against sparse alternatives under the Gaussian copula model. As a by-product of the study, we reveal an identity between the aforementioned three rank correlation statistics, and hence make a step towards proving a conjecture of Bergsma and Dassios.
BibTeX
@article{drton2018high,
  author = {Mathias Drton and Fang Han and Hongjian Shi},
  title = {{High dimensional consistent independence testing with maxima of rank correlations}},
  journal = {The Annals of Statistics},
  year = {2018},
}
Figure