Uniformity Testing Under User-Level Local Privacy

In what follows, we focus on uniformity testing, that is, the task of testing whether the unknown distribution $𝐩$ is uniform on the domain, or at distance at least $\alpha$ (in total variation distance) from uniform. As discussed in Section 1.2, by a now-standard reduction this directly implies the analogous statements for identity testing, where the reference distribution is a fixed, known reference $𝐪$ instead of the uniform distribution ${𝐮}_k$.

Our setting (formally described in Section 2) involves $n$ users, each holding $m\ge 1$ i.i.d. samples from an unknown distribution $𝐩$ over a known domain of size $k\ge 2$. They engage in a distributed protocol, either public- or private-coin, to enable a central server to perform uniformity testing on this underlying distribution in a locally private manner, with privacy parameter $\epsilon >0$. Our specific focus will be on the regime $1\le m\le \sqrt{k}/{\alpha }^2$, arguably the most natural and relevant, where each user has a possibly large number of observations, but not enough that they could run a uniformity testing algorithm by themselves:¹¹1Indeed, if $m\gg \sqrt{k}/{\alpha }^2$, then each user has enough samples to perform uniformity testing by themselves, and so the question boils down to communicating the answer to the server in a locally private manner, for which $n=O(1/{\epsilon }^2)$ users is sufficient. When $m$ is even larger (specifically, at least the sample complexity of uniformity testing in the central DP model, then $n=1$ is enough: a single user can run the DP algorithm and send the outcome. we implicitly place ourselves in this regime throughout.

Our first “warm-up” result is a public-coin algorithm²²2Throughout, and in line with the local privacy literature, we will use “algorithm” and “protocol” interchangeably. which shows that, for uniformity testing, user-level LDP with $m$ samples for each of $n$ user behaves similarly to LDP with one sample for each of $mn$ users:

Whether this result seems unexpected or not to the reader, one interesting aspect is that this result essentially follows from combining, in a very simple way, two known algorithmic building blocks: the first is domain compression [6, 7], a type of hashing which, using shared randomness, allows us to to reduce the domain size without increasing the total variation distance “too much”. The second is the user-level LDP coin learning (asymmetric) protocol of [8], which lets us learn the bias of a single Bernoulli (and so, a fortiori, test it). Combining the two is then rather straightforward, modulo some bookkeeping details: (1) use domain compression to reduce the uniformity testing instance from $(k,\alpha )$ to $(2,\alpha /\sqrt{k})$; then (2) (privately, with $m$ samples) learn the bias of the resulting “coin” to accuracy $\alpha /(2\sqrt{k})$.

In view of the simplicity of the first algorithm, it is natural to expect the private-coin algorithm to be similarly straightforward. As we discuss shortly, this expectation turns out to be significantly optimistic: nonetheless, we are able to establish the following, providing an analogous result in the private-coin setting. (To interpret it, it is useful to remember that, for $m=1$, the sample complexity of private-coin locally private uniformity testing is known to be $\mathrm{\Theta }(k^{3/2}/({\alpha }^2{\epsilon }^2))$.)

One may wonder whether this trade-off between symmetry and communication complexity is inherent: by a simple modification of an argument of Acharya and Sun [9] (originally in the context of (item-level) locally private distribution learning), we provide strong evidence that this trade-off is necessary for at least some parameter regime,³³3We cannot hope to show this trade-off for all values of $m$, since for $m\gg \sqrt{k}/{\alpha }^2$, as discussed before, there is a trivial, private-coin, symmetric protocol with a single bit per user. showing that this is the case for $m=1$:

For completeness, we give a proof of this result in the full version. While only stated for very small $\alpha$, this result shows that one cannot achieve constant communication complexity per user with symmetric private-coin protocols.

Underlying our results is a technical lemma, likely of independent interest, which gives a way to compress many samples into one bit. This compression, which is likely to also find applications in the (non-private) bandwidth-constrained model, enables us to reduce the task to the much simpler task of privatizing a single bit, rather than a higher-dimensional message. Phrased in terms of differential privacy, this considerably reduces the sensitivity of our randomizers.

We briefly describe how the above lemma may lead to Theorem 2. The first (by now somewhat standard) idea is to use a good error-correcting code such as the Hadamard code to define a family of $k$ sets⁴⁴4For simplicity of presentation, we implicitly assume in this overview that $k$ is a power of $2$, that $m$ is odd, and that everything is a multiple of what it needs to be. ${\chi }_1,\mathrm{\dots },{\chi }_k\subseteq [k]$, each of size $k/2$, such that

(note that since each set has size $k/2$, if $𝐩={𝐮}_k$ then the sum is $0$). Then we can partition the users into $k$ groups, where the users of group $j$ “monitor” ${\chi }_j$: by computing how many of their $m$ samples fall into their assigned set ${\chi }_j$. That is, each user of a given group $j$ now observes a random variable distributed as

where we can rewrite $𝐩({\chi }_j)=1/2+{\alpha }_j$. By (1), we then have that ${\sum }_{j=1}^k{\alpha }_j^2$ is either $0$ (if $𝐩$ is uniform) or at least ${\alpha }^2$ ($𝐩$ is far from it). Now, our user has a $\mathrm{Bin}(m,𝐩({\chi }_j))$ in hand, and we would like them to send a single bit: this is where Theorem 2 comes in, letting the user send the bit obtained by thresholding their observation at $m/2$. This yields a bit which has either bias $0$ (if $𝐩$ is uniform, since $m$ is odd) or some bias ${\beta }_j$ such that ${\beta }_j=\mathrm{\Omega }\left(\min (\sqrt{m}{\alpha }_j,1)\right)$.

By piecing together (and centreing) the bits from one user of each of the $k$ groups, we can view it as one $k$-dimensional random bit vector in ${\{-1,1\}}^k$, with mean $({\beta }_1,\mathrm{\dots },{\beta }_k).$

This enables us to reduce our multi-sample-per-user uniformity testing problem to (privately) testing whether a product distribution over ${\{-1,+1\}}^k$ is uniform or has mean vector with norm at least

The good news is that we now longer have to worry about user-level privacy: each user only needs to make their one output bit $\epsilon$-LDP, which is easy to achieve via Randomized Response: by standard arguments, this only changes the mean testing problem by replacing the parameter ${\beta }^2:={\sum }_{j=1}^k{\beta }_j^2$ by $O({\epsilon }^2{\beta }^2)$. All that remains after that is to use an out-of-the-box (non-private) algorithm for mean testing of Rademacher-product distributions such as the ones in [20, 21], (not quite) establishing Theorem 2.

Uniformity testing was first considered in the context of theoretical computer science by [30], and the optimal sample complexity $\mathrm{\Theta }\left(\sqrt{k}/{\alpha }^2\right)$ was obtained in [35]. These results have since been generalized to the identity testing problem, where the reference distribution is not uniform, a problem later proven to be formally equivalent to uniformity testing [25, 29, 24]. The task has since also been considered under (differential) privacy, first in the central model of differential privacy [18], where the tight sample complexity was later shown to be $\mathrm{\Theta }\left(\sqrt{k}/{\alpha }^2+\sqrt{k}/(\alpha \sqrt{\epsilon })+k^{1/3}/({\alpha }^{4/3}{\epsilon }^{2/3})+1/\alpha \epsilon \right)$ [10, 14].

Under the more restrictive model of local differential privacy, the question of testing was raised in [36] and has since been wholly resolved. It is known now that the tight sample complexity for non-interactive private-coin protocols is $\mathrm{\Theta }\left(k^{3/2}/({\alpha }^2{\epsilon }^2)\right)$, while non-interactive public-coin protocols achieve $\mathrm{\Theta }\left(k/({\alpha }^2{\epsilon }^2)\right)$ [2, 5, 1]. Furthermore, allowing interactivity cannot improve the sample complexity beyond the bound given in the public-coin setting [3, 15, 37].

In the shuffle model of differential privacy, where users’ responses are permuted before being received by the central curator, an upper bound of $O\left((k^{3/4}\sqrt{\log (1/\delta )})/(\alpha \epsilon )+\sqrt{k}/{\alpha }^2\right)$ was shown in [22]. The best known lower bounds were derived from a connection to pan-privacy [17].

The user-level setting is a natural generalization of any distributed statistical problem. In practice, it is restrictive to consider users holding only one sample from the distribution of interest whether we are testing, learning, or performing any other distributed task. For this reason, distribution learning with multiple samples was studied under bandwidth constraints, where an intricate interplay between the number of samples per-user and the number of bits available to communicate the samples was shown [4]. Under user-level differential privacy, these results were extended to show that (among other things) for small $\epsilon$, one achieves a sample complexity for learning of $n=O\left(k^2/(m{\alpha }^2{\epsilon }^2)\right)$. Comparing this to the case when $m=1$ (For example [11]) we can see that the risk decreases linearly with $m$. We could say that for the task of learning, having $m$ samples per-user is as beneficial as having $m$ times more users to query.

Even though there is no direct reduction between the two settings, and (as inferred from the previous discussion) the situation, as $m$ grows, becomes quite subtle, this gives strong evidence that our results which show a sample complexity improvement by a factor $m$ are tight, at least in the most relevant parameter regime for $m$.

We first provide the necessary notions and results from the differential privacy (DP), starting with the definition of local differential privacy (LDP).

While Local Differential Privacy is somewhat involved to define for interactive protocols, where each user can send (in an adaptive manner) several messages, it is simpler in our setting. We consider non-interactive protocols, where each user only sends one message to the server. When each user holds several datapoints (that is, $𝒳={[k]}^m$), the above definition then directly corresponds to the user-level LDP guarantee considered in this paper.

We will rely on the (binary) Randomized Response mechanism, which is an optimal $\epsilon$-local differential privacy protocol for 1-bit inputs [33]. Formally, let $Q$ be the local randomizer for this protocol where $Q(x)$ is a random variable, and $Q(y|x)$ is the probability of seeing output $y$ on input $x$.

Here, we formally state the problem and setting. We are interested in the problem of uniformity testing with multiple samples per user. Specifically, given a discrete distribution $𝐩$ over $k$ elements, which we assume without loss of generality is over the domain $[k]$, each user $i=1,\mathrm{\dots },n$ holds a multi-sample $X_i\sim {𝐩}^{\otimes m}$ which is an $m$-dimensional vector of i.i.d. samples from $𝐩$. We are interested in algorithms that can distinguish between the cases where ${\mathrm{d}}_{\mathrm{TV}}(𝐩,𝐮)=0$ and ${\mathrm{d}}_{\mathrm{TV}}(𝐩,𝐮)>\alpha$ via the fewest possible number of users $n$. As mentioned in the introduction, barring some kind of information constraint per-user, this problem reduces to the well-studied case where $m=1$ by having each user send all $m$ of their samples and treating each as its own message. This problem becomes non-trivial when we are either bandwidth-constrained or privacy-constrained. In the former, users have up to $\mathrm{\ell }$ bits with which to communicate their samples. In the latter, the user is constrained by differential privacy.

In the user-level LDP setting, upon receiving $n$ private responses $Y_1,\mathrm{\dots },Y_n$ from the users, the server must distinguish between the two cases:

• $\mathrm{■}$

  ${\mathrm{d}}_{\mathrm{TV}}(𝐩,𝐮)=0$, and

• $\mathrm{■}$

  ${\mathrm{d}}_{\mathrm{TV}}(𝐩,𝐮)>\alpha$,

with probability at least $2/3$, while satisfying $\epsilon$-user-level LDP. (The threshold $2/3$ is somewhat arbitrary, and can be amplified to any $1-\beta$ by standard arguments at a sample complexity cost of $O(\log (1/\beta ))$.)

We first recall Cantelli’s inequality, a one-sided version of Chebyshev’s inequality:

We will also require the following standard tail bound for subgaussian random variables (see e.g., [31]):

Using the same indexing as for the groups, let ${\chi }_j$ be the set of indices where a 1 appears in the column $j$ of the Hadamard matrix $H\in {\{\pm 1\}}^{k\times k}$, that is,

The properties of Hadamard matrices ensure that each of its columns is a column vector of length $2^t$, where half of the positions are $+1$, and the other half are $-1$, and so $\left|{\chi }_j\right|=k/2$ for all $j$. Hereafter, we will write $𝐩({\chi }_j)$ to denote the probability that a sample under $𝐩$ falls in set ${\chi }_j$, i.e., $𝐩({\chi }_j)={\sum }_{r\in {\chi }_j}{𝐩}_r$. User $i$ then computes

i.e., the number (out of their $m$ samples) that lie within ${\chi }_j$ (the subset of the domain they are “monitoring”). One can observe the following distinction of cases:

• $\mathrm{■}$

  If $𝐩={𝐮}_k$, then $X_i\sim \mathrm{Bin}(m,1/2)$.

• $\mathrm{■}$

  If ${\mathrm{d}}_{\mathrm{TV}}(𝐩,{𝐮}_k)>\alpha$, then $X_i\sim \mathrm{Bin}(m,1/2+{\alpha }_j)$, for some ${\alpha }_j$ which will be related to $\alpha$ by Lemma 13.

We call ${\alpha }_j$ the bias observed by group $G_j$. User $i$, instead of directly sending $X_i$, will then compute the one-bit indicator

and send this to the server. We will show that, given $n=O\left(\frac{k^{3/2}}{m{\alpha }^2}\right)$ independently drawn samples $Y_1,\mathrm{\dots },Y_n$ as above, there exists an algorithm that distinguishes between $𝐩={𝐮}_k$ and $𝐩$ $\alpha$-far from ${𝐮}_k$ (with probability at least $2/3$).

(Note that this protocol, which follows the above outline, is asymmetric, as users are partitioned in $k$ distinct groups of equal size, and users from different groups process their $m$ samples differently.) This first algorithm is particularly well suited to the “small $m$ regime” where $m\le 1/{\alpha }^2$, where it achieves the desired number of users.

The rest of this subsection is dedicated to establishing Theorem 11. In view of this, we will need three ingredients: first, demonstrating that $Y_i$ has bias $\sqrt{m}{\alpha }_j$ (this factor $\sqrt{m}$ is where the dependence on $m$ in the final bound will come from); second, showing that a distribution that is $\alpha$-far from uniform induces bias in each group, such that ${\sum }_{j=1}^k{\alpha }_j^2\approx {\alpha }^2$; and third, a known result on uniformity testing for Rademacher-product distributions. The proof proceeds immediately from these results: Each user sends their single bit $Y_i$ with bias $\sqrt{m}{\alpha }_j$. We then take one bit from each group and arrange them into a vector. This vector simulates a sample from the product distribution with mean $\mu =(𝐩({\chi }_1),\mathrm{\dots },𝐩({\chi }_k))$. Applying Lemma 13 we get that the expected ${\mathrm{\ell }}_2^2$ norm of this vector is at least $m{\alpha }^2$. Plugging in an ${\mathrm{\ell }}_2^2$-norm product tester as a black box, we conclude our proof.

As stated above, we begin by capturing the behaviour of $Y_i$ as a function of each ${\alpha }_j$. Recall that $Y_i$ is an indicator variable that declares whether a binomial $X_i$ exceeded the mean it “should” have in the uniform case: in this sense, going from $X_i$ to $Y_i$ converts a “many-bit” sample to a “single-bit” one. We show that for $X\sim \mathrm{Bin}(m,1/2\pm \alpha )$ with small bias $\alpha$, this indicator behaves as a Bernoulli with mean $\sqrt{m}\alpha$, and so this conversion from many bits to one still preserves both bias $\alpha$ and a dependence on $m$. For ease of exposition, we defer its proof to the end of the section.

While the bias ${\alpha }_j$ observed by each group is clearly distribution-dependent, we need to relate them explicitly to the distance parameter $\alpha$. To do so, we use the known fact that multiplication by a Hadamard matrix is ${\mathrm{\ell }}_2$-norm preserving.

(This follows, for instance, from [2, Lemma 3], combined with Cauchy–Schwarz to relate total variation and ${\mathrm{\ell }}_2$ distances.) For completeness, we provide a self-contained proof in the full version.

Finally, the third (and last) ingredient missing is an algorithm to test, given i.i.d. observations from a product distribution on $k$ bits, whether the mean vector is zero (uniform distribution) or has large norm:

For a proof of this in the case $\gamma \in (0,1]$, see, e.g., [20, Section 2.1] or [21, Lemma 4.2], which establish this along the way, while focusing on testing in total variation distance, or [19, Theorem 4.1], which provides slightly stronger guarantees. We note that while stated only for $\gamma \in (0,1]$, the proofs above actually implicitly show the result for the whole range of $\gamma$. For completeness, we provide a self-contained proof (for the whole range of $\gamma$) in the full version.

With these three building blocks in hand, we are ready to analyze Algorithm 1:

The above approach gives the “right” sample complexity under the restriction that

where ${\alpha }_j=𝐩({\chi }_j)-\frac{1}{2}$. We here provide a different protocol, which works well when at least one of the $|{\alpha }_j|$’s is large. The main idea is to have each user just check is any of the $k$ sets ${\chi }_j$ receives a lot more (or less) than half of their $m$ samples, namely, $\frac{m}{2}\pm \mathrm{\Omega }(T)$ for some suitable threshold $T=\mathrm{\Theta }\left(\sqrt{m\log (nk)}\right)$. If $𝐩$ is uniform, then this is highly unlikely, as by Lemma 7 the maximum deviation of $k$ subgaussian random variables (here, Binomials) from their mean is less than $T$ with overwhelming probability. But if $𝐩$ is not uniform and one of the $|{\alpha }_j|$’s is large, then the number of samples falling in the corresponding set ${\chi }_j$ is a very biased Binomial, and for every user this set will receive $\frac{m}{2}\pm \mathrm{\Omega }(T)$ samples with high constant probability. We formalize this idea in Algorithm 2, starting with the non-private version; and prove the following theorem:

There exists a critical regime of parameters that Algorithm 1 struggles with, leading to suboptimal sample complexity; and these are handled exactly by Algorithm 2. We can handle both regimes as follows: have the server run both protocols, the former with $n_1=n-1$ and the latter with $n_2=1$ users, and return accept if, and only if, both of them return accept. Assume

Then, we have the following distinction of cases:

• $\mathrm{■}$

  If $𝐩={𝐮}_k$, then both protocols accept with probability at least $9/10$ each, so overall the centre returns accept with probability at least $8/10$;

• $\mathrm{■}$

  If ${\mathrm{d}}_{\mathrm{TV}}(𝐩,{𝐮}_k)>\alpha$, then

  • –

    If there exists $j^{\ast }\in [k]$ such that

    $${\alpha }_{j^{\ast }}=\mathrm{\Omega }\left(\sqrt{\log (k)/m}\right)$$

    then, by Theorem 15, the second protocol (with one user) outputs reject with probability at least $9/10$, in which case the center outputs reject.

  • –

    Otherwise, then by (4) the mean of the product distribution in the first protocol is at least

    $${\parallel \mu \parallel }_2^2\gtrsim \sum _{j=1}^k\left(m{\alpha }_j^2\wedge 1\right)\ge \sum _{j=1}^k\left(\frac{m{\alpha }_j^2}{\log k}\wedge 1\right)\gtrsim \frac{m{\alpha }^2}{\log k}$$

    (5)

    since $m{\alpha }_j^2\lesssim \log k$ for all $j$, and ${\sum }_{j=1}^k{\alpha }_j^2\ge {\alpha }^2$. Then, concluding as in Section 4 by invoking the uniformity testing algorithm for product distributions of Lemma 14 (which also handles the full range of distance parameter ${\gamma }^2:=\frac{m{\alpha }^2}{\log k}\in (0,k]$), the server rejects with probability at least $9/10$, as

    $$\frac{n}{k}\gtrsim \frac{k^{1/2}}{{\gamma }^2}\vee 1.$$

  Either way, at least one of the two tests outputs reject with probability $9/10$, and so does the center.

The above protocol is asymmetric in that, as stated, it needs users to be divided into $k$ groups. Of these, $k-1$ groups will run Algorithm 1, each with a different column. The last group (of only 1 user) runs Algorithm 2.

To resolve the asymmetry in Algorithm 1 we prove the following statement, which covers the setting we require to make our protocol symmetric: each of $n^{\prime }:=nd$ users independently selects a random coordinate and reports a sample from that coordinate. Formally, observations $(X_1,j_1)\mathrm{\dots },(X_{n^{\prime }},j_{n^{\prime }})$ are obtained by choosing, independently for each $i\in [n^{\prime }]$, $j_i\in [d]$ uniformly at random, and $X_i\sim {𝐩}_{j_i}$. In this case, the numbers of times $n_1,\mathrm{\dots },n_d$ each coordinate $j\in [d]$ is sampled are (correlated) $\mathrm{Bin}(nd,1/d)$ random variables.