# Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 50 references that are in the map.
- First posted on arXiv 4 Mar 2026.

## Builds on (most cited first, 14 of 14)

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (2014)
- [Learning-based Support Estimation in Sublinear Time](https://mlsanity.com/paper/2106.08396/) (2021)
- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [A Distribution Free Conditional Independence Test with Applications to Causal Discovery](https://mlsanity.com/paper/2105.07555/) (2021)
- [Testing Shape Restrictions of Discrete Distributions](https://mlsanity.com/paper/1507.03558/) (2015)
- [Towards Testing Monotonicity of Distributions Over General Posets](https://mlsanity.com/paper/1907.03182/) (2019)
- [Testing Properties of Multiple Distributions with Few Samples](https://mlsanity.com/paper/1911.07324/) (2019)
- [Testing Mixtures of Discrete Distributions](https://mlsanity.com/paper/1907.03190/) (2019)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Better Private Distribution Testing by Leveraging Unverified Auxiliary Data](https://mlsanity.com/paper/2503.14709/) (2025)

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

- [Differentially Private Verification of Distribution Properties](https://mlsanity.com/paper/2604.10819/) (2026)

## Abstract (arXiv)

Independence testing is a fundamental problem in statistical inference: given samples from a joint distribution p over multiple random variables, the goal is to determine whether p is a product distribution or is ε-far from all product distributions in total variation distance. In the non-parametric finite-sample regime, this task is notoriously expensive, as the minimax sample complexity scales polynomially with the support size. In this work, we move beyond these worst-case limitations by leveraging the framework of textitaugmented distribution testing. We design independence testers that incorporate auxiliary, but potentially untrustworthy, predictive information. Our framework ensures that the tester remains robust, maintaining worst-case validity regardless of the prediction's quality, while significantly improving sample efficiency when the prediction is accurate. Our main contributions include: (i) a bivariate independence tester for discrete distributions that adaptively reduces sample complexity based on the prediction error; (ii) a generalization to the high-dimensional multivariate setting for testing the independence of d random variables; and (iii) matching minimax lower bounds demonstrating that our testers achieve optimal sample complexity.