On Differentially Private Sampling from Gaussian and Product Distributions
Authors: Badih Ghazi
Xiao Hu
Ravi Kumar
Pasin Manurangsi
Venue: NeurIPS 2023 poster (2023)
Keywords: privacy
sampling
Gaussian distribution
product distributions
TL;DR: Private sampling algorithms for multi-dimensional Gaussian distributions and product distributions

Abstract: We study the problem, where given a dataset of $n$ i.i.d. samples from an unknown distribution $P$, we seek to generate a sample from a distribution that is close to $P$ in total variation distance, under the constraint of differential privacy. We study the settings where $P$ is a multi-dimensional Gaussian distribution with different assumptions: known covariance, unknown bounded covariance, and unknown unbounded covariance. We present new differentially private sampling algorithms, and show that they achieve near-optimal sample complexity in the first two settings. Moreover, when $P$ is a product distribution on the binary hypercube, we obtain a pure-DP algorithm whereas only an approximate-DP algorithm (with slightly worse sample complexity) was previously known.

On Differentially Private Sampling from Gaussian and Product Distributions
Badih Ghazi Google Research Mountain View, CA, US
Xiao Hu University of Waterloo Waterloo, Canada xiachu@uvaterloo. ca
Ravi Kumar Google Research Mountain View, CA, US ravi k53@gmail.com com
bad wwwpshhhhhiiimmmml...mmm
Pasin Manurangsi
Google Research Bangkok, Thailand pasinggoogle.co com
Abstract
Given dataset of i.i.d. samples from an unknown distribution P, we consider the problem of generating sample from a distribution that is close to P in total variation distance, under the constraint of differential privacy (DP). We study the problem when P is a nulti-dimensional Gaussian distribution, under different assumptions on the information available to the DP mechanism: known covariance, unknown bounded covariance, and unknown unbounded covariance. We present new DP sampling algorithms, and show that they achieve near-optimal sample complexity in the first two settings. Moreover, when P is product distribution the binary hypercube, we obtain pure-DP algorithm whereas only an approximate- DP algorithm (with slightly worse sample complexity) was previously known.
Introduction
Differential privacy (DP) 16) is strong and rigorous notion of privacy that has been increasingly studied and deployed as protection against the leakage of personal data used to train ML models.
A basic setting widely studied in ML is distribution learning. where given samples drawn i.i.d. from an unknown distribution P, we seek output a distribution Q that is as close to as possible (formal definitions are given in Section 1.1). Recent works (27 2 29 4 have studied DP distribution learning, whereby the output distribution is guaranteed to stay roughly the same when a single input sample is changed. A closely related setting is DP mean and covariance estimation studied by [38] (3, 30 7|
15 28 9 26). Motivated by the fact that tasks often require much fewer samples than full-ffee midd-fiedged learning, the very recent work of (35] studied the task of DP distribution sampling. where the goal to generate a sample from a distribution Q that is as close as possible to the distribution P from which the input samples are drawn i.i.d. (In the non-private setting, variants of the sampling task have also been studied, e.g., in the work on sample amplification by (5))
In this work, we study DP distribution sampling, and the quantitative gap with respect to the priori more challenging task of DP distribution learning. For the case of multi-dimeensinal Gaussians, we consider three natural settings: known covariance, unknown bounded covariance, and unknown unbounded covariance; for the first two, we obtain near-tight bounds. This answers an open question of [35]. Moreover, we obtain near-tight bounds on sampling in the case of product distributions on (0, 1) with pure-DP, also improving upon previous work.
"This work was done while the author was visiting Google Rescarch.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Motivation. There are many natural settings where sample from the underlying distribution would be sufficient (as an alternative to the possibly more expensive task of learning the distribution).
For example, if one is implementing an algorithm that would run on sensitive user data, then, as part of the usual software development cycle, unit tests [24] are important. Writing unit tests on real data can violate users' privacy (e.g.. if the unit test code is public), On the other hand, (privately) learning the distribution of the user data could be a significant overkill for this application. A private sample of the underlying distribution would provide a sufficiently representative input for the unit testing algorithm, and this input could be revealed publicly without compromising the privacy of the users.
second motivation arises in distributed settings. Consider the situation where algorithms are being developed medical data provided by multiple hospitals. The algorithm designer would like synthetic dataset that would work well for the algorithm development process. Such a dataset could be obtained if each hospital provides few (private) samples from its underlying distribution.
Finally, we describe another distributed setting motivation where a central curator wishes to build synthetic dataset from multiple users, each contributing multiple items, under the constraint of item-level DP (as opposed to user-level DP). A simple approach for generating such a synthetic dataset is to let each user send to the curator private sample (satisfying item-level DP).
1.1 Formulation
Let D be a class of distributions on some domain X. We consider a setting where there is an unknown distribution D E D and algorithm has sample access to D. There are two natural problems that can be posed in this setting. In the sampling problem, the goal is to design an algorithm that uses samples from D (which is unknown) and outputs element in X. We say that algorithm A is an a-accurate sampler for D iff dev (D. (D.QA.D) S a for all D E DD where QA.D denotes the distribution of A(X) where X D and dev (..)) denotes the total variation distance. Here n is said to be the sample complexity of the sampler. In the learning problem. the goal is to design an algorithm that outputs distribution D' E DD. We say that algorithm A is an (a, B) -cccurate learner for D if Prx=D" D'--A()))(ddaaa (D', D) S a) 2 1 - ,3 for all D E D; as before, n. is the sample complexity of the learner.
The DP version of the learning problem is well studied, e.g., 27 4 in this work we study the DP version of the sampling problem. First, we recall the definition of DP. We consider the substitution notion, i.e., two datasets are neighbors iff they have the same number of samples and we can transform one to the other by changing a single sample.
Definition 1.1 (Differential Privacy [18 16). An algorithm M y + O is said to be (c, 6)- differentially private ((c, 6)-DP) for e 0,8 2 iff. for every S S O and every neighboring datasets Y,Y' E y, we have Pr[M(Y) E S) S et Pr(M((( E S) 8.
We abbreviate (e, O)-DP by eDD,, aka, pure-DP: the o 0 case is approximate-DP We assume that the privacy parameters satisfy < 1, 8 < 1/2, and the accuracy parameter satisfies 0 $ 1/2.
1.2 Our Results for Gaussian Distributions in Rdd
We focus on the d-dimensional Gaussian distribution, i.e., D = N(H, Σ) with μ E Rd, Σ E Rdxd Recall that N(H, Σ) is supported on Rd with ()() xx exp (- (r 14) x - 11)). We study three cases that have been considered in the literature:
Known Covariance: Σ is known, but a is not. More formally, the class of distributions is DN = (N(u, M) μ Rd.. Unknown Bounded Covariance: Both μ4 Σ are unknown but with a promise that < Σ 3 for a known constant & > 0, i.e., the class of distributions is DN : (N(,,)) | p E R M
Raxd s.t. I Σ k. B
Unknown Unbounded Covariance: Both μt, Σ are unknown, i.e., the class of distributions is E (ddxd)
'DN := (N(H, Σ)
summary of our DP sampling results along with a comparison to known DP learning results is in Before we describe our results in more detail, we highlight the following. (i) In all cases,
Table I
We write A A B to denote that B A is positive semi-definn for matrices A and B.

---

the dependence of our algorithms on the accuracy parameter a is only polylogarithiic whereas for DP learning algorithms, this dependence is polynomial. (ii) the case of known covariance and unbounded known covariance, we obtain improvements over DP learning in terms of the dependence on the dimension (iii) All our algorithms run polynomial time, although we do not explicitly state the running time in the formal statements.
Known Covariance. While any DP learning algorithm requires é (
+
ove samples in this
setting [27]. we show that, surprisingly, only Ô (vd/c) samples suffice for DP sampling.
Theorem 1.2. There an a-accurate (c. DDDP sampler for Gaussian distributions with known covariance with sample complexity O ( polylog (Gea)
We also show that the v dependence is necessary, i.e., that our algorithm's sample complexity is tight up to polylogarithmic factors.
Theorem 1.3. Any 0. I.cccuueeeee (e, DP sampler for Gaussian distributions with known covariance must have sample complexity S2( S((vd/e).
Unknown Bounded Covariance. In this setting, we obtain an algorithm with sample complexity of
d² Ö, (:); in contrast, the best known DP learning algorithm requires θ ( ax
samples
Theorem 1.4. There is an a-accurate (e, 6)-DP sampler for Gaussian distributions with unknown covariance, under the assumption < E 3 k- with sample complexity O ( x²² poolyoo ())))
Similar to before, we can show that the sample complexity dependence on d, is near-optimal:
Theorem 1.5. Let a > 0 be sufficiently small constant, and 5 be such that 8 < O (1)))) Then, any a-accurate (c, 6)D sampler for Gaussian distributions with unknown covariance, under the assumption 1 Σ N 21, must have sample complexity n = (vVlog
Unknown Unbounded Covariance. In this setting, the best known DP learning algorithm uses 12
oc samples 4 29 28 For DP sampling, show that we reduce the dependence on polylogarithmic and the dependence on d to d
Theorem 1.6. There exists an a-accurate (e, O)DP sampler for Gaussian distributions (withoul any
assumption) with sample complexity O 42. polylog (~43)
Known Covariance
Bounded Covariance
Unbounded Covariance
Non-Private Learning (Folklore)
θ o2
d
dc
d'
d=
d
(c, 5)-P Learning
axe
0xe
ax
27
22
28
28
(c, 8)DD Sampling (Our results)
vd
θ
($)
11.5
Theorems
1.2 1.3
Theorems
1.4 1.5
Theorem
1.6
Table 1:
Sample complexity of private learning and sampling for Gaussian distributions. Here, Ô θ hide factors that are polylogarithmie d, 1/e, 1/5, 1/a (and 1/3 in the case of learning).
1.3 Our Results for Product Distributions on (0, 1)
For E [0, 1]. let Ber(p) be the Bernoulli distribution supported on {0, 1} with probability mass function [Ber(p) (0) = - p and [ (1) = p. We consider product distributions Ber(pr) 6 other words, the class of distributions
2 (pa) where PI.....P4 [0, are unknown. .o.....P. Pa [0, 1]}-)
Dprod = (Ber(zi) ... Ber(pa) .......

---

Non-Private Learning
We give pure-DP sampler with sample com- plexity O d Previously, only approximate- DP sampler with similar sample complexity was known from [351, which also provided match- ing lower bound.
c-DP Learning
n2
+
27
(c, (e,6) Sampling
35
comparison, DP learning
cDDP Sampling (Our result)
uses Ô ã' + dee) samples 10.
Theorem 1.7
Theorem 1.7. There exists an a-accurate c-DP
sampler for product distributions {0, 1]d with
Table 2:
Sample complexity for private learning and sampling for product distributions {0, 1]
d'loR( d'oog
sample complexity O
Here, Ô hides factors that are polylogarithmic in d, 1/aa (and 1/B in the case of learning).
We also note that our result above improves upon the approximate-DD sampler in B5 by logarithmic factors. Specifically, for a $ 1/ log d, our sample complexity is O d'log(//a) whereas
theirs is O dy (11o01116))
(log 9/4 d log log²/((1/ox)) (1/0)1
dloog
2 Technical Overview
2.1 Gaussian Distributions: Algorithms
When E is known, may w.l.o.g. that E I; otherwise, can transform each sample X into g-1/2 We start by using known algorithms [23] 40 33 to find "rough" estimate for the mean. In particular, we find an estimate fa such that / - R = Ō (d using Ö ((vd/c) samples. By appropriately shifting the subsequent samples, this is equivalent to assuming that ||l|| I R. We then focus on designing a DP sampler for this bounded mean case. turns out, surprisingly, that the Gaussian mechanism suffices here. Specifically, for parameter B > 0 (chosen later), we truncate each sample so that its &2-norm is at most B. We then output their average with (spherical) Gaussian noise N(O, a² added. The description given in Algorithm
Known Covariance.
The analysis the Gaussian mechanism [c.g.. Algorithm 1 SPHERICALGAUSSIANAAAA
Appendix A] shows that the algorithm is (e, 8DP
long pick 2 Ô (B)
Parameters: B, > 0, and n N. Sample for = ...., do
Xn ~
As for the accuracy, observe that there were no truncation, then the output is exactly distributed as N(1, (a² + T), which is precisely N(H,) if we set 2² (n ()/1)/n Therefore, by setting B = R + ((vd log(1/a)) so that the trunca- tion does not occur with probability 1 - a, we
X Xtrane trunc B (X.)
sec
Sample ~ N(O, 0²
return Z - DiEi X trune
ensure that the sampler is a-accurate. The constraint that a 2 Ö ( from privacy implies that we
need Ö(Vd/c) and hence yielding the sample complexity in Theorem 1.2
Unknown Bounded Covariance. Recall that in this setting we know that M While might be tempting to use the above Gaussian mechanism for this setting as well, it turns out that this approach results sample complexity that depends polynomially on 1/a
To circumvent this, we first consider the case where = 0 (i.e., "centered" Gaussians), In this case, our algorithm originates from the following attempt: output Eie(n) a[i]-X, where (a[I)...., a[n]) points on the unit sphere in R It follows from the 2-stability of
Uni.. the uniform distribution the Gaussian distribution [41] that, when X XI...., Xx ~ N(O, E), this results in an output that is distributed exactly N(O, Σ).
Unfortunately, this algorithm not DP: if X1 _.... X,-1 O. then the output will reveal the direction of X,, in the clear. To remedy this, we build on the intuition that, if XI...., Xn "sufficiently span all directions". then there should "enough noise" to make this algorithm DP. In particular, using the bounded covariance property, can show that if all the cigenvalues of EveM)) X,X;
"See Appendix C for a proof sketch of the sample complexity from such an approach.
"Note that this holds even for any fixed unit vector E Rdd

---

are sufficiently large (and each X; is truncated appropriately), then this algorithm is indeed "DP". This is perhaps the most technically challenging part of our work, as the noise data-dependent and therefore poses significant hurdles in the privacy analysis (Section 4.2) Note that this is also the reason we need n 2 (d). as otherwise Xx,...,N, cannot "sufficiently span all directions" in Rd.
With the above, the last ingredient is a testing step (in the "propose-test-relesee" paradigm of [17] that checks this eigenvalue condition. When this condition fails, we return 1; otherwise Lie(n) ali] X,,
To handle the case where μ + O, we take an output be the sum of the average of пı samples and R.. (Eie|na) (l)).U)). where each U; is the difference between two fresh independent samples
/1- I. divided by v2 and (a[1)..... a [n2]) Uni.g. Notice here that each U; N(0, E), while the average mi
over n1 samples is ~ N(J, - Σ); thus, the sum is N(u, Σ) as desired. The full description is presented in Algorithm [ the parameter setting and analysis can be found Appendix B.4
Unknown Unbounded Covariance. We proceed by reducing this case to the previous setting. We do so by first applying the known DP "pre- conditioner" algorithm for Gaussians (with unknown unbounded covari- ance) from the work of [9] in order to obtain rough estimates Ri, Σ of p. Σ respectively. This allows us to trans- form any subsequent sample X into E-1/2(X (i). This reduces us back to DP sampling for N(E-1/22(1
Algorithm 2 BOUNDDDCOVGAUSSINNSAMEE
Parameters: B, > 0, and n1, 122 E.
Sample X1 X1y...: Xn, X +1..1..... X D
for i = 1..... n2 + 2n² do
X. trunc i (X,)
see
for j = l...., do U3 = v2 (X trun
X Xinne
11+22-1
Sample r ~ STLap
E 2:
A)
> see Lemma 3.1
if Amin
Eig[nal U.?
+ 2 0.75mz then
return Sample a ~ Uni
(). 1 The guarantee of the DP preconditioner ensures that this Gaussian actually has bounded covariance. Therefore, we can apply our previous algorithm. Note that significant part of the sample complexity is due to the DP preconditioner of the Gaussian; it turns out that the sample complexity of this task is only Ôz. (d8/2) (compared to (d?) for learning). Furthermore, since we only need the preconditioner to be rough estimate, we can set the accuracy parameter for the learning to be (1) and thus avoid the polynomial dependence on 1/ax. (Note that private preconditioner is standard ingredient in the recipe for DP learning [e.g.. (7..)
return 1 [Ei(mi)) Xtrume V1 L. (Ere(pa) ul]]-U.)
2.2 Gaussian Distributions: Lower Bounds
Known Covariance. Our lower bound in this setting builds on the following insight: if we take constant number of samples from N(u, 7) (using the DP sampler) and use them to estimate je, then we incur an expected E-error that is (dd). It turns out that known lower bounds for DP mean estimation of Gaussians with known covariance (27 hold for this setting and give lower bound of
Ω d where 7² is the Ez-error. Plugging in 7 v in our setting gives the desired lower bound of ((Vd Vd/e). .). In the actual proof, one complication stems from the fact that our DP sampler does not output sample exactly from N(J,, T). Nonetheless, we can quantify this in terms of the accuracy
Unknown Bounded Covariance. In this setting, we reduce from lower bound on DP covariance estimation (28) (28) rrather than DP mean estimation earlier-of centered Gaussians. The challenge is that ((1) samples from N(O, Σ) do not provide a sufficiently high accuracy estimate for Σ so that we can apply the known lower bound5 Therefore, the above approach does not work directly.
To overcome this, will have to use many samples to estimate the covariance. Recall that the sample complexity lower bound of (ddd /c) for covariance estimation requires the accuracy in the Frobenius distance (or the Mahalanobis distance) to be constant (28). Due to this accuracy requirement, we need to use our DP sampler to generate = ((d)) samples YI...., Yz to achieve such an accuracy. We can draw fresh batch X ii..... ...... X of samples from the underlying distribution to generate each
'This high accuracy requirement is inherent in the known DP covariance estimation lower bound; see 28 Remark 4.4] for more details.
5

---

Y, However, since L = 92(d2), this would use Ln samples in total. The covariance estimation lower bound would then yield Ln 2 Q(d2/e) implying n 2 ((1/e) even weaker than the mean estimation lower bound!
Fortunately, it turns out this can be overcome by using advanced composition of DP 19] In partieular, we may rum our sampler L times on the same samples to produce YI...., Yt. covariance estimation algorithm has privacy loss parameter Ó(VL. - = Õ e) due to advanced composition (Theorem A.5 Therefore, we get a lower bound of (2(d /(d e)) = (dd/E) as desired.
In this case, the final
While the above overview seems intuitively plausible, there are certain difficulties that need to overcome. First, the samples Y; that our algorithm produces are not exactly drawn from N(0. Σ); to fix this,
agnostic learner for Gaussians [e.g..B] to recover the estimate of Σ. Second, since run our DP sampler on the same samples, the produced YI..., Yr. are not independent. We fix this by first drawing larger number N of samples, and then produce each Y; using n--uttof-N random samples; this reduces the correlation across the Y,'s Furthermore, using implifiatton--y-ssapliin of DP 66] gives us the desired privacy-vs ss-sppll complexity lower bound guarantce.
2.3 Product Distributions: Algorithm
Our sampler follows the framework of 135 which is built upon the preconditioning procedure proposed by (2 for DP learning.
We start with private preconditioner, which obtains a crude estimate of each Pj (up to a constant multiplicative factor). This similar to that of [27], except that we use Laplace noise instead of Gaussian noise; this ensures that the resulting algorithm is pure-DF By suitably partitioning [0, 1] into geometrically decreasing buckets terms of d//r, the goal then is to estimate P3 by placing it in one of these buckets. This can be done by appropriate thresholding and the Laplace mechanism.
The next step is obtain a refined estimate of the p. using fresh batch of samples. The algorithm then returns sample randomly drawn from the product distribution given by these estimates. The earlier crude estimates are helpful in truncating and clipping the samples make the produced sample DP, without adding any noise to the refined estimate.
3 Preliminaries
For convenience, we use the notation trunc for "truncation" for all X Rd, B> 0,p 1:
(x ( = x B/I|
if |X S B, if | > B.
(1)
Let [k] denote kl. For any X Rd, X[i to denote the value of its jth coordinate.
3.1 Distributions and Tail Bounds
For a discrete distribution D, we use fo to denote its probability mass function (PMF); for continuous distribution D. we use fo to denote probability density function (PDF). Let supp(D) D) denote the support of D. We let Z ~ D denote that the random variable Z is distributed according to D; throughout, we may write the random variable in place of the distribution and vice versa when convenient. Finally, when D ....... Da are distributions, we use D1 @ ... & Da as the product distribution, i.e., the distribution of (Z,,..., Za) where Z1 DI...., Za Da are independent.
For distribution D on dd and Rd write D where ~ D. Furthermore, for a distribution and a (possibly randomized) function h, we write h(D) to denote the distribution of h(X) where X D.
shorthand for the distribution of X +
We will list few distributions that will useful for us.
We remark that a similar analysis has also been done by 37 who uses such pure-DP DP preconditioner to give DP DP algorithms for learning product distributions.

---

(i) Shifted Truncated Discrete Laplace Distribution: For A > O, let s(c, 8) = [1 + log 1/
We define STLap(e, 6, A) to be the discrete distribution supported on [-2s(e, 6).0) 0J such that (.))))) & exp (-e x + s(e,
It is known that adding STpap noise low-sensitivity function results in DP estimate [e.g.. 22
Lemma 3.1. If is a function with sensitivity v A, then the algorithm that outputs g g(X) + STLap(e, 8, A) is (e, 6)-DP.
(ii) Beta Distribution: For a; 3 0, Beta(a, B) has the PDF (Be (2) x x0-1(11 x)8-11
(iii) Uniform Distribution over Unit Sphere: For d E N, let Uni denote the distribution of a random unit vector in R4.
(iv) Projection of Uniform Distribution over Unit Sphere: For any d N and i [d] and e Rd let (z) denote (21,..., 24). Then, let Uni denote the distribution of (Z) where Z ~ Uni This distribution has the PDF (see, e.g., [34] Theorem 21) given below.
(1 )| -
if |= otherwise.
fune, (z) x
(2)
We need a tail bound on the fo-nm of Gaussian-distribnn vector:
Lemma 3.2 (22 Theorem 6.2]). There exists a constant e 2 such for any μ E Rd, E E Rdxd
where Σ
and any (0, 5))
Pr X-N(u,E)
|| ull2 ovT (vd+ vlog(1/3)) s 3.
We also need a tail bound for the beta distribution:
Lemma 3.3 43 Theorem 8). There exists constant E (0, such that, for any 0 < < 3 and
S 2e -omin d²=" 3
a
any x 2 0, we have
Pr (a
Z
2
+
B
The following concentration bound on the empirical covariance will also be helpful.
Lemma 3.4 (27 Fact 3.4]). There exists a constant 2 such that for any E > I, let U1....,
Un
N(0, 3) and 5 1 Eie()) U.UF, we have Pr E. z 1 1 ev + (og(1/3)
T 2 3.
3.2 Differential Privacy
Hockey Stick Divergence. We also recall the definition of c-hockey stick divergence between (fr(w) - e
two distributions P, P,Q: d. Q) = f
where [a]+ := max(a, (, 0}.
pEsupp(P))
The following standard fact about the hockey stick divergence is often useful in proving DP guarantees of algorithms (39 31].
Lemma 3.5. For any 2 and distributions P, Q. d, Q) S Pry-p(Sr(v) e SQ(v)).
will be also useful to keep in mind the "post ppost-processing" property of DP:
Lemma 3.6. For any distributions P. Q and any function h, have d, (h(P) (()) S (P Q).
DP under Condition. Since will convenient to use the notion of "DP under condition" together with its composition properties. The particular definition we use below is from [32 similar notions have been used earlier, e.g., in (17].
"proppssetestt-reeasss" style algorithm [17 it will be
Definition 3.7 (DP under Condition,
32 ). Let V y - {0, 1} be a predicate. An algorithm
M y > O is (e, 5)- under condition v for e, 8 iff, for every S C O and every neighboring datasets Y, y" E y both satisfying V, we have Pr[M E S] < e (Pr[M((")) E S 5 6
Lemma 3.8 (Composition for Algorithm with Halting, (2).. Let : - O2 (1), O, x y + O₂ be algorithms. Furthermore, let M denote the following algorithm:: Let 01 = MY(Y)
and, if 01 =1, then halt and outpul 1. else, ouiput 02 MM(01, (Y).
be any condition such that, Y does not satisfy V, then MI (Y) always returns 1. Suppose that Mj is (e1, DDP and M2 is (E2, -DP under condition V. Then, M is (E1 + =2 + dD)
7

---

4 Gaussian Distribution: Algorithms
Reduction to the Bounded Mean Case. As stated earlier, for the cases of known covariance and bounded covariance, we will need a preprocessing step that computes rough private estimate for the mean. The properties of the reduction are stated below.
Lemma 4.1. Suppose that there is a-acccurte (c, 5DDP sampler for Gaussian distributions under the assumption that I I Σ 3 k. I. |ll|l I R with sample complexity To samplerr (a, R, c, Then, there exists an a-accurate 6) sampler for Gaussian distributions under the assumption that
133 Σ 3 K I with sample complexity Ô
yd
Tbbm-aamperr (a/22, (xx.d))
4.1
Known Covariance
With the reduction in Lemma
we may assume that ||-~//2u|| S R. When the covariance known, we give an algorithm with the following guarantees.
4.1
Theorem 4.2. Assuming Σ is known and ||11/2μl1 S R. there is a-accurate (c,8)-DP DP sampler for Gaussian distributions with sample complexity O
( [ V d log
log(1/6) ae
(1og(1/8)
We assume w.l.o.g. that otherwise, we can consider X = E-1/2X, Before we describe the
algorithm, note that Theorem 4.2 together with Lemma 4.11 Jimplies Theorem 1.2] As stated earlier, the algorithm (Algorithm [ is simple: take the average of the truncated input samples and add (spherical) Gaussian noise.
Proof. Let C' 2 1 be the constant from Lemma 3.2 B R+ 10 d log (2og((2/))
and
1 [10 / log(2/0)/e)) Let A be Algorithm with B,n as specified and
V(n 11/n.
Privacy Analysis. .A the Gaussian mechanism with noise multiplier no n 2 (oog0//))/// therefore, A is (c. 5D- using [20, Appendix A].
Accuracy Analysis. Let D N(p, I) for some unknown μ.. Consider the algorithm A'' where there no truncation, i.e., AA' simply outputs Y == + Eigjn) X,. Via Lemma and union bound, the truncation is not applied anyway in (i.e., X; = X!rune Vi E [rz)) with probability at least Therefore, dev (QA.D. QA,,) S a. Note that A' just outputs Y := 7 + Eiiin) X,, so we have Y N(p, D, i.e. Q = D. Combining these bounds yields de (QA.D. D) S
4.2 Unknown Bounded Covariance
We now move on to the case where both 14, are unknown but under the assumption 1 1 Σ. 1 K The main result of this section is stated below]] Again, note that Theorem 4.3 and Lemma 4.1 immediately yield Theorem 1.4
Theorem 4.3. Assuming 1
and ||||| R, there is an a-accurate (e, 8) sampler for Gaussian distributions with sample complexity ((RR
E 3
K for some
O (R² + R² (d+log [lg((1/8) log(1/8)
As stated the overview, the main challenge lies in the privacy analysis. It will be proved in three steps. First, in Section 4.2.1 we will show that if we add noise that is drawn from projection of random unit vector the first M coordinates
function, then it is DP. Then, in Uni to low-sensitivity function also suffices for privacy long as the smallest eigenvalue of Exern wowf is sufficiently large. Here wi..... Wn, are assumed to be fixed vectors given beforehand. Note that the noises discussed so far are input independent. Finally, Appendix B.4, we relate this to the
Section 4.2.2 we use this to show that adding noise of the form ΣiE a[i] we (where
'The dependence on x can be reduced to polylog(1/)) 1/Kk) by applying the private preconditioning in [27). although this will increase the dependence on d to d it is an interesting question if this increase in the dependence d can be avoided.
8

---

privacy of our crgrrthhm-wiice is more intricate as these wi 's are now X,'s, i..., the noise is input dependent. The accuracy analysis, which is simpler than the privacy analysis, also Appendix (B.4
[B.4
4.2.1 Noise via Random Unit Vector Projection
We first show that adding noise drawn from Uni to a function with low -g-seniitivity ensures DP.
Lemma 4,4. Let M, N be any positive integers such that M 2 max (2N, 10a log(10/5)
where c is
the constant from Lemma 3.3 Furthermore, let T E (0, 0.01) be such that T S 10
log( c.1
Then,
for any vector v such that ||l|| S T, we have de (Uni || Uni + v) -
The proof of this lemma proceeds similarly to those of independent noise addition (c.g., the Gaussian mechanism): using Lemma 3.5, it suffices to bound the probability that the privacy loss is large. We achieve such bound via concentration properties of the beta distribution.
4.2.2 Noise via Spherical Linear Combinations
Next, we relate the previous lemma to privacy in the case where the noise added is of the form Eielg) a[i] Wi, where wi.-.., Wy are fixed beforehand and a ~ Unig. The guarantee of such a noise is stated below. The proof is based on a reduction argument to Lemma 4.4 For notational
convenience, for every matrix W E Rddx,, let Unity be the distribution of Wa where a ~ Unig.
Lemma 4.5. Let q, d N and To (0, 1) be such that q Z max 2d, 10" log(10/6) and To S 5 5 5V/og(10008// (10/8)/c. For any wi,..., Wgg E Rd such that 1 (Ein w,w,) = 0.51 and any u E Rd
such that ||a||| I To. we have de (Unin || Unity + +) I 5, where W1..... Wl are the columns of W E Rdxq
Let W R denote the pseudoinverse of W. Note that WWT -Ex w.s?" = 0.5g Therefore, all singular values of W are at least v0.5g. This means that all singular values of W+ are at most 1/ /0.5q. This in turn implics that ||W+ell S [|e|]/ I To/ 00/00.5q =
Proof.
Since www = 0.5gl, W is full rank and thus dim ()+) = d. Since d < pick any orthonormal basis bi,...,bu ba E R for im(W) and let II : R + Rd be such that II(=) ((2,b1), ...,, (z, ba)).
Furthermore, let h Rd + Ied be defined as h(x) = EiE(g) <||] b. Observe that, for any E R1, we have a + u h(I(a)) and aru1 +... + un + h(Il(a) + IIW++)) Thus,
de (Unig || Unit + v) de (h(L((Un))) (((I((Uni)) =[(++))))
Lemma B.6
de (I [
Note that I ~ Uni So, Theorem 4.4 implies de (II(Un))) || [[(Un))) + +I v)) s 6. C
Discussion and Open Questions
In this work, we give several algorithms for DP sampling. For Gaussian distributions, demonstrate that the dependence on the accuracy parameter a in the sample complexity can be only polylogarith- mic in comparison to the polynomial dependence necessary in DP learning. Furthermore, we also reduce the dependence on d in the case of known variance and unknown bounded variance; in both cases, we show this dependence (of vd and d respectively) to be essentially tight. An immediate open question is whether the dependence of d in the case of unknown unbounded variance tight. Lower bounds for Gaussian sampling in terms of a is also an interesting question. Another-mm more general-direction is to extend the results to other families of distributions. In the case of DP learning, this has been explored by several works. Our algorithms very specifically use the property of Gaussian distributions (namely that a linear combination of Gaussians another Gaussian); other distribution families might need different techniques.

---

Acknowledgment. We thank Shyam Narayanan for pointing us to 19. which improves dependency on in the sample complexity for sampling Gaussians with unknown (unbounded) covariance from da to d=...
References
[1] Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS, pages 308-318, 2016.
[2] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high-dimensional Gaussians. In ALT, pages 185-216, 2021.
[3] Hassan Ashtiani, Shai Ben-David, and Abbas Mehrabian. Sample-efficient learning of mixtures. In AAAI, pages 1679-26866 2018.
[4] Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning Gaussians and beyond. In COLT, pages 1075-1076, 2022.
[5] Brian Axelrod, Shivam Garg, Vatsal Sharan, and Gregory Valiant. Sample amplification: Increasing dataset size even when learning is impossible. In ICML, pages 442-451, 2020.
[6] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In NeurIPS, pages 6280-6886600 120006690,000 2018
[7] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan R. Ullman. Coinpress: Practical private and covariance estimation. In NewrlPS, 2020.
[8] Gavin Brown, Marco Gaboardi, Adam D. Smith, Jonathan R. Ullman, and Lydia Zakynthinou. Covariance-aware private mean estimation without private covariance estimation. In NeurlPS, pages 7950-7964, 2021.
[9] Gavin Brown, Samuel Hopkins, and Adam Smith. Fast, samplc-efficient, affine-invariant private mean and covariance estimation for subgaussian distributions. COLT, pages 5578-5579, 2023.
[10] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothesis selection. IEEE Trans. Inf. Theory, 67(3):1981-2000 2021.
[11] T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. Ann. Stat., 2855),285--2850, 2021.
[12] Damien Desfontaines, James Voss, Bryant Gipson, and Chinmoy Mandayam. Differentially private partition selection. PETS, 2022(1):339-352 2022.
[13] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional Gaussians with the same mean. arXiv:1810.0860 2018.
[14] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high high-dimensions without the computational intractability. SIAM J. Comput., 48(2):742-864, 2019.
[15] Wei Dong, Yuting Liang, and Ke Yi. Differentially private covariance revisited. NeurIPS, 2022.
[16] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486-503, 2006.
[17] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In STOC, pages 371-380, 2009.
[18] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006.
10

---

[19] Cynthia Dwork, Moni Naor, and Salil P. Vadhan. The privacy of the analyst and the power of the state. In FOCS, pages 400-409, 2012.
[20] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput, Sci., 9(3-4):211 (03-4):111-07,,, 407, 2014.
[21] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: Optimal bounds for privacy-preeevving principal component analysis. In STOC, pages 11-20, 2014.
[22] Badih Ghazi, Neel Kamal, Ravi Kumar. Pasin Manurangsi, and Annika Zhang. Private aggrega- tion of trajectories. PETS, 2022(4):626 644, 2022.
[23] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. In NeurlPS, 2020.
[24] Paul Hamill. Unit Test Frameworks: Tools for High-Quality Software Development. " "O'Reilly Media, Inc.", 2004.
[25] Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via a sum-of -fn-of-qquares exponential mechanism. In STOC, pages 1406-1417, 2022.
[26] Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness implies privacy in statistical estimation. In STOC, pages 497-506, 2023.
[27] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately learning high- dimensional distributions. In COLT, pages 1853-1902, 2019.
[28] Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private estimation and generalized fingerprinting lemma. In NeurIPS, 2022.
[29] Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan R. Ullman. A private and computationnall--ffiiiee estimator for unbounded Gaussians. In COLT, pages 544-572, 2022.
[30] Vishesh Karwa and Salil P. Vadhan. Finite sample differentially private confidence intervals. In ITCS, pages 44:1-44:9, 2018.
[31] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using FFT. In AISTATS, pages 2569, 2020.
[32] Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabiliz- ing convex relaxations. In COLT, pages 723-777, 2022.
[33] Shyam Narayanan, Vahab S. Mirrokni, and Hossein Esfandiari. Tight and robust private mean estimation with few users. In ICML, pages 16383-16412, 2022.
[34] Hedvika Ranosova. Spherically Symmetric Measures. Bachelor's thesis, Department of Probability and Mathematical Statistics, Charles University, 2021.
[35] Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, and Marika Swanberg. Differentially private sampling from distributions. In NeurlPS, pages 28983-28994, 2021.
[36] Or Sheffet. Differentially private ordinary least squares. In ICML, pages 3105-3114, 2017.
[37] Vikrant Singhal. A polynomial time, pure differentially private estimator for binary product distributions. CoRR, abs/2304.06787, 2023.
[38] Adam Smith. Privacy-preserving statistical estimation with optimal convergence rates. In STOC, pages 813-822, 2011.
[39] David M. Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. PETS, 2019(2):44--669 2019.
[40] Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Friendlycore: Practical differentially private aggregation. In ICML, pages 21828-21886 2022.
11

---

[41] Vladimir V. Uchaikin and Vladimir M. Zolotarev. Chance and Stability. De Gruyter, Berlin, Boston, 1999.
[42] Roman Vershynin. Hligh-Dimensionll Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018.
[43] Anru R. Zhang and Yuchen Zhou. On the non-asymptotic and sharp lower tail bounds of random variables. Stat, (1)xe31,, 2020.
12

---

A Additional Preliminaries
We consider a generalization of the truncation ① where there a weight vector w Rd and the truncation is w.r.t w:
X =
if X o w/p - B, if X w|pp p > B,
trunc P
(X) X
B,
B/|| o welp
where denotes the element- wise product. Clearly trunc trunc when w is the all-ones vector.
For a, E R where S b, also (l.p( IR R to denote the function:
clip (x) max (a, min(b,
A.1 Total Variation Distance between Gaussians
For our proofs, it will be useful to state the total variation distance bounds for Gaussian distributions. We will the following notation:
Definition A.1. For any matrix A R and positive semi-definite matrix E E Rddd write ||A||: == AX where || || denotes the Frobenius norm.
is well known that when || E||= s O()), the total variation distance between Gaussian with covariance matrices E and and the same mean is O El[=:), as stated more formally below.
Lemma A.2 (133). There exists a constant C 2 1 such that the following holds. For any E, S., if dev (N(0, Σ), N(O, Σ) I 0.001, then || E|I C dev (N(0, Σ), N(O, E)).
Lemma A.3 (e.g.. (1).. There exists constant C O such that the following holds. For any Σ, Σ E Rdxd, we have dis EN, N(O, 2)) < C -- E1[s.
A.2
Differential Privacy
A.2.1 Amplification by Subsampling
Suppose that we have as an input samples, and we draw n < N subsamples (without replacement) randomly from these N samples and run (c, 8)-DP algorithm
these subsamples. Then, is known that this results in an (c',8') D'D algorithm for c' < c, < 6. Such a phenomenon called amplification by subsampling and often used in DP learning [e.g.. M. We will use the following version of this for our lower bound proof.
Theorem A.4 (Amplification by Subsampling, (6). Suppose that A is an (c, 0)DD algorithmn that takes in n samples. Then, the algorithm that draws subsamples randomly without replacement of N samples and runs A on the n subsamples (c',8))-DP where
é' =l (n/N)(EE -1)),
8' (n/N).C
A.3 Advanced Composition
We will also use the following advanced composition of DP.
Theorem A.5 (Advanced Composition, (19).. Let 6o > O and dg 8, E (0,1/2), and A be any (co, dDD algorithm. Then, the algorithm that runs A a total of times is (E1, Kōo + 6D) where
E1 = (V2k 2k (n(6/))) + k(e -1)) Eo.
A.4 Lower Bounds for Mean and Covariance Estimations
As stated in our proof overview (Section 2) our lower bounds for Gaussian samplers (Theorems 1.3 and 1.5) are via reductions from previously known lower bounds for mean and covariance estima- tions. We state them below, starting with the mean estimation lower bound (aka "fingerprinting for Gaussian") result due to [27]
13

---

Theorem A.6 ((27)) For any e, (0, such that I 0
vd if an (c. algorithm
(Vlog(n/d)
M that can take in N samples from N(u, 1) where Rd that satisfies
p and output an estimate
EX p-Mx))l
All S d/6,
then N 2 Ω
Next is similar lower bound but for covariance estimation. Notice that the lower bound the sample complexity below 22(d2 /e²) whereas the lower bound above is only (2(d/c) (for constant accuracy parameter 7).
Theorem A.7 ((88). There exists small constant & such that the following holds: for any e, 8 E (0, 1] such that S. O (min { [1/n, de / /n n1) n) }), if an (e, (eP algorithm M that can take in N samples from D N(O, )) where 3 = 21 and output estimate Rdxd that satisfies
X (~M() ||| -E 5e:
then N 2 9 (dP/e).
A.5
Agnostic Learner
In the main body of the paper, we considered the learner where the samples are drawn from D which belongs certain class D. For lower bound proofs, it will be convenient consider the agnostic setting where D is not assumed to be from D. The definition and accuracy guarantee of agnostic learner is given below. We remark that the definition coincides with the learner definition given earlier if we assume that D E D. (Note that the constant is required for Theorem A.8
Agnostic Learning. Let D be class of distribution. An algorithm A, which takes in samples and output distribution P E DD is said be an (a:, -a-curaceeaatee agnostic learner for class D of distributions iff, for any distribution P. we have
Pr X~PP A(X)
dev (P, P) S3 min des (D. + 2 - B.
PED
We will use the following (well-known) result that the class of centered be learned with sample complexity O(de /-²). For a full proof, see e.g..
Gaussian distributions can
3
Theorem A.8. For any 3 E 1/2), there exists a (y, accccrre agnostic learner for centered Gaussian distributions in dimensions with sample complexity
d Vlg(1/B)
72
B Proofs for Section
B.1 Reduction the Bounded Mean Case
The reduction will be done by applying a so-called "densest ball" algorithm; this an algorithm that, when there ball of radius that contains the majority of the input, can find ball of radius (r)) containing the majority of the input. There are many algorithms known for this problem 23 40
that give similar guarantees 10 We state such guarantee below.
$ write -1 - μ S as shorthand -1 E ッDj & all j E [d].
Recall that centered simply means that μ = 0. We note that our problem that V'- ~ x and the problem can be solved "coordinate- by-cooddnnattt"" This means that many other algorithms e.g., truncated Laplace-basse based histogram [12] also work and give similar bounds. However, we note that some other algorithms [e.g.. 7 require prior bounds ||л.] whereas Theorem B.I does not require any such bound.
fact easier those considered in aforementioned work as assume
14

---

Theorem B.1 (e.g.. 23 For Rdeus B,,,, ô (1a)) there exists an (c, (D algorithm
Adens that takes in X,...., Xn E R together with a radius parameter T > such that: if there is an r-radius ball containing at least 2/3 fraction of the input points, then with probability - B, outputs a ball of radius O that contains at least half of the input points.
We can now give a reduction of an arbitrary mean case to the bounded mean case by first using Theorem B.I to obtain a rough estimate of the mean and then shifting the remaining samples accordingly.
Proof. The new sampler works as follows:
Let n == max redens (d, ael,,a/,4/222211/ 100 444
10Cxyd where C' is the constant from Lemma 3.2, and == (bm-ssampee((//211/10 (a/2, (
Rough Mean Estimator Stage:
Run (c/2, 6/2)-DP Adens from Theorem B.1 on samples (with as specified above) to get
ball centered at Rdd.
Sampling Stage:
Draw To2 additional samples XI,...,X,
Run (e/2, 22,.8/2 6/2)-DP (a/2)-accurate Abm-sampler with R on (X1 - c),..,, (X c): let Y
be its output.
Output Y + c.
Privacy Analysis. Basic composition implics that the sampler (e, 6)DP) as desired.
Accuracy Analysis. Since Σ < kI, Lemma 3.2 implies that Prx-N(p.E) [I] X - 1l/22 2 r] S 0.1. Thus, using standard concentration inequality (e.g., Theorem E. I and since n1 2 100 log(l/////// (4/a), the probability that at least 2/3 of the points sampled in the first stage contains in the ball ( at least a/4. The guarantee the densest ball algorithm then implies that with probability 1 1-a/2, we have || c/1a S
Let us consider fixed e and consider the output distribution Di of in the sampling stage and Di-c of the final output Y + Notice that (X1 c),... (X -) N( c, E). Consequently, when / cl12 S we may apply the guarantee of Abm sampler to yield
a/2 Z div (Dş, N(μ c, ))) (Dv N(u, E)).
Combining these arguments, the sampler is a-accurate as desired.
B.2
Unknown Bounded Covariance
Proof of Lemma
4.4 From Lemma 3.5 we have
d. d,
|| U + +0) S Pr ZuUni
[unnie (z) > e Suun (3 v)].
For convenience, let us also define = T (10
log(10/8) cM
Note that S 0.01.
For such that ||=|| < 0.9, (z, v)) S 1/, we also have || thus
m1 < 0.9 + 0.02 + 0.0001 < 0.9 and
Uni
M
N
1 ||
In Un -U)
- 1
In
2
1 || e1|2
M N - 1 )
(
1 -|=1
2
11-1/- w/12
M - N
||u|]= (22
2
1
M (10(72 2m))
15

---

10 Ing( 10/8)
where the last inequality follows from choice of parameters (i.e., M 2 Combining the previous two bounds, we have
cc
de duUniiar |l Uni + S
Pr zoslnf
0.9 ||| 0.9
|| >
V (2, > nl
Pr snUnf
Pr snUniie
((2,0) > ml
log (10/6) cM
Pr s~UUnfM
|| 0.9]
Pr g~UUn
2, |||l|
10
M.N
Next, recall that when z ~ M.N. ||=||² (eta (M N)/2) and using the assumption that N S M/2, we can conclude that
Thus, applying Lemma 3.3
Pr SOUUNM
Pr || > 0.9] (.-Beta(N/2(MMMN)/)
I > 0.81] S
2exp(-c-0.0LM)) S 6/2,
where the first inequality is from Lemma 3.3 and the last inequality follows from assumption that M 2 100clog(10/a))
Recall also that when Uni
(E, ( T )
Beta(1/2, (M 1)/2). Again, applying
Lemma 3.3
yields
Pr 2-UUni N
2,
2 |ial|
10
log (10/0)
S
Pr Z- Beta (M..
z
100 lo00(10000)
S 8/2,
cM
cM
where the last inequality again follows from our choice of parameters.
Combining the three preceding inequalities, conclude that d, (Uni || Uni + v) - as desired.
B.3 Unknown Covariance
Throughout this section, we assume the standard assumption that the covariance matrix E is full rank. is simple to extend the result to the more general case using an algorithm [4], which can identify the span of Σ with probability one, using Od ( 1/8)/e) samples.
As stated earlier, we will use DP preconditioner from 9.. We say that an algorithm is an (a, B)- accurate preconditioner for Gaussian distributions iff, when the input X is drawn i.i.d. from N(u, Σ) (for any μ Rd. Σ E Rdxd the algorithm outputs fa, Σ that satisfies the following with probability T I Below provide generic
least 1 - 8: - 1 p)ll2 and /--1//E-- reduction from the unbounded covariance case to the bounded covariance case using preconditioner.
Lemma B.2. Suppose that the following hold:
There exists an (a, 3)-accuraee (e, 8)-D preconditioner Apreend for Gaussian distributions with sample complexity Repreend (a, 8,,,8). There exists an a-accurate (c, -DP sampler Abc-sampler for Gaussian distributions with - Σ k I with sample complexity Tube-sampler (K., a,, e, E)
Then, there exists an a-accurate (e, 8)DP) sampler for Gaussian (without any assumption) with sample complexity
Ppreend (0.001, a a/2, Tho-sampler (4002m/2pp044.0022///2..8333
Proof of Lemma B.2
The sampler is as follows:
Let ni == Rerrendd
a.201,.//,,e/2,6/2 and n2 := Thc-sampler(4,00) (4.0/2,,/222551
Estimation Stage:
1' e.g., httts::/ bttps://ee..vikipedia.a pikkpeddia.org/vikk.. o
12e guarantee here in the spectral norm, not Frobenius norm. However, this suffices for purposes.
16

---

Run (c/2, (0.001, a/2) accurate Apreend samples to get fú, Σ
Sampling Stage:
Draw n2 additional samples X1, XI...., Xay
Run 8/22/ (a/2u-accurate Abesampler on 25 25-1/2 -X)) (,) -p); let
Y be its output.
- Output 0.555//2 + j..
Basic composition implies that the sampler is (c,6)-DP.
To see the accuracy guarantee, the guarantee of the learner implies that with probability 1 a/2. we have [ - -m)ll2 & 0.001 and -/511/25511// F|] I 0.001. The latter implies that all eigenvalues of E1/25-1/2 1-2 lie [0.998, 1.002]; turn, this implies that the eigenvalues of É-1/2g1/2 all lie in [0.996, 1.004). Finally, this implies that |/ - /|/2 v 0.01.
Let us consider a fixed Σ, fi and consider the output distribution of the sampling stage. When the above inequalities hold, the guarantee of Abc-sampler implies that
a/2 dev (Y, N(25 1/2 i.), --- do.(5.5) + N(J, E)).
Combining the above arguments, the sampler is o-accuuate desired.
L
Combining the above reduction (Lemma B.2 together with known result on DP preconditioner of Gaussians (Theorem) B.3 below), immediately arrive Theorem 1.6
Theorem B.3 (8). There is an (a, -a-ccureeee (c, 6)-DP preconditioner for Gaussian distributions with sample complexity
a2 + d²/2
polyyoo (.066
B.4 Proof of Theorem
We use Algorithm with the following parameters: B = R+ 10t x d log (2log(2/6) ac 1.A 2B²
and n1 112 10AC2 (B2.. l0g(10/6) ). where C are the constants from Lemmas 3.3 and 3.4
Privacy Analysis. To analyze the privacy constraint, we first notice that the sensitivity of Amin Cie[nal U.U?) is at most A = (V2. B)² and Lemma 3.1 ensures that the check, which only uses Amin (ie(ma) U:UT) + is (e/2,8/2) Passing this check ensures that
Amin
EU,U?
2 0.75n2
(3)
(E[m2]
From Lemma 3.8 it suffices to show that the output of the algorithm is DP, under 3 Let X
Xi...., . +2n2
To do this, it will be more convenient define V42
V I.
Ug. Condition (
implies that
Amin
Σ V.VT > 0.5mg + A. sE|nzl
(4)
a[i] v.). Consider any neighboring inputs X and X that satisfy the condition. There are two cases, based where they differ.
trnne Let M(X) = ni (Eeema))
+
Eieinal
(i) Case I: X differ on the first samples. Let 1 Eie (n (X - X,); notice that
||a||| 2B Furthermore, (4) implies that 1 (Eiemaa) v.V.2) > 0.5I. Letting W denote the matrix vig whose columns are Vi...., Vng. dg (M(X) M(X)) dg (Uni, || Uni + w) s 8/2, where the inequality follows from Lemma 4.5
17

---

( Case 11: X, differ on the last n2 samples; assume w.l.o.g. Xm, +2ng & 22 Let Vi nn and W denote the matrix whose columns are Vi.... Vn--1- 1- Furthermore, let a, be independent samples from Uni..
de (M(X)) M| dž [amzzl Vn2 +
Σ
ali] V
a d'[n2l Vi +
Σ
d'l
Vi
sE|na-31
1
d2
Unity
w
Unfi
Uning, (v)dy.
(5)
y²
where the inequality follows from the coupling a[re] = a' [2 = a[n2] ~ Uniog. and the observation that
all
alma
and
a'
a
are independently distributed
VI-9"*
V1-
v1-v²
as Uni
When lel 1 Furthermore, (4) implies that
10 10/8)
we have
w
log (10/6)
V2 B < 201
log(10/6)
crg
v - y/2
cn2
Σ Eie(na-1|
V.V."
0.5I. Thus, Lemma 4.5 implies
de/2
Uniw
y. w
+ Univy
1 66/4
V1 - y2
Combining this with 5 we arrive at de/2 (M(X) MM()))
S
8/4
Pry-Uung
(og(///))
Since y² ~ Beta(1/2, (nz - 1)/2), we may apply the
mg..
tail bound (Lemma 3.3 to get
10 10log(10/8)
Pr
1² >
< 8/4.
Cn2
Thus, d (M(X) 11 M(X))
S 8/4 + 8/4 = 6/2.
In both cases, we have de/2 (M(X) || M(X)) S 6/2 under This concludes our privacy proof.
Accuracy Analysis. Let D N(p, Σ) for some unknown μ,, E. Consider the algorithm A' where there is no truncation and no halting. Since I = E I k-I, standard concentration bounds (Lemmas 3.2 3.d3.4 3.4 imply that the truncation and halting are not applied in A with probability least 1 a/2. Therefore, we have d,v (Qv.D. QA. a/2.
Now, notice that the algorithm A' just outputs Y = 1 (Erejea) x.) + -1- I. - a.Ui): this output Y N(u, Σ). In other words, we have QND = N(2, E). Combining these, we can conclude that A is a-accurate.
mi
m.
C A Simpler but Worse Algorithm for Unknown Bounded Covariance
In this section, we give simpler algorithm for the unknown bounded covariance setting. Its sample complexity bound of Ô better than Ω
/3/2
is worse than the one in Algorithm and Theorem 4.3 but still
ac
for DP learning 27 for constant >
The simpler sampler is given in Algorithm 3 and its guarantee is given in the theorem below. Note that this algorithm is once again just form of (scaled) Gaussian mechanism, whereas the algorithm in the main body (Algorithm 2 adds noise that is input dependent.
18

---

Theorem C.1. Assume that I 33Σ 3 K. for some K. > 0 and that || (c, CDDP sampler with sample complexity
S R. there is an a-accurate
n n =(((2 + Rdd log + ( loggogg(1/)))
d=/2 log(1/6)
e²
Algorithm 3 BOOINEBCOSSRANNRRASSTTSSSAALLLLL
Parameters: B, O, and RI, 122 N.
Sample XI,..., Xny Xmy+1,....
Xni+2ma ~ D
for ,,..., 11 2n2 do
X; = trune? (X;
Sample 7 N(0,
[ie|ma) X;) + V
1-1in1
(Xn) Xmi+2i) + Z
return
2nz
Proof Sketch of Theorem C.I Let B = R + 10 d (log 2d + log log (2g(2/))), a = 2/174
Va and
n1, ni be such that v = n2 specified.
1008" log(2/5)
Let denote Algorithm with parameters B, n, a as
Privacy Analysis. A is the Gaussian mechanism with noise multiplier
2 10 log (2/8)/
by the setting of our parameters; therefore, is 8)-DP.
Accuracy Analysis. To understand the accuracy guarantee, let D N(u, 2) for some unknown ,., E where N Σ < k- l. Let us consider the algorithm A' where there is no truncation. Again, standard concentration bound implies that the truncation is not applied anyway in A with probability at least 1 - a/2. Therefore, we have
des (Q.. QAA.P.QA.P)B. S
Now, notice that in algorithm A', we just output
1/ni
X,
+
Σ
(X x2 +
2mz
(E(M]
|E[na]
Without truncation, this output Y has identical distribution as N(u, E 021). In other words, we have
(uu. N(H. Σ) = d.v E o I0 E)) | S
= = vd 5/22
where the first inequality follows from Lemma A.3 and the inequality follows from our parameter selection. Combining the above two inequalities, we can conclude that the sampler is a-accurate as desired.
D Gaussian Distributions: Lower Bounds
D.1
Known Covariance
In this section, we prove lower bound (2(vd/e) that holds even for the simplest case known
covariance (Theorem 1.3), showing that the dependence in sampler (Theorem 4.2 is nearly optimal.
We prove this by using DP sampler to draw a large, but constant, number of samples and the use them to perform mean estimation; the lower bound for mean estimation (Theorem A.6 then gives the desired lower bound for the sample complexity of DP sampler.
Proof of Theorem L.3 Given an a-accurate (e, 8DP sampler A, we construct an algorithm M for
mean estimation as follows:
19

---

For i = ....., 10":
Run A n fresh samples from to get y.
Output ji E IRd with j=[i] == 1, (median((iiia (i]....................... Y1o0 []))
Since A is a-accurate, each Y; is sampled from a distribution D' that is a-close (in total variation distance) to D N(u, 1). For a 0.1, this means that
Pr[Y((] S 0.3| = (--033) + + $049..
and similarly,
Pr(Y() μ + < (0.3) + S 0.49.
As result, standard concentration bounds (e.g., Theorem E.1 imply that
Pr[mediian(X161) Yiue (j)) E [u 0.3, 0.3]] 0.99.
This in turn implies that
EX-DN M(X 111 - 112 S d (0.01 2 + 0.99 0.3²) - d/66
Applying Theorem A.6 with y= Vd/6, we can conclude that the sample complexity of M (which
is equal to 1) must be at least Q claimed.
<v//66 22 32(v//c). Thus, we must have 2 22 ((vd/c) as
D.2
Unknown Bounded Covariance
Next, we will prove the lower bound for the unknown bounded covariance case (Theorem 1.5
D.2.1 Reduction to Covariance Estimation
Algorithm 4 COVARIANCEESTTMMATO
Parameters: N,n, L E sampler Asapleer. agnostic learner Alearner for centered Gaussians
Sample XI....,NN P
for 1,...,,, I..ILd do
Randomly draw n subsamples X, X without replacement from X1,.... X
Yt < Asampler (X (X.,..... X₂²) N(O, E) + Awarner (Y,.... Yr.)
if 70.5T < 2.57 then
Σ + Σ
else
Σ + T
return Σ'
As stated earlier in Section 2 we will prove this lower bound by reducing to covariance estimation (Theorem A.7].. This is done by first taking > n samples, and then generating each Y! by subsampling the input to samples and rumning our DP sampler. These Y,'s 's are then feed into the agnostic learner produce an estimate Σ for Σ. The full reduction is given in Algorithm 4 Note that here Asampeer will be the (e, 6DDD sampler and Alearner will be the learner from Theorem A.8
Privacy Analysis. The privacy guarantee of Algorithm 4 follows easily from the amplification by subsampling and advanced composition of DP. This is formalized below.
Lemma D.1. For any
c* E
11, E (0.1), if Asampler is (c,5)-DP for c S
min
1, Any (m(22/6
N' 8 85
(05NN) Ln
8", then Algorithm is (e*,8*)-DD
Proof. First, we apply Theorem A.4 which means that computing a single Y, is (e',8')-DP where e'= In(1 + (n/N) - 1)),
8' (n/N) 6.
20

---

Then, applying Theorem A.5 with 61 = 0.58* implies that all (Y,..... ..) together is (c1, L8 L8' + +1)-
DP where
el (V221)(11))) Mee -1))
Combining the above expressions, we have
61 (2L L(n/N) - -1) In(1 - (n/N)(6 - 1))
(from 1 (2L (2n/N)(2)) In(1+ (n/N)()))22
(2L (2n/N) ((1/N)(26))
N
from E S
4n L (2(26
and Lo' 0 S 8" /2 8 /2 < 8 In other words, (Y,,... Y,) together is (c", -DP Finally,
applying Alcarner on (Y,,..., Yr. simply a post-processing step. Thus, the entire algorithm (6", JDDP as desired.
D.2.2 Accuracy Analysis
Next, we argue that the accuracy of the covariance estimation algorithm, assuming the accuracy of the sampler and the agnostic learner.
Lemma D.2. Let & (0, 0.01] and n, L E N be such that N 2 [10nSd' and suppose that Furthermore, suppose that
-accurate sampler for the class of Gaussians under the assumption 3 M Asampler is an
(
21, and
Alearner is an & g²
aaccurate agnostic learner for the class of centered Gaussians,
2008-
E < E² where ' denotes the output of where is the constant in Lemma A.2 Then, E Algorithm 3
Proof. Let D N(O, E) denote the underlying distribution and for notational convenience, let
5:= (==(6b) (00)) Let Edisjoint denote the event that i!...., th are all different. Note that have
Pr[ Pr(-Edissoiut]
Pr
Σ
1
1?2n2
e²
N2
2N
200d
where the last inequality follows from our choice of parameters.
Next, suppose that Edisjoint holds. Then, we have that Yi,..., Yz are independently sampled from g²
QAampter D. Applying the agnostic learning guarantee of Alearner with probability 1 get
20075
de. (N Σ), (Atampeerr S 3 dev E), QAmmptor D) + + Recall also from the accuracy guarantee of the sampler that dey (N(0, E), Q S Combining all of these together we have
e²
Pr[dey (N(0, I.), Q Amamplor D) 4C] 51
100d
Applying Lemma
A.2
we get
g2
Pr[l[S El|s > E/2
100d
Notice that I|ا 2 5 E/2, then we have Sy E. Furthermore, < = 21 and 0.51 N E =
2.5/ imply that || E - E)>> < 6d. Thus, we have
E||l > s (2/2)² + (6d)². Pr[] Elbs: E/2] (5/2)² (6d)2
100 S 5²
21

---

D.2.3 Putting Things Together
Combing the privacy and accuracy guarantees and plugging in the appropriate parameters immediately yields Theorem 1.5
Proof Theorem 1.3 Let = (110C) where & as in Theorem A.7 and as in Lemma A.2 Suppose for the sake of contradiction that there exists an (c, 8)-DP a-accurate sampler with sample
under the assumption / 1 Σ v 21. Then, let us select the parameters as complexity t/logd/
d
follows:
O (dP) denote the sample complexity of the
ga
-accurate agnostic learner for the
10C
2006
class of centered Gaussians as given by Theorem A.8
1. 27
S 50(n' log d).
8 O (min {1/N, (eM(NNloog) log N))). Note that, when the constant in big-O notation is sufficiently large, our choice of parameters implies that < (9.5N) 8
iney L1(2/8))) o(d//N).
By Lemma D.2 we have that B[I[E' -E < <E² Furthermore, by Lemma D.1 we have that the
algorithm COVARIANCRESTIMATON is (c*,8*)-DD However, we also have o(d? /c)), which contradicts Theorem A.7
L
E Product Distributions on (0,1)
In this section, we describe and analyze our sampler for product distributions on {0, 1)d (Theorem 1.7). We may assume w.l.o.g. that P...... Pa < 3/4. (Otherwise, we first privately estimate p; using, e.g., the Laplace mechanism, and flip the ith bit in all samples if the estimate is more than 3/4.)
Given dataset element X; E {0, 13d, use X, denote its jth coordinate, and X;[S] (Xili)iess denote the vector X; restricted to the subset S C [d] of coordinates.
E.1 Additional Preliminaries
Here list few concentration inequalities that useful. We start with the following version of the Bernstein inequality [see, 122 Thcorem 2.8.4]:
Theorem E.1 (Bernstein's 's inequality). Let Yi...., Yn be independent real-valued random variables such that, with probability 1, Y, E [0, C1 for all i E [n). Let V -ii(n)) var(Yi). Then, for any A > 0, we have
22
Pr
Σ Y. M E|Y KE[N)
>
A
S 2exp
2V + CA
SEin]
We now list a couple of versions of this inequality, which will be more useful in our setting.
Corollary E.2. Let P be a product distribution on {0, 10,1]a For any 3,7 E (0, let n > 50 log and X1 Xi...., Xn, P. Let X = EEE(n) X₁. Then, we have
Pr [Vj E [4] e [0.9p, - -, 1.1pp + 7 2 1 B.
Proof. For each j E [d], applying Theorem E. with A max (7, 0.1p;) }- n and using P5 S 3/4, obtain
2
8
Pr X py| < max 0.1p;}] < 2 exp
S 2 2xxp
2mp; + A
21
d
Taking union bound over all [d] completes the proof.
22

---

Corollary E.3. Let P be product distribution on {0, 13 For any 3,y E (0,
let n >
su
log d
and XI...., Xn P. Then, we have
Pr Vi E [n],
Σ jeld]
X
S 3d
4
log
71 B
2 1 - 3
max [pj,7}
?
Proof. Denote Y, = / max (pj. 7 for all E [d]. Here we have B[V; = Ps/ max (pj: S and var(Y;) S Pj/ [p,, 712 1/7. Moreover, with probability 1, we have Y, I 1/7 As result, we can apply Theorem E. with A 2d + 1lo((n33)3/ which gives
X.Di max (Pj,
- 22exp(-0.55y S 3
Pr
A
S 2 exp
2d/7 ad//+1/7)
}
SEId
Taking a union bound over all E [n]] completes the proof.
E.2 Private Preconditioner
We start with the following private preconditioner, which estimates each Pj up to constant factor. This preconditioner is similar to that of [27]. except that we add noise from the Laplace distribution T3 (instead of Gaussian noise) to achieve pure-DP and that we are looking for a coarser guarantee compared to (27].
Lemma E.4. There exists an e-DP algorithm that takes
o ((
(dlos
d )
log
ag
samples as input and output integers fi....,ee la {O..... [lg(( 2d 11} such that, with probability
1 - 3, the following hold for all j E [d]:
i + [log(
2d )1 then Pj E [1/4 2-442--; ,,,.////// 3/4 2- and
i [log( 2d 11 then Pj S a/2d.
In the remaining of this section, we will focus on the proof of Lemma E.4 and Algorithm
Sample Complexity, From Algorithm 5 the total sample complexity can be bounded by
Σ Th - RE[T]]
Σ (d+2*) FE|T.
log n.9
O
((Jloss
d d
log 0,
as desired.
Privacy Analysis. In each iteration E [T.). the samples Xf..... Xt ne after truncation, are noised with a Laplace distribution; by the privacy guarantee of the Laplace mechanism, each iteration thus c-DP. Furthermore, since each iteration uses fresh set of samples, by the parallel composition property DP, the entire algorithm is eDD as desired.
Accuracy Analysis. We will prove this by induction. Specifically, let S = {j [d] P3 S 3/4-2 and S: == {j E [d] p4 I 1/4 2-(). We will show that
/3 L'
34 (O..... 1), St. S St S 2 Pr
(6)
for all E [L] by an induction on t. Observe that this statement implies the desired accuracy claim in the lemma because j gets assigned l if and only if St Se+1. (Here we use the convention that S = 0.)
The Laplace distribution Lap(b) is given by the PDF ftapt)) (x) exp(-lal/6).
23

---

Algorithm 5 PRECONDITIONER PRODUCTDDSS
Input: An unknown product distribution over {0, 1)², privacy parameter c, accuracy parameter a,
failure probability parameter 3
Output: ,,...., la E {0, (0,1,...., [log( 2d )1}
log( 24)
E - 0 for every j E [d]
So [d]
foreach & = 0, ....., do
B₁ - 1000(d 2 +)
ny -- B₁ 2 log
a3
Sample Xi
X ni
Se+1
1 Gyg
Br Lap
qel [e(Se]
trunc (x))
iE(me]
foreach
j E St do
if qr [j] < 0.57 2-
then
Add to Se+1
else
t
foreach j E Sr. do
Eg 4 L
return l ,,...,ed ld
Base Case. (2) trivially holds for 0 as $ = So = [d].
Inductive Step. Suppose that O6) holds for t - 1 for some t E N. We will also show that it also holds for t. From union bound, suffices to show
Pr s c S, c c S S 21
8 L
To show this, need the following claim: Claim 1. Assume S,-1 S S For each j S,, with probability
0.5g Ldd
we have
1 74
Σ iE(md
trunch, (X!(s.)) E [[..pp, - 0.01 2 1.1p, 0.01 1-.01-29..
let us how to it to finish the proof. Let Zt Lap (Bt/e) be the Laplace noise added, First, by a standard concentration bound for the Laplace distribution, we have
Before prove Claim I
B
4Ld
0.53
Pr
log
2
B
Ld
Note also that by choice of parameters, have Bi/e log (4Ld/ (3 < 0.01 2 n Hence, by a union bound, we have that with probability .//L. for all j E S,,
q [0.8p, 0.02 2 , + 0.02 2-
Consider any j E S, \ ST. Since Pj 2 0.75 --, we have [r] 2 0.58 2 > Tt. Hence, will not be included in S,, coming to a contradiction. In other words, S, \ S = -0. S₁ S S.. Similarly. consider any S Since P, 0.25 2-++1 have q. [j] & 0.57 2- т. By Algorithm j will be included S, Hence, S C S.. These conclude the inductive step.
We are now left to prove Claim

---

Proof of Claim
1
Let Y, (trunc), B, (X(()))),
First note that
Y1
x1 Therefore, may apply Corollary E.2 which gives
sE(ne)
xE(mx]
0.253
Pr
Eys
+ 0.01 2- 1
nt
Ld
vE(mL]
Next, to give lower bound on Y,, we also observe that
Pr|Y, 1| = Pr [ = 1 and || & B.]
2 Pr[X] [j] 1 and || \ (ill BB- -
Pr[X][] 1| Pr[]]X][Ss {Л]ll s B, -1
= Py Pr[lIX;[S, \ fillla B, --11.. 1],
and
E x [iI1]] = E py-
JESADI
We that S₁ St-1 holds by Algorithm and S,-1 C S follows the assumption. Hence, Py 0.75 (--11) for every j' E St-1. Moreover, | S d. Putting everything together, we can further bound
E| E| À UHIN]
Σ
Ps S
Σ J'EST
Py d-0.5 2--(2-111))) s O.1(B. - 1).
J'EAMN
Therefore, by Markov's 's inequality, we have
Pr||| Gill s B, 1] 0.9.
Combining with the above, have Pr[Y; 2 0.9p,. Notice also that Yı,... Y,, are i.i.d. and
always lie between [0, 1]. Thus, we can apply Theorem E.1 with = (0.1p; + 0.01 2- to obtain
A
A
0.253
Pr
Σ tE
2 0.01 0.01
< 2exp
2exp
74
2p,m, + A
21A
Ld
Applying a union bound then yields the claim.
E.3
Sampler
Next, we give a DP sampler for an unknown product distribution, assuming that a rough estimate of each pj is already computed via the private preconditioner in Section E.2 The exact guarantee is given below; combining this with Lemma E.4, we immediately arrive at Theorem 1.7
Lemma E.5. Suppose that ......, la satisfy the conditions in Lemma E.4 Then, there is an c-DP algorithu taking E1.... La as input, that is a-accurate sampler and has sample complexity of
d (log(d/a)
25

---

Algorithm 6 PRODUCTDISTSAMPLER
Input: An unknown product distribution over {0. 1) privacy parameter c, accuracy parameter a, and fi...., la N satisfy the conditions in Lemma E.4
Output: A random sample that is a-accurate for
B 1d00(d/o)) log(d/o)
n < [
Sample x1..... X P
w 4- (2 22.....,,,"" 24a)
q " Lig(m) trunc B B,
for j = I..... do
Pj f clip Biy Bm
(q:)
Sample Z (p) x ... Ber(pa)
return Z
In the following, we will focus on the proof of Lemma E.3 with Algorithm 6
Privacy Analysis. Consider any pair X, X' of neighboring datasets. We may assume w.l.o.g. that the datasets agree except for X, and X We write .',77 denote the values of q, P computed for X', Now, consider any possible output {0, 1]d For each j [d], claim that
Pr(A(X'), V/]
S + Swy p,1-
Pr(A(XX; = Vsl
To show this, we first mention two facts:
Pr(A(X'), 0]
1 1 8/
10, Pil
11
Pr[A(X); = 0 1
1-96 P3
Pj
Pr(A(X');=]) =1 /7/
18/ 831
1 +
Pr(A(X); I] Pj
Pj
suffices show 1/(8w,) Do < 1 1/(ww)) prove 77 This follows since wi and 1/(8w,) S Dj S (880y) due to clipping.
We also note the following useful property:
1/w (d' - (
w| (trunc (X,,,) trunc) 1 B, wu (X,)))lz
2B
w| (trunc)).,, (Xx) + trunc B, (X,)))l1 <
(8)
Finally, we ready prove the privacy guarantee: Pr[A(X') = yl
Pr[A(X'), = yyl
II
II (1+ + Swy 10 1.
Pr(A(X) =
Pr Pr() =リ HE(d]
JE[J]
< II exp (Su,. 18 p21) exp (Sw 1/ - +
jEld]
16B
<exp (8w o 14' - g)) S exp
exp(c),
where the third inequality is due to clipping, the penultimate step follows 8 and the last step follows from our choice of parameters. Thus, the algorithm is c-DP as claimed.
Accuracy Analysis. Let S = Dji [d] p, < 2- We first consider the version of A (Algorithm 6 where there no truncation
all and there is no clipping for any j S. denoted as A'. Let Q. (pr ) @ ... @ Ber Fix 3 = a/12d < a/4. We define the event & as "no X; is truncated for any E [n] and no Pj is clipped for any j $ by Algorithm 6 By concentration results (Corollaries E.2 and E.3 with y 2 -1-1) and our selection of parameters, we can conclude that & happens with probability at least - 3, and therefore
dey (Av.
(.x. E) Pr(E] di (QA.P. -r(E]]
26

---

= -1-
Furthermore, see that E[pj] - Pý if S. For j E S. clipping ensures that pj 2 2 hence E[p3] - 2 2- Together, we have
dcv(QA.p,P) - Σ
Epp ppl = Σ
BBpj Pyl S Σ
2- S d. 2 S a//2.
jE(d
JES
JEB
Combining the above two inequalities yields the a-aceuracy guarantee A:
div (QA,,, P) S dev (QA.P: + des (QAi,, a/2 a a.
1.7 For simplicity, let a' be the target accuracy parameter. Set = / and a/ 12d a' /2/2. We define the event & as "Algorithm returns e,..... La satisfying the properties in Lemma E.4 If & holds, then the error of our sampler is most but this event happens with probability at most 3 < a2/2. Together, the error of our sampler is
Proof of Thheorem 1.7 Finally, we are ready to prove Theorem
most a' /2, which is implied by Lemma E.5 If & fails, the error
a' d2/2 (1 - B) + a' /2 2222222 a', and the sampling complexity (with 3 a' /24d)
d
d
log ap + a'e
=0 (d)
( (d)
a ))
doog
+
log
log"
+ log
a'
a'
a
a'e
as desired.
27


Reviews:
[{"review_id": "RNXowjgcOh", "reviewer": "Reviewer_jqWC", "summary": "This paper considers a very interesting problem: Design a $\\mathit{differentially~private}$ algorithm that given samples from unknown distribution $D$ from a class of distributions ${\\mathcal D}$, output a sample from a distribution $D'$ where $D'$ is close to $D$ in total variation distance. One direct approach is to first learn the distribution $D$ in a differentially private manner and output a sample from the distribution. However, the paper argues that learning is an overkill. The paper shows that the sample complexity of DP-sampling problem is substantially less than the DP-learning problem in many cases. In particular, they design algorithms for DP-sampling algorithms of $d$-dimensional Gaussian distributions with optimal sample complexities. They consider three subclasses of Gaussian distributions: (1) known covariance (2) unknown but bounded covariance (3) unknown unbounded covariance -- and sample optimal DP-sampling algorithms for these class of distributions. They also consider the class of product distributions and give optimal pure DP-samplers. Earlier, only approximate DP-samplers where known.      ", "questions": "I do not have any major questions at this point. ", "limitations": "This is a theoretical paper and does not seem to have any negative societal impact. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The problem they consider is very interesting to me: producing samples from unknown distribution in a differentially private manner appears to be a very basic task. Investigating this problem for Gaussian distributions should be of broad interest.", "weaknesses": "I am not sure whether it is a weakness, all proofs are in the appendix and are for specialist so may not be accessible to general audience. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review & comments.\n"}, {"review_id": "jK4JOrCKYl", "reviewer": "Reviewer_nVvL", "summary": "Raskhodnikova, Sivakumar, Smith, and Swanberg (NeurIPS '21) recently introduced the problem of privately approximate sampling: Given i.i.d. draws from a member D of a known family of distributions, produce one sample whose distribution is close to D in TV distance. This is an easier task than the well-studied problem of private distribution learning, while isolating some of its algorithmic difficulty, and RSSS'21 gave several upper and lower bounds for discrete distributions and product distributions.\n\nThis submission addresses several open directions from RSSS'21 by 1) thoroughly investigating the sample complexity of privately sampling from Gaussians, and 2) giving a pure DP sampler for Bernoulli product distributions with optimal sample complexity (the sample-optimal algorithm from RSSS'21 only guaranteed approximate DP). In more detail, this paper establishes tight (up to polylog factors) sample complexity upper and lower bounds for sampling from Gaussians with either known or a prior bounded covariance, as well as giving an upper bound in the unbounded covariance case that separates DP sampling from DP learning.", "questions": "- On the topic of generalizing to other distributions: Many algorithms for learning distributions (including Gaussians) readily generalize to the semi-agnostic case, incurring additional error that scales with the amount of model misspecification. Does such a ready generalization apply to the algorithms in this paper?\n\n- Lines 81-82 mention that the paper's algorithms run in polynomial time. In what computational model? Since the problems considered require TV-close sampling from continuous distributions, it's not clear that taking a fixed precision discretization suffices.\n\n- Is it possible to incorporate some polylogarithmic in $\\alpha$ dependence on the error in the lower bounds for Gaussian sampling? (As things stand, it could be the case that the right dependence on $\\alpha$ is, say, doubly logarithmic.)", "limitations": "The paper's conclusion raises the question about extending beyond Gaussian distributions mentioned above, as well as the problem of closing the quantitative gap between upper and lower bounds for the unbounded covariance case.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The problem of private sampling is reasonably well-motivated from the standpoint of \"applications\" (i.e., minimizing the overhead of privacy when full distribution learning is not necessary) as well as from the standpoint of doing theory, i.e., developing a finer understanding of what makes private statistical analysis challenging, establishing new algorithmic primitives that can be used elsewhere, and more generally forcing us to develop new techniques.\n\n- Within the context above, this paper addresses two of the most fundamental classes of distributions. In several cases, it identifies nearly matching upper and lower bounds.\n\n- The paper makes the interesting finding that, at least for Gaussian sampling, the dependence on the error parameter $\\alpha$ is at most polylogarithmic. In contrast, the dependence is at least polynomial for learning Gaussians, as well as for the discrete sampling tasks studied previously.\n\n- Both the algorithms and lower bounds exhibit interesting (and in my opinion, surprising) technical insights. For instance, Algorithm 2 for learning Gaussians with unknown bounded covariance describes and analyzes a new sampling distribution based on taking linear combinations of spherical noise. As another example, the lower bound for the same setting implements a conceptually very natural reduction, but has to overcome a technical issue of breaking the correlation between samples generated by running a private sampler multiple times on the same dataset (which addresses a more general issue with DP sampling and could be used in other contexts).", "weaknesses": "- The algorithms for Gaussian sampling are quite specialized to Gaussians, and it's quite difficult to imagine how they might generalize to other classes of distributions.\n\n- This is sort of a nitpick, but I think the writing could highlight some of the new ideas described under \"strengths\" above, e.g., with lemma statements that would make them easier to apply elsewhere.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review & comments. Please find our answers to the questions below.\n\n- It is possible to get some bounds in the agnostic case using our algorithms, but these bounds are not particularly good. In particular, let $n$ be the sample complexity in our algorithms (e.g., from Theorems 1.2, 1.4, or 1.6). Then, if we just run the same algorithm for some distribution $D$ that is $\\gamma$-close in TV distance to a Gaussian (in the corresponding setting), then the accuracy parameter will increase to $\\alpha + n \\gamma$.\n- For simplicity, we assume that our algorithm can add, subtract, multiply, and divide real numbers; furthermore, we assume that we can sample from a (one-dimensional) Gaussian distribution exactly. We note that it is a fairly standard assumption in DP literature when continuous (e.g., Laplace / Gaussian) noise is involved. It is possible to make our algorithm work in the finite-precision setting but this is quite complicated (the accuracy guarantee will need to be with respect to the discrete instead of the continuous Gaussians, or in the Kolmogorov distance instead of the total variation distance).\n- This is a very interesting question. We are not aware of any lower bounds involving $\\\\alpha$ and we will include this as an open question in the revision.\n"}, {"review_id": "1yPhroBGzj", "reviewer": "Reviewer_cbpB", "summary": "The paper considers the problem of sampling from distributions under differential privacy. In particular, the specific formulation presented in the paper assumes the existence of a dataset that has been drawn i.i.d. from a distribution $P$ that belongs in a family of distributions $\\mathcal{F}$ and the goal is to a generate a sample from a distribution $Q \\in \\mathcal{F}$ such that $d_{\\mathrm{TV}}(P, Q) \\le \\alpha$ in a way that protects the privacy of the input dataset. This problem is considered for various choices of $\\mathcal{F}$, which include i) Gaussians with uknown mean but known covariance, ii) Gaussians with unknown mean and unknown covariance $\\Sigma$ which satisfies $I \\preceq \\Sigma \\preceq \\kappa I$ for some known $\\kappa$, iii) Gaussians with unknown mean and covariance without any a-priori bounds on $\\Sigma$, iv) binary product distributions. The results include upper bounds for the aforementioned families, as well as lower bounds for families (i) and (ii).", "questions": "I guess the one question I have has to do with the main issue I raised in the section about weaknesses. Is there something that I have missed or misjudged in terms of the dependencies in the range parameters? If I have misunderstood something and the authors can clarify things to me, I am open to raising my score.", "limitations": "The work is purely theoretical and doesn't have any obvious prospects for societal impact (positive or negative).", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The writing is fairly accessible and it is relatively easy to grasp the results and follow the exposition. In terms of contributions, I feel the main strength of the paper lies in the results about binary product distributions, which constitute significant improvements over prior work. Additionally, the arguments via which the lower bounds are established are quite elegant.", "weaknesses": "I have two main concerns with this work.\n\nThe first has to do with the bounds given for Gaussian distributions. In particular, while the guarantees given in the paper are tight (or nearly tight) with respect to the dimension $d$, it seems like the guarantees are sub-optimal in terms of the range parameters. For the case of Gaussians with known covariance but unknown mean, the dependence in the sample complexity for sampling under approximate differential privacy is polynomial with respect to $R$ (Theorem 4.2), where $R$ is a positive real number such that $|| \\Sigma^{- \\frac{1}{2}} \\mu ||_2 \\le R$. In [KV18], the authors show that, under approx-DP, you do not need any a-priori bounds on the mean to do parameter/density estimation for univariate Gaussians. This immediately extends to $d$-dimensional Gaussians with known covariance, since one can rescale the datapoints by $\\Sigma^{- \\frac{1}{2}}$ to make the Gaussian spherical and then apply the algorithm of [KV18] component-wise. Thus, it feels out of place for sampling to require a polynomial dependence on $R$, despite sampling being an easier task than estimation. Similarly, I have a similar concern for the guarantees of Theorem 4.3, both related to the dependence in $R$ and in $\\kappa$.\n\nThe second concern (which is not as significant as the first one) has to do with the model considered. The standard formulation of the sampling problem involves having a known target distribution that you want to draw a sample from and defining a process that randomly generates points that come from a distribution that's close to the target (e.g., via a random walk). In this formulation, there is no input dataset to work with, thus not leaving much room for formulations that involve DP. In light of this, the variant of the standard sampling problem considered in this paper feels somewhat artificial. It might make sense in the context of e.g., synthetic data generation (a topic on which there is a broad literature), but it feels a bit odd to market this as ``sampling with DP\". However, to be fair, this is a criticism that one could make about [RSSS21], which is the paper that introduced the model that the present paper considers. For that reason, this is not something I hold against this work and I consider it minor compared the points raised in the previous paragraph.\n\nOverall, if the guarantees were to be optimized in terms of the range parameters, I believe a polished version of this paper could stand a chance to be accepted. However, in its current form, I feel this work is not ready for publication.\n\n==== Update ====\n\nThe rebuttal addressed my main concern. For that reason, I raised my score from 3 to 5. Depending on how discussion among reviewers and the AC goes, I might further increase my score to 6. The reason I'm not considering giving the paper a higher score is due to the issue I raised regarding the fact that the model might be of somewhat limited interest.\n\n[KV18] Vishesh Karwa and Salil P. Vadhan. Finite sample differentially private confidence intervals. In\nITCS, pages 44:1–44:9, 2018\n\n[RSSS21] Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, and Marika Swanberg. Differentially\nprivate sampling from distributions. In NeurIPS, pages 28983–28994, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to correct the misunderstanding here: Our bounds are completely *independent of the $R$ parameter* and in fact *do not* require any assumption on $R$. Please refer to Theorems 1.2, 1.4, and 1.6 for our bounds.\n\nIt seems like the misunderstanding is perhaps due to focusing on the bounds in Section 4.2. However, as we point out in Section 4.1, it is simple to use a known result in literature to reduce the general case to the case where $R$ is bounded. In particular, Lemma 4.1 essentially says that we may assume w.l.o.g. that $R \\\\leq O(\\\\kappa \\\\cdot \\\\sqrt{d})$. As we stated in the paper, combining Lemma 4.1 with the bounds in Section 4.2 (Theorem 4.2 and Theorem 4.3 respectively) immediately imply the bounds that are *independent* of $R$ (Theorem 1.2 and Theorem 1.4, respectively).  Apologies for causing the confusion; in the revision, we will reword this more clearly.\n\nDue to this misunderstanding, we kindly ask the reviewer to adjust the score accordingly.\n\nRegarding the dependency on $\\\\kappa$, indeed our Theorem 1.4 for the bounded unknown covariance case has a polynomial dependency on $\\\\kappa$ but we wish to point out that the other two main theorems (Theorem 1.2, Theorem 1.6) *do not* have any dependency on $\\kappa$. As we noted in footnote 6 (page 8), it is possible to reduce the dependency in Theorem 1.4 to polylogarithmic in $\\\\kappa$ but we have to increase the dependency on $d$ to $d^{1.5}$. It remains an interesting question whether one can get $polylog(\\\\kappa)$ dependency while having linear dependency on $d$. We will make sure to highlight it as an open question in the revision.\n"}, {"review_id": "ouEYCVmkjA", "reviewer": "Reviewer_iEFD", "summary": "This work studies the problem of differentially private sampling. In this setting, the goal is the following: Given $n$ iid samples from an unknown distribution (e.g., a Gaussian distribution with an unknown mean), design a private algorithm that produces a fresh sample from the distribution the original samples came from. This framework was recently introduced with the following motivation: Sometimes it would be useful to have access to a synthetic dataset, i.e., a dataset that behaves in the same way as the original one but doesn't reveal any information about it.\n\nThe authors systematically investigate this problem for various cases of the gaussian distribution. They give algorithms and nearly matching lower bounds. They also have some results for the binary setting.", "questions": "Related to my comment above: Do you believe the discrete setting is inherently harder? Could it be that the difference between learning and sampling is less stark in this setting?", "limitations": "The authors discuss limitations and open questions related to their work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In my eyes, this paper makes important contributions to a new interesting line of work. In particular, it shows that, at least for the Gaussian distribution, the private sampling task is inherently easier than the associated learning task, e.g., learning the mean. For the former, the dependence on the accuracy parameters is only logarithmic, while for the latter it is polynomial.\n\nThe authors investigate this task in a systematic way, in the gaussian case, they study three different natural settings (known covariance, unknown and bounded covariance, and unknown and unbounded covariance) and give upper and lower bounds.", "weaknesses": "For the discrete setting, the dependence on the accuracy parameter is qualitatively worse (polynomial vs. logarithmic). It would be nice to give some intuition if this necessary and if so, why. For instance, is there any lower bound that you can prove? Even one that is not necessarily tight.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The polynomial dependence on $1/\\\\alpha$ is necessary in the product distribution case; as indicated in Table 2, it was already shown in [34] that the sample complexity for $(\\\\epsilon,\\\\delta)$-DP is at least $\\\\Omega(d/\\\\alpha\\\\epsilon)$. As you said, it is indeed a pretty interesting situation, since we can get a polylogarithmic dependency for Gaussians but (provably) not for product distributions. We will make this clearer in the revision.\n\nSince the dependency of $\\\\alpha$ in our algorithm is essentially tight in the product distribution case, we kindly ask the reviewer to adjust the score accordingly.\n"}, {"review_id": "CeGmCBScVa", "reviewer": "Reviewer_Tiqw", "summary": "The paper discusses the problem of generating a sample from a distribution that is close to an unknown distribution P, under the constraint of differential privacy. The authors present new differential privacy sampling algorithms for multi-dimensional Gaussian distributions, with different assumptions on the available information. They also obtain a pure-DP algorithm for product distributions on the binary hypercube. The paper aims to bridge the quantitative gap between DP distribution sampling and DP distribution learning.", "questions": "See weakness", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper proposes a new DP sampling algorithm for multivariate Normal and the product Bernoulli distribution.\nIt also aims to bridge the gap between DP distribution sampling and DP distribution learning. It could lead to more effective and efficient methods for privacy-preserving machine learning.\n\n", "weaknesses": "The scope of the paper is quite limited as it only focuses on Gaussian and binary product distributions. While these are important classes of distributions, the applicability of the proposed methods to other types of distributions remains unclear. It would be beneficial if the authors could extend their analysis to a broader range of distributions or discuss the potential challenges and strategies for doing so.\n\nThe paper indicates that fewer samples are needed for estimation under these specific parameter families compared to sampling. It's not clear whether this is due to the geometry of the parameter space and output space, or if it's more related to the properties of differential privacy itself, perhaps due to the use of the composition theorem. It would be interesting to see a discussion on whether similar situations occur in non-DP settings. This could help clarify whether the observed phenomena are intrinsic to differential privacy or if they are more general statistical phenomena.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* While it would be nice to have a more generic algorithm, we note that it is usually quite difficult to nail down the exact sample complexity in DP for a generic family of distributions. To give a sense of this difficulty, note that it required more than a dozen papers (cited in our paper) focusing almost solely on learning of Gaussian distributions to reach the current state-of-the-art results (which nonetheless are still not completely tight in some regime of parameters). This is the motivation for us to focus on Gaussian and product distributions in this work. We do agree that extending this to other distributions is a very interesting direction and indeed we had included this in the last section (Line 361).\n\n* Regarding the intuition, note that without privacy constraints, the sampling problem is trivial: just output the input sample. This requires only a single sample and has no error at all! Therefore, sampling is also easier than learning in the non-private setting as well. On the other hand, the privacy constraints make the sampling problem much more challenging which is why it is unclear whether it is even easier than learning—the question we answer in this paper for Gaussians.\n"}]

Author rebuttal:

Meta-review: The authors consider the problem of differentially private sampling from an unknown distribution (which is easier than learning that distribution). The authors prove multiple results about private sampling from Gaussians and product distributions.

The reviewers found the results interesting and impactful, and in some cases surprising (e.g., the polylogarithmic dependence of the sample complexity of private Gaussian sampling on the accuracy parameter).

Based on these, I recommend acceptance.
Decision: Accept (poster)