Differentially Private Sampling from Distributions
Year: 2021

Abstract:
We initiate an investigation of private sampling from distributions. Given a dataset with n independent observations from an unknown distribution P , a sampling algorithm must output a single observation from a distribution that is close in total variation distance to P while satisfying differential privacy. Sampling abstracts the goal of generating small amounts of realistic-looking data. We provide tight upper and lower bounds for the dataset size needed for this task for three natural families of distributions: arbitrary distributions on {1, . . . , k}, arbitrary product distributions on {0, 1}, and product distributions on on {0, 1} with bias in each coordinate bounded away from 0 and 1. We demonstrate that, in some parameter regimes, private sampling requires asymptotically fewer observations than learning a description of P nonprivately; in other regimes, however, private sampling proves to be as difficult as private learning. Notably, for some classes of distributions, the overhead in the number of observations needed for private learning compared to non-private learning is completely captured by the number of observations needed for private sampling.

heading: 1 Introduction
text: Statistical machine learning models trained on sensitive data are now widely deployed in domains such as education, finance, criminal justice, medicine, and public health. The personal data used to train such models are more detailed than ever, and there is a growing awareness of the privacy risks that come with their use. Differential privacy is a standard for confidentiality that is now well studied and increasingly deployed.
Differentially private algorithms ensure that whatever is learned about an individual from the algorithm’s output would be roughly the same whether or not that individual’s record was actually part of the input dataset. This requirement entails a strong guarantee, but limits the design of algorithms significantly. As a result, there is a substantial line of work on developing good differentially private methodology for learning and statistical estimation tasks, and on understanding how the sample size required for specific tasks increases relative to unconstrained algorithms. A typical task investigated in this area is distribution learning: informally, given records drawn i.i.d. from an unknown distribution P , the algorithm aims to produce a description of a distribution Q that is close to P .
However, often the task at hand requires much less than full-fledged learning. We may simply need to generate a small amount of data that has the same distributional properties as the population, or perhaps simply “looks plausible” for the population. For example, one might need realistic data for debugging a software program or for getting a quick idea of the range of values in a dataset.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this work, we study a basic problem that captures these seemingly less stringent aims. Informally, the goal is to design a sampling algorithm that, given a dataset with n observations drawn i.i.d. from a distribution P , generates a single observation from a distribution Q that is close to P .
To formulate the problem precisely, consider a randomized algorithmA : Un → U that takes as input a dataset of n records from some universe U and outputs a single element of U . Given a distribution P on U , let X = (X1, ...Xn) be a random dataset with entries drawn i.i.d. from P . Let A(X) denote the random variable corresponding to the output of the algorithmA on input X. This random variable depends on both the selection of entries of X from P and the coins of A. Let QA,P denote the distribution of A(X), so that
QA,P (z) = Pr X ∼i.i.d.P
coins ofA
(A(X) = z) = ∑ x∈Un ( Pr(X = x) · Pr coins ofA (A(x) = z) ) .
The dataset size n is a parameter of A and thus defined implicitly. We measure the closeness between the input and output distributions in total variation distance, denoted dTV . Definition 1.1 (Accuracy of sampling [4]). A sampler A is α-accurate on a distribution P if
dTV (QA,P , P ) ≤ α. A sampler is α-accurate on a class C of distributions if it is α-accurate on every P in C.
The class C in the accuracy definition above effectively encodes what the sampler is allowed to assume about P . For example, C might include all distributions on k elements or all product distributions on {0, 1}d (that is, distributions on d-bit strings for which the individual binary entries are independent). Our aim in formulating Definition 1.1 was to capture the weakest reasonable task that abstracts the goal of generating data with the same distributional properties as the input data. Without any privacy constraints, this task is trivial to achieve: an algorithm that simply outputs its first input record will sample from exactly the distribution P , so the interesting problem is to generate a sample of size m > n when given only n observations (as in the work of Axelrod et al. [4], which inspired our investigation). However, a differentially private algorithm cannot, in general, simply output one of its records in the clear. Even producing a single correctly distributed sample is a non-trivial task.
To understand the task and compare our results to existing work, it is helpful to contrast our definition of sampling with the more stringent goal of learning a distribution. A learning algorithm gets input in the same format as a sampling algorithm. We state a definition of distribution learning formulated with a single parameter α that captures both the distance between distributions and the failure probability. Definition 1.2 (Distribution learning). An algorithm B learns a distribution class C to within error α if, given a dataset consisting of independent observations from a distribution P ∈ C, algorithm B outputs a description of a distribution that satisfies
Pr X ∼i.i.d.P
coins of B
( dTV (B(X), P ) ≤ α ) ≥ 1− α.
An algorithm B that learns class C to within error α immediately yields a 2α-accurate sampler for class C: the sampler first runs B to get a distribution P̂ and then generates a single sample from P̂ . Thus, it is instructive to compare bounds on the dataset size required for sampling to known results on the sample complexity of distribution learning. Lower bounds for sampling imply lower bounds for all more stringent tasks, including learning, whereas separations between the complexity of sampling and that of learning suggest settings where weakening the learning objective might be productive.
Differential privacy Differential privacy is a constraint on the algorithmA that processes a dataset. It does not rely on any distributional property of the data. We generally use uppercase letters (e.g., X = (X1, ..., Xn)) when viewing the data as a random variable, and lowercase symbols (e.g., x = (x1, ..., xn)) when treating the data as fixed. Two datasets x,x′ ∈ Un are neighbors if they differ in at most one entry. If each entry corresponds to the data of one person, then neighboring datasets differ by replacing one person’s data with an alternate record. Informally, differential privacy requires that an algorithm’s output distributions are similar on all pairs of neighboring datasets. Definition 1.3 (Differential Privacy [15, 14]). A randomized algorithm A : Un → Y is (ε, δ)differentially private (in short, (ε, δ)-DP) if for every pair of neighboring datasets x,x′ ∈ Un and for all subsets Y ⊆ Y ,
Pr[A(x) ∈ Y ] ≤ eε · Pr[A(x′) ∈ Y ] + δ.
For ε ≤ 1 and δ < 1/n, this guarantee implies, roughly, that one can learn the same things about any given individual from the output of the algorithm as one could had their data not been used in the computation [19]. When δ = 0, the guarantee is referred to as pure differential privacy.

