Replicable Distribution Testing

Thanks for the detailed response. We are encouraged by the positive comments about our tight sample complexity bounds for fundamental problems and the novelty of the random walk argument. In what follows we will address the concerns of the reviewer regarding the significance of our conceptual contribution and questions regarding related proofs.

“doesn’t offer much new conceptually”

While the closeness testing algorithm follows the general paradigm in replicable algorithm design of comparing a randomized threshold to a strongly concentrated test statistic, our independence tester is significantly more involved as known test statistics do not satisfy the required concentration bounds. Furthermore, our main technical contribution is the first unconditional lower bounds for replicable distribution testing (removing the previous work’s assumption that the given algorithm is symmetric and proving a new new-optimal lower bound for closeness testing). Our random walk argument to show that any algorithm’s output under a given family of distributions is well concentrated is novel in this context, specifically does not appear in prior work within this field.

“lower bound framework … replicable independence testing”

We believe that our lower bound framework likely yields non-trivial (and quite possibly optimal) lower bounds for independence testing. However, the hard instance for independence testing is much more complicated than those for uniformity and closeness. Thus, the computation of mutual information (to show similar families cannot be distinguished) and the analysis of the eigenvalues of the random walk (to show that the algorithm output is well concentrated within any given family) would be significantly more challenging. We believe that this is certainly an interesting direction for future research.

Thanks for the detailed response. We are encouraged by the positive comments about our tight sample complexity bounds for fundamental problems and the novelty of the random walk argument. In what follows we will address the concerns of the reviewer regarding the significance of our conceptual contribution and questions regarding related proofs.

“similar to [27]”

While the closeness testing algorithm follows the general paradigm in replicable algorithm design of comparing a randomized threshold to a strongly concentrated test statistic, our independence tester is significantly more involved as known test statistics do not satisfy the required concentration bounds. Furthermore, our main technical contribution is the first unconditional lower bounds for replicable distribution testing (removing the previous work’s assumption that the given algorithm is symmetric and proving a new new-optimal lower bound for closeness testing). Our random walk argument to show that any algorithm’s output under a given family of distributions is well concentrated is novel in this context, specifically does not appear in prior work within this field.

Connections to Tolerant Testing

While tolerant testers do imply replicable testers, our algorithms are significantly more sample efficient than any tester obtained in this way (see also discussion in [27]). For example, a natural approach to a replicable test is the following: sample a random threshold r between 0 and eps, and run a tolerant tester with thresholds r - \rho \eps, r + \rho \eps. Even for constant tolerance, the sample complexity is barely sub-linear in the domain size n. Thus, even for constant \rho, and \eps the sample complexity of a replicable tester will be barely sublinear in n. In contrast, all our algorithms have strongly sub-linear dependency on the domain size parameter.

Connections to Private Testing

While m-sample private testers give rise to m^2-sample replicable testers [12] the sample complexity is suboptimal by a polynomial factor (as discussed in line 52), and in fact linear in n. We do mention that our algorithm for independence testing is inspired by the randomized flattening technique that has been leveraged for designing private independence testing algorithms (see line 173).

On the lower bound side, while private testing lower bounds imply replicable testing lower bounds [12], they will not give any non-trivial lower bounds (beyond standard lower bounds for uniformity testing). This is due to the fact that the known equivalence [12] will only give lower bounds for constant replicability \rho. (In particular, they show a constant replicability algorithm already implies a private algorithm).

Although the current connection is not strong enough to obtain sample-optimal bounds, the connection between replicable and differentially private testing remains an interesting one, and it is possible that a stronger quantitative relationship than what was proven in [12] would allow us to obtain tight bounds.

Thanks for the detailed response. We are encouraged by the positive comments about our tight sample complexity bounds for fundamental problems and the novelty of the random walk argument.

Thanks for the detailed response. We are encouraged by the positive comments about our tight sample complexity bounds for fundamental problems and the novelty of the random walk argument. In what follows we will address the concerns of the reviewer regarding the significance of our conceptual contribution and questions regarding related proofs.

Mostly an improvement of existing arguments and algorithms using known techniques

While the closeness testing algorithm follows the general paradigm in replicable algorithm design of comparing a randomized threshold to a strongly concentrated test statistic, our independence tester is significantly more involved as known test statistics do not satisfy the required concentration bounds. Furthermore, our main technical contribution is the first unconditional lower bounds for replicable distribution testing (removing the previous work’s assumption that the given algorithm is symmetric and proving a new new-optimal lower bound for closeness testing). Our random walk argument to show that any algorithm’s output under a given family of distributions is well concentrated is novel in this context, specifically does not appear in prior work within this field.

“can’t distinguish things… continuously change”

While our lower bound relies on the general framework that similar distributions cannot be distinguished (also observed e.g. for mean estimation [33, 34]), the hard instances for distribution testing consist of similar families of distributions (\mathcal{M}_{\xi} in the text) instead of single distributions. A barrier from previous work (which we resolve) is to show that the algorithm behaves similarly among all distributions in a particular family.

Connections to List Replicability (Randomness and Sample Complexity)

Finally, list replicability does not seem to have any immediate implications for distribution testing as there is a 0-sample algorithm that is replicable with list size 2 (output both {0, 1}).