Adaptive Multiscale Binary Expansion Tests for Independence

This paper introduces a new family of adaptive, distribution-free independence tests for multivariate random vectors based on binary expansion coefficients, supported by a tractable asymptotic theory. Our first key contribution establishes a general equivalence between independence testing and testing cross-covariances among exponentially many binary expansion interaction coefficients, applicable to broad sample spaces and not limited to kernel-induced representations. While this exponential interaction structure makes naive construction and computation infeasible, we overcome this challenge by reformulating the proposed tests as a class of U-statistics and deriving an explicit kernel representation that enables scalable and efficient computation. Exploiting the multiscale nature of binary expansions, the proposed framework automatically adapts to unknown dependence structures by selectively truncating higher-order interactions, yielding both strong power and clear interpretability. To further enhance power and computational efficiency, we introduce an adaptive weighted aggregation procedure, termed wa-dCoBET, which combines a baseline Covariance Binary Expansion Test (CoBET) with a distance-measure–based CoBET. Extensive simulations and a real-data application demonstrate that wa-dCoBET consistently matches or outperforms HSIC and distance covariance, particularly in higher-dimensional and non-monotone settings, while maintaining accurate type I error control.

Contemporary data sets are becoming increasingly complex, with a growing number of features collected in many applications. In machine learning tasks such as prediction, understanding the relationships among features or between features and outcomes is crucial, and testing statistical independence provides an important tool for quantifying such relationships. This paper presents several interesting and surprising findings. We reformulate the independence testing problem as testing the cross-covariance of binary expansion interaction coefficients, and establish their equivalence under very general settings without restrictive assumptions. This result is particularly notable because testing independence is typically regarded as substantially more challenging than testing correlation. Although direct computation is infeasible due to the rapidly growing number of binary expansion interaction coefficients, we derive a scalable and efficient algorithm through an explicit kernel representation. We further improve both detectability and scalability by developing adaptive procedures for unknown dependence structures and deriving an explicit asymptotic distribution for the proposed test statistics. The independence characterization developed in this paper has broader implications beyond independence testing itself. To facilitate further research and applications, we have released a free and easy-to-use software package on GitHub (https://github.com/yyang3388/Cobet).