Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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).

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.
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.

The 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. 

The 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. 

The 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.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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.
limitations_and_societal_impact: The authors have sections on both limitations and societal impact which appears adequate.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.

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.

main_review: Essential points:

My 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. 

The 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.

Moreover, 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.

The 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.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.


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$.

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.


After 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.
limitations_and_societal_impact: N/A
review_title: null

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)