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)- DP algorithm using only
users. For e-DP algorithms, we show 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 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((1/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 pscudo-globall 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-showee
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.vi),.. ..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([(x) # 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.,0)-probahiin probabiliticcll represents
We use PRDim(C) C*) as a shorthand for PRDim1 (C)) 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 arr((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)"))errr))))))
(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 31 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 à 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-glouaaatlee globally stable, where m Os((Dimm())/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....GG
(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 r, 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}1 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 way 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....Guy'
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 Gre (n2 Q()) S / (P H.G.I....GG...
log( [og(LL((3)) for all f E H. When this holds, we have
hg
(P..G.....GG, (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 pseudo-glo geuudoglobblly 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- --globbllyy 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))98-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": "VoYlCk2qTSb", "reviewer": "Reviewer_ZiPC", "summary": "The authors show that any online learnable class can be learned with an epsilon delta DP algorithm using only O(log(1/delta)/epsilon) users as long as each user has enough samples. They show that there exists pure DP algorithm to learn any concept class that has finite probabilistic representation dimension in the local (public randomness) model. They also show that the bound can be improved w.r.t. the number of users in the central model of DP. They also show a lower bound on the number of users there must be for an accurate DP learning to exist. Finally, they show that Statistical Query algorithms can be turned into efficient learners.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "Unfortunately I was not really qualified to review this paper, so I can not provide feedback on almost anything. What I could understand is that by generalizing the definition of global stability one can use public randomness to create private mechanisms to learn certain classes of hypothesis. So this work seems novel. I'm giving an accept but will have to trust the other reviewers on this one. My apologies.\n\nMinor:\n\nLine 53: what is \\alpha?\n\nIs Theorem 3 in page 2 stated correctly? Line 74 mentioned the central model but line 76 mentions the local model.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "6G5tv7WbyeM", "reviewer": "Reviewer_5d6f", "summary": "This work considers the learnability problem under user-level differential privacy. The authors demonstrate that for any privately PAC learnable class, user-level DP algorithms require much fewer users compared to the item-level counterpart, as long as each user has sufficient samples. The main technique is a correlated sampling strategy that relies on a new generalization of global stability.", "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": "Strength:\nThis work gives a new understanding of learnability under user-level DP with strong results on the number of users needed to learn a concept class given sufficient samples per user. For approximate DP, the number of users only depends on the privacy and accuracy parameters. For pure DP in both the central and local model, nearly tight bounds on the number of users are obtained (the bound is tight for the central model). This work demonstrates a gap between $(\\epsilon, \\delta)$-DP and pure DP algorithms (including LDP), and also between user-level and item-level privacy. \n\nWeakness:\nThe main question is that this work assumes that the number of samples of each user is sufficiently large ($poly(d/\\alpha)$ where $d$ is Littlestone or probabilistic representation dimension). I think the result would be more interesting if we could characterize learnability when the number of samples per user is fixed.", "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": "4"}, "extra_text": {}}, {"review_id": "4Edl97ex99h", "reviewer": "Reviewer_Wgf7", "summary": "This paper considers the problem of private PAC learning in the setting of user-level privacy, that is, each user may have $m \\ge 1$ samples. The authors consider three possible settings 1. approximate $(\\varepsilon,\\delta)$-DP, 2. pure $\\varepsilon$-DP, and 3. Local DP. For each setting they show that in the user-level DP version ($m>1$), private learning needs smaller number of users compared to standard DP with $m=1$, with the caveat that each user is required to have sufficiently many samples (usually polynomial in the dimension $d$ and accuracy). For example, they develop an $(\\varepsilon,\\delta)$-DP algorithm that uses only $O( \\log(1/\\delta)/\\varepsilon)$ users to learn any privately learnable class, where each user must have $m \\ge \\text{poly}(d)$ samples ($d$ is the Littlestone dimension of the class). They also provide tight lower bounds on the number of required 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": "The paper considers an interesting problem and makes significant theoretical contributions. However, I have two main comments\\concerns regarding this paper:\n\n1. Motivation: as the authors mention in the intro, their main motivation for studying this problem is its relevance to the federated learning (FL) setting where each user contributes multiple samples. However, the setting of this paper is different than the standard FL setting in two ways:\n\n      1.1 The number of users $n$ is (relatively) small while the number of samples per user $m$ can be too large (polynomial in dimension), in contrast to standard FL setting where $n$ is large and $m$ is smaller.  Currently, all of the algorithms in the paper crucially build on having large $m$ (to accurately estimate the hypothesis distribution), hence new techniques will probably be needed for the more relevant setting where $m$ is small. Moreover, in the setting of the paper, usually the number of samples per user $m$ is large enough that each user can learn on their own without using other users' data. It is therefore important to first highlight this in the paper and motivate this setting (which is different that the standard setting in FL in practice).\n       \n      1.2 I.I.D. samples: the authors assume all of the users have IID samples from the same distribution. I wonder whether these results can be extended to the heterogeneous setting where users have similar distributions (which is more relevant in FL).\n\nIt is therefore important that the authors motivate the setting where their theoretical results are obtained and explain its relevance.\n\n2. Clarity: overall the paper is well-written, especially the intro where the authors clearly explain the problem and their main contributions. However, I think the technical sections need more work and organization to make the important ideas more visible. I suggest a few edits which can help for the reader:\n\n      2.1 The proof of section 4.1 (from list-stability to pseudo-stability) includes many unnecessary lemmas that only include technical mathematical analysis (Lemmas 22-24). I suggest moving all of these to the appendix and instead adding a new lemma that has the consequence of these three lemmas: the distribution $\\hat P_{H,G_1,\\dots,G_k}$ is close to $P$. This lemma is more meaningful and gives some intuition for the design of the algorithm. Moreover, the proof becomes much more intuitive and easier to understand.\n\n     2.2 Sections 2 and 3 include many definitions and lemmas which makes it extremely hard to read. Some parts of it are also used only at the end of the paper, making it challenging to recall some of the definitions. For example, it took me some time to find the definition of $c_h$ in equation $(2)$. It may be useful to reorganize these two section and maybe delay some of the definitions to the sections where they are used.\n\n     2.3 It may be useful to start with the transformation from pseudo-stability to approximate DP of section 4.2 (instead of 4.1) as it's simple and gives a nice motivation for the definition of pseudo-stability.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "-i36Tm3Y2al", "reviewer": "Reviewer_wvJN", "summary": "This paper studies a setting of differential privacy called user-level differential privacy. In this setting, each user has a set of samples and differential privacy is with respect to the addition or removal of a single user (instead of the classical definition where DP must hold with respect to the addition or removal of a single data point).\n\nThe authors prove a number of results. Their first result is that if a class is online learnable with Littlestone dimension $d$ then it is also $(\\epsilon, \\delta)$-DP learnable with $O(\\log(1/\\delta)/\\epsilon)$ users and roughly $\\text{poly}(d/\\alpha)$ samples per user. The authors then go on to discuss further results using another notion of complexity called probabilistic representation dimension. The aforementioned results are not efficient and the authors give another result that is efficient by showing how an efficient statistic query algorithm can be transformed into an efficient learner in the user-level DP setting.\n\nIn terms of techniques, the authors use correlated sampling and build upon the work of Bun et al. and Ghazi et al. (on the equivalence of online learning and approximate differential privacy). With respect, to their result involving Littlestone dimension, the authors show a reduction from \"list-global stability\" to \"pseudo-global stability\" and then a (simple) reduction from \"pseudo-global stability\". List-global stability means that with high probability, given i.i.d. samples, an algorithm will output a list which contains a particular hypothesis. Using correlated sampling, they show that this can be leveraged to output a fixed hypothesis with high probability (which they call pseudo-global stability). Thus, by having all users share the same randomness, they can ensure that most users return a similar hypothesis with high probability and thereby using an approximate-DP selection algorithm to privately return a hypothesis.", "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": "**Strengths**\\\nThe problem that the authors study is interesting, original, and well-motivated. User-level privacy is a relatively new topic (at least when studied from a theoretical viewpoint). In terms of techniques, the starting point appears to be the techniques of Bun et al. and Ghazi et al. for the equivalent of online learning and approximate differential privacy. However, the current paper builds upon these techniques in a nice and original way.\n\nIn addition, the paper is written quite well. The authors explain their approach clearly and the technical exposition is fairly clear as well.\n\n**Weaknesses**\\\nI do not really have any complaints about the present paper although it would certainly be interesting to see if some of their results can be strengthened (for example, removing shared randomness).\n\n**Target Audience**\\\nThe paper will certainly be of interest to researchers working in the area of differential privacy. I also think that the paper sets up some interesting open problems for future work. For example, it would be interesting to see whether or not correlated sampling is required for their result.\n\n**Minor Comments**\\\n-Lemma 13: Fix paranthesis inside the $(\\cdot, \\cdot)$-accurate. \\\n-Line 283: with probability $1-\\beta^2/60$\\\n-Theorem 25: I believe the $(0.9, \\beta/3)$-pseudo ... should be $(0.9, 1-\\beta/3)$-pseudo...\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of private PAC learning in the setting of user-level privacy, where each user holds several labeled samples. They show that if every user holds sufficiently many samples, then very few users are needed to proved user-level privacy. They also provide lower bounds on the number of required users. The reviewers agree that this is an interesting paper with solid contribution, that should be accepted to NeurIPS.
Decision: Accept (Poster)