User-Level Differential Privacy With Few Examples Per User
Authors: Badih Ghazi
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Raghu Meka
Chiyuan Zhang
Venue: NeurIPS 2023 oral (2023)
Keywords: differential privacy
user-level privacy
PAC learning
TL;DR: We give a generic transformation of any item-level DP algorithm to a user-level DP algorithm, that holds even when each user has only a few examples.

Abstract: Previous work on user-level differential privacy (DP) [Ghazi et al. NeurIPS 2021, Bun et al. STOC 2023] obtained generic algorithms that work for various learning tasks. However, their focus was on the *example-rich* regime, where the users have so many examples that each user could themselves solve the problem. In this work we consider the *example-scarce* regime, where each user has only a few examples, and obtain the following results:
* For approximate-DP, we give a generic transformation of any item-level DP algorithm to a user-level DP algorithm. Roughly speaking, the latter gives a (multiplicative) savings of $O_{\varepsilon,\delta}(\sqrt{m})$ in terms of the number of users required for achieving the same utility, where $m$ is the number of examples per user. This algorithm, while recovering most known bounds for specific problems, also gives new bounds, e.g., for PAC learning. 
* For pure-DP, we present a simple technique for adapting the exponential mechanism [McSherry & Talwar, FOCS 2007] to the user-level setting. This gives new bounds for a variety of tasks, such as private PAC learning, hypothesis selection, and distribution learning. For some of these problems, we show that our bounds are near-optimal.

User-Level Differential Privacy With Few Examples Per User
Badih Ghazi Google Research Mountain View, CA, US badihghazi Brathhghaz@@mmaall... com
Pritish Kamath Google Research Mountain View, CA, US pritish@alum.ne mit edu
Ravi Kumar
Google Research Mountain View, CA, US
ravi.k530gman com
Pasin Manurangsi Google Research Bangkok, Thailand pasinggoogle. com
Raghu Meka UCLA Los Angeles, CA, US raghumêcs ucla. edu
Chiyuan Zhang Google Research
Mountain View, CA, US
chiyuan@google com
Abstract
Previous work user-level differential privacy (DP) [GKM21, BGH obtained generic algorithms that work for various learning tasks. However, their focus was the example-rich regime, where the users have many examples that each user could themselves solve the problem. In this work we consider the example-scarce regime, where each user has only few examples, and obtain the following results:
For approximate- -P, give a generic transformation of any item-level DP algorithm to a user-level DP algorithm. Roughly speaking, the latter gives a (multiplicative) savings of Oc.s( (m) terms of the number of users required for achieving the same utility, where m is the number of examples user. This algorithm, while recovering most known bounds for specific problems, also gives new bounds, e.g., for PAC learning.
For pure-DP, we present a simple technique for adapting the exponential mech- anism [MT07] to the user-level setting. This gives new bounds for variety of tasks, such as private PAC learning, hypothesis selection, and distribution learning. For some of these problems, show that our bounds near-optimal.
Introduction
Differential privacy (DP) [DMNS06, DKM+06] has become a widely popular notion of privacy quantifying model's leakage of personal user information. It has seen a variety of industrial and governmental deployments including [Gre16, App17, DKY17, Abo18, RE19, TM20J. Many fundamental private machine learning algorithms in literature have been devised under the (implicit) assumption that each user only contributes a single example to the training dataset, which we will refer to item-level DP. In practice, each user often provides multiple examples to the training data. In this user-level DP setting, the output of the algorithm required to remain (approximately) statistically indistinguishable even when all the items belonging single user are substituted (formal definitions below). Given such strong (and preferable) privacy requirement, it is highly non-trivial for the algorithm take advantage of the increased number of examples. Several recent studies have explored this question and showed- for wide variety of tasks-that while challenging. this is possible (LSY+ 20, LSA+21, GKM21, ILPS22, 23].
+00
To discuss further, let us define some notation. We use n to denote the number of users and m denote the number of examples per user. We use Z denote the universe of possible samples. We write x = (Ii,1...., L1,m D2,1 T2,1 ,,,.,, In.m) E nm to denote the input to our algorithm, and
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

2; := (a..).... Ti.m) ) for E [n] to denote the ith user's 's examples. Furthermore, we write z- to denote the imput with the ith user's data a; removed. Similarly, for S S [n], we write a x-$ ş to denote the input with all the examples of users in S removed.
Definition (User-Level Neighbors). Two imputs æ, x' are user-level neighbors, denoted by a x x', iff æ=, x'=; for some E [n]].
Definition 2 (User-Level and Item-Level DP). For e, 8 > O, we say that randomized algorithm' A : Z + O is (s, -uuerrleee DP iff, for any æ x x' and any S _ O. we have Pr[A(() E S] s e Pr[A(x' x') E 5] + 6. When m I, we say that & is (e, (.,,0)-tt --iitem-level DP.
The case 5 = 0 is referred to as pure-DP, whereas the case > 0 is referred to as approximate-DP
To formulate statistical tasks studied in our work, we consider the setting where there is unknown distribution D over Z and the input x ~ Dam consists of nm i..d. samples drawn from D. A task T (including the desired accuracy) is defined by V=z(D) which is the set of "correct" answers. For parameter 7 we say that the algorithm & is y-useful if Præ-Dmmm [A(z) E VI(D))] 2 for all valid D. Furthermore, we say that nm is the sample complexity of the algorithm, whereas is its user complexity. For m E N and e, ò > 0, let (e, 5;7) denote the smallest user complexity of any (e, -user-elll DP algorithm that is 7-useful for T. When 7 is not stated, it is assumed to be 2/3.
Generic Algorithms Based on Stability. So far, there have been two main themes of research on user-level DP learning. The first aims provide generic algorithms that work with many tasks. Ghazi et al. [GKM21] observed that any eseudo-globallyy stable (aka reproducible [ILPS22]) algorithm can be turned into user-level DP algorithm. Roughly speaking, pseudo- -loobal stability requires that the algorithm, given a random input dataset and a random string, returns a canonical output- may depend on the random string with large probability (e.g.. 0.5). They then show that the current best generic PAC learning item-level DP algorithms from [GGKM21] (which are based on yet another notion of stability) can be made into ppeudo-globally stable algorithms. This transforms the aforementioned item-level DP algorithms into user-level DP algorithms.
In recent breakthrough, Bun et al. [BGH+23 23] significantly expanded this transformation by showing stable algorithm- -abbeit
that any item-level DP algorithm can be compiled into a with some overhead in the sample complexity. Combining with [GKM21], they then get generic transformation of any item-level DP algorithm to a user-level DP algorithm. Such results are of (roughly) the following form: If there is an item-level DP algorithm for some task with sample complexity n, then there is a user- DP algorithm with user complexity (llo(1/6))e) as long as
m 2 Se. (n²). In other words, if each user has sufficiently many samples, the algorithm needs very few users to learn under the user-level DP constraint. However, the requirement on the number of examples per user can be prohibitive: due to the nature of the reduction, it requires each user to have enough samples to learn by themselves. This leads to the following natural question:?
Is there generic transformation from item-level to user-level DP algorithms for small m.?
Algorithms for Specific Tasks & the / m Savings. Meanwhile, borrowing a page from its item-level DP counterpart, another active research theme has been study specific tasks and provide (tight) upper and lower bounds on their sample complexity for user-level DP. Problems such as mean estimation, stochastic convex optimization (SCO), and discrete distribution learning well-understood under user-level DP (for approximate- DD)); see, e.g., ILSY+ 20, LSA+ NME22, GKK+23]. A pattern has emerged through this line of studies: (the privacy-dependes the user complexity in the user-level DP setting is often roughly 1/ym smaller than that of the item-level DP setting. For example, for the task of discrete distribution learning on domain [k]] up to total variation distance of a > 0 (denoted by DDM(a)), the user complexity for the user-level DP is [DHS15, ASZ21, NME22)
part of)
k
Th DDK(a) = -0s E0 Ea
a2
'For simplicity, we will only consider the case where the output space O is finite throughout this work to avoid measure- theorrrticttereciccceo issues. This assumption is often without loss of generality since even the output in continuous problems can discretized in such way that the "additional error" is negligible.
'Of course, there is a generic transformation where each user throws away all but one example; here, we are looking for one that can reduce the user complexity compared to the item- level setting.

---

