How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions

The paper describes how a verifier can check that a distribution which they can sample from has (up to small error) a certain (polynomial time verifiable) property in O(sqrt(n)polylog(n)) time with support from an untrusted prover that already knows the distribution. The protocol consists of the prover commiting to (an approximation of) the true distribution, then proving to the verifier that this matches what they are sampling in a way that only needs O(sqrt(n)) samples, finally the prover proves that the committed distribution has (or rather is clsoe in TV distance to having) the desired property.

A recurring theme in theoretical computer science is that verifying an answer is often (computationally) easier than deriving the answer from scratch. This work illustrates this principle in the context of distribution testing. Let $\mathcal{P}$ be a distribution property (i.e., set of distributions) such that with full knowledge of a given distribution $Q$, I can efficiently decide whether $Q \in \mathcal{P}$ or not. The paper’s main result shows that If someone else (”Prover”) has already put in extensive effort to fully identify a distribution $Q$ and I (”Verifier”) only have sample-access to $Q$, then I can test whether $Q$ satisfies the property $\mathcal{P}$ with far less effort by engaging in an interactive protocol with the Prover. This verification is feasible even without any trust in the Prover and is strictly more efficient than the naive solution of the Prover simply sending over the full representation of $Q$.

The lack of trust in the Prover introduces several challenges. Let $\tilde{Q}$ be the representation of the “distribution” on $[N]$ the Prover holds (quotations since the $\tilde{Q}$ may not even be a valid distribution) and let $Q$ be a distribution on $[N]$ which the Verifier has only sample-access to. Here, the support size $N$ is the index with respect to which computational complexity is defined. In the absence of trust, the Verifier must check that 1) $\tilde{Q}$ is a valid distribution and 2) $\tilde{Q} = Q$. The second part uses the identity (a.k.a. goodness-of-fit) testing algorithm by Goldreich (2017) which has $\sqrt{N}$ sample complexity. The Prover’s overall honesty in responding to Verifier’s queries is enforced through cryptographic commitment schemes, whose security is based on collision-resistant hash functions.

Once the Verifier checks that $\tilde{Q} = Q$, then it remains to check that $\tilde{Q} \in \mathcal{P}$. The deterministic decision $Q \in \mathcal{P}$ potentially requires poly($N$) time to compute. However, PCPs allow the Verifier to probabilistically check this much more efficiently, incurring only poly($\log(N)$) additional communication cost for checking $\tilde{Q} \in \mathcal{P}$ on top of the $\sqrt{N}$ needed for identity testing.

This paper considers the problem of verifying whether an unknown discrete distribution satisfies certain properties with a prover. The authors show that it is possible to verify a wide class of properties using a sublinear number of samples and running time. Without a prover, even testing some properties requires quasi-linear samples, which is a big improvement.

The paper introduces an interactive protocol for the verification of distribution properties, computationally sound. The protocol is performed between a verifier and an untrusted prover, where both have sampling access to some unknown distribution. The major contribution of this work is an argument system that can be used in verifying any property such that, given the full description of a distribution, one may approximately compute its distance from the property in polynomial time.The protocol has a communication complexity and verifier runtime of roughly O( N​/eps^2 ) which is nearly optimal. This yields a quadratic speedup over prior approaches with quasi-linear sample complexity. The authors also provide applications to testing properties like monotonicity and juntas and extend their approach to properties in NP.

This paper considers a setting where an untrusted prover and verifier both have sample access to an unknown distribution, and the prover wishes to convince the verifier that the distribution has some property. The prover does so using an interactive protocol, which is efficient in the sense that the communication complexity and sample complexity of the verifier are low. In particular, their protocol applies to some properties where testing (from scratch, without a prover) provably requires a higher sample complexity than that of the verifier. Their protocol has two components. The first is a distribution-commitment, a new cryptographic primitive that allows a prover to succinctly commit to a distribution and verifiably answer natural queries, such as the probability of any element or the cdf. The second component is a reduction to interactive arguments of proximity, using this distribution commitment. That is, they show a protocol where the prover commits to the distribution. The verifier then tests the correctness of this commitment by sampling from the unknown distribution. The prover and verifier then engage in an interactive argument of proximity to test that the committed distribution indeed has the claimed property.