heading: 1.1 Our results
text: We initiate a systematic investigation of the sample complexity of differentially private sampling. We provide upper and lower bounds for the sample size needed for this task for three natural families of distributions: arbitrary distributions on [k] = {1, . . . , k}, arbitrary product distributions on {0, 1}d, and product distributions on {0, 1}d with bounded bias. We demonstrate that, in some parameter regimes, private sampling requires asymptotically fewer samples than learning a description of P nonprivately; in other regimes, however, sampling proves to be as difficult as private learning.
Our results are summarized in Table 1. Proofs of all results are included in the supplementary material. For simplicity, the table and our informal discussions focus on (ε, δ)-differential privacy (Definition 1.3) in the setting1 where δ = 1/nc for some constant c > 1.
Let Ck be the class of k-ary distributions (that is, distributions on [k]). We show that n = Θ ( k αε ) observations are necessary and sufficient for differentially private sampling from Ck in the worst case. Theorem 1.4. For all k ≥ 2, ε > 0, and α ∈ (0, 1), there exists an (ε, 0)-DP sampler that is α-accurate on the distribution class Ck for datasets of size n = O( kαε ). Theorem 1.5. For all k ≥ 2, n ∈ N, α ∈ (0, 150 ], ε ∈ (0, 1], and δ ∈ (0, 1 5000n ], if there is an ( , δ)-DP sampler that is α-accurate on the distribution class Ck on datasets of size n, then n = Ω ( k αε ) .
The second major class we consider consists of products of d Bernoulli distributions, for d ∈ N. We denote this class by B⊗d. Each distribution in B⊗d is described by a vector (p1, ..., pd) ∈ [0, 1]d of d probabilities, called biases; a single observation in {0, 1}d is generated by flipping d independent coins with respective probabilities p1, ..., pd of heads. We show that n = Θ̃ ( d )
observations are necessary and sufficient for differentially private sampling from B⊗d in the worst case. Theorem 1.6. For all d, n ∈ N and , δ, α ∈ (0, 1), there exists an ( , δ)-DP sampler that is α-accurate on the distribution class B⊗d for datasets of size n = Õ ( d α ) , assuming log(1/δ) = poly(log n).
Theorem 1.7. For all sufficiently small α > 0, and for all d, n ∈ N, ε ∈ (0, 1], and δ ∈ [ 0, 15000n ] , if there is an (ε, δ)-DP sampler that is α-accurate on the distribution class B⊗d on datasets of size n, then n = Ω(d).
Finally, we give better samplers and matching lower bounds for Bernoulli distributions and, more generally, products of Bernoulli distributions, with bias bounded away from 0 and 1. For simplicity,
1This setting precludes trivial solutions (which are possible when δ = Ω(1/n)), but allows us to treat factors of log(1/δ) as logarithmic in n and absorb them in Õ expressions.
we consider distributions with bias pj ∈ [ 13 , 2 3 ] in each coordinate j ∈ [d]. For this class, we show
that differentially private sampling can be performed with datasets of size roughly √ d/ε, significantly smaller than in the general case. Curiously, the accuracy parameter α has almost no effect on the sample complexity. For Bernoulli distributions with bounded bias, we achieve this with pure differential privacy, that is, with δ = 0. For products of Bernoulli distributions, we need δ > 0. Theorem 1.8. For all d ∈ N and , δ, α ∈ (0, 1), there exists an (ε, δ)-DP sampler that is αaccurate on the class of products of d Bernoulli distributions with biases in [ 1 3 , 2 3 ] for datasets of size
n = O (√ d log(1/δ)
ε + log d α ) . When d = 1, the sampler has δ = 0 and n = O( 1ε + log 1 α ).
Theorem 1.9. For all sufficiently small α > 0, and for all d, n ∈ N, ε ∈ (0, 1], and δ ∈ [0, 1100n ], if there exists an (ε, δ)-DP sampler that is α-accurate on the class of products of d Bernoulli distributions with biases in [ 1 3 , 2 3 ] on datasets of size n, then n = Ω( √ d/ε).
Implications Our results show that the sample complexity of private sampling can differ substantially from that of private learning (for which known bounds are stated in Table 1). In some settings, sampling is much easier than learning: for example, for products of Bernoulli distributions with bounded biases, private sampling has a lower dependence on the dimension (specifically, √ d instead of d) and essentially no dependence on α. Even for arbitrary biases or arbitrary k-ary distributions, private sampling is easier when α ε. In other settings, however, private sampling can be as hard as private learning: e.g., for ≤ α, the worst-case complexity of sampling and learning k-ary distributions and product distributions is the same.
A more subtle point is that, in settings where private sampling is as hard as private learning, sampling accounts for the entire cost of privacy in learning. Specifically, the optimal sample complexity of differentially private learning for arbitrary k-ary distributions is n = Θ ( k α2 + k αε ) (e.g., see [3,
Theorem 13]). This bound is the sum of two terms: the sample complexity of nonprivate learning (Θ ( k α2 ) ) plus a term to account for the privacy constraint (Θ ( k αε ) ). One interpretation of our
result that private sampling requires n = Θ ( k αε ) observations is that the extra privacy term in the complexity of learning can be explained by the complexity of privately generating a single sample with approximately correct distribution.
Another implication of our results is that, in some settings, the distributions that are hardest for learning—nonprivate or private—are the easiest for sampling, and vice versa. Consider the simple case of Bernoulli distributions (i.e., product distributions with d = 1). The “hard” instances for nonprivate learning to within error α are distributions with bias p = 1±α2 , but private sampling is easiest in that parameter regime. In contrast, the “hard” instances in our Ω( 1αε ) lower bound for Bernoulli distributions have bias 10α, that is, close to 0 as opposed to close to 1/2. A simple variance argument shows that nonprivate learning is easy in that parameter regime, requiring only O( 1α ) observations. Similarly, for product distributions, we show that the complexity of private sampling is only Θ̃( √ d) when biases are bounded away from 0 and 1. For the same class, however, the complexity of private and nonprivate learning is Θ(d).
Our final point is that our lower bounds for k-ary distributions and general product distributions only require that the sampler generate a value in the support of the distribution with high probability. They thus apply to a weaker problem, similar in spirit to the interior point problem that forms the basis of lower bounds for private learning of thresholds [9].
Taken together, our results show that studying the complexity of generating a single sample helps us understand the true source of difficulty for certain tasks and sheds light on when we might be able to engage in nontrivial statistical tasks with very little data.
Limitations of our results and open questions Our work raises many questions about the complexity of private sampling. First, our upper bounds achieve only the minimal goal of generating a single observation. In most settings, one would presumably want to generate several such samples. One can do so by repeating our algorithms several times on disjoint subsamples, but in general this is not the best way to proceed. Second, we study only three classes of distributions. It is likely that the picture of what is possible for many classes is more complex and nuanced. It would be interesting, for example, to study private sampling for Gaussian distributions, since they demonstrate intriguing data/accuracy tradeoffs for nonprivate sampling [4].
Societal impact We study the feasibility of basic inference under privacy constraints. Our work is motivated by societal concerns, but focused on fundamental theoretical limits. We do not anticipate direct practical impact.

