Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
Maryam Aliakbarpour, Alireza Azizi, Ria Stevens · 2026
Read Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions by Maryam Aliakbarpour, Alireza Azizi, Ria Stevens (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-04635.txt.
Introduction
Aliakbarpour and colleagues design independence testers with prediction help. Independence testing asks whether a joint distribution is a product or far from every product form. In finite-sample work, sample complexity grows polynomially with support size, making the task expensive. Augmented distribution testing moves past worst-case limits using extra prediction tips. The testers stay robust, keeping worst-case soundness, while gaining when predictions are accurate. Work includes a paired tester that cuts sample complexity by prediction error, a wider version, and matching lower bounds showing optimal complexity.
Catalog record
| CREATOR | Maryam Aliakbarpour, Alireza Azizi, Ria Stevens |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 174785 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.04635
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions Maryam Aliakbarpour, Alireza Azizi, Ria Stevens Abstract Independence testing is a fundamental problem in statistical inference: given samples from a joint distribution p p over multiple random variables, the goal is to determine whether p 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 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 high-dimensional multivariate setting for testing the independence of d d random variables; and (iii) matching minimax lower bounds demonstrating that our testers achieve optimal sample complexity. 1 Introduction Independence testing is a central problem in statistical inference, with applications spanning from medical domains ( 27 ; 46 ; 36 ) to machine learning problems such as causal discovery and feature selection ( 12 ; 48 ; 47 ; 35 ; 51 ; 18 ; 19 ) . Formally, given samples from a joint distribution over multiple random variables, the goal is to determine whether the variables are statistically independent or exhibit some form of dependence. While classical approaches like the \chi^{2} test of 42 are widely used, they typically lack guarantees for the non-parametric finite-sample regime (such as small type I and type II error). Instead, their validity stems from either restrictive parametric assumptions or asymptotic properties that hold only in the limit as the number of samples tends to infinity. In the absence of such assumptions, independence testing is notoriously expensive: the minimax sample complexity scales polynomially with the support size ( 13 ; 30 ) . This high lower bound presents a formidable challenge for sample-efficient inference. To move beyond these worst-case limitations, a emerging line of work suggests that the analyst need not operate in a vacuum. In many modern data science contexts, one often possesses auxiliary information: public datasets gathered from disparate institutions, or a distribution originating from historical data, a generative model, or domain-specific heuristics. While such information may be abundant, it often lacks formal quality guarantees. A natural question is to determine if one can leverage such untrustworthy predictive information in a rigorous manner—designing tests that remain mathematically sound (and robust) when the prediction is poor, yet achieve significantly improved sample efficiency when the prediction is accurate. Recently, the framework of augmented algorithms has been proposed to bridge this gap, incorporating auxiliary information into classical statistical problems ( 23 ; 21 ; 40 ; 31 ; 8 ) and beyond ( 3 ) . This paradigm has shown great promise in distribution testing tasks such as uniformity testing, identity testing (goodness of fit), and closeness testing (equivalence testing) ( 8 ; 5 ) . In the augmented testing framework, the tester receives both samples from p , the true underlying data distribution, and a predicted distribution \hat{p} . The tester is required to be robust , maintaining worst-case validity regardless of \hat{p} , while simultaneously exploiting accurate predictions to surpass classical minimax lower bounds. In this work, we bring the framework of augmented distribution testing to the problem of independence testing over a discrete support. Our main contributions are as follows: {i)} We develop an independence tester for a bivariate distribution with finite sample complexity and worst-case error guarantees. This tester leverages a predicted distribution and adaptively reduces the sample complexity depending on the quality of the prediction without hindering the accuracy of the test. {ii)} We generalize this result to the high-dimensional setting, testing the independence of multiple random variables. {iii)} We provide matching lower bounds which indicate that our testers achieve the optimal sample complexity. 1.1 Problem Statement We adopt the framework of property testing of distributions ( 34 ) . In this setting, given sample access to a distribution p , a tester, with high probability, must output accept accept if p belongs to a property \mathcal{P} (viewed as a set of distributions) and reject if p is \epsilon -far in total variation distance from every distribution in \mathcal{P} . Here, we consider \mathcal{P} to be the property of independence —specifically, the set of all product distributions over a desired factorization of the domain. In the augmented setting ( 8 ) , in addition to sample access to the distribution p , we are provided with a predicted distribution \hat{p} and a suggested error bound \alpha representing the purported accuracy of \hat{p} . We assume full knowledge of \hat{p} (i.e., its probability mass function is known). In this framework, an augmented independence tester has a third option beyond outputting accept or reject : it may choose not to answer the test and instead output inaccurate information if the actual quality of the prediction is worse than the suggested error \alpha . However, the tester is required to provide an answer whenever the prediction is sufficiently accurate (i.e., when the suggested error \alpha is correct). Crucially, the tester cannot output an incorrect answer; if the tester does decide to answer the test, its output must be correct with high probability, regardless of the quality of the prediction. Formally, we define the desired augmented tester as follows: Definition 1.1 (Augmented Independence Tester) . Let \alpha\in[0,1],\epsilon\in(0,1),\delta\in(0,1) . For all i\in[d] , let n_{i}\geq 2 be an integer denoting the domain size. Let p and \hat{p} be distributions over \prod_{i=1}^{d}[n_{i}] , and let p_{1},\ldots,p_{d} denote the marginals of p . An algorithm \mathcal{A} which is given sample access to p and explicit access to \hat{p} , and outputs accept , reject , or inaccurate information , is an (\alpha,\epsilon,\delta) -augmented independence tester if for all p , it satisfies: • If p=p_{1}\times p_{2}\times\cdots\times p_{d} , \mathcal{A} outputs reject with probability at most \delta/2 . • If p is \epsilon -far from all product distributions, \mathcal{A} outputs accept with probability at most \delta/2 . • If \mathrm{d}_{\mathrm{TV}}\left(p,\hat{p}\right)\leq\alpha , \mathcal{A} outputs inaccurate information with probability at most \delta/2 . Remark 1 (Finding the prediction error.) . Note that in many practical settings, the prediction error \alpha may not be known a priori. However, the robustness of our augmented tester is naturally suited for identifying a desired error level adaptively. In particular, by employing the search meta-algorithm of 8 , we can search for the true error \alpha^{\star} by starting with the smallest \alpha and repeatedly invoking the augmented tester with increasing values of \alpha until the algorithm provides a definitive answer (i.e., it no longer outputs inaccurate information ). The expected sample complexity of this procedure is \tilde{O}(f(\alpha^{\star})) , where f(\alpha^{\star}) denotes the sample complexity of the tester when provided with the true error \alpha^{\star} of the prediction. For the remainder of this paper, we assume a fixed \alpha is provided and