Interactive Proofs for Distribution Testing with Conditional Oracles

There is now a long line of work on the testing and verification of label-invariant properties [5, 53, 20, 36, 35], and a key object used in this work is the unlabelled approximate $\tau$-bucket histogram of a distribution. Bucketing corresponds to partitioning the interval $[0,1]$ into smaller multiplicative probability intervals. The $\tau$-bucket histogram divides the interval $[0,1]$ into $\tilde{O}\left(\log N/\tau \right)$ buckets where the $\mathrm{\ell }$^th bucket is a set of domain elements with individual probability mass in the range $(\tau {(1+\tau )}^{\mathrm{\ell }}/N,\tau {(1+\tau )}^{\mathrm{\ell }+1}/N]$. The approximate unlabelled bucket histogram of a distribution then corresponds to a list of $\tilde{O}(\log N/\tau )$ fractions, where the $\mathrm{\ell }$^th element of the list is the fraction of domain points whose probability lies in the range specified by the $\mathrm{\ell }$^th bucket. It is well known (see [53]) that the approximate unlabelled $\tau$-bucket histogram of a distribution is a sufficient statistic to (tolerantly) test any label-invariant property with proximity parameter(s) $O\left(\tau \right)$. Thus, similar to prior work [36, 35, 34], our protocol also focuses on efficiently verifying an unlabelled $\tau$-bucket histogram given to us by the prover.

Note that the unlabelled bucket histogram is a distribution over the buckets of the $\tau$-bucket histogram and is hence a distribution over a domain of size $\tilde{O}(\log \frac{N}{\tau })$. Hence, by standard results in distribution learning, $\tilde{O}(\log N/{\tau }^2)$ samples from this bucket distribution would be sufficient to learn it. However, sampling from this bucket distribution is non-trivial since a sample from the original distribution $𝒟$ does not come with information about histogram bucket index.

While sampling from the bucket distribution might be hard with Samp access to the distribution, one might be more optimistic about the possibility of sampling from the $\tau$-approximate histogram with PCond queries. In particular, one approach that we might take is the following: the verifier draws a dataset of size $\tilde{O}(\log N/{\tau }^2)$ (enough to learn the histogram), and sends these samples to the prover, who responds with the bucket index of each sample. From how a $\tau$-histogram is defined, if $x$ and $y$ belong to buckets $i$ and $j$ respectively, then this implies that the ratio of the probability masses of $x$ and $y$ under $𝒟$ is guaranteed to be in the interval $[\frac{1}{{(1+\tau )}^{|j-i|}},{(1+\tau )}^{|j-i|}]$. As PCond access allows us to conditionally sample from a set restricted to two domain elements, it allows us to approximately learn the ratio of their probability masses up to a multiplicative constant. Equipped with this power, for each pair $x\ne y$ from the set of drawn samples, the verifier uses the PCond oracle to check if the learned ratios align with the provers claims. If the prover were to lie significantly, then for at least one pair of samples, the claimed ratio would significantly different from the learned ratio. Unfortunately, this simplistic strategy comes with two pitfalls. Firstly, assuming the above strategy was sound, naively comparing elements with arbitrary bucket indices could require $\mathrm{\Omega }\left(N\right)$ PCond queries if the elements being compared had significantly different probability masses. This would be as bad as learning the distribution itself. Secondly, and more importantly, the above strategy is not sound. It does not catch a prover that “slides” all samples into different buckets in the same way, i.e., it lies about every bucket index by the same offset. As an example, consider two distributions: ${𝒟}_1$ is the uniform distribution over $N^{1/4}$ domain elements and ${𝒟}_2$ is the uniform distribution over $\sqrt{N}$ domain elements. The bucket histograms of both involve a unit mass on a single (but different) bucket. However, pairwise comparisons between samples taken from either distribution will always reveal a ratio that is approximately $1$, since the probabilities of all elements in the support of both distributions are identical. Hence, given distribution ${𝒟}_1$, the prover can output the bucket histogram of distribution ${𝒟}_2$, and it is impossible for a verifier to catch it purely by using the test described above.

A remedy to these obstacles lies in the following observation. If we had a good estimate of the probability mass of a single point $y$ in the domain, then we could resolve the soundness issue discussed above. We simply use the PCond oracle to learn the ratio of probabilities between each of our samples and $y$. Using this ratio, and knowledge of the approximate mass of $y$, we can compute estimates of the probabilities of all samples. This would squash the sliding attack described above. To deal with the first issue (that of the probability mass of $y$ being very far from that of a sample), we would need to do more than learn just one value of $y$. Instead, we could learn the mass of a point $y_j$, for every bucket $j$ that has large enough mass. This way, for any sample $x$ in the tester’s set of samples (which are likely to come from buckets with sufficiently large mass), we can find some $y_j$ that is in a near-by bucket with high probability.