We can see that the first privacy-dependee term decreases by factor of vm whereas the latter privacy-independen term decreases by factor m. A similar phenomenon also occurs in the other problems discussed above. As such, it is intriguing to understand this question further:
Is there a common explanation for these vm saving factors for the privacy-dependent term?
1.1 Our Contributions
Approximate-DP. We answer both questions by showing generic way transform any item-level DP algorithm into a user-level DP algorithm such that the latter saves roughly /m in terms of the number of users required. Since the formal expression is quite involved, state below a simplified version, which assumes that the sample complexity can be written as the sum of two terms, the privacy-independent term (i.e., (ggat) and the privacy-dependen term that grows linearly in 1/e and
m This is the most common form of sample complexity of DP learning discovered so far the literature- in particular, this covers all the tasks have discussed previously. The corollary below shows that the privacy-dependen term decreases by a factor of roughly /m whereas the iwwacy-independett term decreases by a factor of m. The full version of the statement
polylogarithmically in 1/6 (i.e.. Tog(1/ (1800)))00))
be found in Theorem 10.
Corollary 3 (Main Theorem Theorem-Simplitee Simplified). Let E be any task and 7 > 0 be a parameter. Suppose that for any sufficiently small e, 6 >> there is an (E, 8)-ttem--eeeel DP algorithm that is "yusefuu for & with sample complexity Ö (1oR(1/881 I + Dynat for some constant Then, for any sufficiently small E, 8 >> O. there exists an (e, 8) -user-eeee DP algorithm that is (y o(1))-useful for T and has user complexity
=
log(1 (18(1/8)--//
log 1/8)
71
priv
71, stat
Our result provides powerful and generic tool in learning with user-level DP, as it can translate any item-level DP bound to user-level DP bound. Specifically, up to polylogarithmic terms and the dependency e, the corollary above recovers all the aforementioned user complexity bounds for mean estimation, SCO, and discrete distribution learning. In addition, also presents new sample complexity bounds for the moderate regime for PAC learning.
While our result is very general, it-perhaps inevitably-comes a cost: the algorithm is computa- tionally inefficient and the dependence on (and 8) is not tight. We discuss this allng with other open questions- in more detail in Section
Pure-DP. Surprisingly, the pure-DP setting is less explored compared to approximate-DD DP in the context of learning with user-level DP; the sample complexity of several of the problems mentioned above (e.g., discrete distribution learning and SCO) is well-understood under approximate-DP DD but not so under pure-DP. While we do not provide generic transformation from item-level DP algorithms to user-level DP algorithms for pure-DP, we give simple modifications of the popular pure-DP exponential mechanism [MT07] that allow be used the user-level DP setting. Consequently, we obtain improved bounds for several problems. Due to space constraints, in the main body of the paper, we will only discuss PAC learning. Results for other problems, such as hypothesis testing and distribution learning can be found in Appendix E.
In PAC learning, Z X {0, 1} and there is a concept class C C {0, 13xt An error of c: Z + {0, 1} w.r.t. D is defined as errp (c) == Pr(z.g)>Dlcc (c(()) * v]. The task PAC(C; is to, for any distribution D that has zero error on some concept e* E C (aka realizable by C), output - {0.1) such that (r))(c) I We give a tight characterization of the
complexity for PAC learning::
Theorem 4. Let C be any concept class with probabilistic representation dimension d (i.e. PRDim(C) = d). Then, for any sufficiently small ox, E > O and for all m E N, we have
PAC(C.))) (e, 5= 0) (
Previous work (GKM21, BGH 223] achieves the tight sample complexity only for large m (*> d²).
PPRDim is defined in Definition 20.
3

---

1.1.1 Technical Overview
In this section, we give rough overview of our proofs. We will be intentionally vague; all definitions and results will be formalized later in the paper.
Approximate- DP. At a high-level, our proof proceeds roughly as follows. First, we show that any (e, 6) -iteem-level DP A with high probability satisfies a local version of user-level DP for which we only compare* A(x=+) for different i, but with that is increased by a factor of roughly y'm (see Definition 16 and Theorem 17). If this were hold not only for x- but also for all user-level neighbors æ' of æ. then we would have been done since the (e. -)-etmm-lee DP algorithm would have also yielded (svm, -u-eser-lee DP (which would then imply a result favor of Corollary 3). However, this is not true in general and is where the second ingredient of our algorithm comes in: We use a propose-test- testres-tss- style algorithm [DL09] to check whether the input is close for which the aforementioned local condition does not hold. If so, then we output 1; otherwise, we run the level DP algorithm. Note that the test passes w.h.p. and thus we get the desired utility.
"bad" input
This second step is similar to recent work of Kohli and Laskowski [KL21] and Ghazi et al. [GKK [GKK+t33,, 23], who used similar algorithm for additive noise mechanisms (namely Laplace and Gaussian mech- anisms). The main difference is that instead of testing for local sensitivity of the function as in [KL.21, GKK + 23], we directly test for the privacy loss of the algorithm A.
As for the first step, we prove this via a connection to a notion of generalization called sample perfect generalization [CLN+ 16] (see Definition 12). Roughly speaking, this notion measures the privacy loss when we run an (e, 5)-item-level DP algorithm on two x, x' drawn independently from D", We show that w.h.p. A(x) R A(x') for e' On (1/8) =). Although ostensibly unrelated to the local version of user-level DP that we discussed above, it turns out that these are indeed related: if we view the algorithm that fixes examples of all but one user, then applying the sample perfect generalization bound on just the input of the last user (which consists of only m samples) shows that the privacy loss when changing the last user is O(v m (og(1/5) /8) e) w.h.p. It turns out that we can turn this argument into formal bound for our local notion of user-level DP (see Section 3.2.1.)
We remark that our results on sample perfect generalization also resolve an open question of Cum- mings et al. [CLN+ 16]; we defer this discussion to Appendix C.I.
Finally, we also note that, while Bun et al. 23] also uses the sample perfect generalization no- tion, their conversion from item-level DP algorithms to user-level DP algorithms require constructing geeudo-globally stable algorithms with sample complexity m. This is impossible when m is small, which is the reason why their reduction works only in the example-rich setting.
Pure-DP. Recall that the exponential mechanism [MT07] works as follows. Suppose there is set H of candidates we would like to select from, together with the scoring functions (scr и Ie where seTH nn - R has sensitivity at most A. 'Tee algorithm then outputs H with probability proportional to exp (-e-werw (1))222)) (z))/2)). The error guarantee of the algorithm scales with the sensitivity A (see Theorem 9.) It is often the case that sCT depends on the sum of individual terms involving each item. Our approach is to clip the contribution from each user so that the sensitivity is small. We show that selecting the clipping threshold appropriately is sufficient obtain new user-level pure-DP (and in some cases optimal) algorithms.
2 Preliminaries
Let [n] = (1....., n). let [x]+ = max(0, x)., and let Ō(f) denote Of log f) for some constant c. Let sApp(A) denote the support of distribution A. We recall some standard tools from DP [Vad17].
For two distributions A, B. let de (A B) Exemupp( [A(x) e- B(x)]+ denote the e eh-hockey stick divergence. For brevity, we write A Re,5 B to denote de || B) & 5 and (B A) < 6.
Lemma ("Triangle Inequality"). If A Re B and B Re,8 C, then A Rete' 8' 8 C.
Lemma 6 (Group Privacy). Let A be any (8, -item-ellell DP algorithm and x. x' be k-neighbors', then ((x) Re 88 A(x') where s' = ke, = ghe _ < k.
'In Theorem 17, we need to compare A. (( s)) for S's of small sizes as well.
'Le., there exists Bo, $1...., 2b x' such that æ;-1, 2; are item-level neighbors for all i [K].

---

Theorem 7 AApliifictionn-by bubssamlngg [BBG18]) Let n' E N be such that n' 2 n. For any (E, --y-itee-leve DP algorithm & with sample complexity n, let ' denote the algorithm with sample complexity n' that randomly chooses oul of the n' input samples and then runs A. on the subsample. Then A (5', -DP where g In n - 1)) = 16 for vj = n/n'.
We also need the definition of the shifted and truncated discrete Laplace distribution:
Definition 8 (Shifted Truncated Discrete Laplace Distribution). For any e, 6 >> 0, let K = k(e, 8) 1 1+ [ (0) /e] and let TDLap(e, 6) be the distribution supported on 2n) with probability xl).
mass function at being proportional to exp (-e |x
Exponential Mechanism (EM). In the (generalized) selection problem (SELECT), we are given a candidate set H and scoring functions SCTH for all H E H whose sensitivities are at most A. We say that an algorithm is (a, () -accurrte (T) JscT (2:) I ming SCTH + + 2 B
Theorem 9 (IMT07).. There is an E-DP (O(A log H B)/=), B) aaccurate algorithm for SELECT.
3 Approximate-DP
In this section, we prove our main result on approximate-Di user-level learning, which stated in Theorem 10 below. Throughout the paper we say that parameter is "sufficiently small" if it is most an implicit absolute constant.
Theorem 10 (Main Theorem), Let I be any task and y > 0 be a parameter. Then, for any sufficiently
small 8 > and m N, there exists s' log(1/6) log(m/)) and 8' = = (ō m mog((1/5) such that
n
S
log(1
+ nf (c', (c,)8'))).
Note that Corollary follows directly from Theorem 10 by plugging in the expression (e', Ö 1og(1/5')
"pri +
stst into the bound.
While might be somewhat challenging to interpret the bound in Theorem 10, given that the e values on the left and the right hand sides are not the same, a simple subsampling argument (similar to one in [BGH* 23]) allows us to make the L.HS and RHS have the same e. In this case, we have that the user complexity is reduced by factor of roughly 1 /mm, as stated below. We remark that the d values are still different on the two sides; however, we assume that the dependence on 1/5 is only polylogarithmic, this results in at most small gap of at most polylogarithmic factor in 1/5.
Theorem 11 (Main Theorem-Saue Same s Version). Let I be any task and 7 > 0 be parameter. Then,
for any sufficiently small e, O, and m N, there exists = (8 in log(778] such that
n (= S 1og(118)
1
log 1og(1/8)1) 1.5
n (E,
m
Even though Theorem 1 might be easier to interpret, we note that it does not result in as sharp bound Theorem 10 in some scenarios. For example, if Theorem 11 under the assumption in Corollary 3, then the privacy-independent part would be 1 1og(1/6))* maaa instead of n implied by Theorem 10. (On the other hand, the privacy-dependen part is the same.)
ym
The remainder of this section devoted to the proof of Theorem 10. The high-level structure follows the overview in Section 1.1.1: first we show in Section 3.1 that any item-level DP algorithm satisfies sample perfect generalization. Section 3.2.1 then relates this to a local version of user-level DP. We then describe the full algorithm and its guarantees in Section 3.2.2. Since fix a task I throughout this section, we will henceforth discard the superscript for brevity.
3.1
DP Implies Sample Perfect Generalization
We begin with the definition of sample perfect generalization algorithms.
5

---

Definition 12 ([CLN* 16]. For 3, > 0, an algorithm A 2" - O is said to be (3, 6) --smmple
perfectly generalizing iff, for any distribution D (over 2). Pr (A(x) F. A [x')] 2 8.
The main result of this subsection is that any (s.0) DP algorithm is (B,
--n5))- perfectly generalizing: Theorem 13 (DP = Sample Perfect Generalization). Suppose that A 2 - O is (c, o--item-level DP, and assume that E, 6, E. log(1/a)) > 0 are sufficiently small. Then, & is (3,E', 8') sammle perfectly generalizing, where e' < O(e log( //6)) and 8' (
3.1.1 Bounding the Expected Divergence
As first step, we upper bound the expectation of the hockey stick divergence de (A.x). || A(x))):
Lemma 14. Suppose that A z" + O is an (s, -ittem-leee DP algorithm. Further, assume that 6,6, and E log(//) > 0 are sufficiently small. Then, for e' = O log(/))), we have
Ex (der (A(x) A(x')) - O(n)).
This proof follows idea from ICLN+ 16], who prove similar statement for pure-DP algorithms (i.e., = 0). For every output o E O, they consider the function g" : z" + IR defined by ga))) == (n()r(((x) = o)). The observation here is that, in the pure-DP case, this function is e-Lipschitz (i.e., changing a single coordinate changes its value by at most E). They then apply McDiarmid's inequality g" to show that the function values of O(yn- E). This suffices to prove the above statement for the case where the algorithm is pure-DP (but the final bound still contains 8). To adapt this proof to the approximate-DP case, we prove "robust" version of McDiarmid's inequality that works even for the case where the Lipschitz property is violated some pairs of neighbors (Lemma 32). This inequality is shown by arguing that which then allows us to apply
well-concentrated with variance
may change the function "slightly" to make it muutiplicative-Lisshhi standard techniques. Due to space constraints, we defer the full proof, which is technically involved, to Appendix C.3.
3.1.2 Boosting the Probability: Proof of Theorem 13
While Lemma 14 bounds the expectation of the hockey stick divergence, it is insufficient to get arbitrarily high probability bound (i.e., for any / as in Theorem 13); for example, using Markov's inequality would only be able to handle 3 >> 8'. However, we require very small step of the proofs (in particular Theorem 17). Fortunately, we observe that it is easy to "boost" the B to be arbitrarily small, at an additive cost of e log(/s) in the privacy loss.
subsequent
To do so, we will need the following concentration result of Talagrand for product measures:
Theorem 15 ([Ta195)). For any distribution over Z, & C Z", and f > 0, if Pr [x E 8] 2 1/2. then Pra-Dr x Eed 0.5. exp (-P/an). where Egi == {x' 2n 3x E, || æ11o S t).
Proof of Theorem 13. consider two cases based on whether 3 2 2 or not. Let us start with the case that 2- From Lemma 14, for e" = O / log(1/8), we have En (A( || A(x')) & 0(n)) =: 8".
Let E C 2d x n denote the set of (it x²) such that A()) Re" .88" A By Markov's inequality,
we have that Pre, (dg" (A()) A < 48"] 2 3/4 and Pre [de (A(#') || A())) <
48"] 2 3/4 and hence Dr (0r, xr) Ε] 2 1/2. By Theorem 15, for = O log(1/3)) we have
Pr (x, x') &dd 2 B. 20.00 Di.
Next, consider any (ar, x²) E Egg- Since there exists (#. a²) E & such that || 1l 1|x '' llo S f, we may apply Lemma 6 to conclude that (A. || (())), (A('') || A(x')) =
This is substantially simplified version compared the in [Ta195], but sufficient for proof.

---

O(tö). Furthermore, since der((((2) A()') I 48", we may apply Lemma 5 to conclude that de (A(x)) A(x')) S 8' where e' e" + 2te O( log(2/a) and 8' O tō) ( Similarly, we also have der (A(x' || A())) < 8'. In other words, A(x) = Aax'.. Combining this and the above inequality implies that A is
perfectly generalizing as desired.
For the case
2", we may immediately apply group privacy (Lemma 6). Since any I, x' DD
satisfies | x' 2'1lo S n, we have (xx) Re,,5" A(x') for E' ne and 8' = O(n)). This implies that A is (3. e', -'smmae perfectly generalizing (in fact, (0. (0.E","")-samp) -sample perfectly generalizing). which concludes our proof.
3.2 From Sample Perfect Generalization to User-Level DP
Next, we will use the sample perfect generalization result from the previous subsection to show that our algorithm satisfies a certain definition of a local version of user-level DP. We then finally turn this intuition into algorithm and prove Theorem 10.
3.2.1 Achieving Local-Deletion DP
We start by defining local-deletion DP (for user-level DP). As alluded to earlier, this definition only considers - for different i's. We also define the multi-deletion version where we consider s- for all subsets S of small size.
Definition 16 (Local-Deletion DP). An algorithm A (e. 80----oul--deletion DP (abbreviated LDDP) at input x: if A(x=.)) &, A(x for all i, / E [n]. Furthermore, for E N, an algorithm A. is (r,,,0) (1,,,6) local--locld DP at x if A(x #2,5 A(x-s:) for all S, [ [m] such that |S| = =SS| = r.
Below we show that, with high probability (over the input æ:), any item-level DP algorithm satisfies LDDP with the privacy loss increased by roughly rmmm The proof uses the crucial observation that relates sample perfect generalization user-level DP.
Theorem 17. Let n, E N with S and let A ((n-r)m - O be any (c', -itttee-eeeell DP algorithm. Further, assume that e',8', 7,8',s" distribution D
e'r /molm/oo////o 0 are sufficiently small. Then, for any
Pr L is (r, 20 2 1-3,
where O / log(n/88)) and d = O(rm8').
Proof. Let 8r = B//))(;;), Consider any fixed S. C [n]] such that |S] = | = r. Let T SUS SUS't IT' 5 S S. = |0| = U'), and let A denote the algorithm
defined by A/_, (y) = ((x-UUy)
Thus, for any fixed æ-r E Z z(n-tjm Theorem 13 implies that
Pr mu mu -
A (xv) He.6 A'a (EL. s B¹,
(1)
Dum
where = = O('' / (og(//88))))))) < O /m mog((m// (og(()/)))) )) and 8 0(mm8))
Notice that A/e - (wv) = A(x and Ale o. (2v)) st). Thus, we have
Pr (A(x=)) Ke.8 s( Be_r~Din-a m- Dmm
Pr an Der
A' (Iv) $2.8 My (ov:))
(I) E D(-in-)m
[8"] B¹.
Hence, by taking a union bound over all possible S' C [n] such that |S| = -SS| r. we have Pra-Dum [A is not (r, s, 8D-LDDP at a:] < B as desired.
3.2.2 From LDDP DP via Propose-Test-Reles Test-Release
Our user-level DP algorithm is present in Algorithm 1. Roughly speaking, we try to find small subset S such that w-s is LDDP with appropriate parameters. (Throughout, assume that > 4x
7

---

where K is from Definition 8.) The target size of S is noised using the discrete Laplace distribution. As stated in Section 1.1.1, the algorithm very similar to that of [GKK 23], with the main difference being that (i) x stable is defined based on LDDP instead of the local deletion sensitivity and (ii) our output is (x=r),, whereas their output is the function value with Gaussian noise added. It is not hard adapt their proof to show that our algorithm is (s, 6) userrevlle DP, as stated below. (Full proof is deferred to Appendix C.4.)
Lemma 18 (Privacy Guarantee). DelStab is (s, -usser--eee DP.
Algorithm 1 (el
1: Input: Dataset a E Xmm
2: Parameters: Privacy parameters E, 6, Algorithm A (m=mmm)m O
3: + 3. + 8
4e +- K(E, 8).
4: Sample R2 TDLap(E,
{See Definition 8) (See Definition 16)
5: Stahle {S [v] = Rí, (4x RI, RI, E,, x-s)
6: if |
then
7: return
8: Choose S E X X uniformly random
9: Choose T of size 4n uniformly random
return A (
Next, we prove the utility guarantee under the assumption that A is item-level DP: Lemma 19 (Utility Guarantec). Lete, 6 > O be sufficiently small. Suppose that A is ( 8'y-mtem-leeeel DP such that e' = Nvym (ogmm//55) and = + (nmn) If is n-useful for any task with (n 4m samples, then DelStab is (y - o(1)) uuseful / for I (with um samples).
Proof. Consider another algorithm Ag defined in the same way as DelStabe,6.1 except that Line we simply let R,, stable + [ml). Note that Am( is equivalent to randomly selecting 4 users and running A on it. Therefore, we have Præ~Dam (Ao( E W = PranDia-de) [A(x) E Vx]
Meanwhile, Ao and DelStab,, are exactly the same as long as X other words, we have
((r)) in the latter. In
Pr (elstabe.sa(z) Mg] m- Dmmm
2
Pr [Ao()) E Vz DaDam
Pr
(2) + ((x))
20 Dim
27
Pr [A is not (4x, E, 8)-LDDP
27-0(1)
where in the last inequality we apply Theorem 17 with, e.g. 3 = 0.1/um.
Putting Things Together. Theorem now "almost" an immediate consequence of Lemmas 18 and 19 (using O (log(1/6)/E)) The only challenge here is that e' required in Lemma 19 depends polylogarithmically on n. Nonetheless, we show below via simple subsampling argument that this only adds polylogarithmic overhead to the user/sample complexity.
Proof of Theorem 10. Let e' ='(n),,'' be in Lemma 19. Furthermore, let E" 1og(1/8) 1og(m/8) Notice that e'(n)/e" s (1) Let N E be the smallest number
2
such that N is divisible by m and
(es" -1) ni(e",,0)
& ee (NVmm/Akk) -
N
Observe that N < Ō (mx + n (E",
From the definition of ni, there exists an (s", -')-item-level DP algorithm An that is y-useful for with sample complexity ni (e", 8'). We start by constructing an algorithm A N samples as
follows: randomly sample (without replacement) ni(E", ("" out of N items, then run Ag on this

---

subsample. By amplification-by-eeeeee by-subsampling (Theorem 7), we have that A is (='(n), ( -item-eeee DP for N/m + 4xc Thus, by Lemma 18 and Lemma 19, we have that DelStab (e, 6D-DP and (7 ) for I. Its user complexity is
n = N/m + 4k =0 [lg((10))
1 + m
(
2
n1
log(L16) log (ww.m//mmm/mmm
4 Pure-DP: PAC Learning
In this section we prove Theorem 4. Let denote the input and for i E [n]] let 2; ((x1,1 V1.1)..... (Za,m Vi.m) denote the input to the ith user. A concept class set of func- tions of the form X' + 1). For 7 S X' x (0, 1). we say that it is realizable by c X + {0. 1 iff c(z) = y for all (x, E T. Recall the definition PRDim:
Definition 20 ([BNS19]. A distribution P on concept classes an (a, B..--probbbiliitiicc representa- tion (abbreviated as (a, B))PR) of concept class C if for every on X. with probability 1 3 over H P, there exists h E H such that Præ-D,(c(z) + h(x)] I a.
and for every distribution Dx
The (a, 3)RP dimension of C is defined as PRDim (C)) == (a P of size(P), (P), where size(P) == maxp<esupp(P)) log (H). Furthermore, let the probabilistic representation dimension of C be PCD ;= PRDims/an/a(C).
Lemma 21 (BBNS19]). For any C and a E 1/2), PRDim < Ô (PRDim(C)- (1g((1// /a)).
Proof of Theorem 4. The lower bound Đ (d/e) was shown in [GKM2I] (for any value of m). The lower bound Ω d' follows from the lower bound of 52 so on the sample complexity in the item-level setting by [BNS19] and the observation that any (s, du-user-level DP algorithm is also ( -iteem-leeee DP with the same sample complexity. Thus, may focus the upper bound.
zcom
It suffices to only prove the upper bound Ô ( + eam) assuming"
< 1/a. Let P denote (0.01a, PR of C; by Lemma 21, there exists such P with size(P) I Ô (d (ooo((///))). Assume that the number of users is at least s.siza( (P) = Ô _d ). where is sufficiently large constant. com
Our algorithm works as follows: Sample ~ P and then run the e-DP EM (Theorem 9) on candidate
set H with the scoring function (2), := Eien 1[z is not realizable by h).
Observe that the sensitivity of SCT, is one. Indeed, this is where our "clipping" has been applied: standard item-level step would sum up the error across all the samples, resulting in the sensitivity as large as m, while our scoring function above "clips" the contribution of each user to just one.
simple concentration argument (deferred to Appendix D) gives the following:
Lemma 22. With probability 0.9 (over the input), the following hold all E H.:
(i) If (ferrp(h) < 0.01o, then scra (z) < 0.05amm..
(ii) Iferrp(h) (h) > a, then (2) ) > 1.1om.
We now assume that the event in Lemma 22 holds and finish the proof. Since a P is a (0.01a, 1/4)- PR of C, with probability 3/4, we have that there exists h" E H such that erro(h") 0.01a. From Lemma 22(i.. we have SCI (z) < 0.05amm. Thus, by Theorem 9, with probability 2/3, the algorithm outputs h that satisfies scra (z) < 0.05amm O (P)z), which, for sufficiently large K, is at most Oomm. By Lemma 22)ii, this implies that ( < a as desired.
Conclusion and Open Questions
We presented generic techniques to transform item-level DP algorithms to user-level DP algorithms.
If is larger, then simply disregard the extra examples (as the first term dominates the bound).

---

There are several open questions. Although our upper bounds are demonstrated to be tight for many tasks discussed in this work, is not hard to see that they are not always tight"; thus, an important research direction is to get better understanding of the tight user complexity bounds for different learning tasks.
On a more technical front, our transformation for approximate-DP (Theorem 10) has an item-level 5²
privacy loss (roughly) of the form vm (og(1
while it seems plausible that V (og(1/)) can be
achieved; an obvious open question is to give such an improvement, or show that it is impossible. We note that the extra factor of log(1/8)/e comes from the fact that Algorithm uses LDDP with distance unclear how one could avoid this, given that the propose-test-reless
(x)) O (lox(1/6)/e). framework requires checking imput at distance O (8))))
Another limitation of algorithms is their computational inefficieney, their running time grows linearly with the size of the possible outputs. In fact, the approximate-De algorithm could even be slower than this since we need to check whether is LDDP certain input (which involves computing de(A-s A- )) Nevertheless, given the generality of our results, it is unlikely that a generic efficient algorithm exists with matching user complexity; for example, even the algorithm for user-level DP-SCO in [GKK+23] has a worst case running time that is not polynomial. Thus, it remains an interesting direction to devise more efficient algorithms for specific tasks.
Finally, while our work has focused on the central model DP, where the algorithm gets the access to the raw input data, other models of DP have also been studied in the context of user-level DP, such as the local DP model [GKM21, ALS23]. Here again, [GKM21, BGH+23] give a generic transformation that sometimes drastically reduces the user complexity in the example-rich case. Another interesting research direction is to devise a refined transformation for the example-sparse case (like one presented in paper for the central model) but for the local model.
'E.g., for PAC learning. Theorem 4 provides a better user complexity than applying the approximate- DP transformation (Theorem 10) to item-level approximate- DP learners for large regime of parameters and concept classes; the former has user complexity that decreases with 1/m whereas the latter decreases with 1/ /m.
10

---

References
[Abo18] John M Abowd. The US Census Bureau adopts differential privacy. In KDD, pages 2867-2867, 2018.
[ALS23]] Jayadev Acharya, Yuhan Liu, and Ziteng Sun. Discrete distribution estimation under user-level local differential privacy. In AISTATS, 2023.
[App17] Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 2017.
[ASZ21] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private Assouad, Fano, and Le Cam. In ALT, pages 48-78, 2021.
[BBG18] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In NeurIPS, pages 6280-6290, 2018.
[BF16] Raef Bassily and Yoav Freund. Typicality-based stability and privacy. CoRR, abs/1604.03333, 2016.
[BGH+23] Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. STOC, 2023.
[BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu, Private hypothesis selection. In NeurIPS, pages 156-167, 2019.
[BNS19] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of pure private learners. JMLR, 00:146:1-116:33 2019.
[CLN+16) 16) Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu. Adaptive learning with robust generalization guarantees. In COLT, pages 772-814, 2016.
[HS15] Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In NIPS, pages 2566-2574, 2015.
[6KM+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 Kulkamni, and Sergey Yekhanin. Collecting telemetry data privately. In NeurIPS, pages 3571-3580, 2017.
[DL09] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In STOC, pages 371-380, 2009.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise sensitivity in private data analysis. In TCC, pages 265 284, 2006.
[DMR20] Lue Devroye, Abbas Mehrabian, and Tommy Reddad. The minimax learning rates of normal and Ising undirected graphical models. Electronic Journal of Statistics, 14(1):2338 - 2361, 2020.
[GGKM21] Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper PAC learning with approximate differential privacy. In STOC, 2021.
[GKK+23] Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi. Raghu Meka, and Chiyuan Zhang. On user-level private convex optimization. In ICML, 2023.
[GKM21] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. In NeurlPS, pages 20172-201 201844, 2021.
[Gre16] Andy Greenberg. Apple's "differential privacy" is about collecting your data but not your data. Wired, June, 13, 2016.

---

[ILPS22] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In STOC, pages 918-831,22 2022.
[KL21] Nitin Kohli and Paul Laskowski. Differential privacy for black-box statistical analyses. In TPDP, 2021.
[KLSU19] Gautam Kamath, Jenry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately learning high-dimensional distributions. In COLT, pages 1853-1902, 2019.
[Kut02] Samuel Kutin. Extensions to McDiarmid's inequality when differences are bounded with high probability. Dept. Comput. Sci., Univ. Chicago, Chicago. IL, USA, Tech. Rep. TR-2002-04, 2002.
[LSA+21] 21] Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. In NeurIPS, pages 11466-12479, 2021.
[LSY+20] Yuhan Liu, Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and Michael Riley. Learning discrete distributions: user vs item-level privacy. NeurIPS, 2020.
[MT07] Frank McShemr and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pages 94-103, 2007.
[NME22] Shyam Narayanan, Vahab S. Mirrokni, and Hossein Esfandiari. Tight and robust private mean estimation with few users. In ICML, pages 16383-16412, 2022.
[RE19] Carey Radebaugh and Ulfar Erlingsson. Introducing TensorFlow Privacy: Learning with Differential Privacy for Training Data, March 2019. blog. tensorflos org.
[Ta195] Michel Talagrand. Concentration measure and isoperimetric inequalities product spaces. Publications Mathématiques de l'Institut des Hautes Etudes Scientifiques, 81:73-205, 1995.
[TM20) Davide Testuggine and Ilya Mironov. PyTorrh Differential Privacy Series Part 1: DP- SGD Algorithm Explained, August 2020. medium. com.
[Vad17] Salil P. Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pages 347-450. Springer International Publishing, 2017.
[War16] Lutz Warnke. On the method of typical bounded differences. Comb. Probab. Comput., 25(2):269-299 299, 2016
12

---

A
Summary of Results
Our results for pure-DP are summarized in Table 1.
Problem
Item-Level DP
User-Level DP
(Previous Work)
(Previous Work)
Our Work)
θ
θ ( when Ô
θ Theorem 4
PAC Learning
[BNS19]
[GKM21, BGH
Agnostic PAC
θ ( + d
d + δ d + m a
Learning
[BNS19]
Theorem
Learning Discrete Distribution
① ( ( +27)
caym
[BKSW19, ASZ21]
Theorem 43
Learning Product Distribution
θ (
Edd
θ
kd Fir/m
+
ca
[BKSW19, ASZ21]
Theorem
Learning Gaussian (Known Covariance)
Ô ( (4)
d
50y/
amm
[BKSW19, ASZ21]
Theorem 45
Learming Gaussian (Bounded Cav.)
d
d² cmr/m
BKSW19 KLSU19]
Theorem
Table 1: Summary of results on pure-DP. For (agnostic) PAC lcarning, d denotes the probabilistic represen- tation dimension (Definition 20) of the concept class. To the best of knowledge, of the distribution learning problems has been studied explicitly under pure user-level in previous work, although some bounds can be derived using previous techniques for approximate-DP.
For approximate-DP, our transformation (Thcorem 10) is very general and can be applied to any statistical tasks. Due to this, we do not attempt to exhaustively list its corollaries. Rather, we give only a few examples of consequences of Theorem 10 in Table 2. We note that in all cases, we either improve upon previous results or match them up to 1og(1/8)0(1)
factor for all values of m.
Problem
Item-Level DP
User-Level DP
(Previous Work)
(Previous Work)
(Our Work) di EPa vm
when θ [GGKM21, BGH 23]
d c2a
PAC Learning
[GGKM21]
Theorem 10
Learning Discrete Distribution
( & + *
+ cavm
+
1 + Paamm
+ a²
amm
[BKSW19, AS721]
[NME22]
Theorem 10
Learning Product
Ō Ad + Aud
1 Ō
kd Paym
kd m
Distribution
[BKSW19]
Theorem
Table 2: Example results approximate-DP. Each of our results is combination of Theorem 10 and the previously known item-level DP bound. For PAC learning, de denotes the Littlesoone's 's dimension of the concept class. We assume that 5 & and use Ô, Ô to also hide polylogarithmic factors in 1/5.
B Additional Preliminaries
In this section, we list some additional material that is required for the remaining proofs.
13

---

For a, b E R such that S b, let clip,,n RR + I denote the function
if a, b
clipo.((1)
if >
J otherwise.
For two distributions A, B, use dev (A, B) Zsuppp( A))ssppp( B3 [A(x) B(x) denote their total variation distance, dKL. A B) = Exesupp(a) A(x) log(
to denote their
(A(=)-B(=)) B(=)²² to denote the x²- Kullback-Leibler divergence, and d B) = E Eeeppp(A) B(z)
divergence. We use A to denote the distribution of independent samples drawn from A. The following three well-known facts will be useful in proofs.
Lemma 23. For any distributions A and B,
(i) (Pinsker's 's inequality) (A, S V dRI (A B). (ii) (A* B*) k- dRL(A (A B) N. (iii) dKL (KL(A B) S B)
We use ||u]lo to denote the Hamming "norm" 19 of u, i.e., the number of non-zero coordinates of u. The following is well-known fact (aka constant-rate constant-distance error correcting codes), which will be useful in our lower bound proofs.
Theorem 24. For d N. there u1...., uw {0, 1)dh for W =20(1) such that llu uzllo 2
(dd for all distinct i. E [W].
B.1 Concentration Inequalities
Next, we list a few concentration inequalities convenient forms for subsequent proofs.
Chernoff bound. We start with the standard Chernoff bound.
Lemma 25 (Chernoff Bound). Let XI...., Xn denote i.i.d. Bernoulli random variables with success probability Then, for all > O, we have
-52pn
Pr[X1 + ...4 + X, S - (1--5pnn S exp
2
and,
82pp
Pr[X, .... X2 2 6)pn] S exp
2 + 5
McDiarmid's inequality. For distribution D on Z, and function g: n + R. let uD (g) Eu-DD" [x) We say that g is a c-bounded difference function iff (g(x)) g(x')) S for all
x. x E - that differ single coordinate (i.e.. || x' ooolo 1).
Lemma 26 (McDiarmid's incquality). Let g: " - R be any c-bounded difference function. Then, for all t
-2t
Pr[[g(æ) (D) 1 < 2 eexp
n
We will also use the following consequence of Azuma's inequality.
Lemma 27. Let CI...., Cn be sequence of random variables. Suppose that CC < almost surely and that 7 S [C, C2 = cI.... C2-1 = c--1] < f.ror any 6j .3.....Cp Ci-1- Then, for every G > we have Pr ny - avnG < Σie(n) C, < avnG 2 2exp (-G/2).
This is not actually norm, but often called as such.
14

---

B.2
Observations on Item-level vs User-level DP
Here we list couple of trivial observations on the user / sample complexity in the item vs user-level DP settings.
Observation 28. Let II be any task and y be a parameter. Then, for any E, 8 2 and N, holds that
1. n (E,
I (= and [m (e,
2. "m (e,
Proof. Both parts follow by simple reductions as given below.
1. Let A be an (e, --item-llevel DP 7-useful algorithm for I. Then, in the user-level DP algorithm, each user can simply throw away all-but-one example and A. Clearly, this algorithm is (s, d)-user-level DP and is y-useful for 5. The user complexity remains the same.
Let be an (e, 5) -user-level DP uuusefu algorithm for I with user complexity n (e, 7) Then, in the item-level DP algorithm, if there are N m n (E, 7; users, we can just run A by grouping each examples together into a "super-user". Clearly, this algorithm is also (e, 6i-tte-- level DP and has user complexity m-n (s, 8; y). Thus, we have m-n (E, 6: S (= O
C Missing Details from Section 3
C.1 DP Implies Perfect Generalization
We start by recalling the definition of perfectly generalizing algorithms.
Definition 29 (Perfect generalization [CLN+16 16, BF16]). For 8, > 0. an algorithm A z" - O said to be (B, e, 8) pperfectyy generalizing iff, for any distribution D (over Z), there exists distribution SIMp such that
Pr [A(x) Re,8 SIMp) 2 1 w>D"
It is known that perfect generalization and sample perfect generalization (Definition 12) are equivalent: Lemma 30 ([CLN+16 16, 2GH+ Any (3, --prffecyyy generalizing algorithm also (3, 22, 36)- sample perfectly generalizing. Any (B,e,5)-same) 50)spplll perfectly generalizing algorithun is also (vB,e,8 + -Be-peffet generalizing; furthermore, this holds even when we set SIM to be the distribution of A(x)) where a ~ Dm
Thus, by plugging the above into Theorem 13, we immediately arrive the following theorem, which generalizing. This resolves
shows that any (e, -DP algorithm is (3, (E open question of [CLN+ 16).
Theorem 31 (DP implies perfect generalization). Suppose that A is (e, ---itee-leeel DP algorithm. Further, assume that E, 6, B, and e log(//a) are sufficiently small. Then, & is (B,e', ( -perfectly generalizing, where E' & O On log (26))) and 8' = O(n)).
Furthermore, this holds even when set SIM to be the distribution of A(x) where a ~ D
We remark that Bun al. [BGH* 23] showed that any (s, 5DDP algorithm be "repackaged" to an , p'r-perfyt generalizing algorithm with similar parameters as our theorem above. However, unlike result, their proof does show that the original algorithm is perfectly generalizing.
C.2 Achieving the Same E via Subsampling: Proof of Theorem 11
Proof of Theorem 11. Let E"
log(1/6) /m (o)))))) We claim that (=",8") < (1(E,8))
O(E/E ; the lemma follows from this claim by simply plugging this bound into Theorem 10.
To see that this claim holds, by definition of n1, there exists an (c, (e,,')-itemm -t---tte-leve DP algorithm Ao that is usefful for I with sample complexity ni 8'). Let E N be smallest number such that
(e 1-1) (1, 8*)
c=
15

---

Notice that we have N I 81) (((E,)))(((/EE") Let A be an algorithm on N samples defined as follows: randomly sample (without replacement) n, (e, 8') out of N samples, then run Ag on theorem (Theorem 7), we have that A is (c" ".))--tt---eeve DP. also obvious that the output distribution of this algorithm the same as that of Ag on n1 (1, examples, and this algorithm is thus also 7-useful for I. Thus, we have n (s",8) S N S (1) O(s/e") as desired.
this subsample. By the peelfication-by-sussaann
C.3 Proof of Lemma 14
C.3.1 "Robust" McDiarmid Inequality for Almost-ulllpiictiree-ispsttt function
We derive the following concentration inequality, which may be viewed as a strengthened McDi- armid's inequality (Lemma 26) for the multiplicative Lipsshhtz case. To state this, let us define an additional notation: for 2" 5; E Z, we write (+() to denote but with x; replaced by ã..
Lemma 32. Let f z" + Rzo be any function and D any distribution on Z. Assume that e, >> 0, and E /
0 are sufficiently small. Then, for E' = =O(Ev (266). we have
E Be. [[f(x)) - e²' ee .f(2))++ Olppr (f) +
Σ
E B wDn [f(z) - c² ff((())
When the second term in the RHS (i.e., O (E
1 ER.END" [f(z) - c -
is zero, our functions, as
lemma is (essentially) the same McDiarmid's inequality for Mattipllicatie-Liischhh proved, e.g., in [CLN+16] However, our bound more robust, in the sense that it can handle the case where the multiplicative-iisccitta Lemma 14 as we only assume approximate-DP.
condition fails sometimes; this crucial for the proof of
We note that, while there are (additive) McDiarmid's inequalities that does not require Lipschitzness everywhere [Kut02, Warl6], we are not aware of any version that works for us due to the regime of parameters we are in and the assumptions have. This is why we prove Lemma 32 from first principles. The remainder of this subsection is devoted to the proof of Lemma 32.
Scalar Random Variable Adjustment for Bounded Ratio. For the rest of this section, we write Z Rig z' where ,' E R2 to indicate that & E [e [e='=',e==']. We extend the notion similarly to Valuve random variables: for Vaguva random variable Z and 2 R>,, write Z Reg z' if a Re z' for each 2 E supp(Z). ()). Furthermore, for (possibly dependent) R -vauue random variables Z, Z', we write Z R Z' to denote =2 2 for all (z,2¹)
supp((2,2"))
Suppose Z is a Rayuue random variable such that any two values 2, E supp(Z) satisfies Ri_ 3. Then, we also immediately have that their mean is in this range and thus Z Re jr. We start by showing "robust" version of this statement, which asserts that, even if the former condition fails sometimes, we can still "move" the random variable a little bit so that the second condition holds (albeit with weaker 2s bound). The exact statement presented below.
Lemma 33. Let E, 11" 2 O. Let 7 be any -ayuee random variable and μ = T[Z] Then, there exists a random variable Z', which is a post-processing of Z, such that
(i) Z' 2325 n²" (ii E[Z') -
(iii) Ez, 2'1l 1p 1²1 + 2(1 +) - 3 c= [ where (Z,Z") is the
[
canonical coupling between Z, Z' (from post- cost-processingg and Ž is an i.i.d. copy of Z.
Proof. Let = e 14, = e μ. We start by defining 2 = (Z). This also gives a canonical
coupling between 2 and Z, which then yields
E 211 Ez || clipt, (2)1]
= FE [7 - -r]+ + [e - 2]+
Ez [Z e m + Ez _ 2]4]
16

---

Ez
Z c. Eg [2]
+ Ez
Z e -- 2 211]
c c -Bg 2
2,
( -e ee -
+ E,2
-
| c
=1+ 2,2
(2)
where the inequality follows from the convexity of [.]+. Define μ : 12] Note that we have
l - 1 S R 12,22]12 Z]].
(3)
Next, consider two cases based on μl, M²
Case I: f ef 1e or μ e p². We assume w.l.o.g. that μ e μ²; the case μ < pr* can be argued similarly. In this case, simply set Z = always. Obviously, items (i) and (ii) hold. Moreover, we have
Ez 11Z z'Il Ez|Z 1
S E (z, 112 10 12 Z
② E 111 + (2, [12 Ø
A n² (2,2) 22,22112 -21
WPーE² + 2E (2 11 -
where (+) follows from 2 - n². Combining the above inequality with (2) yields the desired bound in item (iii).
Case II: f Re Jr. In this case, we already have supp (2) S [e- e4,e [4] S [e-2 y²" x*) We assume w.l.o.g. that 2 ,²; the case á I p² can be handled similarly. In this case, let f [e, r] R be defined by f(r) == Eg (clip... Notice that f continuous, f() = S μr' and fr) p 2 μ¹" Thus, there exists T" such that f(r*) n². We then define Z' by Z' = clipr,- (2)) This immediately satisfies items (i) and (ii). Furthermore, this gives a natural coupling between Z', 2 (and also 2) such that
E( - Z'1] = E 12,2,, 12 z-= n² s 4 4- 1-= la 14)
Combining this with (2) and (3) yields the desired bound in item (iii).
Concentration for Bounded-Rates Ratio Martingales. Since we will be applying Lemma 27 on the logarithm of the ratios of random variables, it is erucial bound its expectation. We present bound below. Note that similar statements have been used before in DP literature; we present the (simple) proof here for completeness.
Lemma 34, Let Z be any Re random variable such that E[[] = For any sufficiently < O.
small 8 0, Z R 1, then - < E [In 2|
Proof. By the concavity of In()), we get E [I Z| < In = 0.
Note also that for I 1, we have In(x) > - 2(z 1)2 for all E [e]., This implies that 2(Z - 1) (Z
E In Z| Z
N 2(e 1)2 2
We now ready to give concentration inequality for martingales with bounded ratios. Note that the lemma below is stated in "expected deviation from (e-=', -u, e -1]" form since will be more convenient to use in a subsequent step.
Lemma 35. Axsume that e, 5 > O, and E e log(1/s)
> are sufficiently small. Let Yi,... . Yu be Rao-v martingale such that Rig Y,-1 almost surely, and μ TE(Y)). Then, we have
B[[Y,. e²' pl+ [І e²' Yol+1 S O(p 8),
where E' O(E log (og(//))
17

---

Proof. Let т = 100 (1/6). Consider CI...., Cn defined by C2 := In(Y:/Y(-1), where we use the convention Yo = μ. By our assumption, we have |Cj| S E. Furthermore, Lemma 34 implies that - < R - V/--,,...; Vi y1 I 0 for all Di-1,..., ./- Let -8... Applying Lemma 27, the following holds for all > 0:
Pr my EVNG
Σ SevennG
21 - 2exp (-G/2).
KE[k]
This is equivalent to
Pr enmem-ev
-4 Yx S evving
-M) 2
(4)
Thus, we have
E [u lu- e .Y.)+ S n. Pr[y, Se-oai 1 n. Pr(Y, S 6 S p 6,
(4)
where the second inequality follows from the assumption that EV log/oogg////// 1/6) is sufficiently small. Furthermore, we have
E [Yn - -evee 14|+
Pr[Yn -eVnn . yldy
Pr(Yn -EENTT p μ yldy
11.
100
Pr(Y, 2 1. .1 dy
Jever
Pr(Y, 2 evvn 11
Vne exp(ev dG 2VG
Vne
2exp( -G/2).
explev (i) dG
2/G
S n
2exp(-G/H dG
μ 8exp(-T/4)
S 8,
where the second and third inequalities are from our choice of T.
Combining the previous two inequalities yields the desired bound for = 8 8
Putting Things Together: Proof of Lemma 32. Our overall strategy is similar the proof for the always-bounded case, which is to set up martingale from suffix averages and then apply Lemma 35, The main modification is that, instead of using this argument directly on (and its suffix averages), we use it on different function, which is the result of applying Lemma 33 to f.
Proof of Lemma 32. For convenience, let μ := u'r (f). Let us first extend the function f to include prefixes (i.e., f g > R2o) naturally as follows:
f 22) E (Ex......... (a....., ,,, X141............................ X,)).
Next, we construct a function g - + R20 as follows:
g(0) = f(0) (which is equal to (1)
For i 1....,
For all (#1...., 2;-1) E Zi-1:
Apply Lemma with 11" = -(x and Fi.-1 Xz), where
X, ~ D to get random variable Z'.
The coupling between (Z, 7') is naturally also a coupling between (æe, Z') for xs 2.
Let 9(.1,..., Z' based on this coupling for all x; Z.
18

---

For brevity, let = 2(1 2(1+)")), We have
Ew-DD (1g(()) - [x)]]
BenDo Be NDn ( un) Ga)ll
I BewD" [00( f( )1 + p: Es.., ~D (f(zgn-1. - f.
Bmgn- 1 [1g(#gn-1) - f(=zn-1))] + p Ee (f(0gn-1 - e. f()551112
where the inequality is from Lemma 33(ii)).
By repeatedly applying the above argument (to the first term), arrive at
DD (l f(x)ll - p.
Eu, of [f(2gi-1, e. f(
Recall from the definition that ( Ba (2 2ú +>i) and f(zga-1, (/ #x)) Thus, by the convexity of (1,, we further have
EE - f(x) s Σ Expan [f(x) e f(((0))
(5)
Next, let Yo, Yy.... Yn be sequence of random variables defined by sampling Ti..... ~ DD and letting V; == g ). By Lemma 33(i), we have that Yi..... Y, is martingale, Lemma 33(i)
further implies that Y Y. Thus, we may apply Lemma 35 to arrive at
B| e /2 14+ lu of Yn]+1 O(ud),
for L' Ol))n)oo())))). Note that this equivalent
EenD" [[9(>) - e 11- + In e +(x)]++ O(p5).
(6)
We derive the bound the desired quantity follows:
D' [[f(x) - e² f(x')++
B' DD [[[(x) g(x)) + (g(x:) 12 + e 12 (p e (2 + e (g(x') - f(x' M1+
Elf((x) - g(x)]++ =lg(() - el2 /2/11, + e e 1/1EEp E 12 g((x(()) (+ Elg(x') - f(x())
(5.(6) 0(τ)) + 0
Σ Dn [(xx) e s(
C.3.2 Putting Things Together: Proof of Lemma 14
Lemma 14 is now a simple consequence of Lemma 32.
Proof of Lemma 14. For every o and a E 2", let f0(x) Pr(A(()) o). Applying Lemma 32 to fo, we get
E (1f e ff(2')4+]
Σ En En DD (xxx) - - -
< ((p +0
where e' O (og(()))
Summing this up over all E O, we get
Ex. [d (A(x) A )) 0(0) +0
Σ Ex En
(de (A((z) A(( ((6)),
where the second inequality follows from the assumption that A is (s, 6) -iitee-lleeell DP, which implies de (A(()) (()())) 8.
19

---

C.4 Privacy Analysis of Algorithm
Here we prove the privacy guarantee (Lemma 18) of Algorithm 1. This mostly follows the proof for the analogous algorithm in [GKK (IKKK*33.. 23].
We start with the following observation.
Observation 36. For user-level neighboring datasets a,,,, and all in E {0...., n 1} if X stable (x') * 0, then stable (a:) # 0.
Proof. Let E [n] be such that æ- = x'_., and let x'ss' be an element of stabbl (2r). Select S such
that |S| = + 1 and S 2 S' (1). It is obvious from definition that ss E X stable (2)).
Proof of Lemma 18. Let x, x' be user-level neighboring datasets, and let A be shorthand for DelStabe, First, we follow the proof of (GKK+23, Theorem 3.3]:
Pr[A(x) =1]= = Enn=o A(
= 11 R = -r] Pr[Ri = =r]
2
1 1 stable (x) 0] Pr[R] =r]
< Pr[[R| = 0] + 2m= [ stable (a) = 0] Pr[[[] = ml
< 1 stuble (x) 0] e e ri -1] 1]
< <0+ 2x 1 (x') 0] cF. Pr(R = -
$ Ei 1[A(x') =Tد R = =n] - = =rl
= e Pr(A(()) =1T,
and for any Uo S O, we have
Pr[A(xt) E Uo} En= Pr(A(x) E Uo Rí =n] PP(Ri ri]
Σ 2x-1 Pr(A(() E Un Ri =r]] Pr[Rt ri] + Pr[ft = 2k]
8 c. Σn Pr[A(( [A(x) E Un Rí = =n] Pr( = n +1],
To bound the term Pr[A(x) E Un R = ril for r < 2x. observe that if it non-zero, then must be that A(x) #1 or equivalently that X atable (x) # 0. In this case, we ha
Pr[A(x)) E Uo! R =n] E
S~Xt (w) (.3 [Pr(A((r)) E Uo]]
(x') + 0. Thus, we have Since stable (x) # 0. Observation 36 also implies that"! p (x')
Pr[A(z') E Uo! | R1
1] = E S' xx x ( [Pr[A(x,)) E Uol]
Consider an arbitrary pair S E X² stable (x), S' E A (x'). Let i E [n]] be such that æ x'_;- Note that 1 33) {i)l 2 n 4k. Let Je be any subset of (5 5 of size n 4k. From X stable (z),, have
Pr(A(x)) E Uol S e Pr(A(a))) +6] +3,
for all J E ( (n) and, from S' E & (x'), we have
Pr[A(x,-) E Uol S ot P +8,
for all J E ( (. Therefore, by arbitrary coupling of S, S', we can conclude that
Pr[A(x)= E Uo R = = s aH Pr(A(z') e Un R = + 1]+ (e + +18.
Here we write S = [n] S. Agaiin we write 5 = [n] S".
20

---

Plugging this back to (8), we get
Pr(A(()= Uo!
2x
$ 5ō+ Σ
( 2F
Pr[A(a') R1 -1++1 (e + 1)5) Pr(R1 = 11 +
n=
(e + c + 1)8 + 05 - E Up R ril Pr[R1 71
= = +e + 1) + nd Pr(A(x') E Uol.
(9)
Now, consider any U COU {1} of outcomes. Let Uo = UNO and UI = Un (1). Then, have
Pr(A(z) EU Pr(A(z) Uol + Pt(A())
(9,(7)
S ((e 2h + + + ( E Uol) + ( U.))
$ ( + e + 2) + E0H Pr(A(a') EU] <ó+é Pr[A(x') E.]
Therefore, the algorithm is (s, 6) ueser-ele DP as desired.
D Missing Details from Section 4
Below we give the proof of Lemma 22.
Proof of Lemma 22. Consider any h E [0,1) Since z,'s are drawn independently from D, we have that [|, is not realizable by hi]'s are independent Bernoulli random variables with success probability
Ph = 1 -
(1)errphh))
Consider the two cases:
(h) < 0.01a, then we have
Ph. (1- 0.01a) 11-0110. <
0.0lam.
Thus, applying Lemma 25, we can conclude that Pr[scra (2) 2 0.05mmm) S exp (-O (nom)) = exp (-0 (n: size (P)))
Thus, when select be sufficiently large, have
0.01
0.01
Pr|scrs (2) 2 0.05amm] S exp(=10sizeePP) V exp(size(P))
[7|
If (h) > a, then we have
Ph 11- a))
-am 0.2am,
where in the second inequality we use the fact that am < 1. Again, applying Lemma 25, we can conclude that Pr[scra (z) < 0.2cmm] S exp (-O (nam)) exp (-O (N: size (i))) Thus, when we select x to be sufficiently large, we have
0.01
0.01
Pr|sers (x) < 0.2anm] I
exp(size(P))
H
Finally, taking union bound over all E H yields the desired result.
It is also worth noting that the scoring function can be written in the form:
scrA (z) = clipa,1
E 2; M(x) + y))),
which is similar to what we present below for other tasks.
Finally, we remark that the standard techniques can boost the success probability from 2/3 to an arbitrary probability 1 - B, with multiplicative factor of (18)) cost.
21

---

E Additional Results for Pure-DP
E.1 Algorithm: Pairwise Score Exponential Mechanism
In this section, we give user-level DP version of pairwise score exponential mechanism (EM) [BKSW19]. In the proceeding subsections, we will show how apply this in multiple settings, including agnostic learning, private hypothesis selection, and distribution learning.
Suppose there candidate H. Furthermore, for every pair H, H' H of candidates, there is "comparison" function HH Z + []. For every pair H, H' of candidates and any E 2", let
pscr (x) = Σ (x).
WE
then define scr for each candidate H
sCr H (x)
=
pscr v H'EH-(H) H. (a)).
max
Traditionally, the item-level DP algorithm for pairwise scoring function to use EM on the above scoring function scr i (where a denote the entire input) [BKSW19]; is not hard to see that the scr j has (item-level) sensitivity of at most 2.
User-Level DP Algorithm. The algorithm computes:
We now describe our user-level DP algorithm ClippedPairwiseeen
M.T pser H. (x)
Σ iE(m]
clip
e (en
max scr H (H)
U.T (x))
pscr N.TT (x).
Then, simply runs EM using the score scr H with sensitivity 2T.
To state the guarantee of the algorithm, we need several additional distributional-bat based definitions of the score:
v pscr H. (D) EEAD [bH, (x)),
max Ds (D). SCT (D) H'E
Note that these distributional scores normalized, they are in |-1,
The guarantee of our algorithm can now stated as follows:
1o Theorem 37. Let or, 3 E (0, 1/2). Assume further that there exists H such that scr H- (D) S 0.1 There exists an E-DP algorithm that with probability 3 (over the randomness of the algorithm and the input x (Dm)) outputs E such that scr f1 (D) S 0.5c as long as
logg (H)BB)
log((H1/3) Q=vm
log(1H1)3)
θ
+
+
a2m
Proof. We use ClippedPairwisEEM with parameter C. (am + vm log (1/a) and assume that
n 2 C" Tilool H1/M) log (e{(11991)) am
log log((H() (P((11)))) where C,C' are amm sufficiently large constants. The privacy guarantee follows directly from that of EM, since the (user-level) sensitivity is at most A (due to clipping).
è logd (P)(111))))))))
log(1A2//8)
cam
osy'm
To analyze the utility, we will consider following three events:
E ser Whs7 (x) < scr 25.7 (x) + 0.laam. H
H.H Ex: for all H. H' H: if pscr H. (D) I 0.1o, then pscr H. (x) S 0.2onm.
&e
a Eg: for all H, H' H: if pscr H.H D 2 0.5a, then pscr H.H (x) 2 0.4anm.
s)
22

---

M.7 (æ) S (x) + 0.lamm. Observe that & implies When all events hold, ES implies that scT that = (ar) - 0.2omm. Combining these inequalities, get ser (x) 0.3amm; then, &3 implies that jscr",,H' H (D) & 0.5a for all H' E D. In turn, this means that scr (D) v 0.5a
Therefore, suffices to show that each Pr[éi], Pr[E2], Pr[ea] at least 8/3.
Bounding Pr[E1]. To bound the probability of ε₁, recall from Theorem that, with probability 1 1- 8/3, the guarantee of EM ensures that
V.z ser H (az) 2 ser V.T (2) + (108(1)113))
ser'i.
E
From our assumption on n, when C' is sufficiently large, then have O [Io(1H11/3) -A
O log (11108
S 0.1amm desired.
Bounding Pr[Eg] and Pr[Eg]- Since the proofs for both cases are analogous, we only show the full argument for Pr[Ea]. Let fix H, H' E H such that pser it, n (D) 2 0.5a. We may assume w.l.o.g.
that pscr ir, (D) 0.5c
Notice that pscr vh.r H. (x:) a 2- bounded difference function. As a result, McDiarmid's inequality (Lemma 26) implies that
0.05amm]] S 2exp (-0.025a"mm) S Pr [[pser H, (x) WDDm (pser HI am/mm
(10)
3
where the second inequality is due to our choice of n when C' is sufficiently large.
To compute /*p"m (pscr v.r ). observe further that
pDmm (pscr N.. H, 1DD (clip p, )
(11)
Now observe once again that pscr),,H 2 + R is also 2-bounded difference function and IDD (pscrrt..r) pam. Therefore, McDiarmid's inequality (Lemma 26) yields
[pser H. (x) > r] - 2 exp (-0.5(T - -um)²/m/ s 10 1004a?
(12)
- mm
where the second inequality is due to our choice of when C' is sufficiently large. Finally, note that
ND (clip --r (s
Em [clip_.. (pscr H, (x)))
En- /clip_oorr (pscr)) 11 (x))
ExnDi [pser v (x) + EX-D [(T pser (.r (z)) 1 H, (2)
7]]
pM E Ez-Dm [pscr v
H (x) [pscer H. (x) r]]
E Em [pscr v H. H (x) Em [pscrt....r vi H. (x) > r]
pm
W IV
pm
Vm3
Pr DomDm
[pscr H. (x) >
pM 0.01am = 0.49am,
(13)
where the third-to-last inequality follows from Cauchy-Schwarz.
12 "'theewiie, we may keep increasing (=) for different values of = until pscr H.H (D) = 0.5a; this operation does not decrease the probability that pscr u. (x)) 0.4am..
23

---

Combining (10), (11), and (13), we can conclude that
Pr Dr-Dum
[pscr V.7 H. (x:) 0..4mm) - 3/72/2
Taking a union bound over H, H' E H yields Pr(Ea) 2 1 - 3/33 as desired.
E.2
Lower Bound: User-level DP Fano's Inequality
As often demonstrate below that bounds are (nearly) tight, it will be useful to have generic method for providing such a lower bound. Here we observe that it simple to extend the DP Fano's inequality of Acharya et al. [ASZ21] to the user-level DP setting, We start by recalling Acharya et al.'s (item-level) DP Fano's s inequality!3:
Theorem 38 (Item-Level DP Fano's Inequality (ASZ2I]). Let I be any task. Suppose that there exist ..,... Dw such that, for all distinct i & [W].
(D( n Dz
0.
dKL (D, D S B. and
di (D) S%
Then, ni (E, = 0) 2 Ω
log W
log W 8
The bound for the user-level case can be derived follows.
Lemma 39 (User-Level DP Fano's Inequality). Let I be any task. Suppose that there exist
D DI...., Dw such that, for all distinct i,j E [W].
. (D)(D)) n V (D) = 0, and. dKL (D,, Dj) S
Then, n (e, 8 0) 2 Ω
log W
log W cymB
log W
Proof. Let Dj = (D,) for all E [W]; note that (2) || DJ) < m3. By Pinsker's in- equality (Lemma 23(1),, dev DJ) I 0(/m3); furthermore, also have the trivial bound (D) || DJ) s 1. Finally, define task I' by Va (D)) (D( for all i [W]. Now, applying Theorem 38,
log W
log W m3
log W
log W
log W
of (e, 6 0) Ω
(c.
Ω
+
(mnn{1 vm3) e
E
e s
m3
Finally, observing that n (s, = ni (s, yields our final bound.
E.3
Applications
Our user-level DP EM with pairwise score given above has wide variety of applications. We now give few examples.
E.3.1 Agnostic PAC Learning
We start with agnostic PAC learning. The setting is exactly the same as in PAC learning (described in the introduction; see Theorem 4) except that we do assume that is realizable by some concept in C. Instead, the task agn(C; a) seeks an output c X' + {0, 1} such that errp < mingee ccrp(c')+
Theorem 40. Let C be any concept class with probabilistic representation dimension d (i.e., PRDim(C) d) and let dve be its VC dimension. Then, for any sufficiently small a, > and for all E N,
agu(C:a) T
( s o
d
d
+ a²m
asym
The particular version use slight restatement of [ASZ21, Corollary 4].
24

---

and
n (gn(CCa) 0) 2 á (
dvc dvc .evmm a²m
+
Observe that our bounds are (up to polylogarithmic factors) the same except for the d-vs-dye in the last two terms. We remark that the ratio d/ dvc not always bounded; e.g., for thresholds, dyc while d = O (log Z1). A more careful argument can show that d in the last two terms in the upper bound can be replaced by the (maximum) VC dimension of the probabilistic representation (which is potentially smaller); this actually closes the gap in the particular case of thresholds. However, in the general case, the VC dimension of and the VC dimension of its probabilistic represetation are not necessarily equal. It remains an interesting open question to close this gap.
We now prove Theorem 40. The algorithm is similar to that in the proof of Theorem 4, except that we use the pairwise scoring function to compare the errors of the two hypotheses.
Proof of Theorem 40. Algorithm. For any two hypotheses c' X + {0, 13, let the comparison function between two concepts be tinger ((r, u)) = [c(x) = u] - [(((x) = y)-
Let P denote (0.01a, 1/4)-PR of C; by Lemma 21, there exists such P with size(P) S Ö (d log(1/a)). Our algorithm works as follows: Sample H. ~ P and then run the E-DP pair- wise scoring EM (Theorem 37) on candidate set H with the comparison function the defined above. The privacy guarantee follows from that of Theorem 37.
As for the utility, first observe that
pscr oge! (D) = errp(c) - errp(d')
(14)
This means that, if we let h² argminner CIT (h), then scr (D) S 0. Thus, Theorem 37 ensures that, w.p. 0.99, if n 2 Ô (Pize(P) + size(P) stag(( Ô aevm + (mmm) then the output satisfies scr (D) S 0.5a. By (14), this also means that cIrp(h) S 0.5a + crrp(h"). Finally, by the guarantee of P. we have that err S 0.01a minere errp(c') with probability 3/4. By union bound, we can conclude that w.p. more than 2/3, we have erro (h) < a + mingec errp (c').
d
aeym
a2m
Lower Bound. The lower bound (dd/E) was shown in [GKM21] (and holds even for realizable PAC learning). To derive the lower bound ?
Dev/m dvs) we will use DP Fano's inequality (Lemma 39). To do so, recall that C having VC dimension dyc means that there exist {ri....... I dove) } that is shattered by Z. From Theorem 24, there exist UI...., uw E {0, 1jdve where W 2 such that l/u - unllo 2 dyc for some constant x. For any sufficiently small < k/8, we can define the distribution D, for i E [W]b) by
dye
D;(( 2dvc (1 (1+ (21(((()) =y] -1)-
4a
for all E [W] and E {0, 1}. Next, notice that, for any i E [W], we may select ej such that 1 (1 ta).
(cTp(c;) = 2
Furthermore, for any i # j E [W] and any hypothesis h : X {0, 1}, we have
errD, (h) + errp, (h) 2 (1
4a
+ 4a K k- dvc
(1 4a
-1-
+ 4a.
dvc
This means that crT.D, (h) > (1 - 4a + 2a or CTTD, (h) have Vagu(C;a) (D;) n v0 Wagn(C:a) (D,)
> 1 (1 4a + 2a. In other words, we
x = 0. Finally, we have
dkr, (D; || D2) s dx (2))
(D.( v)) - DD w)))
D,((x,
Re(dvcl.vE
Ola/dvc)2
Σ
1/advo
(0)))))
25

---

Σ
Ola2/ /dvc)
Reldvel
2 ((a))
Plugging this into Lemma 39, we get that Tim
agn(C;a))
dvc saamm
dyc ma as desired.
E.3.2 Private Hypothesis Selection
In Hypothesis Selection problem. we are given a set H of hypotheses, where each P E P is distribution over some domain The goal is, for the underlying distribution D, to output P E P that is the closest (in TV distance) to D. We state below the guarantee one can get from our approach:
Theorem 41. Let a. & E 0.1). Then, for any > O, there exists an s-user-level DP algorithm for Hypothesis Selection that, when each user has m samples and minp'ep d D) S 0.la, with probability 1 - B, outputs P B such that der D) I a as long as
1og(1B1/B)
log( (1118) OE m
log( (1/3)
a²m
For = 1. the above theorem essentially match the item-level DP sample complexity bound from [BKSW19]. The proof also proceeds similarly as theirs, except that we use the user-level DP EM rather than the item-level DP one.
Proof Theorem 41. We use the so-called Scheffé score similar to [BKSW19]; For every P,P' B. we define Wp.p' as the set {a E z P(() > (z)} and
up.p (2) = P(Wp,pr) - 1[2 E Wp,rr..
We then use the e-user-level DP pairwise scoring EM (Theorem 37). The privacy guarantee follows immediately from the theorem.
For the utility analysis, let P d. Recall from our assumption that dev (P*, D) s 0.1a. Furthermore, observe that
pscr * p (D) = PP"(W-,p) D(WP- (D. s 0.1a.
Moreover, for every P B3 we have
pscr (D) = P(Wp. D(Wp,p-)
=P((Wp,-.) - P'(WP, (B:::--))((((M)))) (D(Wp,p:) P-' - (Wp,p.))
(d,(P, - (.pp:::))PP((ppp....
> (P,PPP") dP= ,D)
2 dP, - 0.la.
Thus, applying the utility guarantee from Theorem 37, we can conclude that, with probability - 8, the algorithm outputs P such that dev D) < 0.5x + 0.la as desired.
E.3.3 Distribution Learning
Private hypothesis selection has number applications, arguably the most prominent one being distribution learning. In distribution learning, there is a family T of distributions. The underlying distribution D comes from this family. The task dlearn(3; dev Q D) < where > 0 denotes the accuracy parameter.
output distribution Q such that
For convenient, let defined packing and covering of family of distributions:
A family Q2 of distributions is an a-cover of a family & distributions under distance measure iff, for all P E Q there exists Q E 12 such that d(Q, P) ) a.
A family Q of distributions is an a-packing a family & of distributions under distance
measure iff, Q C B and for all distinct Q, Q' e Q, we have d(Q, Q') 2
26

---

The size of the cover packing is defined as size( = 12g( The diameter of Q under distance is defined maxg,0'e2 d( Q Q*).
The following convenient lemma directly follows from Theorem 41 and Lemma 39.
Theorem 42 (Distribution Learning-Arbiree Family). Let & be any familiy of distributions, and let a, E > 0 be sufficiently small. If there exists 0.la-cover R under the TV distance of size L, then
dlearn(Pso) (e) () 1- T
L
asvm
0² a²m
Furthermore, if there exists family Q of size L that is 3a-packing of under the TV distance and has diameter at most 3 under the KL-divergence,, then
L
L
L
(leear((B;a) (s, = 0) n'm
+
EVmB
m3
In theorems below, abuse the notations é, Ô and also them suppress terms that polylogarithmic in 1/ 1/a, d, R, and k.
Discrete Distributions. First is for the task of discrete distribution learning domain [A] (denoted by DD)(a)), which has been studied before in [LS In this case, & consists of all distributions over the domain [k]. We have the following theorem:
Theorem 43 (Distribution Learning Discrete Distributions). For any sufficiently small a,e O and for all m E N, we have
Tem (e, 6 0)
DDM(O)
neym
am
Proof. Upper bound. It is simple to that there exists an 0.1a-cover of the family of size O(k log(k/a)): We simply let the cover contain all distributions whose probability mass at each point is multiple of [10k/a]. Plugging this into Theorem 42 yields the desired upper bound.
Lower bound. As for the lower bound, we may use construction similar to that of [AS721] (and also similar to that in the proof of Theorem 40). Assume w.l.o.g. that & is even. From Theorem 24, there exist u1, ......, uw E {0, 1/2 where W = 20(k) such that | - u, Ilo 2 k- k for some constant w. For any sufficiently small a < k/16, we can define the distribution D. for E [W] by
8a 1[(ui)e = -0
D2(2E - 1) 2h:
1+
K
8a
D2(2() = 2k
1
I(ui)e = 01
K
for all E [k/2]. By a similar calculation as the proof of Theorem 40, we have that it is an (Bak-ig under TV distance and its diameter under KL-divergence is at most O(a?). Plugging this into Theorem 42 then gives the lower bound.
Interestingly, the user complexity matches those achieved via approximate-DP algorithms from ILSY+20, NME22), except for the first term (i.e., k/s) whereas the best known (s, DDD algorithm of [NME22] works even with log(1/5)/s instead. In other words, when is intermediate, the user complexity between the pure-DP and approximate-DP cases are the same. Only for large m that approximate-DD helps.
Product Distributions. In this case, Q is a product distribution over the domain [k] (denoted by PD(k, d; a)). We have the following theorem: Theorem 44 (Distribution Learning Product Distributions). For any sufficiently small a, E >> 0 and for all m E N, we have
8(Kt kd +
kd
kd a²m)
PD(k.dda)) (5, = =0) = =ô n m
+
as m
27

---

Proof. Upper Bound. Similar to before, we simply take Q to be o.leer (under TV distance) of the product distributions, which is known have size at most O Okd log(kd/a)) [BKSW19, Lemma 6.2].
Lower Bound. Acharya al. [AS721, Proof of Theorem 11] showed that there exists family Q of product distributions over [k] that is a -3a)-nacking under TV distance and its diameter under KL-divergence most (aa²) of size (((dd). Theorem 42 then gives the lower bound.
Gaussian Distributions: Known Covariance. Next, we consider Gaussian distributions (H, E), where μ E TR Σ E Raxdd under the assumption that || < R and = 714, Let Gauss( R, d; o) denote this task, where is again the (TV) accuracy. For this problem, we have:
Theorem 45 (Distribution Learning- Gaussian Distributions with Known Covariance). For any sufficiently small a, E > 0 and for all m E 18, we have
Gauss(R, (e, 8 = ô (
d
+ d
n m
aE aEvm
a²m
Proof. Upper Bound. It is known that this family of distribution admits (0.1o)) -colver (under TV distance) of size O(d-log(dR/ log(dR/a)) [BKSW19, Lemma 6.7]. This, together with Theorem 42, gives the upper bound.
Lower Bound. Again, Acharya et al. [ASZ21, Proof of Theorem 12] showed that there exists family Q of isotropic Gaussian distributions with ||사 I O(ylog(1/a)) that is a (aackig under TV distance and its diameter under KL-divergence is at most ((a?) of size ((d). Theorem 42 then gives the lower bound.
We note that this problem has already been (implicitly) studied under user-level approximate-DD d
in [NME22]. 15 who showed that 7mm surprising that our pure-DP bound nearly matches this result, except that we have the extra first term (i.e., d/e).
(I, (e,5 0) S Ō aevm + a²m Again, it perhaps
Gaussian Distributions: Unknown Bounded Covariance. Finally, we consider the case where the covariance also unknown but assumed satisfied < kT. We use Gauss( R, d, k; a) to denote this task.
Theorem 46 (Distribution Learning Gaussian Distributions with Unknown Bounded Covariance).
Let be constant. For any sufficiently small a, > 0 and for all E N, we have
(. (e, = =xx dd ( nym
d
d?
aE a
o²m
Proof. Upper Bound. This follows from Theorem 42 and a known upper bound of (d log(dk/a) d log(dR// a)) on the size of a (0.1a) (under TV distance) of the family [BKSWI9 19, Lemma 6.8).
Lower Bound. Devroye et al. [DMR20) 6 that, for # 2 1 + O(a), there exists a 3a-packing under TV distance whose diameter under the KL-divergence most O(a²) of size (dd)). This, together with Theorem 42, gives the lower bound.
We remark that simple see that Gaussian with unbounded mean or unbounded covariance cannot be learned with pure (even user-level) DP using finite number of examples.
"Orr equivalently that V known; since such an assumption sufficient to rotate the example to isotropic positions.
AAttually Narayanan al. [NME22] studied the estimation problem. but is not hard to see that an algorithm for mean estimation also provides an algorithm learning Gaussian distributions.
"Specificallly, this is shown in [DMR20, Proposition 3.1]: their notation "m" denote the number of non-zero (non-diagonal) entries of the covariance matrix which be set to l2(d?) for purpose.
28


Reviews:
[{"review_id": "zPoWSnL8c4", "reviewer": "Reviewer_Hupm", "summary": "This work develops novel generic algorithms that convert algorithms under item-level differential privacy (DP) to user-level DP in the low user sample regime, where each user holds a small number of samples, and obtains new results for user sample complexity (aka., min # users to achieve a certain utility of the algorithm). Based on a novel observation that connects sample perfect generalization to local deletion DP, the proposed algorithm under approximate-DP leads to tight user sample complexity bound for several privacy-preserving machine learning applications. The proposed algorithm under pure-DP is based on the exponential mechanism with a new score function and it also leads to tight and improved user sample complexity bounds for several applications.", "questions": "This might be a stupid question. How is the randomness of the private algorithms considered in this work? Do we assume that a random seed is given?\n\nIs line 9 in Algorithm 1 for removing the polylog dependence on $n$ users in the proof?\n\nWhat are the major differences between pure DP and approximate DP in changing from item-level DP to user-level DP? What are the challenges that make the techniques to convert from item-level DP to user-level DP for approximate DP not applicable to pure DP?\n\nIn which applications/problems is the user sample complexity bound from this work not tight?\n\nMinor issues: $x_{1, n}$ in line 31 $\\Rightarrow$ $x_{1, m}$. \n\n$\\mathbf{x}_{T}$ in line 265 \n\n$\\Rightarrow$ $\\mathbf{x}_{-T}$. \n\nMight be clearer to add “for some chosen constant $\\kappa$” to the end of line 272. ", "limitations": "Limitations (esp. the runtime of the proposed algorithm) are well discussed in the paper.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The improved user sample complexity results and proposed algorithms under both approximate DP and pure DP are interesting and are widely applicable to several important privacy preserving machine learning tasks. \n\nThe paper is well presented and intriguing to read. The notations are well-defined throughout the paper. Problems and results are well defined and clearly stated. The contribution and overview of techniques are well summarized. \n\nThe paper tries hard to give the readers intuition on the techniques developed and does a good job explaining the observations.\n\nThe paper also explains well its difference from the previous works, especially why the techniques from previous works do not apply when the number of samples per user is low.\n", "weaknesses": "The only places that might need a bit more explanation is why local deletion DP is natural to consider based on sample perfect generalization results, and how local deletion DP is then converted to user level DP?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and questions. Please find our answers below.\n\n## Re randomness: \nWe are in the standard setting in DP where we assume that the algorithm can sample fresh random coins and that these random coins are not accessible by the adversary.\n\n## Line 9 Algorithm 1: \nThis line of the algorithm is not required if we want just the privacy guarantee. However, we need it due to a technicality in our utility analysis: we need to make sure that in the “good” event, we run $\\mathbb{A}$ on a random subset of the input samples so that the distribution of the output is (almost) the same as running $\\mathbb{A}$ on i.i.d. samples from $\\mathcal{D}$.  (See the proof of Lemma 18 for more details.) \n\n## Pure-vs-Approximate DP: \nThe main challenge in using the approximate-DP approach for pure-DP is that the propose-test-release technique does not work for pure-DP. Namely, even if we know that the local (deletion) sensitivity of a function is very small up to a very large distance, it is still not possible to add a small noise and achieve pure-DP. (For pure-DP, we would need either a global bound or at least a bound that is “smooth” enough.)\n\nAt a higher level, the best sample complexity for pure-DP also often contains a privacy-dependent term that does not converge to zero as $m \\\\to \\\\infty$. (For example, the first term $d/\\\\epsilon$ in Theorem 3.) On the other hand, such a term does not appear in approximate-DP. Such a behavior suggests an inherent difference between the two settings. \n\n## Tightness: \n\nThis is a great question. We do not have a general characterization of the tightness of our results, although, as explained in the Introduction, our results are nearly tight for many problems (up to dependencies on $\\\\log(1/\\\\delta), \\\\epsilon$). Interestingly, however, the approximate-DP approach is *not* tight for PAC learning for some classes. For example, taking the class of all functions on $\\\\mathcal{X} = [d]$, our pure-DP upper bound (Theorem 3) is in fact better than our approximate-DP upper bound (Corollary 2) for some regime of parameters ($\\\\epsilon=1,\\\\alpha=1/m, m \\\\leq d$ gives $O(d)$ vs $\\\\tilde{O}(d\\sqrt{m})$). We will add more discussion on this in the revision.\n\n\nThank you for pointing out the typos; we will fix them in the revision.\n"}, {"review_id": "5CtTCSaIuW", "reviewer": "Reviewer_pUZs", "summary": "This paper establishes new generic conversions from item-level DP algorithms to user-level DP algorithms, continuing a line of work initiated by Ghazi, Kumar, and Manurangsi. Previous state-of-the-art due to BGHILPSS '23 shows that any item-level $(\\varepsilon, \\delta)$-DP algorithm using N samples can be converted to a user-level DP algorithm with $n = O(\\log(1/\\delta)/\\varepsilon$ users and $m \\approx N^2$ samples per user. The present submission observes that this previous result is just one end of a spectrum of possible item-to-user-level conversions, and generalizes it to hold for the full range of $1 \\le m \\le N^2$. That is, the main result (somewhat simplifying) shows a conversion from any item-level DP algorithm to a user-level DP algorithm with $n \\approx (N/\\sqrt{m}) \\cdot \\log^{O(1)} ({1/\\delta})/\\varepsilon^2$ users and $m$ samples per user. In addition to generalizing the conversions of GKM'21 and BGHILPSS'23 to the regime of few examples per user, this result unifies previous work on specific problems such as mean estimation, stcochastic convex optimization, and discrete distribution learning for which a $n \\propto 1/\\sqrt{m}$ dependence was previously observed.\n\nAs an auxiliary result, the paper also gives a tight characterization of the sample complexity of user-level pure $(\\varepsilon, 0)$-differentially private PAC learning in terms of the probabilistic representation dimension.", "questions": "- The prior work of BBGHLISS'23 also claims to have resolved the open question of CLNRW'16 on DP vs. perfect generalization, but I believe they did so in a weaker sense. Namely, they only showed that every DP algorithm admits a PG algorithm solving the same problem; whereas this submission shows that the original DP algorithm itself perfectly generalizes. This is an important distinction that I think is worth highlighting.\n\n- I wasn't really able to match the informal description of the proof of Lemma 13 (lines 214-226) to the formal proof in appendix B. In particular, the new contribution of the formal proof seems to be to apply a nice symmetrization argument to the previous results of RRST'16/BGHILPSS'23 that held for a one-sided version of the DP -> PG connection. Does the informal argument in the main body of the text reflect what's going on under the hood of these prior results? And if so, does it suggest a simpler / more direct argument that doesn't go through max-information etc.?\n\n- I'd suggest renaming \"local deletion DP\" (Definition 15) to something else due to the (unfortunate) naming collision that may suggest this definition has to do with local DP. Maybe something like \"pointwise deletion DP\"?", "limitations": "Limitations (overlapping with points identified as weaknesses) are nicely described as directions for future work in the conclusion.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This is a nice contribution to the emerging general theory around user-level DP learning, in particular, building a bridge between one thread of work on general item-level vs. user-level connections and another on understanding the sample complexity of user-level DP for specific problems.\n\n- As part of their analysis, the authors more carefully investigate the connection between DP and perfect generalization, in particular giving a clean solution to an old open question of CNLRW'16 that is likely to have further applications.", "weaknesses": "- The main technical ideas going into the algorithms and their analysis appeared in prior work on this topic. (E.g., the passage from DP to perfect generalization appears in GKM'21/BGHILPSS'23, and a similar PTR-based argument appeared in KL'21/GKKMMZ'23). This paper's technical contribution is to carefully refine each of these steps and piece them together in the right way.\n\n- Neither of the paper's new algorithms is computationally efficient in general, even if the task admits a computationally efficient item-level DP learner. Note that this is the case for previous general item-to-user-level conversions as well.\n\n- The final main result (Theorem 9) is somewhat messy to state and potentially suboptimal in its dependence on $\\log(1/\\delta)$ and $\\varepsilon$. This is likely in part due to stacking various generic tools (DP => PG, amplification by subsampling, PTR) that could potentially be avoided with a simpler algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and questions. Please find our answers below.\n\n## Re [BBH+23]:\nThank you for your suggestion. We will add this to the discussion. We also wish to note that their reduction loses a roughly square factor in the sample complexity. That is, if we start with a DP algorithm with sample complexity $n$, then applying the reduction from [BBH+23] will result in a perfect generalization algorithm with sample complexity $\\\\approx n^2$ (for the same utility guarantee). On the other hand, we do not incur such a loss, since we prove the property directly on the original algorithm.\n\n## Description vs formal proof of Lemma 13:\nWe think that the description still roughly reflects the full proof. Namely, while we do indeed use the one-sided perfect generalization result from [BBH+23], we are not aware of a proof using that directly without the aforementioned strengthened version of McDiarmid’s inequality. In particular, in our proof, we need Lemma 35 which is proved using Theorem 29; the latter is indeed the aforementioned result from [Kut02] mentioned in the outline. We will make sure to also mention the use of the one-sided result in the revision for clarity.\n\n## Local deletion DP:\n\nThank you for your suggestion. We will consider changing the name in the revision.\n"}, {"review_id": "O5skjBkunm", "reviewer": "Reviewer_KRgS", "summary": "This paper studies the problem of user-level differential privacy, giving a generic conversion for any item-level approx DP algorithm to a user-level approx DP algorithm, and a clipped scoring function that allows application of the exponential mechanism to obtain user-level privacy. All results are applicable in the few-samples-per-user setting, significantly extending results beyond the case in which users have enough samples to solve a task independently. ", "questions": "There's a related result from BGHILPSS23 showing that approx DP implies perfect generalization, following from the connections approx DP => one-way perfect generalization, one-way perfect generalization => replicability, replicability => perfect generalization. However, my understanding is that their result is weaker than the one given in this work because it 1) requires correlated sampling and is therefore not necessarily computationally efficient and 2) the transformation from replicability to perfect generalization changes the output distribution of the DP algorithm, whereas the result in this work proves perfect generalization for the same approx DP algorithm A. Is this a correct comparison of these results, or is there any notable distinction between the resulting PG parameters obtained from both results?\n\nIt would be very interesting to understand whether the computational inefficiency is in fact necessary. ", "limitations": "Yes, the authors adequately address societal impact of their work. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This work significantly improves our understanding of when user-level privacy is achievable, though it is unfortunate the transformation from item-level to user-level privacy isn't computationally efficient. The intermediate result that approx DP => sample perfect generalization is also a meaningful contribution to our understanding of the relationships between useful algorithmic stability notions. \n\n", "weaknesses": "In terms of substance, I think this work is very strong, but the clarity of presentation could maybe be improved a little. That said, I do think the authors did a good job overall of assisting the reader with interpretation of their results. \n\nNotes:\n\nThe first paragraph of the technical overview for the approximate DP result was a bit confusing.\n\nPage 4: “it is sufficient get new user-level pure-DP”\n\nPage 6: \t“For example, g is not Lipschitz everywhere anyway anymore”\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and questions. Please find our answers below.\n\n## Re [BBH+23]:\nThe main distinction between the two results is that we show that if an algorithm satisfies DP, then that very same algorithm also satisfies PG. On the other hand, [BBH+23] shows that if an algorithm satisfies DP, then there is *a different algorithm* that satisfies PG and maintains a similar utility guarantee.\n\n\nThe parameters of the two approaches are different. In [BBH+23], the reduction loses a roughly square factor in the sample complexity. That is, if we start with a DP algorithm with sample complexity $n$, then applying the reduction from [BBH+23] will result in a PG algorithm with sample complexity $\\\\approx n^2$ (for the same utility guarantee). On the other hand, we do not incur such a loss, since we prove the property directly on the original algorithm.\n\n## Re computational inefficiency:\n\nWe agree that this is a great question and we had included it in our conclusions as well (lines  347-353). We feel this is necessary for such a generic reduction; however, we do not have a formal proof of such a statement, as it is quite challenging (in general) to prove computational lower bounds for DP algorithms.\n"}, {"review_id": "GkDM7i5q65", "reviewer": "Reviewer_iTdY", "summary": "This work designs a generic algorithm that transforms an item-level DP algorithm into a user-level DP one with $\\sqrt{m}$ improvement in user complexity. It recovers previous user complexity bounds on various learning tasks, and the transformation works in the example sparse setting, i.e. does not require sufficient number of samples per user.", "questions": "1.  I wonder if it is possible show a $\\Omega(\\sqrt{m})$ lower bound as well under some non-trivial conditions?\n2.  In Theorem 16, how sufficiently small are $\\varepsilon', \\delta'$? Is it for some fixed small constant, or some expression that depends on other parameters?", "limitations": "Limitations and potential impacts are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. Compared to Ghazi et.al. 2021 which requires sufficient number of samples per user, the generic transformation from item-level to user-level DP in this work applies to the example scarce setting. The authors derive new bounds in the example-scarce setting for PAC learning.\n2. The authors recover the $\\sqrt{m}$ factor in many known bounds for various learning tasks through a generic algorithm. \n3. The writing is clear and easy to follow.", "weaknesses": "1. The proposed algorithm is not computationally efficient.\n2. Although $\\sqrt{m}$ matches the tight bounds for a variety of problems, it seems that the lower bound is not addressed in this work.\n3. In Theorem 16, it might be helpful to be specific about how sufficiently small should $\\varepsilon', \\delta'$ be. \n\nMinor issues:\n1. In Lemma 4, I feel that it should be $A\\simeq C$ instead of $B$ at the end of the line.\n2. In line 242, it appears that the $\\delta'$ inside the big O should be $\\delta''$, and there should be a factor of $(1+e^{\\varepsilon''})$ for the $\\delta''$ term according to Lemma 4 (even though it does not affect the final bound on $\\delta'$).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and questions. Thank you also for pointing out the typos. We will fix them in the revision. Please find our answers below.\n\n## Re $\\\\sqrt{m}$ lower bound:\n\n\nInterestingly, such a lower bound does not necessarily hold for all problems, even natural ones. For example, taking the class of all functions on $\\\\mathcal{X} = [d]$, our pure-DP upper bound (Theorem 3) is in fact better than our approximate-DP upper bound (Corollary 2) for the following regime of parameters: $\\\\epsilon=1,\\\\alpha=1/m, m \\\\leq d$, which gives $O(d)$ vs $\\\\tilde{O}(d\\\\sqrt{m})$. Thus, the $\\\\sqrt{m}$ lower bound does not hold in this setting. We will add more discussion on this in the revision.\n\n## Re Privacy Parameters in Theorem 16:\n\n\nThe $\\\\epsilon’, \\\\delta’, \\\\epsilon’ r \\\\sqrt{m \\\\log(n/\\\\beta\\\\delta’)}$ values here only have to be smaller than some absolute constant independent of the other parameters. \n\n\n"}]

Author rebuttal:

Meta-review: This paper gives a generic conversion for any N-sample item-level approx DP algorithm to a user-level approx DP algorithm where each user has m samples. Prior work with such a general conversion required each user having N^2 samples making it practically meaningless and useful bounds were known only for several specific problems. This paper applies to any number m and requires $\tilde O(n/\sqrt{m})$ users. This significantly extends our understanding of the relationship of sample complexity of item level and user level DP algorithm. An additional transformation for algorithms based on the exponential mechanism is given. Along the way the paper derives a number of other interesting results such as a strong connection between so called perfect generalization and DP. The main limitation of the work is that the transformation does not lead to efficient algorithms (even if applied to an efficient algorithm).
Decision: Accept (oral)