heading: 1.2 An overview of our proofs and techniques
text: For both algorithms and lower bounds, our results require the development of new techniques. On the algorithmic side, we take advantage of the fact that sampling algorithms need only be correct on average over samples drawn from a given distribution. One useful observation that underlies our positive results is that sampling based on an unbiased estimate P̂ of a probability distribution P (in the sense that E[P̂ (u)] = P (u) for all elements u in the universe U , where the expectation is taken over the randomness in the dataset and the coins of the algorithm) has zero error, even though the learning error, e.g., dTV (P̂ , P ) might be large. For product distributions with bounded biases, we also exploit the randomness of the sampling process itself to gain privacy without explicitly adding noise.
For negative results, we cannot generally use existing lower bounds for learning or estimation, because of a fundamental obstacle. The basic framework used in proving most lower bounds on sample complexity of learning problems is based on identifiability: to show that a large sample is required to learn class C, one first finds a set of distributions P1, ...., Pt in the class C that are far apart from each other and then shows that the output of any sufficiently accurate learning algorithm allows an outside observer to determine exactly which distribution in the collection generated the data. The final step is to show that algorithms in a given family (say, differentially private algorithms with a certain sample size) cannot reliably identify the correct distribution. This general approach is embodied in recipes such as Fano’s, Assouad’s, and Le Cam’s methods from classical statistics (see, e.g., [3] for a summary of these methods and their differentially private analogues). For many sampling problems, the identifiability approach breaks down: a single observation is almost never enough to identify the originating distribution.
One of our approaches to proving lower bounds is to leverage ways in which the algorithm’s output directly signals a failure to sample correctly. For instance, our lower bound for k-ary distribution relies on the fact that an α-accurate sampler must produce a value in the support of the true distribution P with high probability. Another approach is to reduce from other distribution (sampling or estimation) problems. For example, our lower bound for product distributions with bounded biases is obtained via a reduction from an estimation problem, by observing that a small number of samples from a nearby distribution suffices for a very weak estimate of the underlying distribution’s attribute biases.
We break down our discussion of techniques according to the specific distribution classes we consider.
Distributions on [k] For the class of distributions on [k], Theorem 1.4 shows that α-accurate (ε, 0)- differently private sampling can be performed with a dataset of size O( kαε ). Our private sampler computes, for each j ∈ [k], the proportion P̂j of its dataset that is equal to j, adds Laplace noise to each count, uses L1 projection to obtain a valid vector of probabilities P̃ = (P̃1, . . . , P̃k), and finally outputs an element of [k] sampled according to P̃ .
Theorem 1.5 provides a matching lower bound on n that holds for all (ε, δ)-differentially private algorithms with δ = o(1/n). We prove our lower bound separately for Bernoulli distributions and for discrete distributions with support size k ≥ 3, using different analyses. For Bernoulli distributions, we first exploit the group privacy for differentially private algorithms and the fact that the sampler must be accurate for the Bernoulli distribution Ber(0) to show that, on input with t ones, a differentially private sampler outputs 1 with probability at most 2αeεt. Then we consider P = Ber(10α). We use α-accuracy in conjunction with group privacy to give a lower and an upper bound on the probability of the output being 1 when the input is drawn i.i.d. from P . This allows us to relate the parameters involved in order to obtain the desired lower bound on n.
The lower bound for distributions on [k] with k ≥ 3 is more involved. We start by identifying general properties of samplers that allow us to restrict our attention to relatively simple algorithms. First, we observe that every sampler can be converted to a Poisson algorithm, that is, an algorithm that, instead of receiving an input of a fixed size, gets an input with the number of records that follows a Poisson distribution. This observation allows us to use a standard technique called Poissonization that
makes the empirical frequencies of different elements independent. Next, we observe that privacy for samplers can be easily amplified, so that we can assume w.l.o.g. that ε is small. Finally, we observe that every sampler for the class of k-ary distributions can be converted to a frequency-countbased algorithm. A sampler is frequency-count-based if the probability it outputs a specific element depends only on the number of occurrences of this element in its input and the frequency counts2 of the input (that is, the number of elements that occur zero times, once, twice, thrice, and so on). Frequency-count-based algorithms have been studied for a long time in the context of understanding properties of distributions (see, e.g., [5, 6, 20]).
Equipped with the three observations, we restrict our attention to Poisson, frequency-count-based algorithms, with small ε in the privacy guarantee. In contrast to our lower bound for Bernoulli samplers, we show that when the support size is at least 3 and the dataset size, n, is too small, the sampler is likely to output an element outside of the support of the input distribution P. Here, we exploit group privacy, which implies that the probability that a sampler outputs a specific element which appears j times in its input differs by at most a factor of eεj from the probability that it outputs a specific element that does not appear in the input. Then we consider a distribution P that has most of its mass (specifically, 1−O(α)) on a special element, and the remaining mass spread uniformly among half of the remaining domain elements. That is, P is a mixture of a unit distribution on the special element and a uniform distribution on half of the remaining elements. We show that, when the dataset size is too small, the sampler is nearly equally likely to output any non-special element. But it has to output non-special elements with probability Ω(α) to be α-accurate. This means that when the database size is too small, the sampler outputs a non-special element outside the support of P with probability Ω(α). The details of the proof are quite technical and appear in Section 2.
Product distributions Our private sampler for product distributions over {0, 1}d, used to prove Theorem 1.6, builds on the recursive private preconditioning procedure designed by Kamath et al. [17] for learning this distribution class. In our case, the sampler gets a dataset of size which is asymptotically smaller than necessary for learning this distribution class in some important parameter regimes. Let (p1, . . . , pd) be the attribute biases for the product distribution P from which the data is drawn. For simplicity, assume w.l.o.g. that all the marginal biases pj are less than 1/2. The main idea in [17] is that smaller biases have lower sensitivity in the following sense: if we know that a set of attributes has biases pj that are all at most some bound u then, since the data is generated from a product distribution, the number of ones in those attributes should at most 2ud with high probability. We can enforce this bound on the number of ones in those coordinates by truncating each row appropriately, and thus learn the biases of those coordinates to higher accuracy than we knew before. Building on that idea, we partition the input into smaller datatsets and run our algorithm in rounds, each using fresh data, a different truncation threshold, and noise of different magnitude.
Our algorithm consists of two phases. In the bucketing phase, we use half of the dataset and the technique of [17] to get rough multiplicative estimates of all biases pj except the very small ones (where pj < 1/d). This allows us to partition the coordinates into log(d) buckets, where biases within each bucket are similar. We show this crude estimation only requires n = Õ(d/αε). In the sampling phase, we use the buckets to generate our output sample. For each bucket, we can get a fresh estimate of the biases using the other half of the dataset and, again, the technique from [17] to scale the noise proportionally to the upper bound on the biases that bucket. These estimates are essentially unbiased. Flipping d coins independently according to the estimated biases produces an observation with essentially the correct distribution.
The proof of our lower bound for general product distributions proceeds via reduction from sampling of k-ary distributions for k = d. In contrast, lower bounds for private learning of product distributions rely on fingerprinting codes (building on the framework of Bun et al. [10]). Although fingerprinting codes are indeed useful when reasoning about samplers for distributions with bounded biases (discussed below), our approach relies, instead, on the fact that samplers must distinguish coordinates with bias 0 from coordinates with small bias. Specifically, given a distribution P on [2k] that is uniform on a subset of [2k] of size k, we define a product distribution P ′ on {0, 1}2k with biases pj = P (j) = 1k for j ∈ S and pj = 0 otherwise. We use Poissonization and coupling between Poisson and binomial distributions to design a reduction that, given observations from P , first creates an appropriately distributed sample of almost the same size drawn according to P ′, then runs a
2The vector of frequency counts is called a fingerprint or a histogram in previous work.
hypothetical sampler for product distributions to get a vector in {0, 1}2k (drawn roughly according to P ′), and finally converts that vector back to a single element of [2k] distributed roughly as P . The details are subtle since most draws from P ′ will not have exactly one nonzero element—this complicates conversion in both directions.
Distributions with bounded bias Interestingly, our sampler for product distributions with bounded bias does not directly add noise to data. It performs the following step independently for each attribute: compute the empirical mean of the sample in that coordinate, obtain the clipped mean by rounding the empirical mean to the interval [1/4, 3/4], and sample a bit according to the clipped mean. The key idea in the analysis of accuracy is that, conditioned on no rounding (that is, the empirical mean already being in the required interval), the new bit is sampled from the correct distribution, and rounding occurs with small probability. We argue that this sampler is (4/n, 0)-differentially private for the case when d = 1. For larger d, the sampler is a composition of d differentially private algorithms, and the main bound follows from compositions theorems (and conversions between different variants of differential privacy).
The lower bound for this class proceeds by a reduction from the following weak estimation problem: Given samples from a product distribution with biases p1, p2, ..., pd, output estimates p̃1, ..., p̃d such that each p̃i is within additive error 120 of pi, that is, |p̃i − pi| ≤ 1 20 , with probability at least 1− 1 20 (where 120 is just a sufficiently small constant). This problem is known to require datasets of size Ω̃( √ d) for differentially private algorithms [10]. However, nonprivate algorithms require only O(1) data records to solve this same problem! We can thus reduce from estimation to sampling with very little overhead: Given a private sampler, we run it a constant number of times on disjoint datasets to obtain enough samples to (nonprivately) estimate each of the pi’s. The nonprivate estimation is a postprocessing of an output of a differentially private algorithm, so the overall algorithm is differentially private. Some care is required in the reduction, since we must ensure that the nonprivate estimation algorithm is robust (i.e., works even when the samples are only close in TV distance to the correct distribution) and that the lower bound of [10] applies even when the biases pi lie in [ 13 , 2 3 ].

