# Optimal rates for independence testing via U-statistic permutation tests

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

## Key facts

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

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

- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [T-Cal: An optimal test for the calibration of predictive models](https://mlsanity.com/paper/2203.01850/) (2022)
- [BEAUTY Powered BEAST](https://mlsanity.com/paper/2103.00674/) (2021)
- [A survey of some recent developments in measures of association](https://mlsanity.com/paper/2211.04702/) (2022)
- [USP: an independence test that improves on Pearson's chi-squared and the G-test](https://mlsanity.com/paper/2101.10880/) (2021)

## Abstract (arXiv)

We study the problem of independence testing given independent and identically distributed pairs taking values in a σ-finite, separable measure space. Defining a natural measure of dependence D(f) as the squared L2-distance between a joint density f and the product of its marginals, we first show that there is no valid test of independence that is uniformly consistent against alternatives of the form f: D(f) ≥ ρ2 . We therefore restrict attention to alternatives that impose additional Sobolev-type smoothness constraints, and define a permutation test based on a basis expansion and a U-statistic estimator of D(f) that we prove is minimax optimal in terms of its separation rates in many instances. Finally, for the case of a Fourier basis on [0,1]2, we provide an approximation to the power function that offers several additional insights. Our methodology is implemented in the R package USP.