User-Level Differentially Private Learning via Correlated Sampling
Authors: Badih Ghazi
Ravi Kumar
Pasin Manurangsi
Venue: NeurIPS 2021 Poster (2021)
Keywords: User-level privacy
Global stability
Representation dimension
Correlated sampling

Abstract: Most works in learning with differential privacy (DP) have focused on the setting where each user has a single sample. In this work, we consider the setting where each user holds $m$ samples and the privacy protection is enforced at the level of each user's data.  We show that, in this setting, we may learn with a much fewer number of users. Specifically, we show that, as long as each user receives sufficiently many samples, we can learn any privately learnable class via an $(\epsilon, \delta)$-DP algorithm using only $O(\log(1/\delta)/\epsilon)$ users. For $\epsilon$-DP algorithms, we show that we can learn using only $O_{\epsilon}(d)$ users even in the local model, where $d$ is the probabilistic representation dimension. In both cases, we show a nearly-matching lower bound on the number of users required.

A crucial component of our results is a generalization of global stability [Bun, Livni, Moran, FOCS 2020]  that allows the use of public randomness. Under this relaxed notion, we employ a correlated sampling strategy to show that the global stability can be boosted to be arbitrarily close to one, at a polynomial expense in the number of samples.

User-Level Private Learning via Correlated Sampling
Badih Ghazi
Ravi Kumar
Pasin Manurangsi
Google, Mountain View, CA.
(badihghazi, ravi ravi.k53 @gmail. com, pasindgoogle.com
Abstract
Most works in learning with differential privacy (DP) have focused on the setting where each user has a single sample. In this work, we consider the setting where each user holds samples and the privacy protection is enforced at the level of each user's data. We show that, in this setting, we may learn with a much fewer number of users. Specifically, we show that, long as each user receives sufficiently many samples, we can learn any privately learnable class via an (s, 8)- users. For e-DP algorithms, we show DP algorithm using only (llgg(//8)/ that we can learn using only Oz users even in the local model, where d is the probabilistic representation dimension. both cases, we show a pearly-matchinn lower bound on the number of users required.
A crucial component of our results is generalization of global stability [BLM that allows the use of public randomness. Under this relaxed notion, we employ a correlated sampling strategy show that the global stability can be boosted to be arbitrarily close to one, at polynomial expense in the number of samples.
Introduction
Differential privacy (DP) [DMNS06, DKM D6] has emerged as the accepted notion for quantifying the privacy of algorithms, whereby a method considered private if the presence or absence of a single user has negligible impact on its output. The two most widely-studied models of DP are the central model, where an analyzer has access the raw user data, and required to output a private answer, and the local model [War65, KLN+11 11 DJW13], where the output of each user is required to be private. DP has become a widely adopted standard in both industry IEPK14, Shal4, Gre App17, DKY17] and government agencies, including the recent 2020 US Census [Abo18] 18). For technical overview of DP, see the monographs by Dwork and Roth [DR14] 14] and by Vadhan [Vad17].
DP has gained spotlight in machine learning (e.g., [CMS11, 1, ACG 16)), with an increased emphasis on protecting the privacy of user data used for training models. In the traditional notion of DP, the goal is to protect the privacy of each training example, where it is assumed that each user contributed precisely one such example; this sometimes referred to as item-level privacy. However, a more realistic and practical setting is where a single user can contribute more than one training example. Here, the goal would be so-called user-level privacy, i.c., protecting the privacy of all the training ex- amples contributed by single user. This is especially relevant for federated learning settings, where each user can contribute multiple training examples [MRTZI8, WSZ+ 19, AMR + 19, EMM 20]; see the survey by Kairouz et al. [KMA+ + 19, Section 4.3.2), where the question of determining trade-offs between item-level and user-level DP is highlighted. then becomes important to understand the lcarnailiiyy implications of this distinction between user-level vs item-level privacy.
One way to understand this problem is artificially limit the number of training examples con- tributed by each user. This has been explored for some analytics and learning tasks in [AKMV19, 27] and is related to node-level DP [KNRS13]. While this is an interesting line of work, it does not sufficiently address the core of the problem. For instance, is learning possible with
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

