Approximating the null distribution of generalized distance covariance

Technical Summary: Approximating the Null Distribution of Generalized Distance Covariance

Problem Statement
Distance covariance, introduced by Székely et al., is a standard tool for assessing the independence of random variables. In practice, hypothesis testing via distance covariance typically relies on permutation procedures. However, permutations become computationally prohibitive for large sample sizes or when extremely small $p$-values are required with high precision. Existing computationally efficient alternatives, such as moment-matching approaches (e.g., Gamma or Pearson type III approximations) and conservative parametric approximations, often exhibit substantial discrepancies in the tails of the distribution, leading to inaccurate Type I error rates. While the asymptotic null distribution of distance covariance is known to be a weighted sum of chi-square random variables, a rigorous theoretical justification for directly approximating this distribution using empirical spectra has been lacking, particularly regarding measurability and separability conditions.

Methodology
The paper introduces a generalized distance covariance framework and develops a spectral approach to approximate its null distribution directly.

1. Theoretical Framework:

   • The author defines generalized distance covariance using distances of negative type on separable metric spaces, explicitly addressing measurability and continuity conditions often omitted in prior literature.
   • They establish a Central Limit Theorem (Theorem 2.1) showing that under independence, the scaled test statistics ($n\hat{U}^2_n$ and $n\hat{V}^2_n$) converge in distribution to weighted sums of independent chi-square variables. The weights are determined by the eigenvalues of integral operators associated with the distance kernels.
   • Theorem 3.1 proves that the empirical spectra of the doubly centered distance matrices ($A_n$ and $B_n$) consistently estimate the population eigenvalue sequences. Consequently, the empirical distribution functions derived from these spectra converge uniformly to the true limiting distribution, validating the direct approximation approach without requiring independence between $X$ and $Y$ for the spectral consistency itself.

2. Computational Implementation:

   • Adaptive Eigenvalue Computation: To avoid the $O(n^3)$ cost of full eigendecomposition, the author proposes an algorithm that computes only the $k$ largest eigenvalues using a Lanczos method. By utilizing the known sum of all eigenvalues (derived from the trace of the matrices), they construct upper and lower bounds for the $p$-value. The algorithm iteratively increases $k$ until the bounds converge within a specified tolerance or the remaining eigenvalue mass is negligible. This reduces complexity to $O(kn^2)$.
   • Shrinkage Correction: Recognizing that the empirical eigenvalues can be overdispersed relative to the population, the author proposes a shrinkage approach for the weights of the Gaussian quadratic form. This method matches the first two moments of the approximating distribution to unbiased estimates of the test statistic's moments (available in $O(n^2)$ time), thereby improving finite-sample precision.

Key Results

• Theoretical Validity: The paper provides the first rigorous proof that the spectral approximation is asymptotically valid under mild assumptions, ensuring that the empirical Type I error converges to the nominal level as $n \to \infty$.
• Simulation Performance:
  • Type I Error: Simulations demonstrate that the proposed spectral tests are the only available non-permutation methods (aside from costly Monte Carlo) where the empirical Type I error converges to the nominal level. Competitors like Gamma approximations become increasingly anti-conservative for small $p$-values, while others (SPV, SRB) remain conservative.
  • Sample Size Sensitivity: For moderate to large sample sizes ($n \ge 100$), the spectral tests outperform existing competitors. However, for very small samples ($n \le 50$), the spectral approach shows weak performance compared to the three-moment based approximation (BB3) or permutation tests.
  • Shrinkage Efficacy: The shrinkage approach consistently outperforms the uncorrected spectral method (using the "plain spectrum") across almost all scenarios, providing numerical justification for the moment-matching correction.
• Computational Efficiency: The adaptive spectral algorithm significantly reduces runtime compared to full eigendecomposition. For $n=32,000$, the full spectral method takes over 3 hours, whereas the adaptive method (using the first 100 eigenvalues) completes in under 4 minutes. The Gamma approximation remains the fastest but at the cost of accuracy in the tails.

Significance and Claims
The author claims to close a theoretical gap by rigorously establishing the validity of direct spectral approximation for generalized distance covariance, addressing measurability issues often left implicit. The work provides a practical, computationally efficient alternative to permutation tests for large-scale independence testing, particularly where high precision in the tails is required.

The paper modestly notes limitations: the spectral approach is not recommended for very small sample sizes ($n \le 50$), where permutation procedures remain the exact and efficient choice. Furthermore, the $O(n^2)$ memory requirement for storing distance matrices remains a bottleneck for extremely large datasets, though the author suggests potential future extensions via binning or kernel approximation. The results are noted to transfer directly to the Hilbert–Schmidt Independence Criterion (HSIC) and potentially to other degenerate U- and V-statistics.