# An Adaptive Test of Independence with Analytic Kernel Embeddings

arXiv: https://arxiv.org/abs/1610.04782 · HTML: https://mlsanity.com/paper/1610.04782/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2016.

## Built on by (most cited first, 13 of 13)

- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [An Asymptotic Test for Conditional Independence using Analytic Kernel Embeddings](https://mlsanity.com/paper/2110.14868/) (2021)
- [A Permutation-Free Kernel Independence Test](https://mlsanity.com/paper/2212.09108/) (2022)
- [Entropy Regularized Optimal Transport Independence Criterion](https://mlsanity.com/paper/2112.15265/) (2021)
- [Learning linear non-Gaussian directed acyclic graph with diverging number of nodes](https://mlsanity.com/paper/2111.00740/) (2021)
- [DUAL: Learning Diverse Kernels for Aggregated Two-sample and Independence Testing](https://mlsanity.com/paper/2510.11140/) (2025)
- [Nystr"om M-Hilbert-Schmidt Independence Criterion](https://mlsanity.com/paper/2302.09930/) (2023)
- [Nystr"om Kernel Stein Discrepancy](https://mlsanity.com/paper/2406.08401/) (2024)
- [A Stein Goodness of fit Test for Exponential Random Graph Models](https://mlsanity.com/paper/2103.00580/) (2021)
- [Instrument Space Selection for Kernel Maximum Moment Restriction](https://mlsanity.com/paper/2106.03340/) (2021)
- [Private independence testing across two parties](https://mlsanity.com/paper/2207.03652/) (2022)
- [Optimal Online Change Detection via Random Fourier Features](https://mlsanity.com/paper/2505.17789/) (2025)
- [Discussion of `Multiscale Fisher's Independence Test for Multivariate Dependence'](https://mlsanity.com/paper/2206.11142/) (2022)

## Abstract (arXiv)

A new computationally efficient dependence measure, and an adaptive statistical test of independence, are proposed. The dependence measure is the difference between analytic embeddings of the joint distribution and the product of the marginals, evaluated at a finite set of locations (features). These features are chosen so as to maximize a lower bound on the test power, resulting in a test that is data-efficient, and that runs in linear time (with respect to the sample size n). The optimized features can be interpreted as evidence to reject the null hypothesis, indicating regions in the joint domain where the joint distribution and the product of the marginals differ most. Consistency of the independence test is established, for an appropriate choice of features. In real-world benchmarks, independence tests using the optimized features perform comparably to the state-of-the-art quadratic-time HSIC test, and outperform competing O(n) and O(n log n) tests.