Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The problem of testing the closeness of distributions asks to distinguish two cases for input distributions $P,Q$: the case that $P,Q$ are $\epsilon$-close in total variation distance and the case that they're $\eta$-far (for $\epsilon \leq \eta$). One setting that has received attention is the setting where the support of the input distributions is (a subset of) the $n$-dimensional hypercube. The most natural setting for a testing algorithm is to only allow black-box sample access to $P$ and $Q$. However, it is known that this requires the sample complexity to be exponential in $n$. In this submission, the authors present an algorithm, Pacoco, that has sample complexity $\tilde{O}(\sqrt{n} \log n / (\eta - 11.6 \epsilon) + n / \eta^2)$. The algorithm uses two types of conditional sampling queries (COND and DUAL): sample access with conditioning on a subset of the support, and querying the probability of elements of the support. The authors compare their algorithm to one of the most recent works, Barbarik2, which also uses conditional sampling (in a possibly weaker model, see questions below) which has exponential sampling complexity. The experiments show for artificially obtained product distributions and many real-world benchmarks that the asymptotic running time outweighs the constants in the running time for $\epsilon = 0.05$, $\eta = 0.9$ and error probability $\delta = 0.2$.
strengths_and_weaknesses: Strengths:

* The algorithm has nearly linear sampling complexity in $n$. Although the conditional sampling oracle model it uses seems strong, the sampling models were proposed in previous work and are not artificially tailored to the algorithm.
* In summary, the experiments support the claims on the sample complexity and provide some evidence that the constants are not too large.

Weaknesses:

* It seems that the various upper and lower bounds compared in this paper might be somewhat incompatible.
* Only a single set of constants $\epsilon, \eta, \delta$ is chosen for the experiments, and these values are not motivated.
* A running time comparison is lacking.
questions: My rating mainly mirrors that the model assumptions for the various upper and lower bounds from previous work and Pacoco that are discussed in this paper are very unclear to me. Could you elaborate on the exact conditional sampling model / requirements that are assumed by Barbarik2, Pacoco and the lower bounds mentioned? E.g.: Does Barbarik2 assume DUAL oracle access? Is the lower bound derived from [30] assuming DUAL oracle access? More generally, could you group the upper and lower bounds that are mentioned so that all bounds in one group assume exactly the same model?

Why is there a sudden, steep ascent of #samples for Pacoco on wSTS for #instances > 36?
limitations: -
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper is concerned with probabilistically validating if samples are close to high-dimensional distributions.  The model, experiments, implementation, and empirical comparisons are all in the model of Chakraborty-Meel (AAAI19,NeurIPS20).  The framework rejects if the TV distance is too large, and accepts if the multiplicative distance is sufficiently small.  This paper focuses on distributions on n-dimensional hypercubes.  

It leverages several oracles called COND, PCOND, and DUAL which allow the sampler to access about the true distribution other than point-wise probabilities.  These have been used elsewhere in the community to show improved speed-ups, but the paper does not specifically discuss how one could in practice implement these primitives efficiently, although it seems they have.  

For this problem setting, the previous approach required a number of samples exponential the dimension, while the new algorithm requires samples linear in the dimension.  This is accompanied by formal guarantees and proofs.  The empirical results show the implementation's number of samples for a wide array of problems, and the new approach works significantly better.  


strengths_and_weaknesses: Strengths:
  - formal proof guarantees, with exponential speed-up
  - empirical evidence of speed-up when implemented

Weaknesses:
 -What seems missing however, is a measurement of how well the methods actually perform for a fixed amount of time, or the wall-clock runtime. I understand the number of samples is a key constraint, but the two methods compared may require other auxiliary data structures or apply other oracles which may take more or less time.  Moreover, it could be the theoretical bounds on the previous method are not tight, and it actually performs very accurately with many fewer samples.  
  That is, who is testing the testers?  
An evaluation of this of some form would have increased my score for the paper.  
questions: N/A
limitations: No concerns here.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The present work essentially studies tolerant closeness testing of distributions over {1,-1}^n under the assumption that one not only has sample access but also the ability to 1) evaluate the probability mass at any point in the domain ("DUAL access"), and 2) the ability to sample from the distribution conditioned on any subset of size two of the domain ("PCOND access").

