
Abstract
Justin Chen
Title: On the Structure of Replicable Hypothesis Testers
Abstract: We study replicable algorithms for hypothesis testing as defined by Impagliazzo, Lei, Pitassi, and Sorell [STOC’22]. We develop general tools to prove upper and lower bounds on the sample complexity of replicable testers, improving upon and unifying existing results.
For lower bounds, our main contribution is a description of a canonical replicable tester, which performs as well as any other algorithm while satisfying certain structural properties. By reasoning about sample complexity of such a canonical tester, we show improved lower bounds for uniformity, identity, and closeness testing.
For upper bounds, we systematize and improve a common strategy for replicable algorithm design based on test statistics with known expectation and bounded variance. Our general estimators allow testers which have been extensively analyzed in the non-replicable setting to be made replicable with minimal overhead. As direct applications of our framework combined with existing non-replicable testers, we obtain constant-factor optimal bounds for coin testing and closeness testing. We also give state-of-the-art bounds for replicable Gaussian mean testing and hypothesis selection.
This is joint work with Anders Aamand, Maryam Aliakbarpour, Shyam Narayanan, and Sandeep Silwal.