On the Structure of Replicable Hypothesis Testers

A hypothesis testing algorithm is replicable if, when run on two different samples from the same distribution, it produces the same output with high probability. This notion, defined by by Impagliazzo, Lei, Pitassi, and Sorell [STOC'22], can increase trust in testing procedures and is deeply related to algorithmic stability, generalization, and privacy. We build general tools to prove lower and upper bounds on the sample complexity of replicable testers, unifying and quantitatively improving upon existing results.

We identify a set of canonical properties, and prove that any replicable testing algorithm can be modified to satisfy these properties without worsening accuracy or sample complexity. A canonical replicable algorithm computes a deterministic function of its input (i.e., a test statistic) and thresholds against a uniformly random value in [0, 1]. It is invariant to the order in which the samples are received, and, if the testing problem is "symmetric," then the algorithm is also invariant to the labeling of the domain elements, resolving an open question by Liu and Ye [NeurIPS'24]. We prove new lower bounds for uniformity, identity, and closeness testing by reducing to the case where the replicable algorithm satisfies these canonical properties.

We systematize and improve upon a common strategy for replicable algorithm design based on test statistics with known expectation and bounded variance. Our framework 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 analyses of non-replicable testers, we obtain constant-factor optimal bounds for coin testing and closeness testing and get replicability for free for uniformity testing in a large parameter regime. As replicable coin testing can be used as a black-box to turn any tester into a replicable tester, our results directly imply improved replicable sampling bounds for myriad applications beyond the ones specifically studied in this paper.

We also give a state-of-the-art algorithm for replicable Gaussian mean testing. We present a ρreplicable algorithm for testing whether samples come from N (0, I) or from N (µ, I) where ∥µ∥2 ≥ α. Our algorithm improves over the previous best sample complexity of Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sivakumar, and Sorrell [STOC'23] and runs in polynomial time.