Following Meel-Pote-Chakraborty '20, this paper considers a slightly nonstandard notion of tolerant testing where one should whp accept when the two distributions p, q are "multiplicatively close" in the sense that their pdfs are within a factor of $1 \pm \epsilon$ pointwise, and reject when they are $\eta$-far in TV, for $\epsilon$ at most a small multiple of $\eta$.

They give an algorithm with query complexity scaling like $n/\eta^2 + \sqrt{n} / \eta^4$, up to polylog factors. Notably, this avoids the exponential scaling that one would get from traditional closeness testers that only get iid sample access. They also evaluate their algorithm on synthetic and real-world benchmarks and show that their algorithm outperforms a previous baseline, "Barbarik2", which in the worst case has query complexity scaling exponentially in $n$.
strengths_and_weaknesses: My main concern is that even with just DUAL and sample access, Canonne and Rubinfeld '14 already gave a simple and optimal tester for this problem. They consider the standard setting of tolerant closeness testing, where we want to distinguish whether $p$ and $q$ are $\epsilon_1$-close in TV or $\epsilon_2$-far in TV. By Corollary 2 in that work (see also Theorem 4.2.10 from Canonne's survey), they achieve the optimal query complexity of $1 / (\epsilon_2 - \epsilon_1)^2$ in this setting,. The point is that it is easy to come up with an unbiased estimator of the TV between p and q using DUAL and sample access (see (2) in that work for the special case of uniformity testing, which can be adapted easily to closeness testing).

In terms of the parameters in this submission, we would take $\epsilon_2 = \eta$ and $\epsilon_1 = \epsilon/2$. Then if $p,q$ are $\epsilon$-multiplicatively-close, then they are $\epsilon_1 = \epsilon/2$-TV-close, in which case the Canonne-Rubinfeld tester would accept, and if $p,q$ are $\eta$-far, then the tester would reject. Notably, their query complexity is $n$-independent, whereas the submission still has some linear dependence on $n$, and furthermore they do not need a PCOND sampler.

This might just be a big misunderstanding on my part, and if so I'd be happy to see clarification on this point in the rebuttal. In terms of positives, I like the practical motivations with which the submission frames the question of tolerant closeness testing, and the proposed algorithm is a clear improvement over Barbarik2 both theoretically and empirically.
questions: Questions:
- On P. 3 the paper mentions weighted d-DNNFs as yielding one example where DUAL oracle access is possible and says that these are used in the experimental evaluations, but I don't see any subsequent mention of these.
- Relatedly, in the experiments, how did you simulate PCOND and DUAL access?
- Strictly speaking, the guarantees of Barbarik2 and Pacoco are incomparable because the former only assumes conditional sampling access and not DUAL access, right?

Minor comments:
- P. 1 Line 33: "can be take" -> "can take"
- P. 1: While it's formally defined on P. 3, would be helpful to be more specific on P. 1 about what is meant by getting access to the target distribution, because the linear dependence on n is clearly good to be true if one only has sample access.
- P. 4 Line 125: isn't the DUAL oracle being used for both P and Q, not just for P?
- P. 4 Line 133: Line9 -> Line 9
- Would be helpful to state explicitly in Theorem 1 that you are given DUAL and COND access to both distributions.
limitations: The authors have adequately addressed the limitations, and I don't see any potential negative societal impact from this work.
review_title: null

Meta-review: metareview: This submission studies (a somewhat non-standard version of) tolerant closeness testing of distributions over the n-dimensional hypercube. Instead of only iid samples, it is assumed that the tester is able to efficiently evaluate the probability mass at any point in the domain and to sample from the distribution conditioned on any subset of size two of the domain. The main result is
an algorithm with query complexity scaling near-linearly in the dimension. Using only iid samples, one would need exponential dependence on dimension. The algorithm is evaluated on synthetic and real-world datasets. It is experimentally shown that their algorithm outperforms a previous baseline, which in the worst case has complexity scaling exponentially in the dimension. Overall, this is an interesting work that appears to meet the bar for acceptance.
confidence: Certain
Decision: Accept