A Powerful Bootstrap Test of Independence in High Dimensions

1. Problem Statement

The paper addresses the problem of testing the pairwise independence of a single random variable $X$ against a large pool of random variables $Y_1, \dots, Y_p$. The null hypothesis is:
$$H_0: Y_j \perp X \quad \text{for all } j \in \{1, \dots, p\}$$
against the alternative $H_1$ (the negation of $H_0$).

Key Challenges:

• High Dimensionality: The dimension $p$ can grow exponentially with the sample size $n$ ($p \gg n$).
• Unrestricted Dependence: The variables $Y_1, \dots, Y_p$ can be arbitrarily dependent on each other. The test must remain valid without imposing exchangeability or specific dependence structures on the $Y$ pool.
• Multiple Testing: The goal is not only to test the global null but also to screen and select specific variables $Y_j$ that violate independence while controlling the Family-Wise Error Rate (FWER).
• Limitations of Existing Methods: Popular tests based on distance covariance (e.g., Székely et al., 2007; Székely and Rizzo, 2013) often fail to control size under this specific null hypothesis when $p$ is large or when the copula of $Y$ given $X$ depends on $X$.

2. Methodology

2.1 Test Statistic

The authors propose using the maximum of Chatterjee's (2021) rank correlation coefficients across all $p$ variables.

• Chatterjee's Correlation ($\hat{\xi}_j$): A nonparametric measure of dependence between $X$ and $Y_j$. It is defined based on the order statistics of $X$ and the concomitants of $Y_j$.
• Global Statistic:
  $$\hat{T} := \sqrt{n} \max_{1 \le j \le p} \hat{\xi}_j$$
  Under $H_0$, $\hat{\xi}_j$ converges to 0. The test rejects $H_0$ if $\hat{T}$ exceeds a critical value.

2.2 Inference: Block Multiplier Bootstrap

Standard nonparametric bootstrapping fails for Chatterjee's correlation because the underlying summands are not independent (they form a 1-dependent process). To address this, the authors develop a Block Multiplier Bootstrap:

1. Asymptotic Linear Representation: Under $H_0$, $\sqrt{n}\hat{\xi}_j$ admits a linear representation involving a sum of 1-dependent terms $W_{j,i}$.
2. Blocking: The sum of $W_{j,i}$ is decomposed into "big blocks" (size $q$) and "small blocks" (size 1). The big blocks are constructed to be independent of each other.
3. Bootstrap Procedure:
   • Estimate the block sums $\hat{A}_{j,k}$ from the data.
   • Generate independent standard normal multipliers $\varepsilon_1, \dots, \varepsilon_m$.
   • Compute the bootstrap statistic:
     $$\hat{T}^B := \max_{1 \le j \le p} \frac{1}{\sqrt{mq}} \sum_{k=1}^m \varepsilon_k \hat{A}_{j,k}$$
   • The critical value $\hat{c}(\alpha)$ is the $(1-\alpha)$-quantile of $\hat{T}^B$ conditional on the data.

2.3 Tuning Parameter Selection

The block size $q$ is a crucial tuning parameter. The authors derive an optimal choice $q^*(n)$ by minimizing the Mean Squared Error (MSE) between the bootstrap variance and the asymptotic variance of the individual test statistic.

• The optimal rate is approximately $q^*(n) \approx (n/16)^{1/3}$.
• Simulations show the test is robust to the specific choice of $q$, but the optimal choice minimizes bias-variance trade-offs.

2.4 Stepwise Selection Procedure

To identify specific violating variables while controlling FWER, the paper adapts the Romano-Wolf (2005) stepdown procedure:

1. Test the global null over the current set of hypotheses.
2. If rejected, remove all hypotheses where the individual statistic exceeds the critical value.
3. Repeat with the remaining set until no rejections occur.
   This procedure asymptotically controls the FWER uniformly over a large class of data-generating processes.

3. Key Theoretical Contributions

• Uniform Size Control: Theorem 1 proves that the test asymptotically controls size uniformly over a class of data-generating processes where $p$ can grow exponentially with $n$ (e.g., $p = e^{n^\delta}$). Crucially, this holds without restricting the dependence among $Y_1, \dots, Y_p$.
• Consistency: Theorem 2 establishes that the test is consistent against any fixed alternative where variables are continuously distributed.
• Validity of Block Bootstrap: The paper provides a rigorous proof that the block multiplier bootstrap correctly approximates the distribution of the maximum of Chatterjee's correlations, overcoming the failure of the standard nonparametric bootstrap (Lin and Han, 2024).
• FWER Control: Theorem 3 proves that the proposed stepwise procedure controls the Family-Wise Error Rate asymptotically.

4. Simulation Results

The authors conducted extensive simulations comparing their method (BMB) against distance covariance tests (dcov, dcorT) and rank-based tests (ZXZL, ZZYS).

• Size Control:
  • The proposed test controls size at the nominal level (5%) across all scenarios, including high dimensions and dependent $Y$ variables.
  • Distance covariance tests (dcov, dcorT) fail to control size when the copula of $Y$ given $X$ depends on $X$ (a scenario allowed under $H_0$ but violating the stronger joint independence null).
• Power:
  • The proposed test is more powerful than competitors in high-dimensional settings ($p \gg n$) and when $Y$ variables are dependent.
  • It performs exceptionally well against sparse and decaying alternatives.
  • It shows superior power against cosine alternatives (non-monotonic relationships) compared to distance-based methods.
• Robustness: The test's performance is largely insensitive to the choice of block size $q$.

5. Empirical Application

The method was applied to a gene expression dataset (GSE11923) to identify genes with transcript levels oscillating during the cell cycle ($n=48$ time points, $p=45,101$ genes).

• Using the stepdown procedure with $\alpha=0.05$, the method identified 4,554 genes violating independence.
• This set includes 1,919 genes found in the original study (Hughes et al., 2009) but also 2,635 novel genes not previously identified.
• The method provides stronger statistical guarantees (FWER control) compared to the original study's False Discovery Rate (FDR) control.

6. Significance and Conclusion

This paper makes a significant contribution to high-dimensional statistics by:

1. Solving a Validity Gap: It provides a valid test for pairwise independence in high dimensions where $p \gg n$ and $Y$ variables are dependent, a regime where many existing popular tests (like distance covariance) fail.
2. Computational Efficiency: The method is computationally feasible for very large $p$ (unlike some competing rank-based tests which become intractable).
3. Practical Utility: It offers a rigorous framework for feature screening and variable selection with FWER control, demonstrated effectively in a genomics application.
4. Software: The methodology is implemented in the R package hdIndep, facilitating adoption by practitioners.

The authors conclude that their block multiplier bootstrap approach, combined with Chatterjee's rank correlation, offers a robust, powerful, and theoretically sound solution for independence testing in modern high-dimensional data settings.