heading: 1.3 Related work
text: To the best of our knowledge, the private sampling problem we formulate has not been studied previously. There is work on nonprivate sample-size amplification, in which an initial dataset of n records is used to generate an output sample of size n′ > n from a nearby distribution [4]. Our formulation corresponds to the case where n′ = 1 n. There is also work on sampling (also called simulation) in a distributed setting [1, 2] where each of n participants receives a single observation and is limited to ` ≥ 1 bits of communication. We are not aware of a direct technical connection with our work, even though the distributed setting is closely tied to that of local differential privacy.
In the literature on differential privacy, there is work on private algorithms for sampling parameters from Bayesian posterior distributions [12, 13, 24, 22], often driven by the intuition that the randomness inherent in sampling provides some level of privacy “for free”. Our algorithms for product distributions with bounded biases leverage a similar idea. We are not aware of any analysis of the Bayesian approach which provides guarantees along the lines of our formulation (Def. 1.1).
The most substantially related work in the privacy literature is on upper and lower bounds for learning and estimation tasks, dating back to Warner [23] (see [16, 18] for partial surveys). For learning k-ary distributions, the directly most relevant works are those of [11, 3], though lower bounds for estimating histograms were known as folklore since the mid-2000s. For product distributions, tight upper and lower bounds for (ε, δ)-differentially private estimation in TV distance appear in [17]; the upper bound was later shown to be achievable by an (ε, 0)-differentially private algorithm [8]. Our upper bound for general product distributions adapts the technique of [17]; it remains open whether our bound is achievable with δ = 0.
Less directly related is the line of work on the generation of synthetic datasets that match the data distribution in a set of specified characteristics, such as linear queries (e.g., [7]; see [21] for a tutorial). The goal in those works is to generate enough synthetic data to allow an analyst given only the output to estimate the specified characteristics—a much more difficult task than sampling, and one for which a different set of lower bound techniques apply [21].
2 The lower bound for k-ary distributions
In this section, we prove the lower bound for sampling from discrete distributions with the universe of size at least 3. As discussed in Section 1.2, we prove that n = Ω(k/αε). The crux of the proof is the case where the sampler is frequency-count-based, Poisson, and is (ε, δ)-DP for small ε. The transformation from general samplers to this restricted type of sampler is presented in the supplementary materials. This transformation together with the following Lemma 2.1 completes the proof of Theorem 1.5 for discrete distributions with the universe of size at least 3. Lemma 2.1. Fix k, n ∈ N, α ∈ (0, 0.02], ε ∈ (0, 1/ ln(1/α)], and δ ∈ [0, 0.1αε/k]. Let C2k+1 denote the class of discrete distributions over the universe [2k + 1]. If sampler A is (ε, δ)-DP, frequency-count-based, and α-accurate on class C2k+1 with dataset size distributed as Po(n), then n > 160 · k αε .
Proof. We consider the following distribution P over the universe U = [2k + 1]. Fix α∗ = 60α and a set S∗ ⊂ [2k] of size k. Distribution P has mass α∗/k on each element in S∗ and mass 1− α∗ on the special element 2k + 1.
Consider a samplerA satisfying the conditions of Lemma 2.1. LetQA,P denote the output distribution of A when the dataset size N ∼ Po(n) and the dataset X ∼ P⊗N . Observe that
dTV (QA,P , P ) ≥ Pr N∼Po(n) X∼P⊗N [A(X) /∈ Supp(P )]. (1)
We show that if n ≤ k60αε and ε and δ are in the specified range, the right-hand side of (1) is large. We start by deriving a lower bound on Pr[A(x) /∈ Supp(P )] for a fixed dataset x of a fixed size N . Let pj,F (x) be the probability that A outputs a specific element in [2k] that occurs j times in x, where F (x) is the frequency-count of x; these probabilities are well-defined because A is frequency-count-based. Let F ∗0 (x) denote the number of elements in [2k] that occur 0 times in x (excluding the special element 2k + 1 from this count). By definition, F ∗0 (x) ≤ 2k. Consequently,
Pr[A(x) /∈ Supp(P )] = k · p0,F (x) ≥ 1
2 · F ∗0 (x) · p0,F (x). (2)
The next claim uses the fact that A is (ε, δ)-DP to show that the probability pj,F (x) cannot be much larger than the probability that A outputs a specific element in U that does not appear in x. Claim 2.2. For all (ε, δ)-DP samplers, frequency counts f ∈ Z∗, and elements j ∈ U ,
pj,f ≤ eεj ( p0,f + δ
ε
) . (3)
Proof. Consider a frequency count f and a dataset x with F (x) = f . Note that (3) is true trivially for all j such that Fj(x) = 0 because, in that case, pj,F (x) is set to 0.
Fix any j ∈ U with Fj(x) > 0. Let a be any element in U that occurs j times in the dataset x. Let b be any element in U that is not in the support of the distribution P . Let x|a→b denote the dataset obtained by replacing every instance of a in the dataset x with element b. By group privacy [15],
Pr[A(x) = a] ≤ ejε Pr[A(x|a→b) = a] + δ · eεj − 1 eε − 1 . (4)
Note that the dataset x|a→b does not contain element a, since we’ve replaced every instance of it with b. Importantly, F (x|a→b) = F (x) because b is outside of the support of the distribution P and hence does not occur in x. Since A is frequency-count-based and F (x) = F (x|a→b), we get that p0,F (x) = p0,F (x|a→b). Substituting this into (4) and using the fact that e ε − 1 ≥ ε for all ε, we get
pj,F (x) ≤ ejε · p0,F (x) + δ · eεj − 1 eε − 1
≤ eεj ( p0,f + δ
ε
) .
This completes the proof of Claim 2.2.
For a dataset x and i ∈ [2k+ 1], let Ni(x) denote the number of occurrences of element i in x. Next, we give a lower bound on Pr[A(x) /∈ Supp(P )] in terms of the counts Ni(x).
Claim 2.3. Let N ∈ N and x ∈ [2k + 1]N be a fixed dataset. Set Y = ∑ i∈S∗ [ eNi(x)ε ] . Then
Pr[A(x) /∈ Supp(P )] ≥ 1 2 · Pr[A(x) ∈ [2k]] 1 + Y/k − kδ ε .
Proof. In the following derivation, we use the fact that that an element j ∈ [2k] that appears j times in x is returned by A with probability pj,F (x), then split the elements into those that do not appear in x and those that do, next use the fact that all elements from [2k] that appear in x must be in S∗, then apply Claim 2.2, and finally substitute Y for ∑ i∈S∗ [ eNi(x)ε ] :
Pr[A(x) ∈ [2k]] = ∑ i∈[2k] pNi(x),F (x) = F ∗ 0 (x) · p0,F (x) + ∑ i∈[2k]∩x pNi(x),F (x)
≤ F ∗0 (x) · p0,F (x) + ∑ i∈S∗ pNi(x),F (x)
≤ F ∗0 (x) · p0,F (x) + ∑ i∈S∗ p0,F (x) · ( eεNi(x) + δ ε ) ≤ ( F ∗0 (x) + Y )( p0,F (x) + δ ε ) .
We rearrange the terms to get p0,F (x) ≥ Pr[A(x) ∈ [2k]] F ∗0 (x) + Y − δ ε .
Substituting this bound on p0,F (x) into (2), we obtain that Pr[A(x) /∈ Support(P )] is at least
1 2 · F ∗ 0 (x) Pr[A(x) ∈ [2k]] F ∗0 (x) + Y − 1 2 · F ∗ 0 (x) · δ ε ≥ 1 2 · Pr[A(x) ∈ [2k]] 1 + Y/k − kδ ε ,
where in the inequality, we used that k ≤ F ∗0 (x) ≤ 2k. This holds since the support of P excludes k elements from [2k] and since F ∗0 (x) counts only elements from [2k] that do not appear in x.
Finally, we give a lower bound on the right-hand side of (1). Assume for the sake of contradiction that n ≤ kα∗ε . By Claim 2.3,
Pr N,X [A(X) /∈ Supp(P )] ≥ E N,X [1 2 · Pr[A(X) ∈ [2k]] 1 + Y/k − kδ ε ] = 1
2 · E N,X [Pr[A(X) ∈ [2k]] 1 + Y/k ] − kδ ε . (5)
Next, we analyze the expectation in (5). Let E be the event that Yk ≤ e 3. By the law of total expectation,
E N,X [Pr[A(X) ∈ [2k]] 1 + Y/k ] ≥ E N,X [Pr[A(X) ∈ [2k]] 1 + Y/k ∣∣E]Pr(E). (6) In Claims 2.4 and 2.5, we argue that both Pr(E) and EN,X [ Pr[A(X)∈[2k]]
1+Y/k ∣∣E] are large. Claim 2.4. Suppose n ≤ k60αε . Let E be the event that Y k ≤ e 3. Then Pr(E) ≥ 1− α. Proof. Recall that Y was defined as ∑ i∈S∗ [ eNi(x)ε ] for a fixed dataset x. Now consider the case when dataset X is a random variable. If N ∼ Po(n) and X ∼ P⊗N then Ni(X) ∼ Po(α ∗n k ) for all i ∈ S∗ and, additionally, the random variables Ni(X) are mutually independent. When X is clear from the context, we write Ni instead of Ni(X). Now we calculate the moments of Yk . For all λ > 0,
E N∼Po(n) X∼P⊗N
[(Y k )λ] = E N∼Po(n) X∼P⊗N [(1 k ∑ i∈S∗ eNi(X)ε )λ] = E N1,··· ,Nk∼Po(α ∗n k ) [(1 k ∑ i∈S∗ eNiε )λ] . (7)
Finally, we bound the probability of event E. Set c = e3 and λ = ln 1α . By definition of E,
Pr(E) = Pr (Y k ≥ c ) = Pr ((Y k )λ ≥ cλ ) ≤ 1 cλ · E N∼Po(n) X∼P⊗N [(Y k )λ] ≤ 1 cλ · E N1,··· ,Nk∼Po(α ∗n k ) [(1 k ∑ i∈S∗ eNiε )λ] ≤ 1 cλ · E N1∼Po(α ∗n k ) [( eN1ε )λ] (8)
= c−λ · eα ∗n k (e λε−1) ≤ e−3λ · e (eλε−1) ε ≤ e−3λ · e2λ = e−λ = e− ln(1/α) = α, (9)
where we use λ > 0 in the second equality, then apply Markov’s inequality. To get the inequalities in (8), we apply (7) and then use the fact that the moments of the average of random variables is less than the moment of a single random variable (the proof of this fact is in the supplementary material). To get (9), we use the moment generating function of a Poisson random variable, and then we substitute c = e3 and use the assumption that n ≤ k60αε = k α∗ε . The second inequality in (9) holds because λ = ln 1α and ε ∈ (0, 1/ ln 1 α ], so λε ≤ 1 and hence e
λε ≤ 1 + 2λε. The final expression is obtained by substituting the value of λ. We get that Pr(E) ≥ 1− α, completing the proof of Claim 2.4.
Claim 2.5. E N∼Po(n) X∼P⊗N
[Pr[A(X) ∈ [2k]] 1 + Y/k ∣∣E] ≥ 2.3α. Proof. When event E occurs, 1 + Yk ≤ 1 + e 3 < 22. Then
E N,X [Pr[A(X) ∈ [2k]] 1 + Y/k ∣∣E] > E N,X [Pr[A(X) ∈ [2k]] 22 ∣∣E] = 1 22 · E N,X [ Pr[A(X) ∈ [2k]] | E ] .
(10)
By the product rule,
Pr[A(X) ∈ [2k]] | E] = Pr[A(X) ∈ [2k]] ∧ E] Pr[E] ≥ Pr[A(X) ∈ [2k]]∧E] ≥ Pr[A(X) ∈ [2k]]− Pr[E].
Substituting this into (10) and recalling that α∗ = 60α, we get
E N,X [Pr[A(X) ∈ [2k]] 1 + Y/k ∣∣E] ≥ 1 22 · E N,X [ Pr[A(X) ∈ [2k]]− Pr[E] ] ≥ 1 22 · ( α∗ − α− α ) ≥ 2.3α,
since sampler A is α-accurate on P , and P has mass α∗ on [2k], and by Claim 2.4.
Combining (1), (5), and (6), applying Claims 2.4 and 2.5, and recalling that δ ≤ 0.1 · αε/k, we get
dTV (P,QA,P ) ≥ Pr N,X [A(X) /∈ Supp(P )] ≥ 1 2 · E N,X [Pr[A(X) ∈ [2k]] 1 + Y/k ] − kδ ε
≥ 1 2 · E N,X [Pr[A(X) ∈ [2k]] 1 + Y/k ∣∣E]Pr(E)− 0.1α ≥ 1 2 · 2.3α · ( 1− α ) − 0.1α > α,
where the last inequality holds since α ≤ 0.02. This contradicts α-accuracy of A on datasets of size Po(n), where n ≤ kα∗ε , and completes the proof of Lemma 2.1.
Acknowledgments and Disclosure of Funding
We are grateful for helpful conversations with Clément Canonne, Thomas Steinke, and Jonathan Ullman. Sofya Raskhodnikova was partially supported by NSF award CCF-1909612. Satchit Sivakumar was supported in part by NSF award CNS-2046425, as well as Cooperative Agreement CB20ADR0160001 with the Census Bureau. Adam Smith and Marika Swanberg were supported in part by NSF award CCF-1763786 as well as a Sloan Foundation research award. The views expressed in this paper are those of the authors and not those of the U.S. Census Bureau or any other sponsor.

Review summaries:
The paper studies the problem of sampling from a distribution in a differentially private manner.  More formally, the learner is given i.i.d samples from some unknown distribution $P$ over a domain $\mathcal{U}$ and its goal is to output an element of $\mathcal{U}$ such that the distribution of the output is close to $P$ in TV distance.  The problem of sampling is easier than the problem of learning the actual distribution $P$ and the authors show that in some cases it can be done using significantly fewer samples.   The main results are that for arbitrary discrete distributions over $k$, the sample complexity of differentially private sampling is $\theta(k/(\alpha \epsilon))$ (compared to $k/\alpha^2$ for learning and $k/\alpha^2 + k/(\alpha \epsilon)$ for private learning where $\alpha$ is the desired accuracy and $\epsilon$ is the privacy parameter).  For product distributions on $\{ 0,1 \}^d$, the main result is an upper bound of $\widetilde{O}(d/(\alpha \epsilon))$ although this can be improved to $\sqrt{d}/\epsilon + \log (1/\alpha)$ if the coordinates have means bounded away from $0$ and $1$. 

The paper initiates the study of the following sampling problem under privacy: we are given n samples from a (discrete) distribution P, and want to output a (random) value x such that the distribution of the value we output (over the randomness of the samples and the coins of our algorithm) has small total variation distance (TVD) with P. The problem is trivial normally, since the first sample we are given is distributed exactly according to P. When we are concerned with privacy of the samples, i.e. want to output a value x with approximate differential privacy (viewing the n samples as a database), outputting the first sample is non-private, and the problem is more interesting. The motivation for studying this task, is that it is a weaker version of the problem of learning the distribution P (if we learn an approximation of the distribution, we can clearly approximately sample from it).  The authors consider the problem in three settings: When the support of P is [k], when P is a product distribution on the d-dimensional hypercube (i.e. each bit is independent Bernoulli, not necessarily identically distributed), and the distribution over the hypercube but when each coordinate is a Bernoulli with mean in [1/3, 2/3]. They show lower and upper bounds for each problem when delta = 1/n^c for some constant c > 1. For distributions on [k], the authors show matching upper and lower bounds of needing k/alpha*eps to get a sampler within TVD alpha. For product distributions on hypercubes, they show d/alpha*eps samples suffice, but the lower bound is sqrt(d). The authors are able to match this bound, obtaining TVD alpha with sqrt(d)/epsilon + log (d/alpha) samples when the coordinates are Bernoulli with mean close to 1/2.  In addition to quantitative results, the sample complexities shed some light on the problem of learning P rather than outputting a sample from P. In particular, the best upper bounds for private learning match the sum of upper bounds for nonprivate learning and the upper bounds for private sampling given in this paper. The authors' results also show that e.g. in the Bernoulli/hypercube setting, the regime where sampling is easiest is the regime where learning is hardest and vice-versa.

This paper initiates an algorithmic study of how to make sampling from discrete distributions private. The formulation is as follows: Given $n$ independent samples from a discrete distribution $P$ over a universe $U$,  output one sample $y$ whose distribution is close to $P$ in total variation distance.  The efficiency goal is to make the number of samples $n$ as small as possible. This appears to be a trivial task - just output any one sample from the input. However, if we require the algorithm to be differentially private then the task is non-trivial and this is the concern of the paper. The paper first considers the problem of private sampling for general distributions over a domain of size $k$ and establishes matching upper and lower bounds on the sample complexity. Then it considers private sampling from product of Bernoulli distributions and establishes upper and lower bounds. In this case, the complexity is not yet completely clear as there is a gap in their bounds. 

The paper considers the following question: say you observe n data points, drawn iid from some distribution p, and you know that p belongs to some class of distributions P, then how large does n have to be such that you can use the data to generate a single new point that is close in total variation distance to the underlying distribution p, while being differentially private? In the paper, this question is referred to as the sample complexity of differentially private sampling.  The paper then investigates this question for two classes of distributions: any distribution supported on k points, and product distributions on {0,1}^d. It shows that for all the settings, the sample complexity of differentially private sampling is a lower bound for the sample complexity of differentially private learning, and that in some settings, the sample complexity for sampling is strictly smaller than that of learning.