This paper gives efficient interactive verification protocols for distribution property testing. Specifically, the goal is to design a communication protocol between a prover and a verifier, such that the verifier, given sample access to an unknown distribution $D$ and the ability to make certain queries to the prover, is able to verify the membership of $D$ in a class/property of probability distributions. A tolerant verifier parametrized by $\varepsilon_c$ and $\varepsilon_f$ is guaranteed to verify membership of distributions that are at most $\varepsilon_c$-close in total variation distance to some distribution in the class and to reject $\varepsilon_f$-far distributions and the sample complexity depends on the difference $\rho=\varepsilon_f-\varepsilon_c$.

Specifically, the protocol uses $\tilde{O}(\sqrt{N}/\rho^2)$ samples from $D$, which matches that of prior work by [Chiesa and Gur 2018] and is quadratically better than lower bounds for standalone (i.e without a prover) tolerant distribution testing problems. The main novelty of this work lies in the quadratic improvement of the protocol’s communication complexity and running time over prior work. This is achieved using cryptographic collision resistant hash functions. The prover is assumed to have knowledge of the distribution $D$ up to sufficient accuracy and forced to commit to a distribution as part of the protocol without having to transmit an explicit description of it. This fact along with the use of the PCP theorem are the tools that make it possible for the communication complexity and running time to be significantly reduced. The protocol works by first having the prover send a short digest $d$ of the distribution $D$ using cryptographic hashing to commit to it for the answers to future queries. Subsequently, the verifier uses queries to run an interactive argument of proximity (IAP) in order to check if the bit string representation of the committed distribution is accepted by a turing machine that decides closeness to the property.

The above protocol provides a unified way of dealing with any class/property of distributions that is decidable in polynomial time and since there is no sampling involved in that step, the sample complexity is the same for every such property.

This paper falls in the area of distribution testing. In the standard setting of distribution testing, we have given sample access to an unknown distribution $D$ over a finite domain of size $N$ and the goal is to design algorithm that tests whether $D$ is $\epsilon_1$-close (in some distance measure such as total variation distance) to a distribution satisfying a property ${\mathcal P}$ or $D$ is $\epsilon_2$-far from any distribution that satisfies ${\mathcal P}$. It is known that in this (known as the tolerant testing) setting, the sample complexity, even for very simple properties such as testing uniformity, is close to $\theta(N/\epsilon^2)$.

The paper argues that if we take certain interactive proof system approach the sample complexity can be improved by a quadratic factor. In this model, there is a prover and a verifier both of them having sample access to the unknown distribution. An interactive proof is a communication protocol between prover and verifier so that:

1. if the distribution $D$ is close to having the property ${\mathcal P}$, then an efficient prover can convince the verifier of this fact with high probability (completeness).

2. However, If $D$ is far from having the property ${\mathcal P}$, then no polynomial time prover can make the verifier accept with non-negligible probability (soundness).

The main result is that for any ${\mathit efficiently}$ decidable property, there is such a proof system (under standard cryptographic assumptions) with verifiers sample and time complexities $\tilde{O}(\sqrt{N}/\epsilon^2)$. This is a quadratic improvement from the standard scenario. The paper also discusses several extensions.

We would like to thank the reviewers for their thoughtful and insightful feedback. Following multiple comments, we expanded on the existing appendices, and added two additional ones (Appendices C and D) to capture more technical details of the protocol and the proofs behind it. We hope that these additions will help communicate our result better.

This paper considers the problem of verifying whether an unknown discrete distribution satisfies certain properties with a prover. The authors show that it is possible to verify a wide class of properties using a sublinear number of samples and running time. Without a prover, even testing some properties requires quasi-linear samples, which is a huge improvement.

All reviewers converged in praise of the significance of the result and gave positive scores. I thus recommend acceptance and a spotlight presentation.

Accept (Poster)