Private Distribution Learning with Public Data: The View from Sample Compression
Authors: Shai Ben-David
Alex Bie
Clement Louis Canonne
Gautam Kamath
Vikrant Singhal
Venue: NeurIPS 2023 spotlight (2023)
Keywords: differential privacy
distribution learning
gaussians
mixture of gaussians
compression schemes
robust compression schemes
privacy
TL;DR: We connect public-private distribution learning to sample compression and list learning, which yields flexible ways to prove new upper and lower bounds on sample complexity.

Abstract: We study the problem of private distribution learning with access to public data. In this setup, which we refer to as *public-private learning*, the learner is given public and private samples drawn from an unknown distribution $p$ belonging to a class $\mathcal Q$, with the goal of outputting an estimate of $p$ while adhering to privacy constraints (here, pure differential privacy) only with respect to the private samples. 
    
We show that the public-private learnability of a class $\mathcal Q$ is connected to the existence of a sample compression scheme for $\mathcal Q$, as well as to an intermediate notion we refer to as \emph{list learning}. Leveraging this connection: (1) approximately recovers previous results on Gaussians over $\mathbb R^d$; and (2) leads to new ones, including sample complexity upper bounds for arbitrary $k$-mixtures of Gaussians over $\mathbb R^d$, results for agnostic and distribution-shift resistant learners, as well as closure properties for public-private learnability under taking mixtures and products of distributions. Finally, via the connection to list learning, we show that for Gaussians in $\mathbb R^d$, at least $d$ public samples are necessary for private learnability, which is close to the known upper bound of $d+1$ public samples.

