Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions

Mar 4, 2026·
Maryam Aliakbarpour
,
Alireza Azizi
Ria Stevens
Ria Stevens
· 0 min read
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 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.
Publication
To appear at the Thirty-Ninth Annual Conference on Learning Theory (COLT 2025)
publications
Independence Testing Augmented Algorithms
Authors
Maryam Aliakbarpour
Authors
Alireza Azizi
Ria Stevens
Authors
Ria Stevens (she/her)
PhD Candidate

I am a fourth-year Computer Science PhD student at Rice University, advised by Dr. Maryam Aliakbarpour and Dr. Tasos Kyrillidis. My research interests lie in theoretical computer science and statistical learning theory. I am particularly interested in problems involving differential privacy. For the winter 2026 semester, I am a visiting graduate student in the Federated and Collaborative Learning program at the Simons Institute in UC Berkeley. I am also passionate about teaching and recently developed and taught a discrete math course for incoming freshmen in Rice’s CS-RESP program.

Before coming to Rice, I completed my Bachelor’s in Computer Science and Statistics at McGill University, where I was fortunate to be advised by Drs. Elliot and Courtney Paquette.

Outside of my research, I enjoy playing sports, travelling and discovering new coffee shops. I play ultimate frisbee for Torque, Rice’s women’s club team, and I previously played varsity ice hockey for the McGill Martlets.