[2603.04635] Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions

Statistics > Machine Learning arXiv:2603.04635 (stat) [Submitted on 4 Mar 2026] Title:Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions Authors:Maryam Aliakbarpour, Alireza Azizi, Ria Stevens View a PDF of the paper titled Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions, by Maryam Aliakbarpour and 2 other authors View PDF Abstract: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 $\epsilon$-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 \textit{augmented 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 hi...