Private Distribution Learning with Public Data: The View from Sample Compression"
Shai Ben-David University of Waterloo Vector Institute shai@uvaterloo.co ca
Alex Bie University of Waterloo yabie@uwaterloo.cm ca
Clément L. Canonne University of Sydney
clement. canonnessydneeey...oooooo.o..... edu. au
Gautam Kamath
Vikrant Singhal
University Waterloo Vector Institute gocsail .mit.
University of Waterloo
vikrant vikrant.singhann www.sssiiaaaaaaaaaaeeo.oo.o
Abstract
We study the problem of private distribution learning with access to public data. In this setup, which we refer to as mublic-private learning, the learner is given public class Q,
and private samples drawn from unknown distribution p belonging with the goal of outputting an estimate of p while adhering to privacy constraints (here, pure differential privacy) only with respect the private samples.
We show that the public-private learnability of class is connected the existence of sample compression scheme for Q, as well as to an intermediate notion we refer as list learning. Leveraging this connection: (1) approximately recovers previous results on Gaussians over R and (2) leads to new ones, including sample complexity upper bounds for arbitrary k-mixtures of Gaussians over TR. results for agnostic and distribution-shiff resistant learners, as well as closure properties for public-private learnability under taking mixtures and products of distributions. Finally, via the connection list learning, show that for Gaussians in Id, at least d public samples are necessary for private learnability, which close to the known upper bound of d + public samples.
Introduction
Statistical analysis of sensitive data, and specifically parameter and density estimation, is a workhorse of privacy-preserving machine learning. To provide meaningful and rigorous guarantees algorithm for these tasks, the framework differential privacy (DP) [DMNS06] has been widely adopted by both algorithm designers and machine learning practitioners [App17, Abo18, XZA 23], and is, by and large, one of the past decade's s success stories in principled approaches to private machine learning, with host of results and implementations [Goo19a, Goo19b, HBAL19, Ope20] for many of the flagship private learning tasks.
Yet, however usable the resulting algorithms may be, DP often comes at steep price: namely, many estimation tasks simple without privacy constraints provably require much more data be performed privately; more dire, they sometimes become impossible with any finite number of data points, absent some additional strong assumptions.
The prototypical example in that regard is learning a single d-dimensional Gaussian distribution from samples. In this task, learner receives i.i.d. samples from an unknown d-dimensionnl Gaussian p
Authors are listed in alphabetical order. Full paper: https://arxies htwp://wwww..gggab//....00000
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and is tasked with finding an estimate close to p in total variation (TV) distance. Without privacy constraints, is folklore that this can be done with O(d)) samples; yet once privacy enters the picture. in the form of pure differential privacy, no finite sample algorithm for this task can exist, unless bound on the mean vector and covariance matrix are known.
This "cost of privacy" is, unfortunately, inherent to many estimation tasks, as the positive results (algorithms) developed over the years have been complemented with matching negative results (lower bounds). In light of these strong impossibility results, it is natural to wonder if one could somehow circumvent this often steep privacy cost by leveraging other sources of public data to aid the private learning process.
Recent work in finetuning machine learning models has tried address the question whether, in situations where a vast amount of public data is available, one can combine the public data with a relatively small amount of private data to somehow achieve privacy guarantees for the private data and learning guarantees that would otherwise be ruled out by the aforementioned impossibility results. We, on the other hand, address the same question, but in the opposite setting, i.e., when the amount of public data available is much smaller than the amount of private data available. In other words, we answer the following question from new perspectives.
Can one leverage small quantities of public data to privately learn feornfrrm sensitive data, even when private learning is impossible?
This question was the focus of a recent study of Bie, Kamath, and Singhal [BKS22], the starting point of our work. In this paper, make significant strides in this direction, by obtaining new "plug and play" results and connections in this public-private learning setting, and using them to obtain new sample complexity bounds for a range of prototypical density estimation tasks.
1.1 Our results
First, we establish a connection between learning (in the sense of distribution learning or density estimation) with public and private data (Definition 2.4) and sample compression schemes for distributions (Definition 2.5; see [ABDH+20 20, Definition 4.2]), as well as an intermediate notion we refer as list learning (Definition 3.2).
Theorem 1.1 (Sample compression schemes, public-private learning, and list learning (Informal; see Theorem D.I)). Let Q be class of probability distributions and m(a, 3) be sample complexity function in terms of target error a and failure probability B. Then the following are equivalent.
1. Q has sample compression scheme using (m,(a, 3)) samples.
2. public-privately learnable with (mm(a,8) B)) public samples.
3. Q is list learnable with ((m(a, B)) samples.
Despite its technical simplicity, this sample complexity equivalence turns out to be quite useful, and allows to derive new public-private learners for an array of key distribution classes by leveraging known results on sample compression schemes. In particular, from the connection to sample compression schemes are able to obtain new public-private learners for: (1) high- dimensional Gaussian distributions (Corollary E.1); (2) arbitrary mixtures of high-dimensional Gaussians (Theorem I. 1.2/Corollary E.2); (3) mixtures of public-privatelyy learnable distribution classes (Theorem 4.3/E.5); and (4) products of public-privately learnable distribution classes (Theorem 4.3/E.7). For instance, the following is consequence of the above connection.
Theorem 1.2 (Public-privanl learning for mixtures of Gaussians (Informal; see Corollary E.2)). The class of mixtures of arbitrary d-dimensional Gaussians is samples and n private samples, where
learnable with m public
( kdd and n =
kd a²
kd
m =
+
aE
in which is the target error and the privacy parameter.
We also examine public-private distribution learning in a setting with relaxed distributional assump- tions, in which the distributions underlying the public and private data: (1) may differ (the case of

---

public-privee distribution shift); and (2) may not be members of the reference class of distributions, and so we instead ask for error close to the best approximation of the private data distribution by member of the class (the agnostic case). We show that robust sample compression schemes for class of distributions can be converted into public-private learners in this agnostic and distribution- shifted setting. As consequence, we have the following result for learning distributions that can be approximated by Gaussians under public-private distribution shift.
Theorem 1.3 (Agnostic and distribution shifftdd public-private learning for Gaussians (Informal: see Corollary F.I)). There is public-private learner that takes m public samples and private samples from any pair of distributions p and p over Rd respectively, with TV(5.)) S 1, where
m = O (d) and n n=Ō -6
d2
in which a is the target error and E the privacy parameter. With probability To the learner outputs q with TV (g. 2 30PT + a, where OPT is the total variation distance between p and the closest d-dimensional Gaussian to it.
Next, using the aforementioned connection to list learning. we are able to establish a fine-grained lower bound on the number of public data points required to privately learn high-dimensional Gaussians.
Theorem 1.4 (Almost tight lower bound on privately learning Gaussians with public data (Informal; see Theorem 6.1)). The class of all d-dimensional Gaussians is not public-privatee learnable with fewer than d public samples, regardless of the number of private samples.
[BKS22] showed that d-dimensional Gaussians are public-privately learnable with Ö private samples, as soon as d + public samples are available. Thus, our result shows very sharp threshold for the number of public data points necessary and sufficient to make private learning possible.
We also provide a general result for ioolic-privately learning classes of distributions whose Yatracos class has finite VC dimension.
Theorem 1.5 (VC dimension bound for public-private learning (Informal; see Theorem 7.2)). Let Q be a class of probubility distributions over a domain such that the Yatrucos class of Q, defined as
H Hx: f(x) > g(x)} f.g E C
has bounded VC dimension. Denote by VC(H) and (H) the VC and dual VC dimensions of H respectively. Then Q is public-privately learnable with m public samples and n private samples, where
-:(VCCC)
(CC(H)
and n Ō (VCCH)
( VC*(H) (H)
m Ō
E EQ
in which a is the target error and E the privacy parameter.
The Ö( VC(H) public sample requirement is less than the known O VC(H)) 2²
sample requirement to leamn with only public data via the non-private analogue of this result [Yat85, DLO1].
1.2 Related work
The most closely related work is that of Bie, Kamath, and Singhal [BKS22], which initiated the study of distribution learning with access to both public and private data. That work studied algorithms for specific canonical distribution classes, while the present paper aims to broaden our understanding of public-private distribution learning in general, via connections to other problems and providing more general approaches for devising sample efficient public-private learners. In addition, we prove the first lower bounds on the amount of public data needed for private distribution learning.
There a long line of work on private distribution learning, especially with regards to Gaussians and mixtures of Gaussians. [KV18] studied univariate Gaussians, showing that logarithmic dependencies on parameter bounds are necessary and sufficient in the case of pure DP, but can removed under approximate DP. The same is true in the multivariate setting [KLSU19, KMS+22 TCK- 22, AL22,
3

---

KMV22, LKO22]. For mixtures of Gaussians, most studies have focused on parameter estimation of mixture components [NRS07, KSSU19, CKM 21, C3, AAL23b], and employ component separation and mixing weight assumptions. For density estimation (the setting studied in this work) [BKSW19, AAL21] give learnability results under various structural assumptions. The concurrent work of Azfali, Ashtiani, and Liaw [AAL23a] gives the first learnability result for general high- dimensional mixtures Gaussians under approximate differential privacy.
Outside of distribution learning, there is a significant interest in using public data to improve private algorithms. Some problems studied include private query release, synthetic data generation, classification, mean estimation, empirical risk minimization, and stochastic convex optimization [JE13, BNS16, ABM19, NB20, BCM 1 20, BMN20, LVS + 21, KADV23, LLHR23]. The definition of public-private algorithms that we adopt is from [BNS16] 16], which studied classification in the PAC model. The VC dimension bound we give for public-pric private distribution learning relies on results from public-private classification [ABM19] and uniform convergence [BCM+20]
On the technical side, we establish connections with distribution compression schemes as introduced by [ABDH* 20J, and directly apply their results to establish new results for public-public learning. Related compression schemes for PAC learning for binary classification have been shown to be necessary and sufficient for learnability in those settings [LW86, MY16]. For further discussion of related work, please see Appendix A.
1.3 Limitations
Our work investigates the sample complexity of public-private learning, and does not give computa- tionally efficient learners, or in some cases, algorithmic learners that run in finite time. In particular, all public-privatt learners we obtain from sample compression run in time exponential in the sample complexity. Also, for our VC dimension upper bounds, we enumerate all realizable labellings of the input sample as per the relevant Yatracos class H. which is not computable for general H. [AABD* 20]. Finally, dependence on VC (H) sample complexity is not ideal, as VC* (H)) < 2V(H)++ the best possible upper bound in terms of VC(H) for general H [Ass83].
is
2 Preliminaries
2.1 Notation
We denote by X' the domain of examples. For domain U, denote by A(l) the set of all probability distributions over U. We refer to a set Q S (XX' as a class of distributions over X.
We equip ((X) with the total variation metric, which is defined follows: for p. 9 A(X), TV (p, q) == sup (p(B)- - q(B),, where are the measurable sets of X. For E A(X) and set of distributions L A(X)), we denote their point-set distance by dist L) inf gn TV q).
We will let ã- (51 (........ 2m) E x denote a public dataset and (z (........ ... 2n,) E X denote private dataset. Their respective capital versions X, X denote random variables for datasets realized by sampling from some underlying distribution. For A(X), we denote by nd the distribution over x obtained by concatenating m i.i.d. samples from p.
2.2 Public-private learning
Definition 2.1 (Differential privacy [DMNS06]). Fix an input space X' and an output space y. Let e, 8 > 0. A randomized algorithm A X A()" is (s, deiff-lliflrletiaally private ((e, 6)-DP) if for any private datasets æ;, x' E X differing in one entry,
IP \~z(
(Y E B} < exp(e) y'-A(m")
P.P.
(Y' E +8 for all measurable B C.
'The comment of reviewer rJev points out an approach to address the non-constructive nature of the reduction of public-privately learning mixture classes the m public samples and running the public-price coolic-private learner on n "null samples" repeatedly (with different random coins) produces a cover containing the true distribution with high probability. From here, we can run this procedure on all subsamples of the public data and construct containing the true (mixture) distribution.
learning the base class. summarize: fixing

---

The case where 8 = 0 is referred to as pure differential privacy or E-DP.
Our focus is understanding the public data requirements for privately learning different classes of distributions. We seek to answer the following question:
For a class of distributions Q. how much public data is necessary and sufficient render 2 privately learnable?
To do so, give the formal notion of muubicc-prvvate algorithms" algorithms that take public data samples and private data samples as input, and guarantee differential privacy with respect to the private data studied previously in the setting of binary classification [BNS16, ABM19]. We restrict our attention to public-private algorithms that offer a pure DP guarantee to private data.
Definition 2.2 (Public-private E-DP). Fix an input space X and an output space V. Let > 0. A randomized algorithm A: A x X + A (J)) is public-private e-DP if for any public dataset ATT the randomized algorithm A )) X + A()) E-DP.
Definition 2.3 (Public-privatte learner). Let Q C (XX). For a, B (0, 1] and 0, (a, 3,=)-
public-private learner for Q is a public-private s-DP algorithm A X x X - A(A(X)), such that for any p E Q, if we draw datasets X = (X 1 Xm) and X = (X,, (.., X,) i.i.d. from p and then Q XX,
8 2mp" X~m" sa) 1 Q~A(XXx)
Definition 2.4 (Public-privately learnable class). We say that class of distributions Q C ( is public-privately learnable with m(a, 3, public and n(a, 3) private samples if for any a, 8 E (0, and 0, there exists an (a, (aae)))ublcc-pivvatt learner for that takes m(a, a, 3, public samples and n = n(a, 3,e) private samples.
When Q satisfies the above, may omit the private sample requirement, and say that Q is public- privately learnable with m(a. B, E) public samples.
Denote by SCo(a, 3) the sample complexity of learning Q. Our primary interest lies in determining when non-privately learnable Q can be public-privately learned with m(a, 8, = e 3))
public samples (at target e).
2.3 Sample compression schemes
One of the main techniques that we use this work to create public-private learners for various distribution families is the robust sample compression scheme from [ABDH*20], Roughly speaking, every member of a class of distributions Q admits a way to encode enough information about itself in small number of samples from q and extra bits, such that it can be approximately reconstructed by a fixed and deterministic decoder, Q can be learned.
Definition 2.5 (Robust sample compression 2A Definition 4.2]). Let 2 0. We say Q S A admits (r 3), t(a, 3), m(a: 3)) r-robust sample compression if for any a, 3 E (0, letting 7(0,3)) = t(a, (), m((, 3), there exists decoder g: X {0, 1) A(X),
such that the following holds:
For any q E Q there exists encoder fo: n X {0, 1)' satisfying for all E x that for all ė [T]. there exists j E [m] with fg (x); = æy. such that for every E A(X) with TV q) $ r, if we draw dataset X (X1, Xm) i..dd from p. then
(TV(g(F, 2a}21-B.
X-upma
When @ satisfies the above, we may omit the compression size complexity function 7(a, 3) and bit complexity function ((a, B), and say that Q is r-robustly compressible with m(a, B) samples. When = O, we say that Q admits (r(a, B), Mox B), m(a,, realizable compression and is realizably compressible with m(a 3) samples.
Both robust and realizable compression schemes satisfy certain useful properties that we use to develop public-private distribution learners in different settings. For example, the existence of realizable compression scheme is closed under taking mixtures products of distributions.
5

---

3 The connection to sample compression schemes
In this section prove Theorem 1.1/D.1, the sample complexity equivalence between sample compression (Definition 2.5), public-private learning (Definition 2.4), and an intermediate notion refer to list learning (Definition 3.2). We do so by giving sample-efficint reductions between the three notions (Propositions 3.1, 3.4, and 3.5). The propositions state the quantitative translations between:
compression size 7 and number of bits number of private samples n, and list size E.
3.1 Compression implies public-private learning
We start by establishing that the existence of a sample compression scheme for Q implies the existence of public-private learner for Q
Proposition 3.1 (Compression = public-private learning). Let Q C A Suppose Q ad- mits (T(a, 3), t(a, $), mc B)) realizable sample compression. Then Q is mublic-privately
learnable with m(a, (,E) = mc( 2. 2) public and B,c) = O a= + de) (A(g 6 2
g
7 ( log [) + log( h))) private samples.
Proof sketch. The full proof is given in Appendix D.I, and mirrors that of Theorem 4.5 from [ABDH 20] (albeit adapted to the public-prive private setting). Fix a, E (0,1) and > 0. Let ==(@ (). = ( ) and m mc ( ) We draw public sample X of size m, and enumerate all combinations
size subset of X with a binary string of length I. Essentially, we "guess" the encoding of the unknown distribution p. Running the decoder on this set of possible encodings gives us a set of distributions; some of them are close to p. Then, with private samples only, we use the pure DP 3-agnostic learner for finite classes (Fact C.2) to pick one such out.
3.2 Public-private learning implies list learning
Next, show that the existence of public-private learner for class of distributions implies the existence of a list learner for the class. A list learner for a class Q takes input samples from any p E and outputs finite list of distributions, one of which is close to p.
Definition 3.2 (List learner). Let Q S A ((X). For a, 3 E (0, and & E N, an (a, B, E)-list learner
for Q is algorithm L: 8m - {L A(X) |L| I f). such that for any p E Q, if we draw
dataset X = (X1,... Xm) ii.dd from p. then
{dist(p, ((X)) S a} 2 B.
X-upmm
Definition 3.3 (List learnable class). A class of distributions Q ((X) is list learnable to list size f(a, 3) with m(a, 3) samples if for every a, B E (0, 1], letting E = f(a,, B) and m = mma, 3), there is an (a, 3, -eeame-l for Q that takes samples.
If Q satisfies the above, irrespective of the list size complexity E(a,, B), we say Q is list learnable with m(a, (8) samples.
Now, we state reduction of list learning to public-private learning. The key step of our proof is showing that, upon receiving samples ă. outputting a finite cover of the list of distributions that a public-privas learner would succeed on given public data ă is a successful strategy for list learning. Proposition 3.4 (Public-private learning - list learning). Let 2 C A(X). Suppose is public- privately learnable with mp(a, 8,e) public and n((x, B, private samples. Then for all > 0, Q is list-learnable to list size E(a, 3) 10 exp(e n((. 10:e) e)) with m(a, 3) mm 2 8) samples.
9
Proof. Let & > be arbitrary. Fix any a, 3 E (0, 1]. By assumption, Q admits a (Ø) 16 e)- 8
B public-private learner A, which uses = mp(2 2 To: public and n == n Io e) private 10 samples. We use A to construct (a, 8, 7 exp((n))) learner that uses m samples. Consider any == (#1,... "o.,...,mml E x and the class
O2 Q
P
(TV(Q,))
9 10
X-q" Q)

---

Note that by definition, 22 has a (2 1 -leamner under E-DP that takes n samples. Hence, by Fact C.I it follows that any a-packing of Q2 must have size _ 10 exp(en) =: Let Qa be such maximal a-packing, hence it is also a-cover of Q* with [Qal L. We define our list learner's s output, ((#) Qe. It remains to show that for any p E 2, with probability 2 1 3 over the sampling of X ~ dist ((X)) S a. Suppose otherwise, that is, there exists Po E Q, such that
10
g
distt(po, ((X)) a > B. Xnpp
P
{
Since ((X) is a a-cover of 2x- we have that with probability B over the sampling of X P0. Po E ②x This contradicts the success guarantee of A:
P Eapo .x-p Q~A(XXx)
(V()Q.))) a 2 TV)..
P
mo)
po Φ 2x} (po @ 2x}
1 3
10
10
The second inequality follows by the definition of Qx: conditioned on the event po & Qx the
probability, over the private samples X Ph and the randomness of the algorithm A, that the output Q of our algorithm satisfies TV(Q, Po) S is 9
TO
3.3 List learning implies compression
We state the final component of Theorem 1.1/D.1: the existence of list Iearner for class of distributions Q implics the existence of a sample compression scheme for Q. This follows from the definitions: given samples E. the encoder of the sample compression scheme runs list learner L on T. passes along x, and, with knowledge of the target distribution g, the index i of the distribution in (()) that is close to q. The decoder receives this information and outputs L()), The proof can be found in Appendix D.2.
Proposition 3.5 (List learning = compression). Let Q S A(X). Suppose Q is list learn- able to list size f(o, () with (z B) samples. Then Q admits (r(a, (my(a, (a, B), logz (f(a, ()), my (a, B)) realizable sample compression.
B)) =
4 Applications
Here, we state a few applications of the connections obtained via Theorem 1.1/D.1. First, we recover and extend results on the public-private learnability of high-dimensiooal Gaussians and mixtures of Gaussians, using known results on sample compression schemes. Second, we describe the closure properties of public- privaae learnability:: if class Q is public-prive prieaii-rrvatlly learnable, the class of mixtures of Q and the class of products of Q are also public-privated learnable.
4.1 Public-private learnability of Gaussians and mixtures of Gaussians
There are known realizable sample compression schemes for the class of Gaussians in R4, as well as for the class of all k-mixtures of Gaussians in Rdd [ABDH+20]. Hence, these classes are public-privately learnable.
Fact 4.1 (Robust compression scheme for Gaussians [A Lemma 5.3]). The class of Gaussians over Idd admits (O(d), (d log ()), (d 3 2-robust sample compression.
Fact 4.2 (Realizable compression scheme for mixtures of Gaussians [ABDH Lemma 4.8 applied to Lemma 5.3]). The class of k-mixtures of Gaussians over Rd admits (O(kd), Okdd log( ( log( ()) ( kd (ug(/))) (ogg log(1/8)) realizable sample compression.
a
Gaussians. From Theorem L.1/D.1 and Fact 4.1, we get a public-private learner for Gaussians over Rd using Oog })) public and Ō 2f + d +lgg(181) private samples (Corollary E.1). os
This recovers the result of [BKS22] on Gaussians up to a factor of O(log( f)) in public sample complexity, and improves the private sample complexity by polylog(1/B) factor.
7

---

Mixtures of Gaussians. From Theorem 1.1/D.1 1 and Fact 4.2, we get a gublic-privane learner for the class of k-mixtures of Gaussians in IR using Ō kd (odlog public and Ö kd +log(1/8)
kd" +log(1/8) as
private samples (Theorem 1 1.2/Corollary B.2).
In terms of k, d, and the public sample complexity of this learner is less than the O kd a² necessary and sufficient sample complexity for the problem non-privately [ABDH+20], This also implies that in the regime where a, having more public samples (but still o( kd oz) )) cannot improve private sample
complexity. Under pure DP, no finite sample size suffices; under approximate DP, Ō k2a 1og(1/8) has been shown to suffice [AAL23b].
a²
Algorithms for parameter estimation, like the mixture of Gaussians estimators from [BKS22] cannot be directly compared as they target a strictly stronger success criteria under stronger assumptions on the underlying distribution. [BKS22] gives an estimator for separated Gaussian mixtures that uses Ö(" df (k) public and Ó Ow + m=a=) private samples satisfying 5² -zCDP, where w, the minimum component mixing weight. In terms of the privacy guarantee and private sample complexity, our result is a strict improvement for density estimation, since k = ( ). In the setting where w. (2)) [BKS22]'s algorithm uses 1 -fccoo fewer public samples. Furthermore, their algorithm runs in time polynomial in the sample complexity.
w*e
4.2 Public-private learnability of mixture and product distributions
If a class is realizably compressible, the class of its k-mixtures and the class of its k-products are also realizably compressible. Being realizably compressible with (m,(a, .)) samples is equivalent to being public-privately learnable with (m,(a, 3)) public samples. Hence, we have black-box reductions of public their base classes.
public-private private learnability of mixture/product classes to public-private learnability of
Theorem 4.3 (Public- (Public-privaate learning for mixture and product distributions (Informal; see Theorems E.5 and E.7)). Let k 2 1. / C ((X) is public-privately learnable with m(a, 8,5) public samples, then for any En >> 0:
1. The class of k-mixtures of Q is public-privately learnable with O klo((//00) m(a, 5, public samples.
2. The class of k-products of Q (over X*) is public-privately learnable with (log(($)
mla/ k, Eo)) public samples.
The full statements and proof can be found in Appendix E.2. Here, we use the non-constructive reduction of list learning to public-private learning, and hence this does not yield a finite time algorithm. Note also that the target privacy e does not appear in the public sample complexity (it only affects the amount of private samples required).
Agnostic and distribution-shiited public-private learning
The setting we have examined thus far makes the following assumptions the data generation process: (1) same distribution public and private data are sampled from the same underlying distribution; and (2) realizability public and private data are sampled from members of the class Q.
[BKS22] shows that for Gaussians over R4, the first condition can be relaxed: they give an algorithm for the case where the public and the private data are generated from different Gaussians with bounded TV distance. However, they do not remove the second assumption.
We show that for general classes of distributions that robust compression schemes yield mublic-private learners, which: (1) can handle public- priivc-ppivtteeee distribution shifts (i.e., the setting where the public data and the private data distributions can be different); and (2) are agnostic, i.e., they do not require samples to come from a member of Q and instead, promise error close to the best approximation of the private data distribution by a member of Q. Since Gaussians admit a robust compression scheme (Fact 4. l), we obtain public-private Gaussian learners that work under relaxed forms of these assumptions on the data generating process (Theorem 1.3/F.1).
8

---

We first formally define the notion of agnostic and distribution-shiffed public-private learning, and then prove the main result of this section.
Definition 5.1 (Agnostic and distribution-shiif a,8 E (0, 11, e > 0, y E (0, 1], and с 2 1 7-shifted c-agnostic B,&) (a,,B,)) pubbic---pie learner for
public-private learner). Let Q S A For
Q is public-private E- e-DP algorithm A n Xn + (()(X)) such that for any p.p A ( with (f p) - y, if draw datasets X (X,,.... Xm) i..dd from and X (X1, 1....... X iid. from p. and then Q
A(X, X),
(TV(Q,)) S c. cidtis @) + a 2 11-B. B. Qx)(Xx,)
P X~pp
Theorem 5.2 (Robust compression = agnostic and distribution public-price pealic-private learning).
Let Q S (X) and r > 0. If Q admits (r(a, ((( 8), mc .3) r-robust compression, then for every a, 3 (0, 1] and > there exists --shifted --agoostic (a, (a. lel--pull-piiveeee learner for
Q that uses m(a, 3, E) mc 12. ) public samples and n(a, B, E) = (( + de)) (t( 2
7( 12 2 log(me( 12 ()) log( ()) private samples.
The proof again mirrors the proof of Theorem 4.5 in [ABDH+20) The key observation (and difference from the proof in Appendix D.1) is the following: for the unknown distribution p E (A)).
Proof.
consider (ps 2). If dist(p, Q) 2 2' the output Q of any algorithm satisfies TV Q) S
1 I 2 dist(p, Q). Hence, we can assume dist(p, Q) < 2. and let qu E Q with TV(p. <
min dist(p, 2) + 12 } guaranteed by such.
By triangle inequality, (V q.) <. This implies that when we generate hypotheses 2 to choose from using the r-robust sample compression with samples from p. with high probability there will be some 9 Q with TV(g, q.) $ 12- We have
TV(p. S TV) + TV(q.. S dist(p, Q) +
a a
a
12 12
6"
Applying the 3-agnostic s-DP learner for finite classes from [AAAK2I] (Fact C.2) with the above setting of n gives us the result.
6 Lower bounds
We give a lower bound on the number of public samples required public-privately learn Gaussians in Rd4 We know that Gaussians in I2 are from [BKS22]. We show that this within 1 of the optimal: the class of Gaussians in Id is nor public-po privit-py learnable with d - 1 public samples. The following is the formal statement of Theorem 1.4.
learnable with d + public samples
Theorem 6.1. The class o all Gaussians in Rd is not public-private learnable with m 3,&) d-12 1 public samples, regardless of the number of private samples. That is. there exists add Ba > 0 such that for any N, Q does not admit (aa, Ba. "y--uublc-ppiini learner using d - public and n private samples.
Our result leverages the connection between public-private learning and list learning. The existence of such a public-private learner described above would imply the existence of list learner for d-dimensional Gaussians taking 1 samples as input. We show, using argument (c.g. Theorem 5.1 from [SSBD14]) that such a list learner cannot exist. The proof of Theorem 6.1, given in Appendix G, goes through the following steps.
1. We reduce list learning to public-private learning, via Proposition 3.4;
2. We establish technical lemma that relates the PAC guarantee of list learner with its average performance over a set of problem instances, via a "no-free-lunch" -style argument (Lemma G.1);
3. For every d 2 2, we find a sequence of hard subclasses of Gaussians over R2, which satisfy the conditions of Lemma G. This forms the set of hard problem instances that imply lower bound on the error of any list learner for the class (does not receive enough samples);

---

4. Since list learning to arbitrary error with few samples is impossible, public-private learning to arbitrary error with few public samples must also be impossible.
7 Learning when the Yatracos class has finite VC dimension
In this section, describe public-privatt learner for classes of distributions whose Yatracos class has finite VC dimension. We start by defining the Yatracos class of a family of distributions.
Definition 7.1 (Yatracos class). For Q ((X), the Yatracos class Q is given by
H {{x X p(x) > ((x)) p 9 Q).
Theorem 7.2. Let Q (X). Let H be the Yatracos class of Q. denote by VC(H) and (H) the VC and dual VC dimension of H. Q is public-privately learnable with m public and n private samples, where
VC(H) log (2) + log (3)
and n n VC + log( (3)
m =
a
Ea
Theorem 7.2/1.5 says that classes of distributions whose Yatracos class have finite VC dimension can be mublic-privated Iearned. Note that the number of public samples used is indeed fewer than the O VC(H) sample requirement in the non-private analogue of the result (Fact H.1).
The proof is given in Appendix H. The result is consequence of known public- prrivat-prvateeeee uniform convergence result [BCM+20 20, Theorem 10]. To adapt it to our setting, we (1) modify their result for pure DP (rather than approximate DP); and (2) conclude that uniform convergence over the Yatracos sets of Q suffices to implement the learner from Fact H.1.
8 Conclusion
In this work, we connect public-private distribution learning to the notions of sample compression and list learning. In doing so, for broad classes of distributions, we introduce approaches to: (1) design sample-efficient public-private learners; (2) prove lower bounds on how much public data is required for public-privan learnability. In the following, we list several questions for future study.
Question 8.1. For class Q. our work examines the minimal amount of public data needed to render Q pure privately learnable. How much do we need to render Q approximate DP learnable?
Question 8.2. The VC bound of Theorem 1.5/7.2, although more general, is "qualitatively" loose. For Gaussians, it yields ( d' public sample complexity, though we know (dd) is possible, notably with no dependence a. On the other hand, (11/a:) public samples are required for public-pun cublic-privately learning mixtures of Gaussians. What qualities of a distribution admit public-private learning with o- a-independent public sample complexity? Stronger: can we find more illuminating characterizations of the sample complexity of list learning?
Question 8.3. Our work studies sample complexity improvements from using public data. Can public data lead to algorithmic improvements, that is, runtime efficiency or simpler algorithms?
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful feedhack.
AB, GK, and VS acknowledge funding from an NSERC discovery grant. AB supported by a David R. Cheriton Graduate Scholarship. CC is supported by an ARC DECRA and an unrestricted gift from Google. GK is supported by a Canada CIFAR Al Chair, an unrestricted gift from Google, University of Waterloo startup grant, and unrestricted gift from Apple.
2This is for when the distributions in Q are discrete. For classes of continuous distributions, we substitute and g for their respective density functions.
10

---

References
[AAAK21] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high-dimensional Gaussians. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT"21), 2021.
[AA Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-Dar David, Tosca Lechner, and Ruth Urner. On learnability wih computable learners. In Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT"20), 2020.
[AAL2I] Ishaq Aden-Ali, Hassan Ashtiani, and Christopher Liaw. Privately learning mixtures of axis-aligned Gaussians. In Advances in Neural Information Processing Systems 34 (NeurIPS 21), 2021.
[AAL23a] Mohammad Afzali, Hassan Ashtiani, and Christopher Liaw. Mixtures of gaussians are privately learnable with a polynomial number of samples. CoRR, http//309.03844 2023.
[AAL23b] Jamil Arbas, Hassan Ashtiani, and Christopher Liaw. Polynomial time and private learn- ing of unbounded Gaussian mixture models. In Proceedings of the 40th International Conference on Machine Learning (ICML 23), 2023.
[ABDH 20] Hassan Ashtiani, Shai Ben-Davied Nicholas J. A. Harvey, Christopher Liaw, Abbas Mchrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of Gaussian mixtures via compression schemes. J. ACM, 67(6), 2020.
[ABMI9] Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data. In Advances in Neural Information Processing Systems 32 (NeurIPS' 2019.
[Abo18] John M. Abowd. The U.S. Census Bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018.
[ACG+ 16] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS'16: ACM SIGSAC Conference on Computer and Communications Security, 2016.
[ADK20] Brendan Avent, Yatharth Dubey, and Aleksandra Korolova. The power of the hybrid model for mean estimation. Proc. Priv. Enhancing Technol., 2020(4):48-68, 2020.
[AGM*22] Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Vinith M. Suriyakumar, Om Thakkar, and Abhradeep Thakurta. Public data-assisted mirror descent for private model training. In Proceedings of the 39th International Conference on Machine Learning (ICMI. 22), 2022.
[AKZ*17] Brendan Avent, Aleksandra Korolova, David Zeber, Torgeir Hovden, and Benjamin Livshits. BLENDER: Enabling local search with a hybrid differential privacy model. In 26th USENIX Security Symposium (USENIX Security' 17), 2017.
[AL22] Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning Gaussians and beyond. In Proceedings of the 35th Annual Conference on Learning Theory (COLT'22), 2022.
[AM18] Hassan Ashtiani and Abbas Mchrabian. Some techniques in density estimation. arXiv preprint 1 2018.
[App17] Differential Privacy Team, Apple. Learning with privacy at scale, 2017.
[Ass83] Patrick Assouad. Densité et dimension. Annales de I'Institut Fourier, 33(3):233-282. 1983.
[ASZ21] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, ALT '21, pages 48-78. JMLR, Inc., 2021.
11

---

[BBV08] Maria-Floring Balcan, Avrim Blum, and Santosh Vempala. A discriminative framework for clustering via similarity functions. In Proceedings of the Fortieth Annual ACM Symposium Theory of Computing, STOC '08, page 671-680, New York, NY, USA, 2008. Association for Computing Machinery.
[BCM Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan R. Ullman, and Steven Wu. Private query release assisted by public data. In Proceedings of the 37th International Conference Machine Learning (ICML. 20), 2020.
[BKS22] Alex Bie, Gautam Kamath, and Vikrant Singhal. Private estimation with public data. In Advances in Neural Information Processing Systems 35 (NeurIPS'22). 2022.
[BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothe- sis selection. In Advances in Neural Information Processing Systems 32, NeurIPS '19 pages 156-167. Curran Associates, Inc., 2019.
[BLR13] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninter- active database privacy. Journal of the ACM, 60(2):1-25, 2013.
[BMN20] Raef Bassily, Shay Moran, and Anupama Nandi. Learning from mixtures of private and public populations. In Advances in Neural Information Processing Systems 33, NeurlPS 20, pages 2947-2957. Curran Associates, Inc., 2020.
[BNS16] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. Theory of Computing. 12(1):1-61, 2016.
[BTGT18] Raef Bassily, Om Thakkar, and Abhradeep Guha Thakurta. Model-agnostic private learning. In Advances Neural Information Processing Systems 31, NeurIPS '18 pages 7102-7112. Curran Associates, Inc., 2018.
[CCd+23] Hongjie Chen, Vincent Cohen-Addad, Tommaso d' d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, and Stefan Tiegel. Private estimation algorithms for stochastic block models and mixture models. arXiv preprint arXiv:2301. 04822, 2023.
[CDE+23] Rachel Cummings, Damien Desfontaines, David Evans, Roxana Geambasu, Matthew Jagielski, Yangsibo Huang, Peter Kairouz, Gautam Kamath, Sewoong Oh, Olga Ohri- menko, Nicolas Papernot, Ryan Rogers, Milan Shen, Shuang Song, Weijie Su, Andreas Terzis, Abhradeep Thakurta, Sergei Vassilvitskii, Yu-Xiang Wang, Li Xiong, Sergey Yekhanin, Da Yu, Huanyu Zhang, and Wanrong Zhang. Challenges towards the next frontier in privacy. arXiv preprint arXiv:2304.069) 2023.
[CKM+21] Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. Differentially-pre -rrivate clustering of easy instances. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, vol- ume 139 Proceedings of Machine Learning Research, pages 2049-2055 PMLR, 18 24 Jul 2021.
[CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM Symposium the Theory of Computing, STOC 17., pages 47-60, New York, NY, USA, 2017. ACM.
[DKS18] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical Gaussians. In Proceedings of the 50th Annual ACM Symposium the Theory of Computing. STOC '18, pages 1047-1060, New York, NY, USA, 2018. ACM.
[DL01] Lue Devroye and Gábor Lugosi. Combinatorial Methods in Density Estimation. Springer Series in Statistics. Springer New York, 2001.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography (TCC'06), 2006.
12

---

[DMR18] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional Gaussians. arXiv preprint arXiv:1810.0863 080.38 2018.
[DR44] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211 1-0077, 2014.
[GHN+ Arun Ganesh, Mahdi Haghifam, Milad Nasr, Sewoong Oh, Thomas Steinke, Om Thakkar, Abhradeep Guha Thakurta, and Lun Wang. Why is public pretrain- ing necessary for private model training? In Proceedings of the 40th International Conference Machine Learning (ICML 23), 2023.
[GKW23] Xin Gu, Gautam Kamath, and Zhiwei Steven Wu. Choosing public datasets for private machine learning via gradient subspace distance. arXiv preprint arXiv:2303.01256. 2023.
[Goo19a] Google. Google's differential privacy libraries. differential--privaeee 2019. Accessed 07/31/2023.
[Goo19b] Google. TensorFlow privacy. Accessed 07/31/2023.
http://ww..cccoeeeeeeeoeoo///aaa 2019.
[HASP22] Frederik Harder, Milad Jalali Asadabadi, Danica Sutherland, and Mijung Park. Differentially private data generation needs better features. CoRR, (bss/2005.12000 2022.
[HBAL19] Naoise Holohan, Stefano Braghin, P6l Mac Aonghusa, and Killian Levacher. Diff- privlib: The IBM differential privacy library. CoRR, abs/1907.02244, 2019.
[JB13] Zhanglong and Charles Elkan. Differential privacy based on importance weighting. Machine Learning, 93(1):163-188) 2013.
[KADV23] Mikhail Khodak, Kareem Amin, Travis Dick, and Sergei Vassilvitskii. Learning- augmented private algorithms for multiple quantile release. In Proceedings of the 40th International Conference Machine Learning (ICMI. '23, 2023.
[KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high-dimensional distributions. In Proceedings of the 32nd Annual Conference Learning Theory (COLT'19), 2019.
[KMS Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan R. Ullman. private and computationalll-cffiiii estimator for unbounded Gaussians. In Proceedings of the 35th Annual Conference on Learning Theory (COLT'22), 2022.
[KMV22] Pravesh K. Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. In Proceedings of the 35th Annual Conference on Learning Theory (COLTT22), 2022.
[KRRT21] Peter Kairouz, Mónica Ribero, Keith Rush, and Abhradeep Thakurta. (nearly) dimen- sion independent private ERM with adagrad rates via publicly estimated subspaces. In Proceedings of the 34th Annual Conference on Learning Theory, COLT '21, pages 2717-2746, 2021.
[KS17] Pravesh K. Kothari and Jacob Steinhardt. Better agnostic clustering via relaxed tensor norms, 2017.
[KS22] Refael Kohen and Or Sheffet. Transfer learning in differential privacy's 's model. In Proceedings of the 39th International Conference on Machine Learning (ICML '22), 2022.
[KSSU19] Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan Ullman. Differentially private algorithms for learning mixtures of separated Gaussians. In Advances in Neural Information Processing Systems 32, NeurIPS '19, pages 168-180. Curran Associates, Inc., 2019.
13

---

[KV18] Vishesh Karwa and Salil P. Vadhan. Finite sample differentially private confidence intervals. In 9th Innovations Theoretical Computer Science Conference (ITCS' 18), 2018. 8.
[Li10] Shengqiao Li. Concise formulas for the area and volume of hyperspherical cap. Asian Journal of Mathematics & Statistics, 4(1):66- 70, 2010.
[LKO22] Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statisties in high dimensions. In Proceedings of the 35th Annual Conference on Learning Theory, COLT '22, pages 1167-1246, 2022.
[LLHR23] Andrew Lowy, Zeman Li, Tianjian Huang, and Meisam Razaviyayn. Optimal differen- tially private learning with public data. CoRR, abs/2306. 15056, 2023.
[LTLH22] Xuechen Li, Florian Tramèr, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In Proceedings of the 10th Interna- tional Conference on Learning Representations, ICLR '22, 2022.
[LVS+21] Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Steven Wu. Leveraging public data for practical private query release. In Proceedings of the 38th International Conference on Machine Learning, ICML '21, pages 5968-6977. JMLR, Inc., 2021.
[LW86] Nick Littlestone and Manfred Warmuth. Relating data compression and learnability, 1986.
[LWAFF21] Zelun Luo, Daniel Wu, Ehsan Adeli, and Li Fei-Fei. Scalable differential privacy with sparse network finetuning. In Proceedings of the 2021 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR '21, pages 5059-5068, Washington, DC, USA, 2021. IEEE Computer Society.
[MY16] Shay Moran and Amir Yehudayoff. Sample compression schemes for VC classes. Journal of the ACM, 630 2016.
[NB20] Anupama Nandi and Raef Bassily. Privately answering classification queries in the ag- nostic PAC model. Proceedings of the 31st International Conference on Algorithmic Learning Theory, ALT 200, pages 687-703. JMLR, Inc., 2020.
[NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on the Theory of Computing, STOC '07, pages 75-84, New York, NY, USA, 2007.
ACM.
[Ope20] OpenDP Team. The OpenDP white paper, 2020.
[PAE 17] Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi-supervised knowledge transfer for deep learning from private training data. In Proceedings of the 5th International Conference Learning Representations, ICLR '17, 2017.
[PCS+19] 19] Nicolas Paperot, Steve Chien, Shuang Song, Abhradeep Thakurta, and Ulfar Erlings- son. Making the shoe fit: Architectures, initializations, and tuning for learning with 2019.
privacy. https: oppnrevieeeeeeeeeeeeeeeeeeeeeeee mett/forummiddrrr@655
[PSM 18] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. In Proceedings of the 6th International Conference Learning Representutions, ICLR '18, 2018.
[RY20] Prasad Raghavendra and Morris Yau. List decodable learning via sum of squares. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 161-180. SIAM, 2020.
14

---

[SSBD14] Shai Shalev-Shwards and Shai Ben-David, Understanding Machine Learning: From Theory Algorithms. Cambridge University Press, 2014.
[TB21] Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In Proceedings of the 9th International Conference Learning Representations, ICLR '21, 2021.
[TCK*22] Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Friend- lyCore: Practical differentially private aggregation. In Proceedings the 39th Interna- tional Conference on Machine Learning (ICML 22), 2022.
[TKC22] Florian Tramèr, Gautam Kamath, and Nicholas Carlini. Considerations for differentially private learning with large-scale public pretraining, arXiv preprint arXiv:2212.06470, 2022.
[VW02] Santosh Vempala and Grant Wang. A spectral algorithm for learning mixtures of distributions. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS '02, pages 113-123, Washington, DC, USA, 2002. IEEE Computer Society.
[ZA+23] Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher A. Choquette-Choo, Peter Kairouz, H. Brendan McMahan, Jesse Rosenstock, and Yuanbo Zhang. Federated learning of Gboard language models with differential privacy. In Proceedings of the 6lst Annual Meeting of the Association for Computational Linguisties (ACL'23), 2023.
[Yt885] Yannis G. Yatracos. Rates of convergence of minimum distance estimators and Kol- mogorov's 's entropy. The Annals of Statistics, 13(2):768-774, 1985.
[YNB 22] Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang. Differentially private fine-tuning of language models. In Proceedings of the 10th International Conference on Learning Representations, ICLR 22, 2022.
[YZCL21] Da Yu, Huishuai Zhang, Wei Chen, and Tie- Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In Proceedings of the 9th International Conference Learning Representations, ICLR '21, 2021.
[ZWB21] Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private SGD with gradient subspace identification. In Proceedings of the 9th International Conference on Learning Representations, ICLR '21, 2021.
15

---

A Extended related work
Privately learning Gaussians. Our work studies the task of learning arbitrary, unbounded Gaussians while offering differential privacy guarantees. Basic private algorithms for the task (variants of "clip-and-noise") impose boundedness assumptions on the underlying parameters of the unknown Gaussian, since their sample complexities grow to infinity as the bounds widen to include more allowed distributions. Understanding these dependencies without pub- lic data has been a topic of significant study. [KV18] examined univariate Gaussians, showing that logarithmic dependencies pure DP, but can be removed under approximate DP. The same is true in the multivariate set- ting [AAAK21, KMS 22, TCK 22, AL22, KMV22, LKO22]. [BKS22] shows that instead of relaxing to approximate DP to handle arbitrary Gaussians, one can employ a small amount of public data; our lower bound tells us almost exactly how much is needed. Furthermore,
parameter bounds are necessary and sufficient in the case of
reductions
between public-private learning and list learning offers the conclusion that the role of public data is precisely for bounding: distribution classes that be privately learned with small amount of public data are exactly the distributions that can be bounded with a small amount of public data.
Privately learning mixtures of Gaussians. Another line of related work is that on privately learning mixtures of Gaussian, but without any public data. [NRS07] provided a subsample-and- aggregate approach learn the parameters of mixtures of spherical Gaussians based on the work by [VW02] under the weaker, approximate DP. Recently, [CCd*t 23] improved on this by weakening the separation condition required for the mixture components. [KSSU19] provided the first polynomial- time, approximate DP algorithms to learn the parameters of mixtures of non-spherical Gaussians under weak boundedness assumptions. [CKM*21] improved on their work both in terms of the sample complexity and the separation assumption. [AAL23b] provided a polynomial-tinn time reduction for privately and efficiently learning mixtures of unbounded Gaussians from the approximate DP setting to its non-private counterpart (albeit at a polynomial overhead in the sample complexity).
Our work falls into the category of private density estimation, for which [AAL21] gave new algo- rithms for the special case of spherical Gaussians under approximate DP, while [BKSW19] gave (computationally inefficient) algorithms for bounded Gaussians under pure DP. For comparison, the latter would have infinite sample complexity for unbounded Gaussians, but our work provides finite private sample complexity even under pure DP using public data. On the other hand, [ASZ21] showed hardness results for privately learning mixtures of Gaussians with known covariances. The concurrent work of Azfali, Ashtiani, and Liaw [AAL23a] gives the first learnability result for general high-dimensional mixtures of Gaussians under approximate differential privacy.
Theory for private algorithms with public data. Beyond distribution learning, there is lot more work that investigates how public data can be employed in private data analysis. Some specific areas include private query release, synthetic data generation, and classification [JE13, BNS16, ABM19, NB20, BCM+20, 20, BMN20, LVS*21, 21, KADV23], and the results are a mix of theoretical versus empirical. The definition of public-price private algorithms that we adopt from [BNS16], which studied classification in the PAC model. The VC dimension bound we give for public-private distribution learning relies on results from public-private classification [ABM19] and uniform convergence [BCM+20] 20J.
concurrent and independent work [LLHR23] also studies learning with public and private data, focusing on the problems of mean estimation, empirical risk minimization, and stochastic convex optimization. The focus of the two works is somewhat different, both in terms of the type of problems considered (we study density estimation) and the type of results targeted. That is, our objective is to draw connections between different learning concepts and exploring the resulting implications for public-private private distribution learning, while their goal seems to be understanding the precise error rates for some fundamental settings.
Private machine learning with public data. Within the context of private machine learning, there has been significant interest in how to best employ public data. The most popular method pre- training [ACG+ 16, PCS+19, TB21, LWAFF21, YZC1211, LTLH22, YNB-22, GHN+23, HASP22] (though some caution about this practice [TKC22]), while other methods involve computing statistics about the private gradients [ZWB21, YZCL21, KRRT21, +GM+22, GKW23], or training student
16

---

model [PAE 17, PSM 18, BTGTI8). For more discussion of public data for private learning, see Section 3.1 of [CDE* 23].
List learning We also use the notion of list learning in this work, which is a "non-robust" version of the well-known list-decodable learning [AAL21, RY20, BBV08, CSV17, DKS18, KS17], where the goal is still to output list of distributions that contains one that is accurate with respect to the true distribution, but the sampling may happen from a corrupted version of the underlying distribution.
Hybrid differential privacy. Finally, related setting is the hybrid model, in which samples require either local or central differential privacy [AKZ* 17]. Some learning tasks studied in this model include mean estimation [ADK20] and transfer learning [KS22).
B Technical overview
New connections for public-private learning. Our first contribution is establishing connections between sample compression, public-private learning, and list learning, via reductions. We show that: (1) sample compression schemes yield public-private learners; (2) public-private learners yield list learners; and (3) list learners yield sample compression schemes.
(I) and (3) are straightforward to prove: (I) compression implies public-priven learning follows from a modification of analogous result of [ABDH*20] where we observe that in their proof, the learner's two-stage process of drawing a small compression sample used to generate a finite set of hypotheses using the compression scheme, followed by hypothesis selection with a larger sample, can be cleanly divided into using public and private samples respectively. In the latter stage, we employ known pure DP hypothesis selection algorithm [BKSW19, AAAK2I]. (3) List learning implies compression follows immediately from the definitions.
For (2) public-private learning implies list learning, we show non-constructively that there exists list learner for a class, given a public-private learner for that class, but do not provide an algorithmic translation of the public-private learner outputting a finite cover of the list of distributions on which the public-private learner succeeds on, when using S as the public samples, is correct output for list learner. Hence the list learner we construct, on input S, outputs this finite cover as determined by (but not explicitly constructed from) the public-private learner.
list learner. For a set of samples S, we show that
Agnostic and distribution-shifted public-private learning. We identify some distributional as- sumptions that can be relaxed in the public-private learning setup. We obtain agnostic and distribution- shifted public-private learners via a connection to robust compression schemes. The reduction ideas are similar those in the case of public-private learning and non-robust sample compression described above.
Lower bound on public-private learning of Gaussians. Our lower bound for public-privately learning nigh-dimensional Gaussians exploits our above connection between public-private learning and list learning. and applies a "no-free-lunch amnch"-stlle argument. The latter uses the fact that an algorithm's 's worst-case performance cannot be better than its performance when averaged across all the problem instances. other words, we have two main steps our proof: (1) we first claim that due to our above reduction, a lower bound for list learning high-dimensional Gaussians would imply a lower bound on the public sample complexity for public-privately learning high high-dimensional Gaussians; and (2) assuming certain accuracy guarantees and sample complexity for our list learner for high -igh-iiiensional Gaussians; we show that across a set of adversarially chosen problem instances, our average accuracy guarantee fails, which is a contradiction to assumed worst-case guarantees.
We observe that the lower bound from Theorem 6. establishes that at least d public samples are necessary for cublic-private learning to vanishingly small error as d increases (impossibility of learning to a target error, via the application of Lemma G.I, is related to the bound on v) from Equation (6), which decreases exponentially with d). A natural question is whether the result can be strengthened to say that there a single target error, simultaneously for all d, for which learning impossible without d public samples.
17

---

VC dimension upper bound for public-private learning. Our proof involves invoking the existing results for public-privatte binary classification [ABM19] and uniform convergence [BCM*20) 20]. We use them to implement Yatracos' minimum distance estimator [Yat85, DLO0] in public-private way.
C Extended preliminaries
C.1 Notation
Covers and packings. For a > and Q S ((x), we say that C C A(X) is an a-cover of Q if for any Q, there exists a E C with (V(p.g) g) S a. For a > 0 and Q C A(Y), we say that P Q an a-packing of Q if for any p + E P, TV(p, > a.
Class of k-mixtures. Let Q $ ( be a class of distributions. For any 2 1, the class of k-mixtures of Q is given by
w q E Q, w, 2 0 for all i E [k] and
1
Class of k- k-products. Q ( be class of distributions over X. For any h 2 1, (01.....0h g&) is product distribution over X if q Q for all [A] and for X q. the i-th component X; of is independently (of all the other coordinates) sampled from q,. The class of k-products of Q over X is given by
Øsk = f(g....., 9k) : 9 E EQ for all i E [k]]
C.2 Privacy
The following is known hardness result on density estimation of distributions under pure differential privacy, and is based on the standard "packing lower bounds".
Fact C.1 (Packing lower bound [BKSW19, Lemma 5.1]). Let C A(X), a E (0, 1l, and E > Let ② be any o-paccing of Q. Any e-DP algorithm A: X + (()( that, upon receiving n i.i.d.
samples XI, from any p 2, outputs Q with TV p) S T with probability 2 requires
log( ② log( 10 g
The next result guarantees the existence of agnostic learners for finite hypothesis classes under pure differential privacy.
Fact C.2 (Pure DP 3-agnostic learner for finite Q [BKSW19], [AAAK21, Theorem 2.24]). Let ((X) with |Q] < oc. For every a, E (0, 1] and > O, there exists an e-DP algorithm X. + (A(X)), such that for any ( if we draw dataset X = (XI.....,,, i.id
from p and then Q A(X),
P
(TV(Q.P) p) s dist Q) + +a} 21
X~p" Q~A(X)
where
log([2)) + log($))
log(IQ)) + log( (
O
a²
D Statements and proofs for Section 3 The connection to sample compression schemes
The following is the full formal statement of Theorem 1.1.
Theorem D.1 (Sample complexity equivalence between sample compression, public-private learning. and list learning). Let Q C A(X)). Let m (0, 1)2 + N be sample complexity function, such that m(a, (3) poly( : )) Then the following are equivalent.
'The reductions between the learners do not need this assumption, it is only used to state the sample complexity equivalence.
18

---

1. Q is realizably compressible with mc 8) = (mm(a, B]) samples.
2. Q is public-privately learnable with mp(a, = ((m(a, 8)) public samples.
3. Q is list learnable with my ma 3) ((m(a, 6)) samples.
The functions mcc mpp, and are related to one another as: (nll,,,e)) = mc @ 2): m mp( 10 E) for any > O; and mc(a, 3) mm 8). Hence, there exists a apolynomial m (0, 1] N, such that mc(a, , (3) (mm(a,)))) then me (a, B), mr(a, 9). mr(a,3) are all within constant factors of each other.
and
D.1 Compression implies public-private learning
Proof of Proposition 3.1. The proof this proposition closely mirrors that of Theorem 4.5 from [ABDH 20]. We adapt their result to the public-private setting.
Fix a, 3 E (0, 1] and E > 0. Let T = 7 -) t = t ) and m = mc : 2) We draw a public
dataset X of size m i.i.d. from p. Consider
S 5= S' C X where |S r, and be E {0, 1).
Note that the encoding (x) S, so forming 2 (g(S' (5', b) E S) means that with probability
over the sampling of X, ((f) Q has (V S
Now, we run the DP 3-agnostic learner from Fact C.2 on 2 targeting error and failure probability have private samples (given in the statement of Proposition 3.1), which is logarithmic [S]. With probability 2 3, we approximately recover p with the compression scheme and the DP learner succeeds, and the output Q satisfies
8 which is achieved as long 2.
TV(Q.)) 3
3- min TV
qe
0
a
3
6
2
D.2 List learning implies sample compression
Proof of Proposition 3.5. Fix any (0, 1]. Let (2 and and l(a, $). By assumption, Q admits an (a, 3, E)-list learner L: xmm > (L. C ( [L I {} that takes m samples. Letting and = log ()), we define the compression scheme as follows.
Encoder: for any q Q, the encoder fq xm X (0, produces the following, given an input z E xm It first runs the list learner on H. obtaining L()). Then, it finds the smallest index with TV L(ā))) dist(g. L())), where L(ū); denotes the i-th element of the the list L()). The output of the list learner is (ă, i). Note that ă e X and that can represented with log,
bits.
Decoder: the fixed decoder g : X 10, A(X) takes & and i, runs the list learner L on ã. and produces L(ā);
By the guarantee of the list learner, we indeed have for any Q, with probability 2 over the sampling of X nh TV TV(g. (S)) <
D
19

---

E Statements and proofs for Section - Applications
E.1 Public-private learnability of Gaussians and mixtures of Gaussians
Corollary E.1 (Public-private learning for Gaussians). Let d 2 1. The class of Gaussians over Fd is public-privately learnable with m(a, 8, E) public samples and n(a, B, e) private samples, where
m(a, 3,c) = d'log (1))
d log (a) + log
d log (a) + log
nla, ((0, O
ae
Corollary E.2 (Public-private learning for mixtures of Gaussians). Let k 2 1. The class of all k-mixtures of Gaussians over R is public-privately learnable with m(a, B, E) public samples and n(a, B) private samples, where
kid log
log
m(a, 8,E) =0
(1)
kdlog ($) log
d
1 3
n(a, =
kd log
+ kd log
a22
EC
a
E.2
Public-private learnability of mixture and product distributions
Mixture distributions. We first mention fact from [ABDH 20], which says that if a compression scheme exists for class of distributions Q, then there exists a compression scheme for the class of k-mixtures of Q.
Fact E.3 (Compression for mixture distributions [ABDH 20, Lemma 4.8]). a class of distributions Q admits (r(a, M(, 3), m(a, 3)) realizable sample compression, then for any 2 1, the class of k-mixtures of admits (Ta(a, B), & (a, B), mi(a, B)) realizable sample compression, where
Th, tk, my (0, 1 + are as follows:
3k
(a 3) = k 3: 9), ()) = k -
loga
3
m2 48k log
Gk
a
(3)
a
3
Next, we state a corollary of Propositions 3.4 and 3.5, which describes the existence of a compression scheme, given the existence of public-private learner.
Corollary E.4 (Public-private learning - compression). Lei Q C A(X) be class of distributions. Suppose Q is public-priee privittyyy learnable with mp(a, B, public samples and n(a, 8, E) private samples. Then for any 0, Q admits
log 10 +
3
10
(r(a, (), m(,
mp 2 10
mp
log(2)
2 10
realizable sample compression.
Proof. Fix & > O. From Proposition 3.4, if Q is public-privately learnable, then it is list learnable to mz (a, 9) samples, where
list size E(a, 3) with my
10
a B :) and mI 3) = -mp
a 3 2 10
((a 3) 9
exp
E n
20

---

Proposition 3.5 implies Q admits (T(a. (), mc(a, (aa,,,))) B)) m,,
sample compression, where
T(a, B) = m = mp
2 10
log( 10)
+
a 8
2
10
((a,8) = logz(e(a,, =
log(2)
a B
mc(a,8) m2(a, = mp 10
This completes the proof.
As a consequence of Corollary E,4, Fact E.3, and Proposition 3.1, we have the following result about the public-private learnability of mixture distributions.
Theorem E.S (Public-private learning for mixture distributions), Suppose Q S ( is public- privately learnable with m(a, 5,e) public samples and n(a, () private samples. Then for any 2 o the class of k-mixtures of public-privately learnable with my(a, 3, public samples and ny na( B, E) private samples, where
k log
m4(a, 3,E), =0
3
m
a
B
36
20
3,E, =0 ((
a
a
Eok
36
20
E0
+
k: log
k
B
B
k klog
80
80
+ log
36'
20
36
20
for any choice of eo > O.
We give example of an application of this result. Consider the class of Gaussians over Idd, for which there exists a public-private learner that uses m (d) public samples and n = (
+ d²
a²
ea
polylog (d, 1. 3 private samples [BKS22]. Then Theorem E.5 implies that there exists a public-
private learner for the class of k-mixtures of Gaussians that uses my = O (odlog(k/))) samples and
public
n4 =
((2
Ea 11)
cnk:
de d²
kd) ) polylog
1 d, ki a
Egoe
private samples for any Eg >
With the choice of So
we get private sample complexity of 0 polylog (d, a: 33 Notably, this private sample complexity, obtained by specializing the general result of Theorem E.5, suffers some loss compared to our learner for mixtures of Gaussians from Corollary E.2.
luff kuff
Product distributions. We start by mentioning a fact from [ABDH 20), which says that if a compression scheme exists for class of distributions Q, then there exists compression scheme for the class of k-products of Q.
Fact E.6 (Compression for product distributions [ABDH+ + Lemma 4.6]). If a class of distributions Q admits (T(a, B). t(a, (3, m(a, 33) r r-robust sample compression, then for any k 2 1, the class of k- products of admits (Tx(a,, B), (x(a, m4(a, B)) r-robust sample compression, where Tke tk my
(0, N are follows:
(a, 9) k. ( 3). ta B) = k () mx(a, B) = logs
33k 3
m
21

---

As consequence of Corollary E,4, Fact E.6, and Proposition 3.1, we have the following result about the public-private learnability of product distributions.
Theorem E..7 (Public-private learning for mixture distributions). Suppose C ( public- privately learnable with m( B,&) public samples and n(a, B, private samples. Then for any k 2 1, Q the class of k-products of Q over X* is public-privately learnable with my (a, 3,e) public samples and ny (a, (,E) private samples, where
m 3,5, = {
log
k 3
m
Q
B
ED
))
12k:
20'
((1
B
nx(a,,,E) =
+
Euk
+
a²
12k'
20"
k blog
log
m
3
ED
m
a
3
E0
+ log
1 3
12k
20
12k:
20"
for any choice of co > O.
As an example, for the class of Gaussians over IR, there exists a public-private learner that requires
1 m = O(1) public samples and n O + + (.) polylog a 3 private samples [BKS22]. Then
Theorem E.7 implies that there exists a public-private learner for the class of k-products of Gaussians that requires mn O (l))) public samples and nig = -(a++ + = (sok
Coo + +k))
polylog (k. a 3)) private samples, for any choice of Eo 0. Note that if were apply Fact E.6 to Fact 4.1 after setting d = in the latter, and then apply Proposition 3.1, we would obtain better terms of the private data than what would after combining Corollary E.1 (setting d = 1) and Theorem E.7 here. However, Theorem E.7 is a more versatile framework, so some loss is to be expected again.
sample complexity
F Statements and proofs for Section 5 Agnostic and distribution-shifted public-private learning
Theorem 5.2 gives an agnostic and distribution-shifte learner for Gaussians over R2, stated in the following corollary.
Corollary F.1 (Agnostic and distribution-shifted public-private learner for Gaussians). Let d 2 1. For any a. (0, and > O, there exists 1/2 -hhifted 3- 3-agnostic public-private learner for the class of Gaussians in IRd that uses m public samples and n private samples, where
m = 0 dloog (1))
d log (a) + log (1) (1)
d log (2) ( + log (1)
(3)
O
a²
as
G Statements and proofs for Section 6 Lower bounds
Lemma G.1. Let Q C ((X) and N. For subclass C Q. denote by U(C) the uniform distribution over C. Suppose there exists a sequence of distribution classes (Qx) kep with each
O C Q, and set B rm such that following holds:
1. There exists n) E [0,1) and ko E N with
(X (XE)) B)2
Q- X~Q"
for all k 2 kn
22

---

2. There exist > 0 and E (0, 1] such that, defining (ux)k=r- (rt) and (sx) as
Uk sup (x),
we 2
7k = sup
P
(TV(p,Q) S 20),
p Q~1((2))
8k == inf
P
(Q) 2 c uk),
xEB Quil(Qn)
we have that
Pk Sk
lim
0.
Then for any & E N, there does not exist any
on on (
I--ist learner Q that uses m samples.
T
Proof. We provide proof by contradiction. Suppose for some N. we have an ( -, ()-list learner for Q using samples, denoted by L: 7 {L S ( LI s E). Then for all k e N. we have that
E Q- x X-l2m
(dist(2,
S
1 1
(1)
Now, since oom In = O, there exists kn 2 kn E N, such that
Uku - 1
(2)
8kg
Clkko
11
and
P Qril((mn)) X~Q""
(3)
Fix any B, and let R = {g E Qro dist(y, L(x)) a) and S = (g Qio (x) 2 cuko (uote that both and depend on a²).
For i E [6], further let R₁ = {q E QRo TV ((x), S a) so that R= R
Now, fix i [e]. Assuming that R₁ * 0, consider any E R. For any 9 R. we have TV(p, q) & 2a. Hence, R, C (4 Qk. TV(p.) q) I 2a.. Regardless of whether R3 is empty,
P
E S sup
P pe Q~1)(2nn)
(V () 2a) rko
Q~11(
Moreover, conclude that
Q (QER) < Σ
(QE Rg) S TTpp" l.
(4)
Quel(On)))
Observe that this implies, since uko 2 (xx)
[ n" (x)S((()) S usa / fo(9)da uko Qu))(
{Q R] < uk, .Tk
(5)
n
23

---

an inequality we will use momentarily. We can now write (dist(Q,C(x)) x œ fo/x(9) x) dist(q, (d
E (x X~Q
Qho
/
fqix(9 x) dist(q, d(
S(R
[ fqix (q æ)dd
(L saix(1 22)qq Jr fa)x(a
(Js
dq S ("(())s(l)) da) fx(x)
fx(x))
(M Jn (
fx(x)
cukko / fal()dg uko L. Tkk
fx(x)
(By definition of S and (5))
cukk
P Qxo)
[Q S} -uko E TTo
fx(x))
Plugging (4) in, along with the definition of 8ko we have.
(Qist(Q,((()). x == ax] 2 fx (x)
(cuRo 8ho Uko E r.kk)
Qu1((QM)) X-Q"
1
(10 Uko L r.rk))
(ku from Equation 2)
fx(x)
9Th ((2(
2 10a
dg
(by (5))
fx(
R
= 100
IQER X x)
Quil(Qnn)
X-Q
Integrating over all x E B and using Inequality B Q~1)(Q())) X-Q"
(dist(),<(x))]
2
P
(XEB) B}
(dist(Q, B) Quu(O.))
E
x-Q"
X~Q"
Q-1((Oa))
X-Q"
n 10a
(dist(Q, S X B). Qu
P
X~Q
P (dist (Q, & a X E B} 2 10
then (dist(Q, 2 on, contradicting (1). Other-
wise,
EE [dist(Q Q2 ((X))
2 1) E [di ((X)) X B]
2 .7.a P (diist(Q, ((X)) a X E B}
2 n (a- 11))
also contradicting Equation 1.
Proof of Theorem 6.1. To prove Theorem 6.1, it suffices to find for every d 2 2, sequence of subclasses ( and a set E (Red)d-1 that indeed satisfy the conditions of Lemma G.1. In what follows, we fix an arbitrary d > 2.
24

---

The construction of the sequence of hard subclasses. the following sets:
Let = [0, 0,
1 E R We define
T
i
E R : 1d-1 with ||d||2 <
1
0
2
C A
E R LE En- with ||4|2 - and X E [1, C IR
That is, 7 a -isk (a disk with radius 3) in Rd-1 embedded onto the (d 1) -i-dimensional hyperplane IR spanning the first (d - 1) dimensions (axes), centered at the origin. C' is cylinder of unit length and radius placed unit distance away from in the positive ed-direction.
Let Sd-1 = {ar Rdd ||
1] be the unit- unit-sphere, centered at the origin, in R4, and let
N sd-
Sd-1 :lu elueeal eal S
2
That is, N is the set of vectors on the unit hypersphere with angle from ea. For E N, define "rotatiou" matrix
R
u
02
Vd E Rddd
where {og...., J is any orthonormal basis for {u} to the subspace spanned by the set of vectors {u)).²
(where {u} L. denotes the subspace orthogonal
Now, for > O. E T, and E N, define the Gaussian
o²2
G(a,t, u) N
RiT
=(124).
O
For all k 2 1, let
2x ===fo
( : : x:
1
That is, each Qx is class of "flat" (i.e., near (d - -idmennsio)) Gaussians in Rd, with 0² = 전 variance on single thin direction and unit variance all other directions. Their mean vectors come from a point on the hyperplanar disk T' (which we recall is (d - -)-dimensional disk orthogonal to ea), and the thin direction u comes from N (which is 5 excluding points that form angle < y with eg). As k oc, the Gaussians get flatter.
Lower bounding the weight of B. We start with the following claim, which shows the probability that d samples drawn the uniform mixture of o all fall into the cylinder can be uniformly lower bounded by an absolute constant, independent of kt
Claim G.2. Let B be the set of all possible vectors of d points in the cylinder C, i.e, Cd-11 E (Rddd-1, There exists such that for k > 10,
P
(X B} 2 n
Q-U((Q))
X~Q"-1
Proof of Claim G.2. Consider the inscribed cylinder C' CC
1 C' - aad te Rd-1 with ||t||2 S and
[ 5
C
3 3'3
'Technically, H., is an equivalence class of matrices since we do not specify which orthonormal basis of {u]+ However, it turns out, the choice of the orthonormal basis of {u}+ does not matter since they all result the same Gaussian densities in the proceeding definition of G(a, 2, u).
25

---

Also, consider T" T and N' Ç N:
1 5
T
E R² LE Ra- with |10|2 S
N' u E sut-1 lu. lu.eal S
36
Now, fix u E N' and E T". Define the plane going through with normal vector u as,
P(u, t) = {t + x: x E Rd with x u u= 0}. First, we show t(u,t) C contains (d 1) dimmesssia region. Consider,
=
The projection onto P(u, t) of y is given by,
t
y = (y 1) - ((y 1) u)u +
cu,
where |c| 11 t)
1. Since ||t||2 S i. the norm of the first (d - 1) dimensions 1 1 and 3/2 E E1 24:2 + 2. and y' C.. Moreover, adding any with 1 dimensions being at most 1 24 S and (y +2)a E E 12'2 12.. Hence, y/ + E C². This shows that P(u, nC contains a (d 1)ddimensional subspace, since it contains a (d -idimmensional disk radius 24
u| S
21'
of y is S 1 0nd |||||2 S results in y' + with the norm of the first
24
1 3
Next, let
M p su : P(u, -
C R
6'0
That is, M is rectangular "extrusion" of C' n P(u, 1) have M C C, since adding a vector of length cannot take a point C' outside C. We also have that M is d-dimensional region, so
along both its normal vectors. Indeed,
P
(X C} z
(X XEM) >0 O.
X--G(1/10...u)
x~G(1/10.MM)
Note that for S 10 we have
T X~G(a,,t.)
(XEM)
P
(XeM)
E
This is because any E M be written X=G(L/10,t.a)
cu, where æ is such that w 0, and |cl < z. Plugging in this decomposition of x into the densities of G(1/10, u, () and G(a,, u, L). and simplifying yields the above.
To conclude, for k 2 10, we have
P {x -²
P (u((T asl(N)
C
Q~u((e)) X-Q"
X-GG(/EAAu))+
c
{x E ctd Id
X-Gll/Raaj
2 6 JT NN X.GGI/RANee
fx ExE
ctd -d-
d-1 J JN. (X-G(1/kLa)) (XEC))
(
du
[ JN' ( (x-CC//A
d-1
(XEM)
du dt
1
(x (XEM)
du dt
1 JN' (x~G(1/10.M))
= 0,
(6)
26

---

where c ff) fv(u) > 0 is the uniform density over T x N. Note that the final integral is non-zero since T N has non-zero measure T N and that IP X=G(1/10,tta)
{X E M3 is indeed
non-zero for all T', E
Upper bounding rss the weight of a-TV balls.
We prove the following.
Claim G.3. For k 2 let
11 QV) S
Tk == sup pEcx Q-H(Qe)
406
Then we have,
T 0
+0 as k + co.
We use the following three facts regarding total variation distance, Gaussians, and the surface area of hyperspherical caps.
Fact G.4 (Dota-processing inequality for TV distance). Let p.q A(X). For any measurable TV( S TV(p.9).
f: X + v,
where for p A(X), f()) denotes the push-forward distribution assigning for all measurable C V. (A) p(f (A)).
Fact G.S (TV Distance between I-Dimensional Gaussians [DMR18, Theorem 1.3]). Let N(u of) and N (u2, o be Gaussians over IR. Then
1
min {
max
o31 |o of
40
u2l
}} < TV (N (1), ,N (12,0²)
200
01
Fact G.6 (Surface area of hyperspherical caps [Li10]). For Sd-1 and [0, 2). define
Clu, 0) = (x E Sd-1, (xx, u) < }}
where for u, Sd-1, L(u, v) = cos 1 (u. We have
Area(C(u,, 0)) = 2n (d-121)/2 1)/2
r( 10" sin sin d- (x)
Note that
4/2
Area( (rd)())1))=
r
Proof of Claim G.3. Let > O. Lett,, t2 E T and u1 U2 E N. We will compare the total variation
distance of the Gaussians defined by these parameters. Let
D2 =
0
By Fact G.4, taking f: IRd - to be ((x) uI (x I1),
TV(G(a, t1, u2),, G(a,t u2)) 2 TV(N(u (V -t1), un Ra, Do D.R u1),N(uT (to - -t1), Ry, D, DTR u1)) o2) At, cos? (os2(/(u), (2)) + sin (in?(
27

---

where = t2 - t1. For the last line above, we take Rus = [uz, U2..... val, where (uz,..., Ud} an orthonormal basis for {uz}= Then the equality in the last line for the variance of the second Gaussian uses,
U1 Ruz Dr Rug u1 = o (ui u2) + (02 u2)² + ..... + (aa u2)²
o² (ul uz)² + (1 - (u1 . u2)
o² cos? (/ U2)) + (1 cos² (oos?(/(un) (4(11
= o² cos? ( u2)) + sin sin (< u2),
where Ry being unitary implies that (uy . u2)² + (uj . 02)² + ... + (22 va)a = 1. yielding the second equality in the above.
We show that if (wi, u2) E 2 σ, 2a 0
TV(G 4, u1), G(a, u2)
200 First,
consider the case where Z(u1, u2) E | a, z. Using that on [0, Z). we have sin(x) 2 2 and cos(x) 2 we get
o² cos? (<(1,, u2)) + sin? sin?(L (L(u), U2)) 2 x2 (u,,, u2) 20²
Therefore,
of 02 of
0² 202
s o²
-1,
and by Fact G.5, we can conclude that TV(G(a, t, u1), Glo, t2, 22) 2 200
Now, consider the
case where (un,, W2) E 1 n
22m Note that in this case, there exists u/ = 12 E V
2 π
with
2
2 2
G(a, 12, u2) = G(o,, 12, u²), bringing us back to the previous case.
Next, note that since || |22 = 1 and |u = |ui eal < /
2 (by the definition of N), letting r =
(t) u1
(TT Rd-1, we have ||r||2 2 3.4 Let f 1F
We have that if [At,..... Ata-1] TT.
A > 20 G, then,
u1 Al = |A ...,, Add,11)) ATd-1)
At Ata-1]
2||||2
1// |At....., Ata-1]
40
This implies that
40(m) - 122)
40(-u) Al) I --1,
σ1
and by Fact G.5, we can conclude TV(G(a, 41 un), G(a, (i0,,2,,0 (())))) 1
Therefore, for any E N,
200
t T,
1
1
P Q=))(Q+)
T, u),
()) < w(-2((N)
P (--
400
400
1
<
P
G() v/)) <
1' (M(( v' ((()
200
the [lAt
Ata-i] f < 20%
IP wHMnN))
((<(
10,
v2T U
-2T
26
2
28

---

For the first term, note that the event
20 S 1'
+
x 0
( (0)
||a|l S f 00 20k
1
which under (T),, for some ca > 0 depending only on d, has probability S Cd 201-
For the second term, note that <(,, [0,
v 22
U (a
van
means w' C(u,
/2x
U
2
2h
C(-u, u, 22x 2k
By Fact G.6, we know that under (NN)), for some ca depending only on d.
V2n/2k
P {ur E C(u, vēT } ca
sin d (x)dx
x')(((N)
22 /2k
d dxr
S Ca
d
d-1
Cd
V V
d 1
2
kd-1
The bound is the same for C(-u,
v2x) 2k
Plugging these into the above, we can conclude that
sup pERe Q~i((E))
(V(p,Q)
1
}
<
1 k
+ 0
as k - Do.
400
This proves the claim.
Lower bounding 8k, the weight of alternative hypotheses.
First, we note that
o d- (x:) (x:) (2 Jar2 h exp((pp))) ( -))
UK: sup B Q
which is achieved by G O, e1) (where Idd is the origin) and æ = (Ed, ea). Let
5)p(-5)d1
(((d (9(d-1) - 1)
exp( f
exp
2
Claim G.7. For k 2 letting (ux) and be defined as above, define
8% = inf xEB Q=((((+)
TP.
(Qt- (xx) 2 cup)
Then we have,
8% =
kdd-
+0 as l: + 00.
Proof of Claim G.7. Let k 2 1. Fix any x (#1...., Id-1) E B. For every t T, there
exists u E {#1 - 1, 82 f,..., Id-1 t) We show L(u, ea) 2 Suppose otherwise, that is,
L(u, ed) I |u eal = |d) /2 Then,
( f) a (z (1) {1))
a (d- (x) (d-1) {(d-1)) + u (()))
By our assumption on (d)), and by the fact that E C, we have that (z))) (d)] Cauchy-Schward in d we have that,
/2 By
2
(x (1) +... n (dd-1) (2 (d-1) ((1-1))]
s (1) a (d=1)] I|2 || ,..., . (d-1)] (e0.... 1T
/2
2 1.
29

---

The last inequality uses that ||u||2 = 1 and (u(4))2 > 1 so the norm of the first (d- 1) coordinates is L/2 and also the fact that the first (d - 1) coordinates of x and t are in the 1 d-iik. This inequality, combined with the fact that [=(4)11
2
(d)) 2 contradicts that that (x1 - 1)
0.
Now, for the and the a from above, consider an arbitrary of with (u, u/) S f. and the Gaussian with mean and normal vector u', G u²). We will show that any such Gaussian assigns high mass to the point a, and furthermore that there is a high density of such Gaussians. Note that for 2 5, S
= L(u', ea) 2 π = u' E N. We compute the minimum density this Gaussian assigns œ. Consider, for E
d 1],
(2, - t) (Re D1 DI " t)
||D vT Ry
RT (z, - -)]l
12 (z. - t)l² + |12 (z. - t)l² + .... + Wd (x; - t) s 5(k2 .112 + +1,,
where F == (2; - +t/l12; t|| and (uz,..., } is orthonormal basis of {u'}' 1. We have that,
|n 2/2 (u (u u²)) APp
S ||u 1u-w- u u1112 ||f12
u 2u v + u' u
2 - 2 cos( L('l, u))
< 2 - 2(1 <(u',u)²
1
= LW',, u)² v k22
Hence, the density of G ( 1, w²) on is lower bounded by,
d-1
1 (2rr//22 k texp(-
Cull.
For every E T, we found a set of u' E N such that the density than cug. Since for some constant ca > 0 depending only on d,
G t, u/) assigns to æ is greater
1/k
P {ul E C(u, }}} = ca w((((N)
sin
dnd
(x)ddz
1/k
d-2
2 Cd
da
π
d-2
2
Cd
Rid-I
π
and since B was arbitrary, we indeed have,
inf P (Q)-1(x) 2 cuz) = S wEB Q-1((2))
kdd-
This completes the proof of the claim.
With the three claims, applying Lemma G.1 allows to conclude that the class of all Gaussians in Rd is not list learnable with m(a, B) = d - 1 samples. This implies that the class is also not public-privatelyy learnable with m(a, 3, = d 1 public samples.
H Statements and proofs for Section 7 --earnnnng when the Yatracos class has finite VC dimension
When the VC dimension of the Yatracos class of finite, the following gives an upper bound on the number of samples required to non-privately Iearn Q.
30

---

Fact H.1 ([Yat85), [DL01, Theorem 6.4]). Let Q S A(2). Let H. be the Yatracos class of Q and let VC(H). learnable with
( (d+ log( (
d
= 0
a²
samples.
For some classes of distributions, the above bound is tight. For example, it recovers the θ sample complexity for learning Gaussians in I [AM18].
To prove Theorem 7.2 we employ the following result on generating distribution covers for binary hypothesis classes with public data.
Fact H.2 (Public data cover [ABM19, Lemma 3.3 restated]). Let H C 2 and VC(H) There exists A: X + {H C
|H| < oo}, such that for any a, B (0, 1] there exists
[d + log( }})
m =
such that for any p E ((X), ) if we draw X (X .m)) i.i.d. from p. with probability 1-11-
A(X) outputs H. C 2 and a mapping f: H - H with
p(hAf(h)) Sa for all H
(where for A, C X, A&B denotes the symmetric set difference (A \ B) (B A)). Furthermore, we have |
2d
We also use the following pure DP algorithm for answering counting queries on finite domains.
Fact H.3 (SmalIDB [BLR13], (DR14, Theorem 4.5]). Let X be finite domain. Let 2 Let a. B E (0, and > 0, There is e-DP randomized algorithm, that on any dataset =
(I1, , Fn) with
+ log( (})
== Ω
EQ
outputs estimates 9: H such that with probability 2 11 B,
n
g(h) Σ un(a:)
sa for all h E H.
Proof of Theorem 7.2. We use our public samples from the unknown Q to generate public data cover H and mapping f: H + H courtesy of Fact H.2, selecting to target error g and failure probability &. Note that this implies that with probability 2 g. for every h H. (p(h) (())) < (p(h@f(h)) < g.
Next, we consider the representative domain of X' with respect to H. denoted by Xz. In other words, for every unique behaviour (1, (x)) {0, 11 induced by point X' on H. we include exactly representative [ax] in Xz- By Sauer's lemma conclude that
H
d
Then, we take our n private samples X = (X Xx)) and map each point X; to its representative
[X,] E Lz.. yielding a dataset of n examples [X] on the finite domain XR. Note that for any E H.
E (X,) = Σm= J ([X,)). Hence when we run SmalIDB (Fact H.3) on the input [X]
over the finite domain X₂ with finite class H,, choosing n large enough, we obtain ğ Rl such Σn (X,)) for all h E H.
that with probability > /. lā(h)
31

---

We also ensure is large enough so that we get the uniform convergence property on H. which has VC dimension d, with the private samples. That is, for all h H. with probability 1 3 (p(h) Σ 1, (x,) S 6-
8
As post-processing of J. our learner outputs
q = arg min sup lg(h) ((f(h)) 1Ea NEH
By the union bound, with probability 2 3, all of our good events occur. In this case, we have for all h H.
(p(h) - -(s()))
p((h)) + Σ (Xs) ==1
/.
-
M.
which implies 1p(h) - ((f(h)) $ 2. So for any q E Q
la(h) - -r(h)
a S (h) ((((h)) s la(h) - -p(h)) +
a
2
2
(V..p))
a < sup lg(h) (((())) & (V.)p) 2
a
hCH
2
We have that
sup 14(h) 0(f(h)) S sup (p(h) 9(f(h) S TV(p,)) + - NEW
Therefore,
a <a
(4 < sup - -(()))((()))
heH
can be verified that the choices of m and n in the statement of Theorem 7.2 suffice.
32


Reviews:
[{"review_id": "6c6gbQPmnu", "reviewer": "Reviewer_PbeY", "summary": "In public-private learning, an algorithm gets two sets of i.i.d. samples from an unknown distribution $q$ from a class $\\cal{Q}$ (say, the first set of size $m$ and the second one of size $n$), but is required to preserve DP only with respect to the second set. \nThis research direction is about understanding what are the (minimal) regimes of $m$ and $n$ that allows to learn a distribution from $\\cal{Q}$. The interesting regimes are when $m$ is much smaller than the sample complexity required to learn without privacy, and $n$ is smaller than what is required for learning under (full) DP. \nThis research direction has been initiate by Bie, Kamath and Singhal (NeurIPS 22’, BKS22), who showed that a relatively small amount of public samples suffices to improve the sample complexity of privately learning a single Gaussian and a mixture of Gaussians. \nThis work makes a significant step towards characterizing public-private learning by proving that it is equivalent (in terms of sample complexity) to two other notions: (1) Compressible Learning (Ashtiani et al., J.ACM 2020, ABDH+20) and (2) List-Learning. In more detail (ignoring running times and low order terms and constants in the sample complexity parameters):\n\nProposition 3.2: $(\\tau, t, m)$-compressible learning implies $(m,n = t + \\tau \\log m)$-public-private learning, where the former means that we encode $m$ samples using a $\\tau$ size subset plus an auxiliary string of size $t$, and this information suffices for estimating the distribution. \n\nProposition 3.5: $(m,n)$-public-private learning implies $(m,\\ell=\\exp(n))$-list learning, where the latter means that using $m$ samples we can output a list of size $\\ell$ of candidate distributions that at least one of them is a good estimation to the true distribution.\n\nProposition 3.6: $(m,\\ell)$-list learning implies $(\\tau=m, t = \\log(\\ell), m)$-compressible learning. \n\nThe main applications comes from the equivalence to compressible learning, since [ABDH+20] proved that learning a Gaussian or a mixture of Gaussians is compressible learnable with relatively small amount of samples, so using this connection they deduce an improved sample complexity upper bounds for these tasks under private-public learning, as well as a tight lower bound of the number of public samples that is required for learning a single Gaussian. The upper bound on public-private learning a mixture of Gausians is actually an upper bound for learning any mixture of distributions for a given class $\\cal{Q}$ as a function of the sample complexity that is required to learn a single distribution from $\\cal{Q}$, as [ABDH+20] proved that for compressible learning, learning a $k$ mixture requires (esseitially) $k$ times the sample complexity for a single distribution.\n\nIn section 5 they also handle the agnostic case where the samples comes from a distribution that is only close to a one in the class, a setting which was also considered in the previous work of [BKS22]. They prove (Theorem 5.2) that robust compression implies agnostic public-private learning, and deduce an upper bound on learning a Gaussian in this case.\n", "questions": "No questions.\n\n\nOne suggestion:\n\nI think it is worth adding short proof sketches of the reductions (Propositions 3.2, 3.5, 3.6) in the main body. The proofs are not long, and I'm sure you can explain the idea in each proof using a few sentences.\n\nMinor comments:\n\n(1) Theorem 1.1, item 2: \"$\\cal{Q}$ is has\".\n\n(2) Theorem 1.3: robust compression is not defined at this point.\n\n(3) Definition 2.5: In ABDH+20, $f_q$ is explicitly defined by outputting an $\\tau_0$-subset of samples, and a short string. Here, you just claiming the existence of such $f_q$, which is strange to me since, for example, if $f_q$ is randomized and depends on $q$, it could simply ignore the input samples (which are sampled from a distribution that is only close to $q$) and just use fresh samples from $q$.\n\n(4) Corollary 4.2: I think it is worth comparing the sample complexity to existing efficient and fully DP methods like https://arxiv.org/abs/2303.04288 and https://arxiv.org/pdf/2112.14445.pdf (BKS22 only compared their result to KSSU19 https://arxiv.org/abs/1909.03951 which is significantly inefficient compared to the first two results I mentioned).", "limitations": "The authors present the limitations in Section A (supplementary material).", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The equivalences between public-private learning to the other notions of learning are very interesting, and the progress from the work of [BKS22] (both quantitative and qualitative) is significant. Despite the significant limitations (described below), in my opinion, this is a good submission which is above the acceptance threshold. Therefore, I recommend acceptance.", "weaknesses": "As mentioned in the limitations section (Section A, Supplementary material), the reductions between the different notions are inefficient, and sometimes not even constructive (e.g., in the reduction from list learning to public-private learning). So all the new upper bounds of this paper are inefficient, and it is still left open whether we can construct efficient public-private learning algorithms with the improved samples complexities achieved in this paper.\nWhile the results of [BKS22] are more restricted and weaker in terms of sample complexity, they are computationally efficient (unlike this work), so if we are only interested in computationally efficient learners, this work does not make any progress except the lower bound which holds (in particular) for efficient learners.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments and suggestions. We are glad that the reviewer finds the connections we present between public-private learning and other notions of learning interesting. Indeed, our investigation only answers questions regarding the statistical complexity of public-private learning. Finding efficient algorithms for these tasks is not addressed by our work, and is an important open question.\n\nIn what follows, we address specific points raised by the reviewer.\n\n—---------------------\n\n> Adding short proof sketches for the reductions.\n\nYes, we’ll add proof sketches for the reductions in the revised manuscript.\n\n> Typos and organization\n\nThanks for pointing out typos and the out of order definition. Theorem 1.3 requires some setup, so we’ll introduce its consequence (agnostic and distribution shifted learner for Gaussians) and leave the statement for the main body. \n\nWe’ll also move the limitations to the main body in the revised version, with the extra space granted.\n\n> Definition 2.5: In ABDH+20, $f_q$ is explicitly defined by outputting an 𝜏-subset of samples, and a short string. Here, you just claiming the existence of such $f_q$, which is strange to me since, for example, if $f_q$ is randomized and depends on $q$, it could simply ignore the input samples (which are sampled from a distribution that is only close to $q$) and just use fresh samples from $q$.\n\nYes, we missed a condition in the definition. The $f_q$ defined should have the property that on all samples $S \\in \\mathcal X^m$, $ f_q(S)$ is a subset of $S$. We’ll fix this in the revised version.\n\n> Corollary 4.2: I think it is worth comparing the sample complexity to existing efficient and fully DP methods like https://arxiv.org/abs/2303.04288 and https://arxiv.org/pdf/2112.14445.pdf (BKS22 only compared their result to KSSU19 https://arxiv.org/abs/1909.03951 which is significantly inefficient compared to the first two results I mentioned).\n\nWe’ll do a more comprehensive discussion of results in the updated version.\n\nAll three of these are looking at parameter estimation with assumptions on the underlying Gaussian mixture, whereas we focus on density estimation of arbitrary Gaussian mixtures (and we are not aware of any $\\text{poly}(k,d,\\alpha,\\beta)$ algorithms even in the non-private case).\n\n[AAL23] uses [MV10] as a black box, and inherits its unoptimized and very large polynomial sample complexity. We believe the exponent of the polynomial is something like $\\approx 300$, but we are not exactly sure.\n\n—---------------------\n\nIf the reviewer has any additional comments or questions that have not been adequately addressed, we would be happy to speak more during the discussion phase.\n\n**References**\n\n[AAL23] Jamil Arbas, Hassan Ashtiani, and Christopher Liaw. Polynomial time and private learning of unbounded gaussian mixture models. ICML’23.\n\n[MV10] Ankur Moitra and Gregory Valiant. Settling the polynomial learnability of mixtures of gaussians. FOCS’10.\n"}, {"review_id": "AyOFhfghPB", "reviewer": "Reviewer_rJcv", "summary": "Continuing a line of work recently initiated by Bie, Kamath, and Singhal (NeurIPS '22), this submission studies differentially private distribution learning (a.k.a. hypothesis selection) in the presence of public data. The main result is a collection of quantitative equivalences between this task and the problems of sample compression and list learning. More specifically, the paper shows that for any class of distributions Q, the following are (roughly) equivalent:\n1) Q admits a sample compression scheme using m samples and compression size t\n2) Q is pure $\\varepsilon$-DP learnable using m public samples and t private samples\n3) Q is list learnable using m samples and list size exp(t).\n\nAs applications of this set of equivalences, the paper proves new upper and lower bounds on the sample complexity of pure public-private learning. These include new algorithms for learning Gaussians, mixture distributions, and product distributions via sample compression, as well as a lower bound on the public sample complexity of pure public-privately learning a single Gaussian that follows from a lower bound for list learning. The paper also works out a connection between robust sample compression and agnostic/distribution-shifted public-private learning, and a pure public-private learner for classes whose Scheffe sets have finite VC dimension.", "questions": "- Lines 235-239 offer a comparison to the previous result of BKS'22 on learning mixtures of Gaussians, but isn't easy to make sense of without a brief (informal) statement of what their result actually is.\n\n- Line 500: Should be $\\tau_0 = \\tau(\\alpha/6, \\beta/2)$\n\n- While ultimately short, I found the contradiction-based proof of Proposition 3.5 unnecessarily hard to follow for this reason. Why not just do a direct proof along the following lines, using roughly the same calculations? For every distribution $p \\in \\mathcal{Q}$, accuracy of $\\mathcal{A}$ implies that whp over $\\widetilde{X} \\sim p^m$, we have $p \\in Q_{\\widetilde{X}}$. This latter event implies $p$ is close to $\\mathcal{L}(\\widetilde{X})$, which is the success condition of the list learner.\n\n- I didn't understand why Lemma F.1 is called a \"no free lunch\" theorem. To my mind, a no free lunch result rules out the existence of learning algorithms that are simultaneously optimal for a sufficiently broad class of problems. Did the authors have in mind a different context in which this name makes sense to describe this result?", "limitations": "Some limitations (overlapping with weaknesses described above) are discussed in the appendix.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The equivalences shown in this paper provide a nice set of perspectives on the public-private distribution learning problem, both conceptually and \"practically\" in terms of offering new avenues for proving upper and lower bounds.\n\n- The proofs of these equivalences are simple, conceptually clear, and illuminating.\n\n- I'd say the main technical contribution in this paper is a lower bound showing that it is impossible to list-learn d-dimensional Gaussians using fewer than d samples. (This in turn implies a lower bound of public-private learning.) This is a sharp result that matches an upper bound from BKS'22. The proof goes through a general lower bound technique for list-learning, called a \"no-free-lunch\" theorem in this paper, roughly based on exhibiting collections of distributions that are not close in TV distance, but easily confused using a small number of samples.\n", "weaknesses": "- The characterizations shown in this work all apply to pure differential privacy. This is good for upper bounds, but is a major limitation of the most technically-involved contribution of the paper on lower bounding list- / public-private learnability of Gaussians. In particular, the conversion from a public-private learner to a list-learner depends crucially on pure differential privacy; while it can probably be extended to a quantitatively weaker result for concentrated DP, it doesn't say anything about, say, Renyi or approximate DP.\n\n- The paper's conversion from a public-private learner to a list-learner is not quite constructive, as it relies on a covering-based characterization of pure private distribution learning. However, this characterization can probably be unrolled into an algorithmic construction of a cover using the usual technique of running the DP algorithm repeatedly on a fixed dataset using many sequences of coin tosses. Also, none of the equivalences proved preserve computational efficiency in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments and suggestions. We are glad the reviewer finds that our work offers some nice perspectives on the public-private learning problem. Indeed, we acknowledge the limitations pointed out by the reviewer: (a) that our equivalence only holds for the pure DP setting and (b) we do not address issues pertaining to computational efficiency.\n\nBoth aspects are important directions for future work; indeed for one of the tasks studied – density estimation of arbitrary Gaussian mixtures – the authors are not aware of any poly-time algorithm for the task, even in the non-private setting.\n\nIn what follows, we reply to specific points raised by the reviewer.\n\n—---------------------\n\n> This characterization can probably be unrolled into an algorithmic construction of a cover using the usual technique of running the DP algorithm repeatedly on a fixed dataset using many sequences of coin tosses. \n\nThat’s really interesting. We would be happy to learn more about this – would it be possible to elaborate further/link an example of a paper that uses this technique?\n\n> Lines 235-239 offer a comparison to the previous result of BKS'22 on learning mixtures of Gaussians, but isn't easy to make sense of without a brief (informal) statement of what their result actually is.\n\nNoted. We’ll add a more comprehensive discussion of this result and other related results.\n\n> Line 500: Should be 𝜏 = 𝜏(ɑ/6, β/2)\n\nThanks, we fixed this.\n\n> I found the contradiction-based proof of Proposition 3.5 unnecessarily hard to follow for this reason. Why not just do a direct proof\n\nGood point, we’ll change it to a direct proof.\n\n> I didn't understand why Lemma F.1 is called a \"no free lunch\" theorem. \n\nThe context we had in mind is from the VC lower bound results for PAC learning, i.e., Theorem 5.1 from [SSBD14]. In that result, using the flexibility of a hypothesis class, a class of hard instances are constructed such that any algorithm that doesn’t see enough samples must fail on one of them. Hence, there is no universal learner (free lunch).\n\nSimilarly, in our Lemma F.1, we use the flexibility of the class $\\mathcal Q$ to construct a sequence of classes of hard instances ($\\mathcal Q_k$). Each $\\mathcal Q_k$ rules out the existence of a list learning algorithm that takes few samples, outputs a list of size $\\leq k$, and succeeds on every $p$ in $\\mathcal Q_k$. This rules out the existence of any finite list learner that sees few samples and succeeds on every $p$ in $\\mathcal Q$.\n\nWe hope this clarifies things. We’ll include this discussion in the revised version of the manuscript.\n\n—---------------------\n\nIf the reviewer has any additional comments or questions that have not been adequately addressed, we would be happy to speak more during the discussion phase.\n\n**References**\n\n[SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014."}, {"review_id": "IzIgZPJYZn", "reviewer": "Reviewer_cweb", "summary": "The authors consider the problem of learning a distribution in a known class using private samples under pure DP, as well as a number of public samples drawn from the same distribution. Some distribution classes, such as Gaussians, are not learnable using a finite number of private samples, or even with a finite number of private samples and a small number of public samples, but are learnable with private samples and a medium number of public samples.\n\nThe authors make progress towards understanding what classes of distributions are learnable with what number of public samples. Their main contribution is to establish that the following three are equivalent (up to constants): (1) A class of distributions is public-private learnable, i.e. learnable with m public samples and some finite number of private samples (2) A class of distributions is realizably compressible with m samples, i.e. given a finite number of samples from a distribution, one can encode the distribution into m samples and some finite number of auxiliary bits such that some decoder can learn the distribution using only the encoded information (3) A class is list learnable with m samples, i.e. there is an algorithm that takes m samples and outputs a finite list of distributions such that one distribution in this list is close to the target distribution. The authors also give concrete/non-trivial bounds on the finite number of samples/finite list size in the equivalence statement.\n\nThe above equivalence has a number of applications. For example, since mixtures of Gaussians are known to be compressible, the above equivalence immediately shows they are public-private learnable. More generally, since the class of mixtures (resp. products) of distributions from compressible classes is also compressible, mixtures (resp. products) of distributions from public-private learnable classes are also public-private learnable. While BKS22 established public-private learnability of Gaussians, the authors' result has several qualitative advantages, such as a stronger notion of DP and allowing arbitrarily small mixture probabilities. Similarly, the authors show that d-dimensional Gaussians are not learnable with d-1 public samples and any number of private samples, by showing that this implies list-learnability of d-dimensional Gaussians with d-1 public samples, which violates a lower bound. \n\nThe authors also extend the reduction from compressible classes to public-private learnable classes, to a reduction from robust compressible classes to classes that are public-private learnable, with out-of-distribution public samples and a private distribution that is only close to a member of the class. \n\nFinally, the authors show that classes of distributions whose Yatracos class has VC dimension d and dual VC dimension d* are learnable with d private samples and d^2 times d* private samples.", "questions": "-You mention that you do not optimize the private sample complexity - do you have a sense for how large the slack in the private sample complexities might be? (i.e., are they optimal up to log factors, small polynomials, large polynomials?)", "limitations": "Yes; in Appendix A the authors nicely state the limitations of their work. \nN/A on negative societal impact, since it is a theory work on improving privacy-preserving algorithms.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Overall I feel the paper is quite strong. The main contribution of the paper, the equivalence of three properties of a class of distribution, is elegant and likely to have high impact, as distribution learning is obviously a very central and fundamental problem in learning theory, and using public data for private learning is becoming increasing popular. As an example of the potential for impact, just from the equivalence of these three classes, the authors are able to show a lower bound on the number of public samples needed to learn a Gaussian that is optimal up to an additive difference of 1, which was an open problem beforehand. I am not very confident in my knowledge of the field of distribution learning, but I suspect the elegance of the result could easily lend itself to understanding the public-private learnability of other important classes of distributions. In addition to this main contribution, there are a number of other contributions that are independently interesting. The paper is also technically interesting and novel. e.g, this paper is the first to use list-learning (which is related to, but not the same as list-decodable learning) in establishing upper and lower bounds for other definitions of learnability. The paper was enjoyable and easy to read - while there are several involved definitions needed to fully understand the results, the authors do a good job distilling the results down into a form that's easier to parse, without sacrificing too much detail. ", "weaknesses": "I felt the main \"weakness\" of the paper is that there are many results the authors provide, and so the authors had to save most of the discussion of proof techniques for the appendix. In particular, I felt Sections 6 and 7 did not offer much more insight than the related sections of the introduction, and could be moved to the appendix in favor of e.g. a proof sketch for Prop 3.2, which would help the reader better understand the equivalence between the different definitions of learnability. Of course, such a weakness is likely to not exist in a camera-ready or arxiv version.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful comments on our work. We are glad the reviewer finds the problem we study to be relevant, and our results to have potential for impact.\n\nIn what follows, we address specific points raised by the reviewer.\n\n—---------------------\n\n\n> Inadequate discussion of proof techniques in the main body.\n\nNoted. We’ll add proof sketches for the reductions (Proposition 3.2, 3.5, 3.6) and spend more time discussing results, in particular for Sections 6 and 7, since right now they are mostly repetitions of the theorem statements in the intro.\n\n> You mention that you do not optimize the private sample complexity. Do you have a sense for how large the slack in the private sample complexities might be? (i.e., are they optimal up to log factors, small polynomials, large polynomials?)\n\nWhat we were referring to there were the reductions to and from sample compression. They preserve public data complexity, but lose polynomial factors in the private sample complexity. \n\nFor example: by applying the public-private learning/sample compression equivalence to obtain the generic “public-private learning implies public-private learning for mixtures” statement, if we apply it to a Gaussian public-private learning using $m = \\tilde O(d)$ public and $n = \\tilde O(d^2/\\alpha^2 + d^2/\\alpha\\varepsilon)$ private samples, we get a $m = \\tilde O(kd/\\alpha)$ public, $n = \\tilde O(d^2/\\alpha^3 + d^2/\\alpha^2\\varepsilon)$ private public-private learner for Gaussian mixtures. This is a factor of $1/\\alpha$ off from the sample complexity obtained from using the compression scheme for mixtures of Gaussians (Theorem 1.2).\n\nOn another note, for Theorem 1.2 and Corollary 4.1, in the specific regime where $\\varepsilon>\\alpha$, the private sample complexities are tight up to log factors, based on non-private lower bounds of $\\Omega(d^2/\\alpha^2)$ for a single gaussian and $\\tilde \\Omega(kd^2/\\alpha^2)$ for mixtures. This would be the case even with more than $O(d)$, but $o($non-private sample complexity$)$ public samples. \n\n—---------------------\n\nIf the reviewer has any additional comments or questions that have not been adequately addressed, we would be happy to speak more during the discussion phase.\n"}, {"review_id": "lBToW4K00F", "reviewer": "Reviewer_7w9P", "summary": "This paper studies differentially private learnability of probability distributions.\nThe results put forward are very interesting!\nFor example, they show that the public-private learnability of a class of distributions is connected to the existence of sample compression schemes as well as to an intermediate notion of learning they define.", "questions": "Are there any complexity-theoretic implications of your work?\nLearning is connected to complexity lower bounds.\nIs this the case for private learning?\nMaybe some stronger connection exists?\n\nLine 43:\nNice question!\nCan you please discuss similar questions?\n\nTheorem 1.1:\nYou should emphasize this result more, as it is a main important result.\n\nLine 118:\nPlease define TV.\n(This is in the appendix...)\n\nLine 142:\nPlease define $SC$ (as \"sample complexity?\").\n\nGeneral comment:\nSince you are not including proofs in the main body, maybe simplify the bounds you are presenting?\nThis will save space and thus allow for more explanations.\n\nSection 5:\nCan you please better explain the notion of distribution shifted?\n\nSection 6 and Section 7:\nCan you please add some more intuition here?\n\nMaybe put limitations in the main body?\n\nThere is no conclusion section!\nWhy?\nYou could put open problems there.\n\nThis paper has so many novel results (proofs in appendix).\nImpressive!", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality:\nThis work is original, to the best of my knowledge.\n\nQuality:\nQuality of results and topic choice are very good; see questions.\n\nClarity:\nWriting is clear; see questions.\n\nSignificance:\nThe results are very significant for the learning community.", "weaknesses": "Not significant weaknesses detected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for thoughtful comments on our work. We are happy to hear the reviewer finds our results and topic of study interesting. We also thank the reviewer for their nice suggestions and questions.\n\nIn what follows, we respond to specific points raised by the reviewer.\n\n—---------------------\n\n> Are there any complexity-theoretic implications of your work? Learning is connected to complexity lower bounds. Is this the case for private learning? Maybe some stronger connection exists?\n\nWe are not aware of any. But we are generally unfamiliar with this line of work – could you elaborate further on what kind of connections you have in mind (and link some papers)? The only thing that comes to mind is [Dan16] – but since our learners are (a) not efficient; and (b) are for distribution learning, rather than PAC learning), it seems like this work is not related.\n\n> Line 43: Nice question! Can you please discuss similar questions?\n\nSure. Our work examines the minimal amount of public data needed to render a class pure privately learnable. We can also examine this question in the approximate DP case. Note that here, it is open whether there is even a separation between learnable and approximate DP learnable.\n\nThe VC bound of Theorem 1.5, although more general, is loose and is off “qualitatively” also: when applied to gaussians, it yields a $d^2/\\alpha$ public sample complexity, though we know $d$ is possible, with no dependence on $\\alpha$. It would be interesting to understand what qualities of a distribution admit $\\alpha$-independent public sample complexity, beyond a not-too-illuminating “it has an $\\alpha$-independent compression complexity”. The situation is quite different in binary classification: [ABM19] shows that any class that is not learnable under pure privacy learnable requires $1/\\alpha$ public samples.\n\nAnother interesting question is whether a small amount of public data can lead to algorithmic improvements (runtime efficiency, simpler algorithms), as opposed to sample complexity improvements. For Gaussian mean estimation, one public sample removes the need for coarse estimation in [HKM22] (their coarse estimation algorithm formulates the task as an SDP via sum-of-squares paradigm, and runs in polytime for a large polynomial). It would be interesting to see if with more, but o(non-private sample complexity) public data, we can replace other steps to devise simpler, faster algorithms.\n\n> Missing or unclear definitions.\n\nWe’ll address these in the revised version.\n\n> Section 6 and Section 7: Can you please add some more intuition here?\n\n> Maybe put limitations in the main body?\n\n> There is no conclusion section! Why? You could put open problems there.\n\nYes, in our revised manuscript, we’ll focus on better discussion of our results. \n\nIn particular, we plan to add proof sketches of the reductions, explanations of the results in Section 6 and 7, as well as more comparison to previous results (particularly for Gaussian mixtures) and implications. \n\nWe also plan to put limitations and a conclusion in the main body. We’ll use the extra space granted and also try to find some space by simplifying or deferring bounds to the appendix and removing repeated theorem statements.\n\n—---------------------\n\nIf the reviewer has any additional comments or questions that have not been adequately addressed, we would be happy to speak more during the discussion phase.\n\n**References**\n\n[Dan16] Amit Daniely. Complexity theoretic limitations on learning halfspaces. STOC’16.\n\n[ABM19] Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data. NeurIPS’19.\n\n[HKM22] Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. STOC’22."}]

Author rebuttal:

Meta-review: The reviewers unanimously agreed that this work provides insightful perspectives on the public-private distribution learning problem, both conceptually and algorithmically in terms of offering new avenues for proving upper and lower bounds.
Decision: Accept (spotlight)