Differentially Private Sampling from Distributions
Authors: Sofya Raskhodnikova
Satchit Sivakumar
Adam Smith
Marika Swanberg
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
Distribution Estimation
Distribution Learning

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,\ldots ,k\}$, arbitrary product distributions on $\{0,1\}^d$, and product distributions on on $\{0,1\}^d$ 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.

Differentially Private Sampling from Distributions
Sofya Raskhodnikova Department of Computer Science Boston University sofya@bu.. edu
Satchit Sivakumar Department of Computer Science Boston University satchit@bu. edu edu
Adam Smith Department of Computer Science
Marika Swanberg Department of Computer Science Boston University marikas@bu. edu
Boston University ads220bu. edu
Abstract
We initiate an investigation of private sampling from distributions. Given dataset with n independent observations from an unknown distribution P, a sampling algorithm must output single observation from a distribution that is close in total variation distance 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 {l...., ,,, k}. arbitrary product distributions {0, 1 and product distributions
{0, 1) with bias in each coordinate bounded away from 0 and We demonstrate that, in some parameter regimes, private sampling requires asymptotically fewer observations than learning a description of nonprivately; in other regimes, however, private sampling proves to be difficult private learning. Notably, for some classes of distributions, the overhead in the number of observations needed for private learning compared non-private learning is completely captured by the number of observations needed for private sampling.
Introduction
Statistical machine learning models trained sensitive data 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 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 algo- rithm's 's output would be roughly the same whether not that individual's I's record was actually part of the input dataset. This requirement entails a strong guarantee, but limits the design of algorithms significantly. As result, there is substantial line of work 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 description of distribution Q that is close to P.
However, often the task at hand requires much less than full-fledged learning. to generate 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 software program or for getting a quick idea of the range of values in dataset.
may simply need
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this work, we study basic problem that captures these seemingly less stringent aims, Informally. the goal design sampling algorithm that, given dataset with n observations drawn i.idd from a distribution P. generates a single observation from distribution Q that is close to P.
To formulate the problem precisely, consider randomized algorithm A 21 -> 14 that takes as input a dataset of n records from some universe U and outputs single element of Ut Given a distribution P on U, let X (..,).. 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 algorithm A 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.((z) = Pr (A(X)=2)
Σ (PI(X=x) XEU
Pr coins of
(A(x) = =2))
coins
The dataset size is a parameter of A and thus defined implicitly. We measure the closeness between the input and output distributions in total variation distance, denoted drv. Definition 1.1 (Accuracy of sampling [4]. A sampler A a-accurate on a distribution P if
drv P) S
A sampler is a-accurate on class C of distributions if it is a-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 & elements or all product distributions on {0. 1) (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. learning algorithm gets input in the same format as sampling algorithm. We state a definition of distribution learning formulated with a single parameter a that captures both the distance between distributions and the failure probability.
Definition 1.2 (Distribution learning). An algorithm B learns distribution class C to within error if, given a dataset consisting of independent observations from distribution P E C, algorithm ousputs description of distribution that satisfies
Pr (dTv P) X Knaad P coins of B
2))
An algorithm B that learns class C to within error a immediately yields 20-accurate sampler for class C: the sampler first runs B to get a distribution Î 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 constraint on the algorithm A that processes a dataset. does not rely on any distributional property of the data. We generally use uppercase letters (e.g..
X = (X,,.., X,))) when viewing the data as a random variable, and lowercase symbols (e.g.. x == (Ii, .) when treating the data as fixed. Two datasets x, x' E Utth 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 's output distributions are similar all pairs of neighboring datasets.
Definition 1.3 (Differential Privacy [15, 14I). A randomized algorithm A U + y is (c, differentially private (in short, (s, ()D)) for every pair of neighboring datasets x, x' E U and for all subsets Y C.),
Pr(A(x) Y] S e -Prr(((x') e

---

Table 1: Sample complexity of sampling and estimation tasks. Our negative results hold for (s, 6)- differential privacy when < 1/n. In this table, e I and 1/n for constant c > 1.
Distributions on
Product distributions {0, 1}
Product distributions
with 8-
Nonprivate learning
+
a²
o
Vd
(e, C)DP sampling
+
Ô
log
(this work)
Theorems 1.4, 1.5
Theorem 1.6
Theorem 1.8
((d)
Theorem 1.7
vd/e
Theorem 1.9
h
d
(s, 5)DD learning
θ + aE
m
117,8]
a
aD
For e S and 5 < 1/n, this guarantee implies, roughly, that one can learn the same things about any given individual from the output of the algorithm could had their data not been used in the computation [19]. When 8 = 0, the guarantee is referred to as pure differential privacy.
1.1 Our results
We initiate 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] {L..... k). arbitrary product distributions on {0, 1]dd and product distributions on {0, 1jd 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 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 (E, -ddifferennt privacy (Definition 1.3) in the setting' where 1/n² for some constant c
Let Cg be the class of k-ary distributions (that is, distributions [ε:). We show that O + observations are necessary and sufficient for differentially private sampling from C₁ in the worst case.
Theorem 1.4. For all 1 2 2, > O, and a (0, 1), there exists an (s, OPPD) sampler that a-accurate on the distribution class Ck for datasets of size n k)
Theorem 1.5. For all k 2 2, n E N, a E (0, 5/l E (0, 1]. and E (0, (00n)) if there is an (e, D) sampler that is a-accurate on the distribution class C2 on datasets of size n. then - (((
The second major class we consider consists of products of d Bernoulli distributions, for E N. We denote this class by g Each distribution in Bood is described by vector (p1.....Pdl [0, 1] of probabilities, called biases; a single observation in {0, 1)d is generated by flipping d independent coins with respective probabilities Pi.... Pa of heads. We show that n ((d) observations are necessary and sufficient for differentially private sampling from Bdd in the worst case.
Theorem 1.6. For all d, n E N and e, ô,a (0,1), there exists an (e, ()-D) sampler that is a-accurate on the distribution class Bod for datasets of size a Ō a assuming log(1/8) poly(logn).
Theorem 1.7. For all sufficiently small > O, for all d, n e N. (0, 1), and 8 E [0, 5000n J. if there is an (e, DDD sampler that is a-accurate on the distribution class Bdd on datasets of size n, then ()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,
'This setting precludes trivial solutions (which are possible when 8 ((1/x)), but allows us to factors of loggoo////// (1/0) as logarithmic in and absorb them in Ô expressions.
3

---

we consider distributions with bias Pj E 13 3] in each coordinate j E [d]. For this class, we show that differentially private sampling can be performed with datasets of size roughly vdje, 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 ō = O. For products of Bernoulli distributions, we need 8 >> 0.
Theorem 1.8. For all d E N and e, a E (0, 1), there exists an (E, 6)- sampler that is a- accurate on the class of products of d Bernoulli distributions with biases in [ 2] for datasets of size
n -00 (0 + log a. When d 1, the sampler has 8 0nd = O + +og 2.
Theorem 1.9. For all sufficiently small a > O, and for all d, n E N, E E (0, 1]. and ô E 10, ToomL if there exists (s, dDDP sampler that is a-accurate on the class of products of d Bernoulli distributions with biases in [31 3] on datasets of size n, then n n(Vd/s).
Implications Our results show that the sample complexity of private sampling can differ substan- tially from that of private learning (for which known bounds 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, v instead of d) and essentially no dependence on a. Even for arbitrary biases or arbitrary k-ary distributions, private sampling is easier when a < 6. In other settings, however, private sampling can be as hard as private learning: e.g., for S a, 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 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 n = O & + as (e.g., see [3, a
Theorem 13)). This bound is the sum of two terms: the sample complexity of nonprivate learning (9 (+x) )) plus a term to account for the privacy constraint (0 (())) ). One interpretation of our result that private sampling requires complexity of learning can be explained by the complexity of privately generating a single sample with approximately correct distribution.
O k. ((*))
observations is that the extra privacy term in the
Another implication of our results is that, in some settings, the distributions that are hardest for or private-are the easiest for sampling, and vice versa. Consider the simple case of Bernoulli distributions (i.c., product distributions with d = 1). The "hard" instances for nonprivate learning to within error are distributions with bias is easiest in that parameter regime. In contrast, the "hard" instances in our 22( lower bound for Bernoulii distributions have bias 10o, 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 ) observations. Similarly, for product distributions, we show that the complexity of private sampling is only θ(vd) when biases are bounded away from 0 and 1. For the same class, however, the complexity of private and nonprivate learning is (dd).
1+a but private sampling
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 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 com- plexity 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.
1.2
An overview of our proofs and techniques
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 algorithmss need only be correct on average over samples drawn from given distribution. One useful observation that underlies our positive results is that sampling based on an unbiased estimate P of probability distribution P (in the sense that [E [x)(w)) = P(u) () for all elements u 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, c.g., drv (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 fundamental obstacle. The basic framework used in proving most lower bounds on sample complexity of learning problems based on identifiabiliy: to show that a large sample is required to learn class C, one first finds a set of distributions Pi..... P. in the class C that are far apart from each other and then shows that the output of any sufficiently accurate learning algorithm allows 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 certain sample size) cannot reliably identify the correct distribution. This general approach is embodied in recipes such as Fano's, s, Assouad's s, and Le Cam's 's methods from classical statistics (see, e.g., [3] for summary of these methods and their differentially private analogues). For many sampling problems, the identifiability approach breaks down: 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, lower bound for k-ary distribution relies on the fact that an a-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 estimation) problems. For example, our lower bound for product distributions with bounded biases is obtained via a reduction from estimation problem, by observing that a small number of samples from nearby distribution suffices for a very weak estimate of the underlying distribution's '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 a-accurate (c, 0)- differently private sampling can be performed with a dataset of size O k ). Our private sampler computes, for each j E [k], the proportion P7 of its dataset that is equal to j. adds Laplace noise to each count, uses L1 projection to obtain valid vector of probabilities p (P....., Ps), and finally outputs an element of [k] sampled according to P.
Theorem 1.5 provides a matching lower bound on that holds for all (E. 6) differrenttil private algorithms with 8 = o(1 /n). We prove our lower bound separately for Bernoulli distributions and for discrete distributions with support size k 2 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(O) to show that, on input with t ones, a differentially private sampler outputs I with probability at most 2te Then consider P = (10 We use a-accuracy in conjunction with group privacy to give a lower and an upper bound on the probability of the output being I 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 2 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 Poisson algorithm, that is, an algorithm that, instead of receiving an input of fixed size, gets an input with the number of records that follows a Poisson distribution. This observation allows us to use standard technique called Poissonization that
5

---

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 E is small. Finally, we observe that every sampler for the class of k-ary distributions can be converted to a frequency-count based algorithm. A sampler is frequency-couuntbusee if the probability outputs a specific element depends only on the number of occurrences of this element in its input and the frequency counts? of the input (that is, the number of clements that occur zero times, once, twice, thrice, and so on). Frequency-coume siweenccy-cont-baseee baaud algorithms have been studied for 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- 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 sampler outputs specific element which appears j times in its input differs by at most a factor of g from the probability that outputs specific element that does not appear in the input. Then we consider distribution P that has most of its mass (specifically, 1- (aa) on a special element, and the remaining mass spread uniformly among half of the remaining domain elements. That is, P is 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 output any non- non-special element. But it has to output non non-special elements with probability 22(a) to be a-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 ((x). 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 (pi..... Pa) be the attribute biases for the product distribution is drawn. For simplicity, assume w.l.o.g. that all the marginal biases Py are less than 1/2. The main idea in [17] is that smaller biases have lower sensitivity in the following sense: we know that a set of attributes has biases P, 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 that idea, we partition the input into smaller datatsets and run algorithm in rounds, each using fresh data, a different truncation threshold, and noise of different magnitude.
from which the data
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 p; except the very small ones partition the coordinates into log(d) buckets, where biases within each bucket are similar. We show this crude estimation only requires = (ddae)). 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.
(where P, < 1/d). This allows
The proof of our lower bound for general product distributions proceeds via reduction from sam- pling of k-ary distributions for k = d. In contrast, lower bounds for private learning of product distributions rely on fingerprinting codes (building 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 with biases p5 = P(j)= = & for j E 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 Pl, then runs
'The vector of frequency counts is called a fingerprint or histogram in previous work.

---

hypothetical sampler for product distributions to get vector in {0, 1).. (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 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 the interval [1/4, 3/4] and sample 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) 0)-differentially private for the case when d 1. For larger the sampler is 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 P2, .... Pd. output estimates P1,...: Pa such that each P. is within additive error 20 of pt, that is, 10; pa| S 20 with probability at least 1 - 20
(where 1 is just a sufficiently small constant). This problem is known to require datasets of size 20 ((vd) for differentially private algorithms [10]. However, nonprivate algorithms require only Q(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 constant number of times on disjoint datasets to obtain enough samples to (nonprivately) estimate each of the p 's. The nonprivate estimation 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 robust (i.e., works even when the samples are only close in TV distance the correct distribution) and that the lower bound of [10] applies even when the biases p; lie in I 3).
1.3
Related work
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 records is used to generate output sample of size n' > from 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 participants receives single observation and is limited to >1 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 diffcrential 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 random- ness inherent in sampling provides some level of privacy "for free".. Our algorithms for product distributions with bounded biases leverage 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 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 [1 1,, 3]. though lower bounds for estimating histograms were known as folklore since the mid-2000s. For product distributions, tight upper and lower bounds for (e, 8) -iifferrentil private estimation in TV distance appear in [17]; the upper bound was later shown to be achievable by an (e, -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 5 = O.
Less directly related is the line of work on the generation of synthetic datasets that match the data distribution in set of specified characteristics, such as linear queries (e.g.. [7]: see [21] for 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-aa much more difficult task than sampling, and one for which different set of lower bound techniques apply [21].
7

---

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 {((//a)) The crux of the proof the case where the sampler is frequency-count-basse
Poisson, and is (e, 6)-DP for small e. 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 E N,a E (0, 0.02), E (0, 10,1//ul lm(1//]) and E [0, [0,0.lae/k) Let C2441
denote the class of discrete distributions over the universe [2k + Il. If sampler A is (S, frequency-coutt-bee and o-accurate on class C2x-1 with dataset size distributed as Po(n), then
n 60
Proof. We consider the following distribution P over the universe 21 = [2k: + 1j. a² 60c and a set S* C [2k] of size Distribution P has mass a² /k: k on each element in S and mass 1 a² on the special element 2k 1.
Consider sampler satisfying the conditions of Lemma 2.1. Let A.P denote the output distribution of A when the dataset size N Po(n) and the dataset X p&N Observe that
drv ()
Pr
[A(X) $ Supp(P)].
N~Po(n) X-p88
We show that if n S 60oz and and 8 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 fixed dataset x fixed size N. Let Pj.((s) be the probability that A outputs specific element in [2k] that occurs times in where F(x) is the frequency-count of x; these probabilities are well-defined because AA is rrequency-count-bee
Let F (x) denote the number of elements in [2k] that occur times in (excluding the special element 2k + from this count). By definition, F (x) S 2k. Consequently,
Pr[A(x) & Supp(P)] = k- Po,F(x) 2 (x) F(.)(x)
The next claim uses the fact that A is (e, 8DD to show that the probability F())()) cannot be much larger than the probability that A outputs specific element in Ul that does not appear in
Claim 2.2. For all (s, 6DD samplers, frequency counts f E Zz, and elements j E U,
PjJ S ed (po.s + 2).
(3)
Proof. Consider frequency count f and a dataset x with F(x) = f. Note that (3) is true trivially for all j such that (x( because, in that case, Pj.F(x) is set 0.
Fix any j E U1 with (x) > O. Let a be any element in LI that occurs times in the dataset Let b be any element Vi that not the support of the distribution P. Let x| denote the dataset obtained by replacing every instance of in the dataset x with element b. By group privacy [15].
Pr(A(x) = a) < de Pr[[A((aa-s) = + 1
(4)
Note that the dataset x x does not contain element o, since we' 'e replaced every instance of with b. Importantly, F(x]a=>b)= F(x) because is outside of the support of the distribution P and hence does not occur in x. Since AA is frequency-coum coanncc-oout-bbseee based and F(x) = F(xla->b), we get that
Po,F(x) Fxx w²) Substituting this into (4) and using the fact that e
for all e, get
Pj.F(x) S e== Po,F(x) + eー S 50 po.s 2)
This completes the proof of Claim 2.2.
For a dataset x and i E [2k + 1), let (x( denote the number of occurrences of element in x. Next, we give a lower bound on Pr[A(x) & PPpp(P)) in terms of the counts (x).
8

---

Claim 2.3. Let N E N and [2k + 11W be a fixed dataset. Set Y = Eies [eMx(x]e].
Then
1 Pr[A(x) [2k]] Pr[A(x) & Supp(P)) 2
kd
1 1+ Y/k
the fact that that element j E [2k] that appears j times in x is returned by A with probability Pj. 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 S", then apply Claim 2.2, and finally substitute for Eies [x)c]:
Proof. In the following derivation,
Pr[A(x) [2k]]
Σ iE(2N)
(x)()))(()) = F) PO,
Σ
PN.()).
VE RE/2N/
< Fö (x) Po, + Σ (N(()))P(()
ES
S Fx) Po, +
Σ Po,F(x)
(cEN(()) +
8 -)
+ (F +
xES*
We rearrange the terms to get Fo,)(x) 2 Pr[A(x) E
[2k]] 8
F +Y E
Substituting this bound on Po,F(x) into (2), we obtain that Pr(A(x) & Support(P)) is at least
1 (x E [2]]
(x) 8 Pr(A(x) E [2k]]
kd
(x) +Y
Y/k
where in the inequality, we used that l: S (x) S 2k. This holds since the support of P excludes k: elements from [2k] and since F (x) counts only elements from [2k] that do not appear in
Finally, we give a lower bound on the right-hand side of (1). Assume for the sake of contradiction that n S -7 By Claim 2.3,
A.
Pr (A() & Supp(P)) [1
Pr[A(X) E [2k]]
kd
2
E N.X
N.X
2
1+ Y/k
E
Pr[A(X)
[2h]]
k8
(5)
N.X
1+ Y/K
Next, we analyze the expectation in (5). Let E be the event that x expectation,
e3.
By the law of total
Pr(A(X) E [2k]]]
Pr(A(X) [2k]]
E
E
E Pr(E).
N.X
Y/k
N.X
Y/k
Pr(A(X)E 1+Y7k
In Claims 2.4 and 2.5, argue that both Pr(E) and EN.
E are large.
Claim 2.4. Suppose < kn Let E be the event that Y
ea. Then Pr(E) 2 1110
60n5'
T
Proof. Recall that Y was defined as EiEs- [(x)5] for fixed dataset Now consider the case when dataset X a random variable. N Po(n) and X p&& then N2 Po(="n) for all i S* and, additionally, the random variables N;(X) are mutually independent. When X is clear Y. from the context, we write N; instead of (X))). Now we calculate the moments of F. For all À > 0,
T (+))
=
E N-Po(1) X-P
IG= Σ
M.XX)) SES
E Na... Ne (
[G
Σ
e Nie Mie ) (7)
N~Po(() p&N
1E5

---

Finally, we bound the probability of event E. Set c = = and À = In a.
By definition of E.
Y Pr
1
I
Pr(E) = Pr
2 c)
5
E
k
N~Pa(n) X~pOo
(6 Σ
e
S
E N NimPo
[(aMie) "1
(8)
No Po
IES'
=
-33 (ode-1)
S ead e E (-I((11/) a, (9)
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 single random variable (the proof of this fact is in the supplementary material), To get (9), we use the moment generating function of Poisson random variable, and then we substitute
where we use
c ex and use the assumption that < 60az a-g"
A
js The second inequality in (9) holds because
in 1 and E E 1/ In J. so Äs S 1 and hence e < 1 + 2de. The final expression is obtained
by substituting the value of X. We get that Pr(F) 2 a, completing the proof of Claim 2.4. L.
Pr(A(X) E [2k]]
Claim 2.5.
E N-Po(a) X-p8A
[E] 2 2.3a.
1+Y/k
Proof. When event E occurs, 1 + Y 21 6 < 22. Then
Pr[A(X) E [2k]] N.X
Prr[A(X) E [2x]]
1
E N.X
E =
E [P((A(X) E [2k]]
1+Y/K
22
22
N,X
(10)
By the product rule,
Pr[A(X) E [2x]] F. Pr(A(X)= [2)] EJ
2 Pr[A(X) E [2 2 Pr(A(X) E [21]] Pr(F..
Pr[E]
Substituting this into (10) and recalling that a = 60a, we get
E N.X
Pr[A(X) E [2X]]] 1+ Y/k
E
1
E Pr(A(X) E [2k]] Pr[E]] N.
1
(a" - a a) 2.3a, (a-
22
22
since sampler A is a-accurate on P, and P has mass a" on [2k:] and by Claim 2.4.
Combining (1), (5), and (6), applying Claims 2.4 and 2.5, and recalling that d S 0.1 ae/k, we get
Pr[A(XX) E [2k]]
kō
drv (rv(P.QAP)) N
Pr N.
(A()
& Supp P)] 2
E N.X
2
1+ 1+Y/k
=
1
E N.X
Pr[A(X) E 2
E
Pr - 0.1a 2 2.3a (1-a) 0.1a (1.a)-0.la>>
2
1+ Y/k
2
where the last inequality holds since < 0.02. This contradicts a-accuracy of A on datasets of size Po(n), where n I ate. and completes the proof of Lemma 2.1.
&
Acknowledgments and Disclosure of F 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-20464 as well as Cooperative Agreement CB20ADR016000 with the Census Bureau. Adam Smith and Marika Swanberg were supported in part by NSF award CCF-1763786 as well Sloan Foundation research award. The views expressed in this paper are those of the authors and not those of the U.S. Census Bureau any other sponsor.
10

---

References
[1] Jayadev Acharya, Clément L. Canonne, and Himanshu Tyagi. Inference under information constraints I: lower bounds from chi-square contraction. IEEE Trans. Inf. Theory, 66(12):7835- 7855, 2020.
[2] Jayadev Acharya, Clément I.. Canonne, and Himanshu Tyagi. Inference under information constraints II: communication constraints and shared randomness. IEEE Trans. Inf. Theory, 66(12):785-7877, 2020.
[3] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private Assouad, Fano, and Le Cam. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pages 48-78. PMLR, 2021.
[4] Brian Axelrod, Shivam Garg, Vatsal Sharan, and Gregory Valiant. Sample amplification: In- creasing dataset size even when learning is impossible. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 442 451. PMLR, 2020.
[5] Tugkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 442 451. IEEE, 2001.
[6] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing that distributions are close. In Proceedings 41st Annual Symposiun on Foundations of Computer Science, pages 259-269, IEEE, 2000.
[7] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. Journal of the ACM (JACM), 60(2):1-25, 2013.
[8] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothesis selection. IEEE Trans. Inf. Theory, 67(3):1981-2000 2021.
[9] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA. USA, 17-20 October, 2015, pages 634. IEEE Computer Society, 2015. 2015
[10] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approxi- mate differential privacy. SIAM Journal on Computing. 47(5): (((5):1888-1)) 188-1998, 2018
[11] Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In Advances in Neural Information Processing Systems, pages 2566-2574, 2015.
[12] Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, and Benjamin I. P. Rubinstein. Robust and private Bayesian inference. In Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles, editors, Algorithmic Learning Theory- 25th International Conference, ALT 2014, Bled, Slovenia, October 8-10, 2014. Proceedings, volume 8776 of Lecture Notes in Computer Science, pages 291-305. Springer, 2014.
[13] Christos Dimitrakakis, Blaine Nelson, Zuhe Zhang, Aikaterini Mitrokotsa, and Benjamin I. P. Rubinstein. Differential privacy for Bayesian inference through posterior sampling, J. Mach. Learn. Res., 1:111:1- 2017.
[14] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '06, pages 486-503, St. Petersburg, Russia, 2006.
[15] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Journal of Privacy and Confidentiality, 7(3):1751, 2017.
11

---

[16] Cynthia Dwork and Adam Smith. Differential privacy for statistics: What we know and what we want to learn. Journal of Privacy and Confidentiality, 1(2):135-154, 2009.
[17] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately learning high- dimensional distributions. In Alina Beygelzimer and Daniel Hsu, editors, Conference Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ. USA, volume 99 Proceedings of Machine Learning Research, pages 1853-1902, PMLR, 2019.
[18] Gautam Kamath and Jonathan Ullman. A primer private statistics, 2020. ArXiv preprint 2005.00010 [s..
[19] Shiva Prasad Kasiviswanathan and Adam D. Smith. On the 'semantics' of differential privacy: Bayesian formulation. Journal of Privacy and Confidentiality, 2014.
[20] Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith. Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM Journal on Computing, 39(3):113 842, 2009.
[21] Salil Vadhan. The Complexity of Differential Privacy, pages 347-450. Springer, 2017.
[22] Yu-Xiang Wang, Stephen E. Fienberg, and Alexander J. Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In Francis Bach and David M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 1 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 2493-2502. JoLR.org, 2015.
[23] Stanley L. Warnrr Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-00 69, 1965.
[24] Zuhe Zhang, Benjamin Rubinstein, and Christos Dimitrakakis. On the differential privacy of Bayesian inference. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 2365 23711. AAAI Press, 2016.
12


Reviews:
[{"review_id": "xJkkhr_AUVh", "reviewer": "Reviewer_haGa", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this is a nice paper initiating an algorithmic investigation of how to sample from distributions with privacy constraints. The paper establishes solid results that should be of interest to a general NeurIPS audience and hence will be a good paper in the conference. The paper is clearly and nicely written.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have sections on both limitations and societal impact which appears adequate. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 "}, "extra_text": {}}, {"review_id": "TMX6NAHkSI", "reviewer": "Reviewer_xLGh", "summary": "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).\n\nThe 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.\n\nIn 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers a problem that is new theoretically, but very fundamental. Despite the seeming simplicity of the problem, the results are fairly technical and while some draw on ideas from other papers, I don't believe any part of the analysis simply reduces to reusing techniques from other papers. The distinction between the sampling and learning problems are made very clear in the intro (although some more discussion on what techniques in the paper are fundamentally new, if any, might be useful). Despite the line of work being new, the authors point out that their results also shed more light on and connect together past results in learning, suggesting the problem is new but still interesting, not new for the sake of being new, adequately citing past works of interest.\n\nThe work is technically sound and interesting, the analyses feel very complete and did not leave me wondering about details, and the work is complete. The submission is also open about limitations of their work/point out several future directions in this line of work, suggesting this paper could inspire more papers in this area. \n\nThe introduction is clearly written and does a good job explaining the qualitative improvements of the paper, not just pointing out the quantitative comparisons with past work. A weakness of the submission is that only one result is covered extensively in the main body, however I view this as more likely a function of the paper length limit rather than poor planning by the authors; the analyses deferred to the appendix are nicely summarized by the author in the introduction. In general I felt like after one pass over the paper I already had a pretty good understanding of the work and its importance. \n\nThe main weakness of the paper is that it is not yet clear how important/fundamental this line of work and this paper will be in the future, but the authors do a very good job showing that their results are interesting in relation to other problems in this area, and generally motivating initiating the study of this problem.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "OhpLNQ07wu", "reviewer": "Reviewer_b21p", "summary": "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.\n\nThe 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.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Essential points:\n\nMy main criticism of the paper is with the problem formulation. The paper currently motivates its set up with the question of sampling from a target distribution p using iid data drawn from p. But this setup does not really capture the real difficulty of sampling, which usually lies in the amount of computation needed to generate a sample, or the number of queries to the target distribution needed. As a result, the paper’s setup results in the task of trying to find a distribution that is close in total variation to the target distribution, which is really quite similar to the task of learning distributions. \n\nThe only difference, between this paper’s setup and the learning setup, is that in the objective of this paper, the expectation over given data is taken inside the total variation distance, whereas in the learning setup, the expectation is taken outside the total variation distance. This difference seems a bit artificial to me. The paper also did not provide any concrete motivating questions that suggest their framework is worth studying, which makes me unsure whether researchers who are not specialists of differential privacy will be interested in the setting of the paper.\n\nMoreover, once one realizes that taking the expectation inside the total variation distance is the main difference between the paper’s setup and and the learning setup, some of the paper’s results then seem fairly natural. For instance, the paper notes that in the Bernoulli setting, the hard instances for learning are when the bias is close to ½, whereas these instances are easy for sampling. But that is not surprising, because if we take the expectation inside the total variation distance, then we don’t need to determine the exact bias.\n\nThe contribution of this paper seems to be mostly a technical one. Although the technical work is good, the arguments of this paper seem quite specific, and it is unclear if the general audience will be interested in the details.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Eo_iEnluIzd", "reviewer": "Reviewer_behk", "summary": "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.\n\n\nThe 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$.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the contributions are solid and the concept of sampling with differential privacy seems nice and novel.  The presentation is reasonable, although I found the choice to focus on the lower bound for arbitrary discrete distributions in the main paper (deferring the rest to the supplement) a bit puzzling.  In think the results for product distributions are more interesting while the results for arbitrary discrete distributions are mostly unsurprising/straight-forward.  For product distributions it is a bit unsatisfying that there  is a  simple algorithm for the case when the means are bounded away from $0$ and $1$ but the general case involves much more work and a much more complicated algorithm with worse guarantees.\n\n\nAfter Author Response:  Thanks for the clarifications!  My score remains unchanged and I still think that the paper is a solid, but not quite spectacular contribution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper initiates the study of differentially private *sampling* (as opposed to learning) discrete distributions. The authors obtain nearly tight results for this problem, when the underlying distribution is discrete on a finite alphabet or a binary product distribution. The reviewers agreed that the question studied is interesting and the results are technically novel. Overall, there was a consensus that this paper is above the acceptance threshold.
Decision: Accept (Poster)