Given that we simply need to identify the probability of a few points in the domain, one might expect that this could be done even without access to a prover – this would give a query-efficient tester for label-invariant properties. However, this ends up being a surprisingly challenging task. Indeed, our lower bound in Theorem 1.1 shows that this is impossible (if we wanted to bypass the $\mathrm{poly}(N)$ lower bound). This indicates a power of an untrusted prover; it is able to certify the probability of a few points in the distribution support. Indeed, the proof system with super-linear communication [22] achieves something stronger- it certifies the entire distribution. Since we only need to certify the mass of at most $O\left(\log N\right)$ points, we ask if this be done in a more communication efficient way?

Inspired by the “sliding” cheating prover from earlier, we consider the orthogonal but related problem of verifying the support size of a flat distribution.⁴⁴4A distribution is flat if it is uniform over its support. We will subsequently show that a protocol for this problem can be combined with the ability of a PCond oracle to learn neighbourhoods around points, enabling us to solve the probability approximation problem for “relevant” domain elements.

Given a support size claim represented by four numbers $A^{\prime },A,B,B^{\prime }$, corresponding to the claim that , our hope is to accept if the claimed support size range is accurate, and reject if the true support is larger than $B^{\prime }$ or smaller than $A^{\prime }$. Given different values of $A$ and $B$, we develop a number of tests to verify with sub-linear communication, the support size assuming the distribution is uniform over its support⁵⁵5We relax this condition in the main protocol, but assuming uniformity makes the description more intuitive.. We summarize the ideas below.

If the claimed support size upper bound $B$ is small (that is, $O\left(\sqrt{N}\right)$), we could ask the prover to send us the claimed support of the distribution. If the prover lies, and the true support is actually much larger, then taking a few samples from the distribution would give us a domain element outside the claimed support, thus catching the lie of the prover. If the true support is much smaller than $A$, then taking a number of uniform samples from the claimed support sent by the prover would result in a sample outside the support of the distribution, which could be easily detected with a few PCond queries. This gives us a protocol with a constant number of queries, and communication complexity roughly $O(B)$.

On the other hand, if the claimed support size lower bound $A$ is large (that is, $\omega \left(\sqrt{N}\right)$), then asking the prover to send the support is not communication-efficient. Our approach instead involves using uniform samples from the domain. The first test is to catch provers that lie that the support is much larger than it really is. It involves drawing $O(N/A)$ uniform samples $S_1$ from the domain, and sending them to the prover. We ask the prover to send back a sample in this subset that is in the support of the distribution. If the true support is much smaller than $A$, there are (with high probability) no samples in the support of the distribution in $S_1$, and we can ensure the prover does not cheat by checking whether any element it sends back is in the support using a constant number of PCond queries. The second test catches provers that lie that the support is much smaller than it really is. It involves drawing $O(N/B^{\prime })$ samples $z_1,\mathrm{\dots },z_m$ uniformly from the domain and permuting them with one sample $x$ taken from the distribution. We ask the prover to identify the index of $x$ in the permuted set. If the true support is smaller than $B$, then w.h.p, we expect that none of $z_1,\mathrm{\dots },z_s$ are in the support of the distribution and hence, the honest prover can identify $x$ exactly. On the other hand, if the support is larger than $B^{\prime }$, we expect that at least one of $z_1,\mathrm{\dots },z_s$ is in the support of the distribution, and the prover is unable to tell what the sample inserted by the prover was (since it could be $x$ or $z_i$). This gives us a protocol with a constant number of queries, and communication complexity roughly $O(N/A)$. Balancing parameters in these tests to optimize the communication complexity, we get an overall protocol for support size verification with communication complexity roughly $\sqrt{N}$.

We emphasize that the above outline is a simplification of the truth, and sweeps important details under the rug. Recall that our main goal is to certify the histogram of a distribution. In an attempt to do so, we will use the support size protocol above repeatedly as a sub-routine. This requires bounding the soundness and completeness errors in a meaningful way. As described above, these protocols do not have low enough soundness and completeness error to be used as sub-routines. Additionally, the above description assumes that distributions are exactly flat. In practice this will not be the case, and we need to be able to handle distributions where the probability ratio between any two elements in the support is upper bounded by some constant $\alpha$ (nearly flat). We show how to analyse the protocols above to facilitate amplification of soundness and completeness errors, and make the protocol work for the more general class of $\alpha$-flat distributions.