only a small number of users if each user contributes sufficiently many training examples? This question was addressed by Liu et al. [LSY+20] 20] for learning discrete distributions and by Levy et al. [1 for some learning tasks including mean estimation, ERM with smooth losses, stochas- tic convex optimization. They show that the privacy cost decreases faster as the number of samples per user increases.
In this paper we address the question in a very general setting: what can user-level privacy gain for any privately PAC learnable class? Recall that it had recently been shown that a class is learnable via (e, 5)-DP algorithms iff it is online learnable [ALMM19, BLM20), which in turn equivalent to the class having a finite Littlestone dimension [Lit87]. Furthermore, it is also known that class learnable via e-DP algorithms iff has a finite probabilistic dimension [BNS19a].
As discussed below, our protocols are based on a novel connection hetween correlated sampling tool from sketching and approximation algorithms [Bro97, KT02, Cha02] and DP learning.
1.1 Our Results
Our first main result is that, for any online learnable class, it is possible to learn the class with an (e, 8)- algorithm using only (log((18))/ users, long as each user has at least (oly(d/o) samples (Theorem 1), where is the Littlestone dimension and a is the error of the hypothesis output by the learner. It should be noted that the remarkable and arguably surprising aspect of this result is that we can learn using a constant number of samples (depending only on the privacy parameters 8), regardless of how complicated the class might be, long the class is online learnable. (For all formal definitions, see Section 2.) Indeed, previous work [A [AKMV19) had explicitly conjectured that such bound is impossible for user-level learning, albeit in different setting than ours.
Theorem 1. Let a, 3 E (0, 0.1), and C be any concept class with finite LDim(C) d. Then, for any E, 8 E (0, 1). there exists an (e, (e.8)-DP (a, B3 Ba-ccuraeeee learner for that requires O (l0g(1/(68))ee) users where each user has OB ((d/))((1) samples.
Our algorithm in Theorem I can in fact be extended to work even in the weaker shuffle model of DP. We provide more detail about such an extension in Appendix D.
Our second result is generic E-DP learner in the local model for any class C' with finite probabilis- tic representation dimension PRDim(C). This gives a separation in the local DP model between the user-level and item-level settings; the sample complexity in the latter is known to be polyno- mial in the statistical query (SQ) dimension [KLN+11], which can be exponentially larger than the probabilistic representation dimension. A simple example of such separation is PARITY on d unknowns, whose probabilistic representation dimension is O(d) (this can be seen by taking the class itself to be its own representation), whereas its SQ dimension is 20(d) [BF]+94]. In this case, our Theorem 2 implies that PARITY can be learned using only (d) users when each user has (d)) examples; by contrast, the aforementioned lower bound [KLN+ 11] implies that, in the iteellevel setting (where each user has a single example), 20))) users are needed.
Theorem 2. Let a, , E (0, 0.1), and C be any concept class with finite PRDim(C)= d. Then, for any (0, 1), there exists an E-DP (a.,))accuratee learner for C in the (public randomness) local model that requires O d+log(1/8)
users where each user has Öi (d*) samples.
In the central model, we get a slightly improved bound on the number of users in terms of l/e. Theorem 3. Let a, 3 E (0, 0.1), and C' be any concept class with finite PRDim(C) = d. Then, for any E e (0, 1), there exists an s-DP (a: B)-accureeee learner for C that requires O [d+og(1188) users where each user has Ö3 (e/a²) samples.
Interestingly, we can also show that the number of users required in the above results is essentially the smallest possible (up to a 1/8 factor in Theorem 2), as stated below.
Lemma 4. For any B S 1/4,e
(0,1) 1) and DP (a. 3)-accurate learner on n users for a concept class C, then we must have n. 2 ((mii((lo(1// (C)))(())/e)..
(0, 1-111,)),, if there exists an (c, 8)-
The summary of our results described above can be found in Table 1.

---

User-Levee
Item-Level
Bounds
# users
samples/user
Ref.
users
s-DP
Upper
PPDDDm
PRDim O(L)
Theorem 3
@(PRDim /s)
(Central)
Lower
ST(PRiim /e]
Lemma 4
[BNS19at
s-DP
Upper
O(PRDim /E")
PRDinn
Theorem
SQDim ([1)
(Local)
Lower
ST(PiiDim /e]
Lemma 4
[KLNT] 11J
(e, 8)-DP
Upper
(llog(1/8)/ [}]
LDim Theorem
LDim (41) [GCKM2IJ
(Central)
Lower"
Lemia 4
2[oog "DDim)
PRDim}/et
[ALMM19]
Table 1: Summary of our results in the user-level setting and prior results in the item-level setting. For sim- plicity, assume that the accuracy parameter and success probability of the learner constants, and disregard their dependencies. lower bounds hold regardless the number samples each user receives.
While our previous results establish nearly tight bounds on the number of users required for DP learning, they are in general not efficient. For example, the pure-DP DPre-DP learners have running times that grow (at least) exponentially in the size of the probabilistic representation, and the approximate-DP learner similarly has running time that grows (at least) exponentially in the Littlestone dimension. Our final result investigates how to get efficient learners. Informally, we show that we can take any efficient SQ algorithm and turn it into efficient learner in the user-level setting (Theorem 5).
Theorem 5. Let C' be any concept class, and suppose that there exists an algorithm that can a-learn C using q statistical queries STATp(T). Furthermore, suppose that any hypothesis output by can be represented by b bits. Then, there exist the following algorithms:
(i) An 8)-P) (a, -cccurraeeeee learner with (llo((//8)/e users. where each user has poly samples.
(ii) An E-DP (a, -a--uuure learner with (b+log(1/3) users, where each user has poly (BF) samples.
5
(iii) An E-DP (a, -accuraae learner in the (public randomness) local DP model with O (+log(1/2) users, where each user has poly Br samples.
Moreover, all DP learners described above run in time poly(time(A), 1/T,)))))))
Thanks to the abundance of SQ learning algorithms, the above result can be applied to turn those into efficient user-level DP learners. We discuss some interesting examples of these in Appendix B.2.
Independent Work of Impagliazzo et al. [ILPS21]
As an intermediate step of our proofs, we define a property called pseudo-globaliy stability for learning algorithms (Definition 15) and provide several such algorithms (Corollaries 21 and 27, and Lemma 32). In an independent work, Impagliazzo et al. [ILPS2I] studies a similar notion under the name reproducibility and provide several reproducible algorithms e.g. for heavy hitters, SQ-based algorithms and learning halfspaces. Below we provide more detailed discussion on the similarities and differences between the two papers:
Definition. Strictly speaking, the main definition in [ILPS21] is slightly different com- pared ours, but they note in the appendix that the two definitions equivalent up polynomial factor in the parameters.
SQ Algorithms. Both Impagliazzo al.'s work and ours (Lemma 32) give generic reduc- tions for turning SQ algorithms to pseudo-globar stable ones.
Amplification of Stability Parameter. [ILPS21, Theorem A.2], a reduction for decreas- ing the stability parameter is given. Indeed, one can also view our reduction in Theorem 20 in this form but our result weaker as our reduction starts out with (not pseudo) globally stable algorithms, whereas their reduction works even when starting with pseudo globally stable algorithms.
Heavy Hitter Algorithms. Our aforementioned reduction also implicitly gives an algo- rithm for heavy hitters. Once again, this is weaker than that in Impagliazzo al.: ours only gives single heavy hitter whereas that of [ILPS21] can provide a list of all heavy hitters.

---

Additional Results in [ILPS21]. [ILPS21] also contains many additional results, includ- ing a lower bound on the overhead due to pseudo-global stability, a pseudo-globally stable median algorithm and a pseudo-globally stable algorithm for learning halfspaces with a margin.
1.2 Proof Overview
For simplicity of presentation, we will focus on Theorem I; we will briefly discuss the proofs of the other results, which are similar in flavor, at the end of this section.
Let us assume for the moment that each user, given their m samples drawn i..d. from D, can output the same hypothesis h" (with small error) with high probability. If this holds, then we would be done: we can simply run a DP selection algorithm to pick the most frequently seen hypothesis.
This assumption is quite strong, but not completely unreasonable. Specifically, Bun al. [BLM20]-in their seminal work that characterizes hypothesis classes learnable in the item- that it is possible come up with a learner that outputs some hypothesis h" with probability 2 O(d), where d denotes the Littlestone dimension of the concept class. We may attempt to use this in the approach described above, but this does not work: in order to even see ht at all (with say a constant probability), we would need 20(4) users, which is prohibitive!
level DP setting-shovee
To overcome this, we exploit shared randomness between users. Our main technical result here is that, if the users share randomness, we can ensure that they output the same h" with probability arbitrarily close to one; we can then run the DP selection algorithm to pick h². This immediately allows our overall strategy described above to go through.
The shared randommess is used in our algorithm(s) via correlated sampling. Recall that a correlated sampling strategy is an algorithm that takes in probability distribution P together with randomness The guarantee is that, if we run it on two distributions Pi, P2 but with the same randomness r, most constant times the total variation
then the probability (over r) that the outputs disagree distance between P1 and P2. The task then is simply to compute, for each user i, such a probability distribution P, from their own samples such that the P,'s do not differ much between different users.
Our algorithms in Theorems 1 to 3 follow this framework. The differences are in the DP selection algorithms (based on central vs local model and whether we are interested in pure- or approximate- Dnd,and, more importantly-howw we construct the distribution P; of hypotheses. In the case of the approximate-DP learner (Theorem 1), we build this on top of learning algorithm of Ghazi et al. [GGKM21], which has a slightly stronger guarantee than that of [BNS19b]: it outputs a list of size at most (noly(d) with the guarantee that h" belongs to it with probability at least 1 1/poly( (d). Each user runs such an algorithm poly(d) times on fresh samples drawn from D. and uses the output hypotheses to build the distribution P.. For pure-DP learners (Theorems 2 and 3), each user simply uses the empirical error the probabilisticc representation of the class to build the distribution P..
Finally, our SQ algorithm (Theorem 5) deviates slightly from this framework. Instead of computing P: outright (which is usually inefficient since its support is large), we proceed one statistical query at a time. Specifically, each user employs correlated sampling to answer each statistical query; if they manage to answer all queries in the same manner, then the algorithm will output the same hypothesis. The point here is that, since the answer to each statistical query is just a bounded-precisee number in [0, 1]. building a probability distribution of the possible answers can be done efficiently.
2 Preliminaries
Let Y = {0, 1}. For set Q, we use 20 to denote the set of all functions from Ω to Y and use Ag to denote the set of all distributions on Ω. For distributions P, Q, we use p ~ P to denote that p is drawn from P and de (P, Q) to denote the total variation distance between P. and Q.
Let X be a finite 2 Let C' denote the set of concepts from to Y, and let D be any distribution on X x Y realizable by some h E C.
SSecton 2.3 contains the formal definition of the selection problem and known DP algorithms for 'While our results can be extended to the case where X is infinite, it does require non-trivial generalization of notation and tools (e.g., correlated sampling) that setting.

---

We first recall the notion of DP. Let E, ó E Rzu. Two datasets are neighboring if one can be obtained from the other by adding or removing a single user.
Definition 6 (Differential Privacy (DP) [DMNS06, DKM* 06]). A randomized algorithm A taking as input a dataset is (e, 8) - private ((e, 6)-DP or approximate-DP) ffr any two neigh- boring dalasets D and D', and for any subset S of oulputs of A, it holds that Pr[A(D) E S] < ef -rr(A(D') E S] + 5. If = 0, then A is e-differentially private (e-DP or pure-DP).
A dataset in our setting consists of n users, where user receives a sequence of m samples (ri. ..yyi........ (otn ymm) drawn i.idd from D. Similar the standard PAC setting [Val84], the al- gorithm A takes in the dataset and outputs a hypothesis f. We say that it is an (a, acccurate learner if (fr < a with probability 1 8 (where a, E (0,1) are parameters); here, errp(f) = ('(a.,)~D([(() # v). We use time(A) A) to denote the running time of A. If A is random- ized, sometimes we use the notation A(:r) to explicitly call out the (public) randomness r it might use.
When each user holds exactly a single example (i.e., m = 1). we call this the item-level setting. We show results in both the (usual) central and local models of DP.
All missing proofs are in the Supplementary Material.
2.1 Correlated Sampling
Definition 7 (Correlated Sampling), A correlated sampling strategy for a set Q with multiplicative error K is an algorithm CS Aa x R' Ω2 and distribution R' on random strings such that
(Marginal Correctness) For all P E An and w 2 Pr (C) (Error Guarantee) For P, Q E Ån, Pr (CS(P;r') $x
5x.
Theorem ([Bro97, KTO2, Hol07J). For any finite set Q there exists a correlated sampling strategy for Ω with multiplicatiie error 2.
2.2 Representation Dimension
The size of hypothesis class H is defined as size(H) := log [H]. and the size of distribution H of hypothesis classes is defined as size(H)) := maxp()) size( (f).
Definition 9 (Probabilistic Representation Dimension [BNS19al)- A distribution H on 2x is said to (a, 3) probbbbbbiillstically represent a concept class C for every every f E C and for every distribution D on X, with probubility 1 - 3 over H ~ H, there exists h E H such that PTzeD (xx) + h(x]] S a.
The (a, ()) probabiiiistic representation dimension of a concept class C is defined as
PRDim,, ==
min
size H.).
H that (a.,8)-probahiin probabiliticcll represents
We use PRDim(C) C*) as a shorthand for PRDim1 (CC) Lemma 10 ([BNS19a)). For every concept class C and a, 3 > O, we have
PRDim (C) < O (log(1/a)) (at////)))PDDm(((((( + log log log(1 /a) + log log(1/3)))
For a concept class C, let LDim(C) denote its Littlestone dimension [Lit87].
2.3 Tools from DP
In the selection problem, each user i receives an element u; from a universe U. For each u E U, define c, : Ki E [n] u, = w.}. The goal is to output u* such that cu- maxnet Cu - or when the output satisfies this with probability 1 - B, the algorithm is said to be (a, aaaauuraeeeeee Lemma 11 (Approximate-DP Selection [KKMN09, BNS19b]). There is an (E,8)-DP (((og(1/88//) 0) -cccurate algoritium for the selection problem in the central model. Moreover, the algorithm runs poly(n log (U]) time.
'A DP algorithm the local model consists randomizer whose input the samples held by one user and whose output is a sequence of messages, and an analyzer. whose input is the concatenation of the messages from all the randomizers and whose output is the output of the algorithm. An algorithm is DP in the local model if for any dataset, the concatenation of the outputs of all the randomizers is DP.
5

---

The following pure-DP histogram algorithm in the central model follows from the exponential mech- anism [MT07]. While trivial implementation would result rumning time that depends linearly on [0' it is not hard to see that we can first toss a coin to determine whether the output would come from the input set. If so, the sampling can be done in O(n) () time; if not, one can randomly output one of the remaining candidates in U, which only requires time Oloog UT). This yields the following.
Lemma 12 (Pure-DP Selection [MT07]). There is E-DP (O(lo((U11/8)e -accuratee al- gorithm for the selection problem in the central model. Moreover, the algorithm runs in poly(n, log (U]) time.
The next guarantee follows from the heavy-hitters algorithm of Bassily et al. [BNSTI7]:
Lemma 13 (Pure-DP Histogram in the Local Model [[PK14]). There is an E-DP (o VVnloo((U1////// ,3) -accurate algorithm for the histogram problem in the local model. Furthermore, the algorithm runs in poly(n, log Ul) time.
3 Global Stability and Pseudo-Global Stability
We recall the notion of global stability of Bun al. [BLM20] and generalize it in ways.
Definition 14 (Global Stability (BLM20]). A learner A said be m-sample a-accurate 7-globally stable if there exists hypothesis h (depending on D) such that err S a and Pr(m)))) (f.. M.. >D (((11 y1)..... ., (Ims 3m ) h] 2 17.
We now present the first generalization. Let R be distribution of random strings.
Definition 15 (Pseudo-Global Stability). learner A is said to be m-sample (a, Ja-curretee (17, v)- pseudo-globally stable if there exists hypothesis hy for every E supp(RR) (depending on D) such that PIy~R jerro (h,) S a] 3 and
Pr R
Pr
[A((21, (Im. r) = hr 2 2
(1
Nm (Fm. (mm.
We also generalize global stability in slightly different manner, in order capture the guarantees of [GGKM21].
Definition 16 (List Global Stability). A learner A is said to be m-sample a-accurate (L, 1)) globally stable if A outpuss set of at most T. hypotheses and there exists hypothesis h (depending on D) such that Pr Pr(gu..).... Rm IDD (h E A((21, (11,,1),..... (Im Dm Dm))) 2 v) and err S a.
3.1 Learners with Global Stability
Bun et al. [BLM20] give globally stable learner in terms of the Littlestone dimension:
Theorem 17 ([BLM20J). Let > 0 and C' be any concept class with LDim(C) d. Then, there exists a (20(d) /a)) a-accurate 2 - -'d)--gobbllly stable learner for C.
Although not explicitly stated in this manner, the improved result of Ghazi et al. [GGKM21] pro- ceeds by giving a list globally stable learner, where the stability parameter n (11dd). the list size L is 2()/a)00) and the sample complexity is (d)))0(1)
Theorem 18 ([GGKM21J). Let a > 0 and C be any concept class with LDim(C) = d. Then, there is a (d/o) (1)) ((1) -ample a-accurate (exp (Id/a)oni) (2(1dd) -list globally stable learner for C.
We will need a slight strengthening of the above result, where there is another parameter <> 0 and want ensure that every hypothesis in the output list has error most 2a. This is stated below. Lemma 19. Let a, > and C be any concept class with LDim(C) 2((1/)) -list globally stable learner for C such that with probability 1 - every hypothesis h'' in the output list satisfies arrp(h) < 2a.
Then, there is
(d log(1 (olo((1/)/o))))
a-accurate (exp ((d/a) 011)) ,

---

Proof Sketch. This can be done by first running the algorithm in Theorem 18 to get a set H of size at most L = cxp (d/a) Then, we draw additional 100 log(L/S)/a² samples S. Finally, we output H' [h' H crrs(h') - 1.5a). By the Chernoff bound, with probability 1 1-Ç, every hypothesis h E H satisfies errp(h') (ersh)")eerrr))))))
(hr) s 0.5a, which yields the desired guarantees. O
4 Approximate-DP Learner
In this section, prove Theorem 1. We first show how to go from list global stability to pseudo- global stability using correlated sampling (Theorem 20). We then show how to go from pseudo- global stability an approximate-DP learner using DP selection (Theorem 25).
4.1 From List Global Stability to Pseudo-Global Stability
Theorem 20. Let a,,3, E (0,0.1), E N, and C a concept class. Suppose that there exists learner A that is m-sample o: a/2-accurate ())ss) globally stable. Furthermore, with probability
every hypothesis h/ the output list satisfies errD(h') S a. Then, there exists a learner A' that is -samlle (a, Ba-accuraeee (1 -1-B8 3, m' Og (m (L/n)/rr²)
1 3n2 (og-)og(L//))
ppseudo-globally stable, where
Before we prove Theorem 20, we note that with Lemma 19, gives the following corollary.
Corollary 21. Let a E Ryo and C' be any concept class with finite LDim(C). Then, there exists learner A that is m-sample (a, 3a-cuuraeeee and (1 3, 1 -)-peudo -as---s-ulouaaatlee globally stable, where m Os((Diim())/aa00))
Proof of Theorem 20. Let 0.57, 10 log(L/((rr) ki 10 Iog(L/(3r)) and li2 3 Log[///18)
Let CS be correlated sampling strategy for 2 and let R' be the (public) randomness uses, in Theorem Algorithm I presents our learner A'.
Algorithm Pseudo-Globally Stable Learner A'.
for i = 1....,,,, hi do Draw S; Dm run A S; to get set H;
Let H be the set of all f E 2 that appears in at least T k2 of the sets H1.... H
for j =1=1 =1....,k ., do
Draw ~ D'H run A on T3 to get set G3
for do
Let QH.GG.....G
(h) = Иग{[ta]bЕE;;}|
Let PH........
be the probability distribution on 2 defined by
exply: Cng (b))
if E H, otherwise.
PH.,o.... (h)
Ewen exp(x Qa, (1/))
Output CS(PH (P.........GiTT).. where r' R!
Notice that the number of samples used in is m (ki + k2) = m Oz(log(((/n))))) as claimed.
(Accuracy Analysis) Since we assume that the output of A consists only of hypotheses with dis- tributional error at most with probability 1 B/ki, union bound implies that this holds for all hypotheses in H with probability 1 - B. This yields the desired (a, 3)accurayyy of the algorithm.
(Pseudo-Glode Global Stability Analysis) For this, need few additional notation. First, for every 2-X we let Q(h) denote Prswpm E A(S)). Moreover, let H21.17 {h E 2x Q(h) 2 1.17] and similarly Hz0.97 {h 2x Q(h) 2 0.9r). crucial property we will use is that H is w.h.p. sandwiched between H H2111 and H 20.9. .r. as stated below.

---

Lemma 22. Let & denote the event that H21.11 S CHC H20.9r. Then,
Pr(6)] 1 32 /30,
where the probability is over the randomness of S1, ........ Sk, and that of on these datasets.
Proof of Lemma 22. We will separately argue that Pr[H21.1r g H] S 8 and Pr[H g H H2 - /²/ /60. union bound then yields the claimed statement.
To prove the first bound, observe that since A outputs a set of size at most T,, H2 > (1((117)
T//T. Consider each f E H>1.17: notice that I H. is simply i.i.d. Bernoulli random variable with success probability Q()) 2 1.17. Hence, by the Hoeffding inequality, we have
Pr[f & μI] S exp (-0.027 k1) 0.00132T/L,
where the last inequality follows from choice of k1- Taking union bound over all f H21ir concludes our proof for the first inequality.
For the second inequality, consider the set Ho : 2*x H20.9r. Since each element E He0.9r satisfies Q()) < 0.9r, we may partition" He0.9r into H 20,9 U... U H such that EsEH Q() < 0.97 for all j E [q] and S T./(0.457) + 41//T. T. Fix j E [4]; notice that
Pr(H H <0.9r + 0] S Prilie [k]] A& H <0.9r + 0} 2 rka).
Now, each 1[H1 n THe 2..9 + 0] is i.d. Bernoulli random variable with success probability at most EjEHLon Q() < 0.9r. Thus, we can apply the Hoeffding inequality to conclude that
Pr[H n H2o.or 0 exp(-0.027*k)) 0.001357/L.
Taking a union bound over all j E [q]. we have Pr[H n H * 0] < 0..0133. This completes our proof of the second inequality.
Next, let P be the probability distribution on 2 defined by
exP()-Q1)) E Eyenzos exp(T-QUP))
if H20.9
P())
otherwise.
Furthermore, let PH be the probability distribution on 2 defined by
exp(x-Q(f)) E Men exp(y-Q(P")
if E H, otherwise.
Pa(f)
Once again, notice that P is independent of the run of the algorithm (i.e., it only depends on A), whereas Pa can vary on different runs, depending on H. Our first component of the proof is to argue that P and Pa are often close:
Lemma 23. When & holds, we have (P, S 32/30.
Proof of Lemma 23. Recall that from the assumption of list global stability, there exists h such that Q(h) 2 n 2r. When & holds, Hl is subset of 11 20.977 meaning that PH the conditional probability of P on H. Thus, we have
dev < P(H Hz0.97) = EsEHso0r /n exp(y Q(f)) (a) EieH M.r.. exp(7-Q(f)
Evetzoor exply Q(f))) v EreHzo exp(7-Q(f)) Q(f)))
EjeHsone (o exply 1.17)
|120001 exp(p- 1.17)
EpeNzoo. exp(p. Q(())
exp(7.Q(1)) Q(h))
(8) $ H20.97 exp(-x 0.97) S L/(0.97) exp((y- 0.97) S 82/30,
(0)
where inequality (a) follows from H>111 C (which in turns holds because of 8), inequality (b)
follows since (h) 2 2T, and inequality (c) follows from our choice of
A simple is to start with singleton partition and then merge any two parts whose total Q(-) is less than 0.9r: in the end, will left with partition where all but most part has weight least 0.457.

---

Next, we show that PH is often close to its "empirical" version PH PH.GI....Gry'
Lemma 24. Eld PH.GG....Grr. S / where the probability is over the randomness of Ti..... Tk2 and that of A's executions on these datasets.
Proof of Lemma 24. From how H is selected and from the assumption that the output of A has size at most L,, we have |H] S L./r. Now, fix S E H. Note that QH.G.....GG. (f) is simply an average of 22 i.i.d Bernoulli random variables with success probability Q(f). Using the Hoeffding inequality,
log(LL(r())
g
Pr
QH. Gr. (...C........
- > 1
k2
60
(L/T)
By a union bound over all f E H. we can conclude that with probability - /2 we have Gr, (n2 Q()1 S / (P H...I....GG...
log( [og(LL((3)) for all f E H. When this holds, we have
hg
(P..G.....GGr (h) PH (h)
-1)}
Σ PH(h)) (h)
max
O,
hgh
log(L/(TT))
log( (og(L/(TB))
Σ Pn(h)-
exp
7. 7-100
1
I exp
7-10
1/2
h2
hEh
log log(L/(TB))
2
/60, from our choice of lzz-
1:2
Combining Lemmas 22 to 24, we can conclude that Eldrv (P, PH. PH.......G..) )1 I B2/100 where the expectation is over the randomness involved in the algorithm except Now, let It, CS(P:r)). From the error guarantee of correlated sampling in Theorem 8, we conclude that
Pr M'RR' S1R',S1-- St,....,e Ti..... Tee
(S1, (........ Sky T1..... Tkyir * hrd 82/5.
Thus, applying Markov inequality, we get the pseudo-globe stability
Pr R'R
Pr
IA Sk, Ti...... Tkgir') had 2 1 B 2 1 B.
S
The
4.2 From Pseudo-Global Stability to Approximate-DP Learner in the Central Model
In this section we prove Theorem 25 that allows us convert any sseudo-globally stable learner to an approximate- DP learner. Combining Theorem 25 and Corollary 21 yields Theorem 1.
Theorem 25. Let a,, B E (0, 0.1) and C concept class. Suppose that there exists a learner A that is m-sample (a,, /accurree (0.9, e E (0, 1), there is an (e, 6DP (ax, 3)-cccurate learner for the central model that re- quires O (log(1(683))/5 users where each user has samples. The learner runs in time (tlyetmme n.d).
pseudo-globally stable. Then, for any
Proof. Let K log (1/(6))) /a where K is a sufficiently large constant. Let R denote the public randomness shared between the users. Algorithm shows our approximate-DP learner.
Algorithm 2 Approximate- Learner in the Central Model.
User randomly draws m samples 5; ~ D and runs A(S;; r) obtain a hypothesis h; Run the (c, 5)-DP selection algorithm from Lemma 11 where U = 2 and user i's item is hyg Return the output h from the previous step
clear that Algorithm 2 (c, 5)-D. We will now analyze its accuracy. First, from the definition of pseudo-global stability and union bound, with probability - 2,8/3 over r R, there exists h,

---

such that elTp(h,) I a, and Prs-pm (A(S:)) = h,] 2 0.9. Conditioned on this, we can use the Hoeffding inequality to conclude that, with probability 3/6, we have"
Ch 2 0.8m.
(2)
Conditioned on (2), Lemma 11 guarantees that c* 2 maX - -..1n with probability 1 3/6 (for sufficiently large K); when this the case, Algorithm 2 outputs h- hy. Hence, applying union bound (over this and (2)), we can conclude that the algorithm is (a, -accuurae as desired. [
5 Conclusions and Future Directions
In this work, we study the question of learning with user-level DP when each user may have many examples. We prove tight upper and lower bounds on the number of users required to learn each concept class, provided that each user has sufficiently many i.i.d. samples. An immediate open question here is whether one can also derive a tight bound on the number of samples per users required; note that this bound will depend on the number of users. For approximate-DP learn- ing, this problem might be hard because the big gap in the item-level learning setting between (oly(LDim) [GGKM21] and (logg" LDim) [ALMM19]) is still open. The pure-DP case might be easier since tight bounds are known both in the central [BNS19a] and the local models (up to polynomial factor) [KLN+ 11].
Another interesting direction is to derive additional efficient user-level DP learners whose sample complexities are better than item-level DP learners. We give "weak" examples of this in Ap- pendix B for the case of the non-interactive local model. would be good to give such an example for general algorithms in the local model as well. On this front, PARITY seems to be good candi- date; as stated earlier, it has SQ dimension 20(d) [BFJ* 94] meaning that it requires 20()) samples in the (interactive) item-level local model [KLN 11]. Can we come up with an efficient user-level DP algorithm in the local model that requires poly(d) samples in total?
Furthermore, our algorithms make extensive use of shared randomness- in the form of correlated sampling. Is this necessary? In particular,
Is there local user-level DP algorithm for learning any class C using poly poly(P)iim(())
users each having poly(PRDD (PRDii(( samples, without using public randomness? In other words, can the use of public randomness be removed from Theorem 2?
Is there an 17- --globblly stable learner for any class C' with finite Littlestone dimension where 17 0 is some absolute constant? In other words, can the use of public randomness be removed from Corollary 21?
While it is not hard to show that the second question has negative answer if require 1 1/2, we are not aware of a proof that v) must go to zero for some family of concept classes.
Lastly, it would also be interesting to whether techniques employed in our paper may be useful beyond the PAC setting. For example, Golowich [Gol21] gives DP regression algorithms based on stability notions similar to [BLM20, GGKM21J and it is plausible that our approach gives user-level regression algorithm in a setting similar to [Gol21].
Acknowledgement
We thank Jessica Sorrell for pointing us to [ILPS21] and explaining the main results of that paper.
References
[Abo18] John M Abowd. The US Census Bureau adopts differential privacy. In KDD, pages 2867-2867, 2018.
[ACG+16 16) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS, pages 308-318, 2016.
RRcall that ca K(i E [n] hu [t)l is as defined in Section 2.3.
10

---

[AKMV19] Kareem Amin, Alex Kulesza, Andres Munoz, and Sergei Vassilvtiski.. Bounding user contributions: bias- trade-off in differential privacy. In ICML, pages 263- 2019.
[ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite Littlestone dimension. In STOC, pages 852-860) 2019.
[AMR* 19] Sean Augenstein, H Brendan McMahan, Daniel Ramage, Swaroop Ramaswany, Peter Kairouz, Mingqing Chen, Rajiv Mathews, al. Generative models for effective ML on private, decentralized datasets. In ICLR. 2019.
[App17] Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 2017.
[BBGN20] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Private summation in the multi-message shuffle model. In CCS, pages 657-676, 2020.
[BC20] Victor Balcer and Albert Cheu. Separating local shuffled differential privacy via histograms. In ITC, pages 1:1-1:14, 2020.
[BEM 17] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnés, and Bernhard Seefeld. Prochlo:
Strong privacy for analytics in the crowd. In SOSP, pages 441-459, 2017.
[BF]+94] Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In STOC, pages 253-262, 1994.
[BLM20] Mark Bun. Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In FOCS, pages 389-402, 2020.
[BNS19a] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of pure private learners. JMLR, 20:146:1-146:3: 2019.
[BNS19b] Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning multiple concepts. JMLR, 20:94:1-94:34 2019.
[BNST17] Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Guha Thakurta. Practical locally private heavy hitters. In NeurlPS, pages 2288-2296, 2017.
[Bro] Daniel G. Brown. How wasted too long finding a concentration inequality for sums of geometric variables. Available at https: //cs. wwaterloo. ca/bbroongg/eegbi.. pdf.
[Bro97] Andrei Z. Broder. On the resemblance and containment of documents. In SE- QUENCES, pages 21-29, 1997.
[Cha02) Moses S Charikar. Similarity estimation techniques from rounding algorithms. In STOC, pages 380-388, 2002.
[CMS11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. JMLR, 12(3), 2011.
[CSU+19] 19] Albert Cheu, Adam D. Smith, Jonathan Ullman. David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In EUROCRYPT, pages 473, 2019.
[CZ21] Albert Cheu and Maxim Zhilyaev. Differentially private histograms in the shuffle model from fake users. CoRR, abs/2104.02733) 2021.
[DF19] Amit Daniely and Vitaly Feldman. Locally private learning without interaction requires separation. In NewrIPS, pages 14975-14986. 2019.
[DJW13] John C Duchi, Michael Jordan, and Martin Wainwright. Local privacy and statistical minimax rates. In FOCS, pages 429-438, 2013.

---

[DKM 06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486-503, 2006.
[DKY17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data pri- vately. In NeurlPS, pages 3571-3580, 2017.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found, Trends Theor. Comput. Sci., 933-4)(211 1-407, 2014.
[DV88] John Dunagan and Santosh S. Vempala. A simple polynomial-time rescaling algorithm for solving linear programs. Math. Program., 14(1):101-114, 2008
[HFM+19) 19] Úlfar Frlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity, In SODA, pages 2468-2479 2019.
[EFM 20] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation. CoRR, abs/2001 0061100010,618,,, 2020.
[EMM+20] Alessandro Epasto, Mohammad Mahdian, Jieming Mao, Vahab Minrokni, and Lijie Ren. Smoothly bounding user contributions in differential privacy. NeurlPS, 2020.
[EPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized ag- gregatable privacy-preserving ordinal response. In CCS, pages 1054-1067, 2014.
[GGK+20] Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Pure differentially private summation from anonymous messages. ITC, 2020.
[GGK+21] Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. On the power of multiple anonymous messages: Frequency estimation and selection the shuffle model of differential privacy. In EUROCRYPT, pages 463-488, 2021.
[GGKM21] Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper PAC learning with approximate differential privacy. In STOC, 2021.
[GKM+21] Badih Ghazi, Ravi Kumar,
Pasin Manurangsi, Rasmus Pagh, and Amer Sinha. Differ- entially private aggregation in the shuffle model: Almost central accuracy in almost single message. In ICMI., pages 3692-3701, 2021.
[GKMP20] Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Rasmus Pagh. Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead. In ICML, pages 3505-3514, 2020.
[GKMP21] Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Rasmus Pagh. Private counting from anonymous messages: Near-optimal accuracy with vanishing communication over- head. CoRR, abs/2106.04244 2021. This version contains a correction of calculation eπrrrs in Theorem 13 of [GKMP20].
[GMPV20] Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Private aggre- gation from fewer anonymous messages. In EUROCRYPT, pages 798-827, 2020.
[Gol21] Noah Golowich. Differentially private nonparametric regression under a growth con- dition. In COLT, pages 2149-2192, 2021.
[Gre16] Andy Greenberg. Apple's "differential privacy" is about collecting your data but not your data. Wired, June, 13, 2016.
12

---

[Hol07] Thomas Holenstein. Parallel repetition: simplifications and the no-signaling case. In STOC, pages 411 411-419, 2007.
[HTI0] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, pages 705-714, 2010.
[ILPS21] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. 2021.
[Kea98] Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. JACM, 45(6)998-11066 1998.
[KKMN09) Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In WWW, pages 171-180, 2009.
[KLN+11] 11] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SICOMP, 40(3):733-826, 2011.
[KMA + 19] Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Ben- nis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et Advances and open problems in federated learning. arXiv:19/2.04977, 2019.
[KNRS13] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing graphs with node differential privacy. In TCC, pages 457-476, 2013.
[KT02] Jon M. Kleinberg and Eiva Tardos. Approximation algorithms for classification prob- lems with pairwise relationships: metric labeling and Markov random fields. JACM, 49(5):616-639, 2002.
[Lit87] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear- threshold algorithm. In FOCS, pages 68-77 1987.
[LSA + 21] Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. In NeurlPS, 2021.
[LSY+20] Yuhan Liu, Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and Michael Riley. Learning discrete distributions: user vs item-level privacy. In NeurlPS, 2020.
[MRTZ18] H Brendan McMahan. Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differ- entially private recurrent language models. ICLR, 2018.
[MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pages 94-103, 2007.
[Riv87] Ronald L. Rivest. Learning decision lists. Mach. Learn., 2(3):229-246, 1987.
[Sha14] Stephen Shankland. How Google tricks itself to protect Chrome user privacy. CNET, October, 2014.
[Vad17] Salil P. Vadhan. The complexity of differential privacy. Tutorials on the Foundations of Cryptography, pages 347-450. Springer International Publishing, 2017.
[Va184] Leslie G. Valiant. A theory of the learnable. CACM, 27(11):1134-112 1984.
[War65] Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. JASA, 60(309):63-69, 1965.
[WSZ+19] 19] Zhibo Wang, Mengkai Song. Zhifei Zhang, Yang Song, Qian Wang, and Hairong Qi. Beyond inferring class representatives: User-level privacy leakage from federated learning. In INFOCOMM, pages 2512 2520, 2019.
[WZL++0]] Royce Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Hommons-Marenge and Bryant Gipson. Differentially private SQL with bounded user contribution. PoPETS, 2:230-250, 2020.
13


Reviews:
[{"review_id": "g42AQk7t2wq", "reviewer": "Reviewer_xkiJ", "summary": "This paper studies user-level privacy for any privately PAC learnable class in the setting where each user holds more than one training example. It first shows that for any online learnable class (with finite Littlestone dimension), it's possible to learn the class with an (\\eps,\\delta)-DP algorithm using only O(\\log(1/\\delta)/\\eps) users. Then it gives sample complexity of a generic \\eps-DP learner in both the local and the central models. Finally, it shows that we can take any efficient SQ algorithm and turn it into an efficient learner in the user-level setting. The protocols are based on a novel connection between correlated sampling and DP learning.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a well-written paper. I enjoy reading it. Protecting user-level privacy has raised much attention recently, and it's timely research. I particularly like the idea of exploiting the shared randomness between users, which is handled by using correlated sampling. It's nontrivial to connect the correlated sampling technique with DP learning. The theoretical results and algorithms are sound. My only question is in Algorithm 1, how do you select A? Can it be any learners satisfying that A's output consists only of hypotheses with (\\alpha, \\beta/k)-accuracy? \n\nMinor comment: A type in line 35 ``artifically''", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper discussed the limitations and proposed several open questions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "f_CymUEiPMT", "reviewer": "Reviewer_4gym", "summary": "This paper studies user level differential privacy in the setting of PAC learning. They study both central and local model of differential privacy and both approximate and exact differential privacy. In the central model, they show that they only need log(1/\\delta)\\epsilon users and Ldim^O(1) samples per users to guarantee (\\epsilon, \\delta)  differential privacy whereas in the item level DP, one needs Ldim^O(1) samples.  They also provide nearly matching lower bounds on the number of users.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the paper studies an interesting problem of DP guarantees for user level setting in the PAC model. Generally, there is a lot of interest in differentially privacy and it would be of interest to the community. This paper obtains the first bounds in the user level model in PAC setting. It shows an interesting result that we only require users  depending on epsilon, delta for (epsilon, delta) DP independent of the Littlestone dimension and the number of samples depend on the Littlestone dimension. This paper builds on existing connections between global stability and differential privacy and additionally, uses the technique of correlated sampling. This idea of using correlated sampling in this setting seems interesting to me. The paper is mostly well written.\n\nSome questions - \n\n1) I don’t understand the statement in line 35 “One way to understand this problem is to artificially limit the number of training examples contributed by each user.” when the later statement says that DP cost is less when each user has large number of samples.\n2) Is this the first paper studying user level DP in the PAC learning setting?\n3) The authors mention that there is a gap between user level and item level privacy in the local model. What is the relationship between SQ-dim and PRdim? The authors mention that SQ-dim can be bigger. Is it always lower bounded by PRdim?\n4) Is there any general connection or relationship that one can obtain between the user level and item level bounds?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "SWBICvNTe36", "reviewer": "Reviewer_kC68", "summary": "This work tackles the problem of PAC learning with user-level privacy guarantees. The paper's primary contribution is a nearly tight characterisation of the number of users required when the learning is via an 1) $\\epsilon$-DP and 2) $(\\epsilon,\\delta)$-DP algorithm. At the core of the paper is the idea that users can share randomness before the sampling stage. This insight allows for the learnability of all online learnable classes, with much fewer users(exponentially fewer in terms of $d$).", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is quite well written. The work presents a creative and original connection between correlated sampling and DP learning. The implications of the assumption are explored in-depth. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately discussed the limitations and the societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "BfcAFyC_3U1", "reviewer": "Reviewer_R7Bc", "summary": "The setting in the paper is PAC learning with user-level DP, where the main difference from previous works is that each user may have many examples (instead of only a single example).\nThe main result is that it is possible to learn [(epsilon,delta)-DP] with a small number of users as long as each user has sufficiently many samples.\nAnother main result is epsilon-DP learner in the local model.\nMoreover, the authors provide nearly matching lower bounds. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Significance: It seems like the paper discusses some fundamental questions in Learning with DP guarantees. The results are significant and interesting.\nIt seems like the techniques introduced in the paper might be of independent interest.\nIt is hard for me to fully understand the motivation of this setting, due to some lack of knowledge of previous results.\n\nClarity and relation to prior work: The paper is very clear and easy to follow. Also, the literature review is thorough.\n\nIt was quite hard for me to check some proofs, due to lack of previous technical background. \nI tend to accept the paper, but I will keep my confidence low.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "1BHFDj5YrW_", "reviewer": "Reviewer_R9c6", "summary": "Given a dataset consisting of $n$ users, where each user $i$ has a sequence $(x^i_1, y^i_1), \\ldots, (x^i_m, y^i_m)$ of $m$ samples, the goal of this paper is to investigate differentially private learning in three settings: central-pure ($\\epsilon$-DP), central-approximate (($\\epsilon, \\delta$)-DP), and local-pure.\n\nUsing results on correlated sampling, global stability, and private selection algorithms, the authors built efficient algorithms for the three above-mentioned settings. The key idea is to have each user first \"learn\" insights from their $m$ samples (and obtain a local hypothesis candidate), and then use DP selection algorithm (e.g., the Exponential Mechanism) to find the best hypothesis. Finally, the authors give lower bounds for the three DP models.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think the authors made a great contribution towards the problem of differentially private learning where each user has $m$ samples. I like the comprehensive results and the systematic investigation of the problem. \n\n\nSome (minor) issues:\n- Practicality: while from a theoretical point of view, the paper made significant contribution, it is unclear to me how practical the algorithms are. For example, how to learn a hypothesis from samples, how to encode hypotheses into the DP selection algorithms. It would be great if the authors can explain them more clearly and even provide corresponding code.\n- The relationship between item-level and user-level: in this paper, item-level DP means each user has only one item. But more commonly, item-level DP assumes each user has some number of items, but the definition of neighborhood Is different (only one item is different). I understand that the authors might want to avoid confusion, but this could still confuse those who are familiar with DP. A better way of presentation could be changing item-level and user-level to single-value setting and multi-value setting, and clarifying the difference between item-level and user-level protection (e.g., in the graph setting, item-level definition protects the existence of an edge, while user-level definition protects the existence of a node). \n- Theorems 2 and 3 both mention the local model: Theorem 3 should be in the central model?\n- SQ is not spelled out.\n\n\nDisclaimer: I am outside of the NeurIPS community and haven't read a lot NeurIPS papers. This paper is a clear acceptance for me, but I cannot rank it among other papers.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A: In Checklist, the authors said they describe the limitations in Section 5; but Section 5 only includes conclusions and several open questions for future work. The authors did not mark any potential negative societal impacts.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers greatly appreciate the significance and novelty of this work, with some minor issues raised. For example, 
- making the statement of some theorems more clear, 
- motivating this work better, 
- explaining the practicality, 

and so on. Please try the best to address these issues in the final version
Decision: Accept (Poster)