Replicable Uniformity Testing

We thank the reviewer for their thoughtful comments! In the proof sketch we have focused on the sub-linear regime ($m \leq n$). The dependence $1/(\varepsilon^{2} \rho^{2})$ is incurred to handle the super-learning regime ($m \geq n/\varepsilon^2$). We redirect the reviewer to the proof of Lemma 3.2 (Appendix A.1) for the analysis of this case. We will also add this dependence to the discussion in the main body.

Our approach incurs a $\log (1/\delta)$ overhead in the sample complexity. In particular, for arbitrary error parameter $\delta$, we may replace $m_0 \gets \log (1/\rho)$ with $m_0 \gets \log(1/\min(\rho, \delta)) = \log(1/\delta)$ (assuming $\delta \leq \rho$). This guarantees that in the completeness and soundness regimes, the test statistic is sufficiently concentrated such that the random threshold will lie on the correct side of the empirical test statistic. Using our approach, this $\log(1/\delta)$ approach seems necessary, however, we do not know if this is tight. We hope to investigate in future work whether this dependence is necessary in general, or if better sample complexity (say $\sqrt{\log(1/\delta)}$) is possible.

We thank the reviewer for the encouraging comments. Below we provide some more succinct explanation of this surprising linear dependency on $\rho$. First we note that this sample complexity is perhaps not so surprising if one focuses on designing testers for the specific hard instance we constructed in our lower bound section. In particular, for constant $\varepsilon$, the i-th element of the distribution has probability mass of the form $( \pm \xi) / n$, where $\xi$ will be some randomly sampled value bounded from above by some constant $\varepsilon$.

In that case, it amounts to estimating the squared $\ell_2$ norm of the distribution up to accuracy $\rho / n$ (which is simply $\rho$ times the usual expectation gap for uniformity testing). For this particular instance, since there are no elements whose mass is heavier than $2 / n$, the variance of the usual collision statistics is at most of order $m^2 / n$. Solving $m^2 / n < \sqrt{\rho / n}$ then gives the sample complexity bound of $m = \Theta( \sqrt{n} / \rho )$. In short, at least in this case, the reason we have this surprising linear dependency on $\rho$ is conceptually similar to the birthday paradox phenomenon (where we expect an $n$ dependency for uniformity testing but $\sqrt{n}$ turns out to be sufficient).

The main technical challenge is to analyze the case when there are heavy elements. While the presence of heavy elements makes collision-based test statistics sub-optimal (as discussed in the technical overview), it turns out that their presence quickly pushes the expected value of the TV test statistics to the soundness regime, leading to replicable rejection.

We thank the reviewer for their comments. While we have reviewed the extensive line of work on uniformity testing to the best of our abilities, we admit that our survey might not be complete. Thus, we would greatly appreciate any pointers to missing citations.

Indeed, there is an extensive literature on uniformity testing, with a variety of algorithmic techniques. However, none of these algorithms explicitly guarantee replicability when the input distribution is neither uniform nor far from uniform. While there is a simple transformation to obtain replicable algorithms (by treating the outcome of a non-replicable algorithm as a coin flip), any such reduction introduces quadratic overhead in the replicability parameter. In particular, these algorithms require $\sqrt{n} \rho^{-2} \varepsilon^{-2}$ samples.

Our key technical contribution is a replicable algorithm that achieves sample complexity $\sqrt{n} \rho^{-1} \varepsilon^{-2}$ in the worst case, and is thus the first algorithm (as far as we know for any statistical task, not just uniformity testing) that has linear overhead in the replicability parameter. While the algorithm is a simple modification of known algorithms, our primary technical contributions are new analyses in the concentration of the test statistic. Furthermore, as discussed in the technical overview, it is not immediately clear which of the many uniformity algorithms can be made replicable with linear overhead. We find one such test statistic that admits a replicable variant, and introduce new analysis to show that this is the case.

While our lower bound holds only against symmetric algorithms, we remark that all known uniformity testers in prior works are indeed symmetric. Moreover, in our opinion, symmetric algorithms are natural for the problem of uniformity testing as the property itself is invariant under domain relabeling. It is unclear whether there is any natural/intuitive way to exploit asymmetry in replicable algorithm design. We believe the fact that our lower bound holds only against symmetric algorithms is more of a technical issue than a conceptual gap, and we leave it as an important future direction to develop a fully unconditional lower bound.