Finally, we explain how we can use the support size protocols to estimate the probability of a point. Prior work [13] using the PCond oracle has shown that it can be used to estimate the mass within a multiplicative $(1+\tau )$-neighbourhood of any point⁶⁶6As long as the point does not have prohibitively small probability mass under the distribution.. We ask the prover to send us a point $y^{\star }$ ⁷⁷7Recall that in the final protocol, we will ask the prover to send us points from every bucket with sufficiently large mass. For simplicity, we consider a single point in this description. with sufficiently large mass in its neighbourhood (by an averaging argument, at least one histogram bucket needs to have $\tau /\log N$ mass, ensuring that such a point exists, and tell us the bucket the $y^{\star }$ belongs to. We then use the PCond oracle to estimate the mass within the multiplicative neighbourhood of $y^{\star }$. The learned mass of the neighborhood divided by the prover’s claimed probability mass⁸⁸8The bucket index gives a lower and upper bound on the true probability mass of $y^{\star }$. This is sufficient to catch a cheating prover. of $y^{\star }$ gives us bounds on the number of elements in $y^{\star }$’s neighbourhood. Additionally, by definition the neighbourhood of $y^{\star }$ will be nearly flat. Hence, we have reduced the problem to a claim about the support size of a nearly-uniform distribution over a subset of the domain. Observe that we can sample from the distribution restricted to this bucket using PCond queries – since there is sufficient mass in the neighbourhood of the point, $O(\mathrm{poly}\log N)$ samples from the distribution will contain at least one sample from the bucket, and we can use PCond queries between the samples and $y^{\star }$ to find out which sample it is. If the prover was telling the truth (or rather did not lie egregiously), then the support size claim holds and the verifier will accept, thereby giving us a point and its approximate probability mass⁹⁹9The claimed mass of $y^{\star }$ is derived from the bucket sent by the prover.. If the prover significantly lied, then the support size claim will be false and the prover will be caught. We note that the final analysis needs to handle some additional subtleties, since the PCond oracle is itself only approximate and does not provide perfect comparisons (which can affect the sampling), and additionally the bucket boundaries and the neighbourhood of the provided point do not overlap precisely. Once we have estimated the probability of important points, we can use the ratio learning techniques discussed earlier to certify the prover’s claim about the bucket histogram of the distribution. We refer the reader to the full version for precise technical details.

As mentioned earlier, interactive proofs for verifying distribution properties were first introduced in the work of [22]. Follow-up work [36, 35] studied interactive proofs for verifying label-invariant properties, focusing on sublinear communication, and doubly efficient protocols (i.e. computationally-efficient and sample-efficient generation of a proof). [34] studied public-coin interactive proofs for testing label-invariant properties, where the verifier has no private randomness. [37] gives communication-efficient and sample-efficient interactive proofs for more general distribution properties that can be decided by uniform polynomial-size circuits with bounded depth. [38] introduces computationally sound interactive proofs and shows communication-, time-, and sample-efficient protocols for any distribution property that can be decided in polynomial time given explicit access to the full list of distributiom probabilities. All of the above works assume that the verifier only has sample access to the distribution, and the verifier sample complexity in all of them is $\mathrm{\Omega }(\sqrt{N})$ (where $N$ is the size of the domain).

A related but orthogonal line of work [31, 42, 33, 16, 15] focuses on interactive proofs for verifying learning problems- for a specific hypothesis class $H$, given access to an untrusted prover, the goal is for a verifier to output an accurate hypothesis from $H$ for an underlying unknown distribution $D$ if the resource-rich prover is honest, and to reject if the prover lies egregiously. Different types of resource asymmetry between the prover and the verifier are explored in these papers – including differing number of samples, different computational complexities, different types of access to the underlying function (sample vs query), and differing access to computational resources (classical vs quantum computation and communication).

Our work focuses on interactive proofs for verifying distribution properties under conditional sampling models. There is a long line of work on testing with access to conditional samples. [20, 12] introduced the conditional sampling (Cond) model and its more restricted variants ($\text{PCond},\text{ICond}$). They gave algorithms for uniformity testing, tolerant uniformity testing, identity testing etc. in these conditional sampling models with query and sample complexity significantly better than the Samp model. Follow-up work shows improved bounds for identity testing (and its tolerant version), tolerant uniformity testing, and new algorithms for other tasks such as equivalence testing and support size problem in the Cond model [24, 43, 19, 18]. There is also a line of work studying the power of non-adaptive queries in the conditional sampling model [1, 39]. The PCond model was studied in detail by [43] who gave optimal bounds for identity testing and tolerant uniformity testing in this model, improving on results from [13]. Testing under other types of conditional sampling has also been studied in the literature including subcube conditioning, where the distribution is supported on the hypercube, and the tester is allowed to ask for conditional samples from subcubes [7, 11, 21, 40, 17], and coordinate conditional sampling [8] (a version of subcube conditioning where all but one coordinate is fixed to a specific configuration and a sample is obtained from the remaining coordinate). Testing under other types of access to the distribution such as Probability Mass Function queries or Cumulative Distribution Function queries has also been studied in the literature [4, 49, 32, 14, 44].