On Scalable Testing of Samplers 
Authors: Yash Pote
Kuldeep S. Meel
Venue: NeurIPS 2022 Accept (2022)
Keywords: Sampling
Distribution Testing
Constraints

Abstract: In this paper we study the problem of testing of constrained samplers over high-dimensional distributions with $(\varepsilon,\eta,\delta)$ guarantees. Samplers are increasingly used in a wide range of safety-critical ML applications, and hence the testing problem has gained importance. For $n$-dimensional distributions, the existing state-of-the-art algorithm, $\mathsf{Barbarik2}$, has a worst case query complexity of exponential in $n$ and hence is not ideal for use in practice. Our primary contribution is an exponentially faster algorithm, $\mathsf{Barbarik3}$, that has a query complexity linear in $n$ and hence can easily scale to larger instances. We demonstrate our claim by implementing our algorithm and then comparing it against $\mathsf{Barbarik2}$. Our experiments on the samplers $\mathsf{wUnigen3}$ and $\mathsf{wSTS}$, find that $\mathsf{Barbarik3}$ requires $10\times$ fewer samples for $\mathsf{wUnigen3}$ and $450\times$ fewer samples for $\mathsf{wSTS}$ as compared to $\mathsf{Barbarik2}$.

On Scalable Testing of Samplers *i
Yash Pote
Kuldeep S. Meel
School of Computing, National University of Singapore
Abstract
In this paper we study the problem of testing of constrained samplers over high- dimensional distributions with (E, .7.6)) guarantees. Samplers are increasingly used in a wide range of safety-critical ML applications, and hence the testing problem has gained importance. For n-dimensional distributions, the existing state-of-the-art algorithm, Barbarik2, has a worst case query complexity of exponential in and hence not ideal for use in practice. Our primary contribution is an exponentially faster algorithm that has query complexity linear in and hence can easily scale to larger instances. We demonstrate our claim by implementing our algorithm and then comparing it against Barbarik2. Our experiments on the samplers wUnigen3 and wSTS, find that Barbarik3 requires 10x fewer samples for wUnigen3 and x50x fewer samples for wSTS as compared to Barbarik2.
Introduction
The constrained sampling problem is to draw samples from high-dimensional distributions over constrained spaces. A constrained sampler Q(ye, u) takes in of constraints yo {0. 1) "M - {0, 1) and a weight function w (0, 1)" - Ry and returns a sample a E E with probability propor- tional to w(a). Constrained sampling is core primitive of many statistical inference methods used in ML, such as Sequential Monte Carlo Markov Chain Monte Carlo(MCMM) 9] Simulated Annealing 44. and Variational Inference 24 Sampling from real-world distributions is often compu- tationally intractable, and hence, in practice, samplers are heuristical and lack theoretical guarantees. For such samplers, it is an important problem determine whether the sampled distribution is close to the desired distribution, and this problem is known as testing of samplers. The problem was formalised in [1] (7) follows: Given access to a target distribution P. sampler Q(p,, w), and three parameters (s, 17, 8), with probability at least 1 - 6, return (1) Accept if (P, Q(p, w)) < or (2) Reject dry (P, Q(y,, w)) > 7). Here dry the total variation distance, d the multiplicative distance, and 77, and 5 are parameters for closeness, farness and confidence respectively. Access to distribution P is via the DUAL oracle, and access Q is via the PCOND and SAMP oracles (defined in Section 2.1
There is substantial interest in the testing problem due the increasing use of ML systems in real-world applications where safety is essential, such as medicine (2]. transportation [8] 25), and warfare (28 For the ML systems that incorporate samplers, the typical testing approach has been to show the convergence of the sampler with the target distribution via empirical tests that rely on heuristics and do not provide any guarantees 199 22 34 In a recent work [27. novel framework.
called Barbarik2, was proposed that could test given sampler while providing (s, d)) guarantees, queries, where (Pl = max
using ò ( vin 3233
P(a1) for P((z) > 0. Since the filt(P)
(0,1) P(az)
* "The accompanying tool, available open source, can be found at httpss//gitubb.co/mmcegggggg
1 The authors decided forgo the old convention of alphabetical ordering of authors in favor of randomized ordering, denoted by ( The publicly verifiable record of the randomization available at hhtpps: //wp/ /www aeaweb. wwwooog/oooo pwgg/jurnaasspolll For citations, the authors request that the citation guidelines by AEA for random author ordering be followed,
raaeeeranoo--- author - order/ /earcch with confirmation code: LcrlccP-xv14
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

can take arbitrary values, we observe that the query complexity can be prohibitively large
On the
Va/ Ing(n)
other hand, the best known lower bound for the problem, derived from [30], is ? this work, we take step towards bridging this gap with our algorithm, Barbarik3, that has query
In 1y²
complexity of Ô Villog n art.
(1-11.6))7> 1/² representing an exponential improvement over the state of the
To be of any real value, testing tools must be able to scale to larger instances. In the case of constrained samplers, the only existing testing tool, Barbarik2, is not scalable owing to its query complexity. The lack of scalability is illustrated by the following fact: product distributions are the simplest possible constrained distributions, and given union of two n-dimensional product distributions, Barbarik2 requires more than 10t queries for n > 30. On the other hand, the query complexity of Barbarik3 scales linearly with the number of dimensions, thus making it more appropriate for practical use.
We implement Barbarik3 and compare it against Barbarik2 to determine their relative performance. In our experiments, we consider two sets of problems, (1) constrained sampling benchmarks, (2) scalable benchmarks and two constrained samplers wSTS and wUnigen3. We found that to complete the test Barbarik3 required at least 450x fewer samples from wSTS and 10x fewer samples from wUnigen3 as compared to Barbarik2. Moreover, Barbarik3 terminates with a result on at least 3 more benchmarks than Barbarik2 in each experiment.
Our contributions can be summarized as follows:
For the problem of testing of samplers, we provide an exponential improvement in query complexity over the current state of the art test Barbarik2. Our test, Barbarik3, makes total of Ô
Vollog (116e
+ ///
queries, where Ô hides polylog factors of e, and 8.
2. We present an extensive empirical evaluation of Barbarik3 and contrast it with Barbarik2. The results indicate that Barbarik3 requires far fewer samples and terminates more benchmarks when compared to Barbarik2.
We define the notation and discuss related work in Section 2 We then present the main contribution of the paper, the test Barbarik3, and its proof of correctness in Section 3 We present our experimental findings in Section 4 and then conclude the paper and discuss some open problems in Section S Due to space constraints, we defer some proofs and the full experimental results to the supplementary Section A and B respectively.
2 Notation and preliminaries
Probability distributions In this paper we deal with samplers that sample from discrete probability distributions over nigh-dimensiioal spaces. We consider the sample space to be the n-dimensional Boolean hypercube {0, 13". A constrained sampler @ takes in a set of constraints yp : {0, 1)" > {0, 1) and a weight function w: {0, 13" n + R2o, and samples from the distribution @(p,, w) defined as w(o)//(p)) a E (1) where x(y)) = Eoeo 1(1) w(o). To improve readability, a (0)
O x)
we use Q to refer to the distribution Q(pp, w). For an element i, D(i) denotes it's probability in distribution D and i ~ D represents that is sampled from D. For any non-empty set S C (0. 1)", Dg is the distribution D conditioned on set S, and D(S) the probability of D i.e. D(S) = Eies D(i).
The total variation (TV) distance of two probability distributions Dj and D2 is defined as:
(D (D1,D2) D2) = ii (0.1)) (i) (2). For S C {0, 13", , we define drv(s) (D1, D2) = Eies (i) (i)). The multiplicative distance of D3 from D, is defined as: dac (D,, Dz) maxie (0 (D2(i)/Di - 1/. The two notions of distance obey the identity: 2drv (D1, D2) S de D2).
In the rest of the paper, E(y] represents the expectation of random variable e and represents the set 21,..... k).
simple modification reveals that in terms of n, E, the bound is
4t

---

Tools used in the analysis
Proposition 1 (Hoeffding). For independent 0-1 random variables X,, X Σ X, and Pr(X- - EX > I exp (-2fk) and Pr(EX - X > t) S exp (-2t²
Proposition 2 (Chebyshev). Given bounded X, have Pr(IX E[X]I B[X]) xxp
Proposition 3. Given distributions D1 and D2 supported on {0, 1)", and a set S S {0, 1)",
( 2div(s)
Di((i)22(1)
4
iES
The proof can be found in the Appendix A.1
L
If we are given samples {si, 8n3 from distribution over [k], then the empirical distribution
D is defined be D(i)= 1 n
Σ (s==))
Proposition (See [1] for a simple proof). Suppose 'D is distribution over [k],, and D is constructed
using max 7 1/2
2m(2/6)
samples D. Then drv (D, D) S 1 with probability least 1 8.
2.1 Testing with the help of oracles
In distribution testing, we are given samples from an unknown distribution P over a large support {0, 13", and the task is test whether P satisfies some property of interest. One of the important properties we care about is whether P is close to another distribution Q, and this subfield of testing is known as closeness testing. was shown by Valiant and Batu al. that the ability to draw samples from P and Q is not powerful enough, of probabilistic guarantee for closeness testing. Since n is usually large, it was desirable to find tests that could solve the closeness testing problem using polynomially many samples in n.
least 22222//3 samples are required to provide any sort
Motivated by the above requirement, Canonne al. and [hhkrrborrty et al, introduced the conditional sampling oracle (COND), that is more powerful way to access distributions. A COND oracle for distribution D over {0, 1 takes as input a set C {0, 1]"" with D(S) > 0, and returns a sample i E S with probability D(i)/ D(i)/D(S). (S)). It has been shown that the of the COND oracle, and its variants, drastically reduces the sample complexity of many tasks in distribution testing 2 12 15! (see 110 for extensive survey). In this paper, we consider the pair-conditioning (PCOND) oracle, which is a special case of the COND oracle with the restriction that |S| = 2 i.e., the size of the conditioning set has to be two. To engineer practical PCOND oracle access into constrained samplers, we use the chain formula construction introduced in 14].
21
6. 26.2677 7 17
13 30
With the same goal of designing tests with polynomial sample complexity, a different kind of oracle, known as the DUAL oracle, was proposed by Canonne et al.. The DUAL oracle allows one to sample from a given distribution and also query the distribution for the probability of arbitrary elements of the support. Tractable DUAL oracle access is supported by a number of distribution representations, such as the fragments of probabilistic circuits (PC) that support the EVI query [18.. In our experimental evaluation, we use distributions from one such fragment: weighted d- d-DNNFs. Weighted d-DNNFs class of arithmetic circuits with properties that enable DUAL oracle access in time linear in the size of the circuit [6 23
Barbarik3: an algorithm for testing samplers
We start by providing brief overview of our testing algorithm before providing the full analysis.
3.1 Algorithm outline
The pseudocode of Barbarik3 is given in Algorithm I We adapt the definition of bucketing of distributions from (30 for use in our analysis.
Definition 1. For a given i E Noo, the bucketing (0, 13"d with respect to P is defined as follows:
For 1 < k let St {b 2- < P(b) < 2 2-+11 and let So = {0, 13"h \ &Uien S. Given
3

---

Algorithm 1 Barbarik3(P, 2,,,6,0
1: k
[log2 (100/1))
2: for = 1 to to k do
3: 8 (b:
(()) - 2
4: Su = (0, Ueera) S
5: By is the distribution over [c] U (0) where we sample ~ Bp if we sample j P and j E S
6: Be the distribution over [k] {0) where we sample Be if we sample j and E S
7: 6 <- n/20
8: d 4- OutBucket( Bp, ko,
9: if d e/2 + 0 then
10: Return Reject
11: 62 d 0
12: Return InBucket(P. s,,,,,2,
any distribution D over {0,1}", define a distribution BD over [R] U {0} as: for 0 k. (D D(S)). We call BD the bucket distribution of DD and S, the 7t bucket.
Barbarik3 takes as input two distributions P and Q defined over the support {0, 1)"h along with the parameters for closeness(E), farness(1). and confidence(0).. On Line Barbarik3 computes the value of k using 1) and the number of dimensions n. Then, using DUAL access to P, and SAMP access to Q, Barbarik3 creates bucket distributions Bp and Bg as Defn. in the following way: To sample from Bp, Barbarik3 first draws sample j P. then using the DUAL oracle, determines the value of P(j). Then, j lies in the 2th bucket i.e., 2- P(() S 2-++1, the algorithm takes sample as the sample from Bp. Similarly, to draw a sample from Be. Barbarik3 draws sample j ~ Q and then, using the DUAL oracle to find P(j), finds such that lies in the 7th bucket, and then uses as the sample.
Barbarik3 then calls two subroutines, OutBucket (Section 3.4p and InBucket (Section 3.3 The
OutBucket subroutine returns an 6-multiplicative estimate of the TV distance between Bp and Be. the two bucket distributions of and Q, with an error of at most 8/2. If found on Line that
the estimate is greater than e/2 2 + 0, we know that drv (P, Q) > e/2 and also that dxx (P, Q E, and hence the algorithm returns Reject. Otherwise, the algorithm calls the InBucket subroutine.
Now suppose that drv (P, Q) 2 7/. Then, for 22 (Line I1). it is either the case that drv (Br, Bo) > 22 else drv(Bp, BB) I E2. In the former case, the algorithm returns Reject on Line I0 and in the latter case the InBucket subroutine returns Reject. In both cases, the failure probability is at most 8/2. Thus Barbarik3 returns Reject given far input distributions with probability least 1 8.
We will now prove the following theorem:
Theorem Barbarik3(P, 2,1,e, () takes in distributions and Q defined over 1), and parameters (0, 1J. E [0. n/116) and 8 E (0, 1/2). Barbarik3 has DUAL access to P, and PCOND+SAMP access to Q. With probability at least Barbarik3 returns
Accept if doo (P, Q) S Reject if drv (P, Q) >n
vn (ng) + )) where Ô hides polylog factors of e, and 8. (1.66)))))
Barbarik3 has query complexity
3.2 Lower bound
The lower bound comes from the paper of Narayanan (30] where it appears in Theorem 1.6. Phrased in the jargon of our paper, the lower bound states that distinguishing between drv Q) > r and doe (P, Q) = 0 requires 5 /n log(n)/1²² samples. Note that the lower bound is shown on special case (8 0) of our problem. Hence the lower bound applies to our problem as well. Furthermore, the lower bound is shown for the case where distribution P provides full access, i.e., the algorithm can make arbitrary queries to P. This is stronger access model than DUAL. Since the lower bound for stronger access model, it extends to our problem well.

---

3.3 The InBucket subroutine
In this section, we present the InBucket subroutine, whose behavior stated in the following lemma.
Lemma InBucket(P, E, 8) takes as imput nwo distributions P, an integer and parameters E,E,, 6. If dx, Q) < E, InBucket returns Accept. If dry Q) 2 n and drv(Bp, B2) < 82, then InBucket returns Reject. InBucket errs with probability most 8
Algorithm 2 InBucket 22,
E1 (0.997 3.258z - 1.05 + 2z/(1
2: m [Vk/(0.99n 3.2562 E1)
3: a < (E1 + 2e/(1 =))
In(4/8)
4: t [m010/(10 (10
5: for iterations do
6: Pp <- m samples from P
7: ViEnn] p T n.
D. Sy defined in Defn.
8: Te
samples from Q
9:
ViE f ns,
2
10:
for all [k] s.t. [
I
0 do
11:
I
> p is an arbitrary sample from the set I
12:
D is an arbitrary sample from the set I
P(p)
13:
+ P(p)+P(()1++
1-
P(p)
14:
P(p)+
21n(4mt/0
15:
(h-1)²
16:
õ e Bias(Q, p. r.
17:
i S. (h + f then
18:
Return Reject
Return Accept
Algorithm 3 Bias g.
1: if and are identical then
2: Return 0.5
3: Tetp.a) samples from (p.e)
4: Return # of times p appears in ((p.)
InBucket makes extensive use the PCOND oracle access to Q via the Bias subroutine, which we describe in the following subsection.
The Bias subroutine The Bias subroutine takes in distribution Q, two elements and a positive integer Then, using the PCOND oracle, Bias draws samples from the conditional distribution ((rgg) and returns the number of times it sees p in the r samples. It can be seen that the returned
value is an empirical estimate Q(p) O (g)
Qip)
Let the estimate be Eyg. We use the Hoeffding bound in
Prop. I and the value of r from Line 15 of Alg.
(2) to show that:
((p) Pr Q(p) Q(g)
h -
8
((p)
8 4mt
pq
2
4mt
Pr
Ppppp
Q(p) Q(9) 2
<
Here / represents the number of iterations of the outer loop (Line D. and is the number of samples drawn from Bp and Bo. Together, there are at most mt pairs of samples that are passed to the Bias oracle. Since in each invocation of Bias, the probability of error is 6/4mt, using the union bound we find that the probability that all mı Bias calls return correctly at least - 6/4 and thus with probability at least 1 - 8/4, the empirical estimate Epg
- is closer than (h- 0) to 2
2(p)
5

---

Henceforth we assume:
2(p) 2(p) + 2(a)
h-6
$ 2
(I)
3.3.1 The Accept case
In this section we will provide an analysis of the case when da (P, 2) < e. We will now state a proposition required for the remaining proofs, the proof of which we relegate to Appendix A.4
Proposition 5. Let P, Q be distributions and let p P and Q Then,
1. If do (P, Q) then
(()) + + P(p) + (1+ 26 P((g)
P(p)
2. dfvv (P, en, then for ét, with probability least 2)
②(p)
P(p)
2()) + 2(1)
+ +()++110))PP)
From our assumption
i we know that for all invocations of Bias, with probability at least 5/4, (h f)/2. Using Prop. and using the value given on Line 13 we can
O(p)
Cgg
(p) O
that 26)++ Q h. From this
Q(p)
observe that for all invocations of Bias, Cpg (h f)/2
and the test does not return Reject in any iteration, hence eventually returning Accept. Thus, in the
case that dx (P, Q) < E, the InBucket subroutine returns Accept with probability at least 1 - 8
3.3.2 The Reject case
In this section we analyse the case when (Tv((,,)) Q) 2 and (trv(Br Be) 62 and we will show that the algorithm returns Reject with probability at least 1 8. For the purpose of the proof we will define set of bad buckets Bad S [k). Note that bucket {0} is not in Bad.
Definition 2. Bad ii E [k] drv (Ps,, Qs.) > A (p BB( E [5 1.2}
Suppose we have an indicator variable X,,, constructed as follows: draw m samples from P and Q, and if the 4h sample from p and the 4hh sample from Q both belong to some bucket E Bad, then X,,s else X,,s 0. Then.
Σ Bp(b))o(b)> (Br(Bad) + Bø(Bad) - -Bar (Br, Bo))² BEBad
E[X,,s]
4K
The inequality is by the application of Prop.
We analyse the expression for the expectation in the following lemma, the proof of which we relegate to Appendix[e A.2
Lemma 2.
13
Be(Bad) (B 2dTv Bp) 0.99m
E2
Using Lemma immediately derive the fact that E[X,, > (0.99n Le2 51) /K. Let X En.eei (m] Xr.s- Given m samples from P and Q Pr(X 2 1) is the probability that there is at least bucket in Bad that is sampled least once each in both sets of samples.
Lemma 3. Pr(X 1) 1/5
The proof can be found in Appendix A.3

---

Henceforth we will condition on the the event that X > 1. In such case, we know that for some k Bad, there is sample p ~ Ps. and sample q ~ 2,s, Then for such a pair of samples (p. q). and some a, Prop. 5 tells us that with probability at least (drv (P, Q) ox/22 we have
(p))
P(p)
2(p) + 2(1) P(p) + (1+
Using the assumption made in I we immediately have that Cpg
Q(1) + h-f But from
(pp)
Prop. we have that e(+++Q(g)
2(p)
and hence Epg < (h + 8)/2. Since drv (P, 2) 2 E1. we see that
if X 1, then with probability at least (51 a2/2, the iteration returns Reject.
Then, using Lemma we see that in every iteration, with probability at least (e1 / /10 InBucket returns Reject. There are / iterations, where t (line 4) chosen such that the overall probability of the test returning Reject is least 1 8/2.
3.4 The OutBucket subroutine
The OutBucket subroutine takes as input two distributions D1, D2 over + 1 elements and two parameters 9 and 8. Then with probability least 1 5, InBucket returns 6-multiplicative estimate for drv (D1, D2).
The OutBucket starts by drawing max 4(k+1) 8lm(4/8) samples from the two distributions Dj
and D2, and constructs the empirical distributions D1 and D2. Then from Prop. we know that with probability least 1 6, both drv (D1, s 0/2 and dry (D2, D2) $ 0/2. From the triangle inequality we have that,
dDi, D2) S dDv Di) + (D), + drv D2)
and also that,
drv S (D dTv D2) + dTv (Di, < + drv (Di, D2)
Thus with probability at least the returned estimate drv (Di, D2) satisfies |drv (Di, DD2) drv (D,, D2)1 < 0.
Query and runtime complexity The number of queries made by OutBucket to P and Q is where Ô hides polylog factors of e and 8. The number of queries required given by Ô n1 w)
by InBucket is given by mtr. Bounding the terms individually,
that Ô (--
yn
t Ö 1 and = Ô logn) (n)
1/² Thus mtr Ô vTilogg ) and hence the total query complexity
Ô vn log + 1/ 11.6ejm
4 Evaluation
To evaluate the performance Barbarik3 and test the quality of publicly available samplers, we implemented Barbarik3 in Python. Our evaluation took inspiration from the experiments presented in previous work 14 (27). and we used the same framework to evaluate our proposed algorithm. The role of target distribution P was played by WAPS (2] WAPS compiles the input Boolean formula into a representation that allows exact sampling and exact probability computation, thereby implementing the SAMP and EVAL oracles necded for our test.
For the role of sampler Q(p,,), w). we used the that-atf-the-art samplers wSTS and wUnigen3. wUnigen3 32) is hashing-based sampler that provides (c, 8) guarantees on the quality of the samples. wSTS 20 is sampler designed for sampling over challenging domains such as energy barriers and highly asymmetric spaces. wSTS generates samples much faster than wUnigen3, albeit
htngss/githbb.ccmm/neegggg////a

---

without any guarantees on the quality of the samples. To implement PCOND access, we use the Kernel construction from [4]. Kernel takes yp and two assignments 01, 22 and returns a function P on m variables, such that: (1) m > n, (2) yp and & are similar in structure, and (3) for (1) holds that (p) E (2) Here (eupp(() denotes the projection of on the variables of yp
For the closeness(s), (1) and confidence parameters,
choose the values 0.05, 0.9 and 0.2. This setting implies that for a given distribution P. and for a given sampler Q w), Barbarik3
returns (1) Accept if d (P, Q(p,, w)) 0.05, and (2) Reject if drv Q( x)) 0.9, with probability at least 0.8. Our empirical evaluation sought to answer the question: How does the performance of Barbarik3 compare with the state-of-the-art tester Barbarik2?
Our experiments were conducted on a high-performance compute cluster with Intel Xeon(R) E5- 2690v3 @ 2.60GHz CPU cores. We use single core with 4GB memory with timcout of 16 hours for each benchmark. We set a sample limit of 10s samples for our experiments due to our limited computational resources. The complete experimental data along with the running time of instances, is presented in the Appendix B
4.1 Setting A scalable benchmarks
Dataset Our dataset consists of the union of two n-dimensional product distributions, for n E (4, 7, 10,..., 1183. We have 39 problems in the dataset. We represent the union of two product
2k distributions as the constraint: (pa)) = A (038+1 V Vo,) A 1 (-034+1 V Vos), and the weight
function: w(o) = I1: 3 where σ; is the value of a at position i.
Results We observe that in the case of wSTS, Barbarik2 can handle only 12 instances within the sample limit of 10a On the other hand, Barbarik3 can handle all 39 instances using at the most 10t samples. In the case of wUnigen3, Barbarik2 solves 5 instances, and Barbarik3 can handle 17 instances.
Figure [ shows a cactus plot comparing the sample requirement of Barbarik3 and Barbarik2. The r-axis represents the number of benchmarks and y-axis represents the number of samples, a point (x. implies that the relevant tester took less than y number of samples to distinguish between (Pv ((p w)) 1) and d (P, ((v, x)) < E, for x many benchmarks. We display the set of benchmarks for which at least one of the two tools terminated within the sample limit of 10S. We want to highlight that the y-axis is in log-scale, thus showing the sample efficiency of Barbarik3 compared to Barbarik2. For every benchmark, we compute the ratio of the number of samples required by Barbarik2 to test sampler and the number of samples required by Barbarik3, The geometric mean of these ratios indicates the mean speedup. We find that the Barbarik3's speedup on wSTS is 451 x and on WUnige33 is 10x.
4.2 Setting B- real-life benchmarks
Dataset We experiment on 87 constraints drawn from a collection of publicly available benchmarks arising from sampling and counting taske5) We use distributions from the log-linear family. In a log- linear distribution, the probability of an element a E & (11 is given as: Pr[a] x exp (2 a,0,). where 0g E Rn We found that wUnigen3 was not able to sample from most of the benchmarks in the dataset within the given time limit, and hence we present the results only for wSTS.
Results We find that Barbarik3 terminated with a result on all 87 instances from the set of real-life benchmarks, while Barbarik2 could only terminate on 16. We present the results of our experiments in Table [ The first column indicates the benchmark's ' name, and the second column has the number of dimensions of the space the distribution is defined on. The third and fifth columns indicate the number of samples required by Barbarik2 and Barbarik3. The fourth and sixth columns report the output of Barbarik2 and Barbarik3.
httgs://eenndoooog///oo//////999
8

---

wSTS
10
# of samples (logscale)
Barbarik2
107
Barbarik3.
10
109
10a
0
5
10
15
20
25
30
35
38
wUnigen
10
# of samples (logscale)
107
10c
Barbarik2
105
Barbarik3
2
4
6
8
10
12
14
16
# of instances
Figure 1: Cactus plot: Barbarik3 vs. Barbarik2. We set the sample limit to 10 and our dataset consists of 39 benchmarks. The plot shows all the instances where at least of the tools terminated within the time limit of 16 hours and sample limit of 10
Table Runtime performance of Barbarik3. We experiment with 87 benchmarks, and out the 87 benchmarks we display 15 in the table and we display the full data in Appendix(B: [B] In the table 'A' represents Accept, 'R' represents Reject and "TO' represents that the tester either asked for more than 10Sh samples or did not terminate in the given time limit of 16 hours.
Barbarik2
Barbarik3
Benchmark
Dimensions
Result
of samples
Result
of samples
SetTest.sk 9 9_21
21
R
2817
R
58000
Pollard.sk 10
10
R
7606
R
36000
s444_3_2
24
R
848148
R
64000
s526a 2
24
R
848148
R
64000
s510_ $$10_15__ 15_7
25
R
12708989
R
66000
$27 new 7 4
7
A
23997012
R
30000
$298_15_1
17
R
38126967
R
50000
$420_3_2
34
TO
R
83000
x382_3_2
24
TO
R
64000
$641_3.2
54
TO
R 123000
111.sk_2_36
36
TO
R 87000
7.sk -450
50
TO
R 115000
56.sk_6_.3
38
TO
R 91000
s820a 15_
23
TO
R 62000
ProjectServiceess__122..
12_55
55
TO
R
125000

---

Conclusion
In this paper, we studied the problem of testing constrained samplers over high- digensiimnsional distribu- tions with (s. 17, 6) guarantees. For n-dimensional distributions, the existing state-of-the-art testing algorithm, Barbarik2, has worst-case query complexity that is exponential in n and hence is not ideal for use in practice. We provided an exponentially faster algorithm, Barbarik3, that has query complexity linear in n and hence can easily scale to larger instances. We implemented Barbarik3 and tested the samplers wSTS and wUnigen3 to determine their sample complexity in practice. The results demonstrate that Barbarik3 is significantly more sample efficient than Barbarik2, requiring x fewer samples when it tested wSTS and 10x fewer samples when it tested wUnigen3. Since there a vn gap between the upper bound provided by our work and the lower bound shown in [30], the problem of designing more sample efficient algorithm finding stronger lower bound, remains open.
Limitations For given farness parameter 7). Barbarik3 requires the value of the closeness parame- ter to lie in the interval [0, /1116)). In the case of Barbarik2, the previous state-of- offthhe-rt test, the permissible values of for given 7) lie in the interval [0, n/3). Thus, Barbarik3 supports testing with only a subset parameter values that Barbarik2 support.
Acknowledgments and Disclosure of Funding
We grateful to the anonymous reviewers of NeurlPS 2022 for their constructive feedback that greatly improved the paper. We thank Ayush Jain and Shyam Narayanan for helpful discussions regarding the paper. We would also like to thank Anna L.D. Latour and Priyanka Golia for their useful comments on the code and the earlier drafts of the paper.
This work supported in part by National Research Foundation Singapore under its Campus for Re- search Excellence and Technological Enterprise (CREATE) programme, NRF Fellowship Programme and Ministry of Education Singapore Tier 2 grant POEE-22P2011 0011], Ministry of Education Singapore Tier Grant [R-252-000-B59- 14). The computational work for this article was performed on resources of the National Supercomputing Centre, Singapore
INRF-NRFFAII-20W
References
[1] Jayadev Acharya, Clément L. Canomne, and Gautam Kamath. A chasm between identity and equivalence testing with conditional queries. Electron. Colloquium Comput. Complex., 2014.
[2] Filippo Amato, Alberto López, Eladia María Peña-Méndez, Petr Vañhara, Aleš Hampl, and Josef Havel. Artificial neural networks in medical diagnosis, 2013.
[3] Christophe Andrieu, Nando De Freitas, Arnaud Doucet, and Michael Jordan, An introduction to meme for machine learning. Machine learning, 2003.
[4] Christophe Andrieu, Nando De Freitas, and Arnaud Doucet. Reversible jump meme simulated annealing for neural networks. arXiv preprint 101.3333 2013.
[5] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing closeness of discrete distributions. Journal of the ACM (JACM), 2013.
[6] Rishiraj Bhattacharyya and Sourav Chakraborty. Property testing of joint distributions using conditional samples. ACM Transactions on Computation Theory (TOCT), 2018
[7] Eric Blais, Clément L Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory (TOCT), 2019.
[8] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp. Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint /604.0:66040033 2016.
[9] Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of markov chain monte carlo. CRC press, 2011.
10

---

[10] Clément L Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing, 2020.
[11] Clément L Canonne. A short note on learning discrete distributions. arXiv preprint 1042 2020.
[12] Clément L. Canonne, Dana Ron, and Rocco A Servedio. Testing probability distributions using conditional samples. SIAM Journal on Computing, 2015.
[13] Clément Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten. Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning, In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2021.
[14) Sourav Chakraborty and Kuldeep Meel. On testing of uniform samplers. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
[15] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah. On the power of conditional samples in distribution testing. SIAM Journal on Computing. 2016.
[16] Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence, 2008
[17] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Learning and testing junta distribu- tions with sub cube conditioning. In Conference on Learning Theory. PMLR, 2021.
[18] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. 2020.
[19] Mary Kathryn Cowles and Bradley P. Carlin. Markov chain monte carlo convergence diagnosties:
A comparative review. Journal of the American Statistical Association, 1996.
[20] Stefano Ermon, Carla P. Gomes, and Bart Selman. Uniform solution sampling using constraint solver as an oracle. In UAI, 2012.
[21] Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Faster algorithms for testing under conditional sampling. In Confer- ence on Learning Theory. PMLR, 2015.
[22] Andrew Gelman and Donald B. Rubin. Inference from iterative simulation using multiple sequences. Statistical Science, 1992.
[23] Rahul Gupta, Shubham Sharma, Subhajit Roy, and Kuldeep Meel. Waps: Weighted and projected sampling. In TACAS, 2019.
[24] Matthew D Hoffman, David M Blei, Chong Wang, and John Paisley. Stochastic variational inference. Journal of Machine Learning Research, 2013.
[25] Kyle D Julian, Mykel J Kochenderfer, and Michael P Owen. Deep neural network compression for aircraft collision avoidance systems. Journal of Guidance, Control, and Dynamics, 2019.
[26] Gautam Kamath and Christos Tzamos. Anaconda: non-adaptive conditional sampling algorithm for distribution testing. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2019.
[27] Kuldeep S. Meel(), Yash Pote ①. and Sourav Chakraborty. On testing of samplers. In Proceedings of Advances in Neural Information Processing Systems/NeurIPS), 12 2020.
[28] Forrest E. Morgan, Benjamin Boudreaux, Andrew J. Lohn, Mark Ashby, Christian Curriden, Kelly Klima, and Derek Grossman. Military Applications of Artificial Intelligence: Ethical Concerns in Uncertain World. RAND Corporation, Santa Monica, CA, 2020.
[29] Christian A Naesseth, Fredrik Lindsten, and Thomas B Schön. Elements of sequential monte carlo. arXiv preprint 17X1v.1903.04797, 2019.

---

[30] Shyam Narayanan. On tolerant distribution testing in the conditional sampling model. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2021.
[31] Christian Robert, George Casella, and George Casella. Monte Carlo statistical methods, volume 2. Springer, 1999.
[32] Mate Soos, Stephan Gocht, and Kuldeep S Meel. Tinted, detached, and lazy enf-xor solving and its applications to counting and sampling. In International Conference on Computer Aided Verification, 2020.
[33] Paul Valiant. Testing symmetric properties of distributions. SIAM Journal on Computing, 40, 2011.
[34] Aki Vehtari, Andrew Gelman, Daniel Simpson, Bob Carpenter, and Paul-Christian Bürkner. Kank-normalization, folding, and localization: An improved R for assessing convergence of MCMC (with Discussion). Bayesian analysis, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/relcusing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "qbGY4gT-fOj", "reviewer": "Reviewer_wbEk", "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.  \n\nIt 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.  \n\nFor 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.  \n\n", "questions": "N/A", "limitations": "No concerns here. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n  - formal proof guarantees, with exponential speed-up\n  - empirical evidence of speed-up when implemented\n\nWeaknesses:\n -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.  \n  That is, who is testing the testers?  \nAn evaluation of this of some form would have increased my score for the paper.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YIXtAFE6OG", "reviewer": "Reviewer_nZVA", "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\").\n\nFollowing 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$.\n\nThey 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$.", "questions": "Questions:\n- 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.\n- Relatedly, in the experiments, how did you simulate PCOND and DUAL access?\n- Strictly speaking, the guarantees of Barbarik2 and Pacoco are incomparable because the former only assumes conditional sampling access and not DUAL access, right?\n\nMinor comments:\n- P. 1 Line 33: \"can be take\" -> \"can take\"\n- 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.\n- P. 4 Line 125: isn't the DUAL oracle being used for both P and Q, not just for P?\n- P. 4 Line 133: Line9 -> Line 9\n- 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.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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).\n\nIn 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.\n\nThis 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TR_9c_WBF2j", "reviewer": "Reviewer_3NiS", "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$.", "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?\n\nWhy is there a sudden, steep ascent of #samples for Pacoco on wSTS for #instances > 36?", "limitations": "-", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* 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.\n* In summary, the experiments support the claims on the sample complexity and provide some evidence that the constants are not too large.\n\nWeaknesses:\n\n* It seems that the various upper and lower bounds compared in this paper might be somewhat incompatible.\n* Only a single set of constants $\\epsilon, \\eta, \\delta$ is chosen for the experiments, and these values are not motivated.\n* A running time comparison is lacking.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept