Learning discrete distributions: user vs item-level privacy

Much of the literature on differential privacy focuses on item-level privacy, where loosely speaking, the goal is to provide privacy per item or training example. However, recently many practical applications such as federated learning require preserving privacy for all items of a single user, which is much harder to achieve. Therefore understanding the theoretical limit of user-level privacy becomes crucial. We study the fundamental problem of learning discrete distributions over $k$ symbols with user-level differential privacy. If each user has $m$ samples, we show that straightforward applications of Laplace or Gaussian mechanisms require the number of users to be $\mathcal{O}(k/(m\alpha^2) + k/\epsilon\alpha)$ to achieve an $\ell_1$ distance of $\alpha$ between the true and estimated distributions, with the privacy-induced penalty $k/\epsilon\alpha$ independent of the number of samples per user $m$. Moreover, we show that any mechanism that only operates on the final aggregate should require a user complexity of the same order. We then propose a mechanism such that the number of users scales as $\tilde{\mathcal{O}}(k/(m\alpha^2) + k/\sqrt{m}\epsilon\alpha)$ and further show that it is nearly-optimal under certain regimes. Thus the privacy penalty is $\mathcal{O}(\sqrt{m})$ times smaller compared to the standard mechanisms. We also propose general techniques for obtaining lower bounds on restricted differentially private estimators and a lower bound on the total variation between binomial distributions, both of which might be of independent interest.

Differential privacy is studied in two scenarios, local differential privacy [Kasiviswanathan et al., 2011, Duchi et al., 2013, and global differential privacy [Dwork et al., 2006]. In this paper, we study the problem under the lens of global differential privacy, where the goal is to protect the privacy of the algorithm outcomes. Before we proceed further, we first define differential privacy.
Definition 1. A randomized mechanism M : D → R with domain D and range R satisfies (ε, δ)differential privacy if for any two adjacent datasets D, D ∈ D and for any subset of output S ⊆ R, it holds that P r[M(D) ∈ S] ≤ e ε P r[M(D ) ∈ S] + δ.
If δ = 0, then the privacy is also referred to as pure differential privacy. An important aspect of the above definition is the notion of neighboring or adjacent datasets. If a dataset D is a collection of n items x 1 , x 2 , . . . x n , then typically adjacent datasets are defined as those that differ in a single item x i [Dwork et al., 2006].
However, in practice, each user may have many items and may wish to preserve privacy for all of them. Hence, this simple definition of item-level neighboring datasets would not be enough. For example, if each user has infinitely many points of the same example, then the bounds become vacuous.
Motivated by this, user-level privacy was proposed recently. Formally, given s users where each user u has m u items x 1 (u), x 2 (u), . . . x mu (u), then two datasets are adjacent if they differ in data of a single user. For example, in the simple setting when each user has m samples, if two datasets are adjacent in user-level privacy, they could differ in at most m items under this definition of item level privacy.
Since user-level privacy is more practical, it has been studied in the context of learning machine learning models via federated learning [McMahan et al., 2017, Wang et al., 2019, Augenstein et al., 2019. The problem of bounding user contributions in user-level privacy in the context of both histogram estimation and learning machine learning models was studied in Amin et al. [2019]. Differentially private SQL with bounded user contributions was proposed in Wilson et al. [2019]. Understanding trade-offs between utility and privacy in the context of user-level global DP is one of the challenges in federated learning [Kairouz et al., 2019, Section 4.3.2].
Our goal is to understand theoretically the utility-privacy trade-off for user-level privacy and compare it to the item-level counterpart. To this end, we study the problem of learning discrete distributions under user and item level privacy.

Learning discrete distributions
Learning discrete distributions is a fundamental problem in statistics with practical applications that include language modeling, ecology, and databases. In many applications, the underlying data distribution is private and sensitive e.g., learning a language model from user-typed texts. To this end, learning discrete distributions under differential privacy has been studied extensively with various loss functions and non-asymptotic convergence rates [Braess and Sauer, 2004, Kamath et al., 2015, Han et al., 2015, with local differential privacy [Duchi et al., 2013, Kairouz et al., 2016, Acharya et al., 2019a, Ye and Barg, 2018, with global differential privacy [Diakonikolas et al., 2015, Acharya et al., 2020, and with communication constraints [Barnes et al., 2019, Acharya et al., 2019a, among others.
Before we proceed further, we first describe the learning scenario. Let p be an unknown distribution over symbols 1, 2, . . . , k i.e., i p i = 1 and p i ≥ 0 for all i ≤ k. Let ∆ k be the set of all discrete distributions over the domain [k] := {1, 2, . . . , k}.
Suppose there are s users indexed by u, and let U denote the set of all users. We assume that each user u has m i.i.d. samples X m (u) = [X 1 (u), X 2 (u), . . . , X m (u)] ∈ X := [k] m from p 1 . Let X s = [(u, X m (u)) : u ∈ U] ∈ X s be the collection of user and sample pairs. The case when each user has samples from different distributions is an interesting open question, but it is not within the scope of this paper.
For an algorithm A, letp A (X s ) be its output, which is a mapping from X s → ∆ k . The performance for a given sample X s is measured in terms of 1 distance, 1 (p,p A ) = k i=1 |p i −p A i (X s )|. We measure the performance of the estimator for a distribution p by its expectation over the algorithm and samples i.e., We define the user complexity of an algorithm A as the minimum number of users required to achieve error at most α for all distributions: The min-max user complexity is Well known results on non-private discrete distribution estimation (see [Kamath et al., 2015, Han et al., 2015) characterize the min-max user complexity as follows: Let A ε,δ be the set of all (ε, δ) differentially private algorithms. Similar to (1), for a differentially private algorithm A, let S A m,α,ε,δ be the minimum of samples necessary to achieve α error for all distributions p ∈ ∆ p with (ε, δ) differential privacy. We are interested in characterizing and developing polynomial-time algorithms that achieve the min-max user complexity of (ε, δ) differentially private mechanisms.

Previous results
The min-max rate of learning discrete distributions for item level privacy, which corresponds to m = 1, was studied by Diakonikolas et al. [2015] and Acharya et al. [2020]. They showed that for any (ε, δ) estimator: The goal of our work is to understand the behavior of S * m,α,ε,δ w.r.t. m. We first discuss a few natural algorithms and analyze their user complexities.
One natural algorithm is for each user to sample one item and use known results from item level privacy. Such a result would yield, . 1 We extend our algorithms to the case when users have different number of samples in Appendix E.

3
The other popular algorithms are Laplace or Gaussian mechanisms that rely on counts of users. For a particular user sample X m (u), let N (u) = [N 1 (u), . . . , N k (u)], be the vector of counts. A natural algorithm is to sum all the user contributions to obtain the overall count vector N , where the count of a symbol i is given by Finally a non-private estimator can be obtained by computing the empirical estimate: To obtain a differentially private version of the empirical estimate, one can add Laplace or Gaussian noise with some suitable magnitude. To this end, we need to compute the sensitivity of the empirical estimate.
Recall that two datasets D, D are adjacent if there exists a single user u such that N (u, D) = N (u, D), and N (v, D) = N (v, D ) for all v ∈ U and v = u. Therefore the 1 sensitivity is and the 2 sensitivity is A widely used method is the Laplace mechanism, which ensures (ε, 0) differential privacy.
Definition 2. Given any function f that maps the dataset to R k , let the 1 sensitivity ∆(f ) = max D,D adjacent ||f (D) − f (D )|| 1 . The Laplace mechanism is defined as: where Y i are i.i.d random variables drawn from Lap(∆f /ε).
The Gaussian mechanism is defined similarly with 2 sensitivity and Gaussian noise. We first analyze Laplace and Gaussian mechanisms under user-level privacy.
Lemma 1. For the Laplace mechanism, given bŷ Similarly if ε ≤ 1, for the Gaussian mechanism, given bŷ The proof follows from the definitions of the Laplace and Gaussian mechanisms, which we provide in Appendix A for completeness. The non-private user complexity term O(k/(mα 2 )) decreases with the number of samples from user m, but somewhat surprisingly the additional term due to privacy O(k/αε) is independent of m. In other words, no matter how many samples each user has, it does not help to reduce the privacy penalty in the user complexity. This could be especially troublesome when m gets large, in which case the privacy term dominates the user complexity.

New results
We first ask if the above results on Laplace and Gaussian mechanisms are tight. We show that they are by proving a lower bound on a wide class of estimators that only rely on the final count. The proof is based on a novel coupling technique with details explained in Section 4 .
Theorem 1. Let ε + δ < c, where c is determined in the proof later. Let A be any (ε, δ) mechanism that only operates on summed counts of all users N = [N 1 , N 2 , . . . N k ] directly. Then, The above lower bound suggests that any algorithm that only operates on the final count aggregate would incur additional cost for user complexity independent of m due to privacy restriction. However it may not apply to algorithms that do not solely rely on the counts, which justifies the need to design algorithms beyond straightforward applications of the Laplace or Gaussian mechanisms.
We proceed to design algorithms that exceed the above user-complexity limit. The first one is for the dense regime where k ≤ m: on average each user sees most of the high-probability symbols. The second one is for the sparse regime where k ≥ m: users don't see many symbols. By combining the two of them, we get the following improved upper bound on min-max user complexity.
Theorem 2. Let ε ≤ 1. There exists a polynomial time algorithm (ε, δ)-differentially private algorithm A such that The algorithm in Theorem 2 assumes that all users have the same number of samples. In Appendix E, we modify it to the setting when users have different number of samples. The sample complexity is similar to (3), with m replaced by m median , the median of number of samples per user.
Finally we provide an information theoretic lower bound for any (ε, 0)− pure differentially private algorithm: Theorems 2 and 3 resolve the user complexity of learning discrete distributions up to log factors and the δ-term in privacy. It would be interesting to see if Theorem 3 can be extended to nonzero values of δ. In the next two sections, we first analyze the lower bounds and then propose algorithms.

Lower bounds
The Ω(k/(mα 2 )) part of the user-complexity lower bounds in Theorem 1 and 3 follows from classic non-private results (2). Therefore in this section we focus on the private part.

(ε, δ)-lower bound for restricted estimators
We first start with the lower bound for algorithms that work directly on the counts vector N = [N 1 , N 2 , . . . , N k ], even though the learner has access to {N (u) : u ∈ U}. This motivates the definition of restricted estimators, which only depends on some function of the observation rather than the observation itself.
Definition 3 (f -restricted estimators). Let f : X s → Y which maps users' data to some domain Y. We say that an estimatorθ is f -restricted if it has the formθ(X s ) =θ (f (X s )) for some functionθ .
We generalize Assouad's lemma [Assouad, 1983, Yu, 1997 with differential privacy and the restricted estimators using the recent coupling methods of Acharya et al. [2018Acharya et al. [ , 2020. These bounds could be of interest in other applications and we describe a general framework where they are applicable.
Let X be some domain of interest and P be any set of distributions over X . Assume that P is parameterized by θ : P → Θ ∈ R d , i.e. each p ∈ P can be uniquely represented by a parameter vector θ(p) ∈ R d . Given s samples from an unknown distribution p ∈ P, an estimator θ : X s → Θ takes in a sample from X s and outputs an estimation in Θ. Let : Θ × Θ → R + be a pseudo-metric that measures estimation accuracy. For a fixed function f , let A f be the class of f -restricted estimators. We are interested in the min-max risk for (ε, δ)-differentially private restricted estimators: We need two more definitions to state our results.
Definition 4 (f -identical in distribution). Given a function f and two random variables X and Y , we say they are f -identical in distribution if f (X) and f (Y ) have the same distributions, denoted by Y ∼ f X. If X ∼ p and Y ∼ p , then we can also say p ∼ f p .
Definition 5 (f -coupling). Given a function f and two distributions p, q, we say that random variables (X, Y ) are an f -coupling of p and q if X ∼ f p and Y ∼ f q. When f is the identity mapping, then an f -coupling is same as standard coupling.
We make the following observation for restricted estimators: since we can only estimate the true parameter θ through some function f of the observation X s , then any random variable Y s such that f (Y s ) has the same distribution as f (X s ) would yield the same distribution for restricted estimatorŝ θ. Thus, ifθ could distinguish two distributions p 1 , p 2 from the space of product distributions P s := {p s : p ∈ P}, then it should also be able to distinguish p 1 ∼ f p 1 and p 2 ∼ f p 2 . We are able to prove tighter lower bounds because p 1 , p 2 (potentially outside of P s ) could be harder to distinguish than the original distributions p 1 , p 2 .
With this intuition, we show a generalization of Assouad's lower bound in Theorem 4. It relies on an extension of the Le Cam's method [Le Cam, 1973, Yu, 1997. The proofs are in Appendix B.1. For two sequences X s and Y s , let d h (X s , Y s ) = s i=1 1 X i =Y i . For a distribution p ∈ ∆ k , let Mul(m, p) denote the multinomial distribution.
Theorem 4 ((ε, δ)-DP Assouad's method for restricted estimators). Let V := {±1} k be a hypercube. Consider a set of distributions P V := {p ν : ν ∈ V} over X . Assume loss satisfies that ∀u, v ∈ V: (4) For each i ∈ [k], define the following mixture of product distributions: The proof of Theorem 1 follows from Theorem 4. We provide a sketch here and details in Appendix B.2. In our problem setting, X = [k] m is the domain and P is the set of multinomial distributions P = {Mul(m, p) : p ∈ ∆ k }. The parameter we are trying to estimate is the underlying p and the loss is 1 distance.

(ε, 0)-lower bound for the general case
We provide the complete proof of Theorem 3 in Appendix B.3 and sketch an outline here. We use [Acharya et al., 2020, Corollary 4], which is based on Fano's method and applies to ε ≤ 1. For each ν ∈ {±1} k/2 we define p ν the same way as (5), except by [Yu, 1997, Lemma 4] we restrict V to be the maximal subset of {±1} k/2 such that each pair u, v ∈ V is at least k/6 apart in Hamming distance, and |V| ≥ exp(c 0 k/2) =: M where c 0 = h(1/3) and h is the binary entropy function.

Algorithms
We first propose an algorithm for the dense regime where k ≤ m. In this regime, on average each user sees most of the high-probability symbols. However, this algorithm does not extend directly to the sparse regime when k ≥ m. In the sparse regime, we augment the dense algorithm regime with another sub-routine for small probabilities. Both algorithms could be extended to the case when users have different number of samples (see Appendix E).

Algorithms for the dense regime
We first motivate our algorithm with an example. Consider a symbol with probability around 1/2. If m is large, then by the Chernoff bound, such a symbol has counts in the range  with probability ≥ 1 − δ. Hence, neighboring datasets differ typically with √ m counts. However, in the worst case, they could differ by m and hence standard mechanisms add noise proportional to m.
We propose the following alternative method. The count for symbol i ∈ [k] can take values from 0, 1, . . . , m and is distributed according to Bin(m, p i ). Thus, we can learn this distribution Bin(m, p i ) itself to a good accuracy and then estimate p i from the estimated density of Bin(m, p i ).
We propose to use the private hypothesis selection algorithm due to Bun et al.
[2019] to learn the density of the Binomial distribution. It gives a score for every hypothesis using the Scheffe algorithm [Scheffé, 1947] and then privately selects a hypothesis using the exponential mechanism based on the score functions. For completeness, we state private hypothesis selection algorithm in Algorithm 1. We state the following guarantee on private hypothesis selection from Bun et al. [2019].
Lemma 2 (Bun et al. [2019]). Given d distributions p 1 , p 2 , . . . , p d and n independent samples from an unknown distribution p, such that min i 1 (p i , p) ≤ α, Algorithm 1 returns a distribution p i such that E[ 1 (p i , p)] ≤ 4α, with probability ≥ 1 − β, if the number of samples satisfies, Furthermore, Algorithm 1 is (ε, 0)-differentially private. Our proposed algorithm for learning Binomial distributions is given in Algorithm 2. We compute a cover of Binomial distributions and use Algorithm 1 to select an estimate of the underlying Binomial distribution. We return the parameter of the Binomial distribution as our estimate for the underlying parameter. Translating the guarantees on total variation distance between binomial distributions to difference of parameters requires a bound on parameter estimation from the binomial density estimation. To this end, we show the following theorem, which might be of independent interest.
Due to space constraints, we provide the proof in Appendix C. We show empirically that the bounds in Theorem 5 should hold by estimating the 1 distance between Bin(m, 0.01) and Bin(m, 0.011). Figure 1 shows that the 1 distance grows linearly with m when m is small, and grows linearly with √ m when m is large, which illustrates our bounds in Theorem 5. Combining Lemma 2 with Theorem 5 yields guarantees for Algorithm 2. Its sample complexity and utility are given by Theorem 6. We provide a proof in Appendix D.1.
Applying Algorithm 2 independently on each symbol i to learn p i , we obtain Algorithm 3, an (ε, δ)-private algorithm that learns unknown multinomial distributions under the dense regime. Its user complexity is given by Theorem 7. We provide the proof in Appendix D.2.
Theorem 7 (Dense regime). Let k ≤ m and ε ≤ 1. Algorithm 3 is (ε, δ)-differentially private and has sample complexity given by, Theorem 7 has a better dependency on m than that of the Laplace or Gaussian mechanism. Furthermore, even if the number of samples tends to infinity, the number of users is least O( √ k).

Algorithms for the sparse regime
We now propose a more involved algorithm for the sparse regime where m ≤ k. In this regime, users will not see samples from many symbols. A direct application of the private hypothesis selection algorithm would not yield tight bounds in this case. We overcome this by proposing a new subroutine for estimating symbols with small probabilities, say p i ≤ 1/m. In this regime, most symbols appear at most once. Hence, we propose each user sends if a symbol appeared or not i.e., Hence, if we get a good estimate for this quantity, then since p i ≤ 1/m, we can use it to get a good estimate of p i . We describe the details of this approach in Algorithm 4. Its user complexity and utility guarantee are given by Lemma 3, whose proof is in Appendix D.3.
Algorithm 4 is (ε, 0)-differentially private and returnsp such that with probability at least 1 − β, Combining the private hypothesis selection algorithm and the subroutine described in Algorithm 4, we obtain an algorithm for the sparse regime, shown in Algorithm 5. We first estimate p using the private hypothesis selection algorithm. If for some i, the estimated probability is too small, we run Algorithm 4 to obtain a more accurate estimate of p i . Theorem 8 gives the user complexity guarantee of Algorithm 5. We provide the proof in Appendix D.4.

Conclusion
We study user-level privacy and its theoretical limit in the context of learning discrete distributions.
We discover a fundamental limit in terms of user complexity for Laplace or Gaussian mechanisms and propose a nearly-optimal algorithm which surpasses this limit. It would be interesting to investigate A Proof of Lemma 1 Note thatp i = (N i + Z i )/(sm). Thus: The first term is upper bounded by k/(sm) from classic learning bounds for discrete distribution, which can be obtained by applying Jensen's and Cauchy-Schwartz inequality, and noting that For Laplace mechanism, Z i ∼ Lap(2m/ε), we have E|Z i | = 2m/ε. Thus: For Gaussian mechanism, Z i ∼ N (0, σ 2 ) where σ 2 = 4 log(1.25/δ)m 2 /ε 2 . Using Jensen's inequality we have E|Z i | ≤ E[Z 2 ] = σ. Thus: Setting the right hand side of the above inequalities to be ≤ α and rearranging the terms we obtain the desired lower bound on s.

B Lower bounds B.1 Proof of Theorem 4
The proof of Assouad's Lemma relies on Le Cam's [Le Cam, 1973, Yu, 1997] method, which provide lower bounds for min-max error in hypothesis testing. Let the hypothesis classes be P 1 ⊆ P and P 2 ⊆ P, which are two disjoint subsets of distributions. Letθ : X s → {1, 2} be an estimator of the indices, which receives s samples and predicts whether the samples come from P 1 or P 2 . We are interested in the worst case error probability: Theorem 9 ((ε, δ)-DP Le Cam's method for restricted tests). Let p s 1 ∈ co(P s 1 ) and p s 2 ∈ co(P s 2 ) where co(P s i ) represents the convex hull of P s i := {p s : p ∈ P i }. Let (X s , Y s ) be an f −coupling between p s 1 and p s 2 with E[d h (X s , Y s )] = D. Then for ε ≥ 0, δ ≥ 0, any f -restricted (ε, δ)-DP hypothesis testing algorithmθ must satisfy: Proof. The first term follows from the classic Le Cam's lower bound (see [Yu, 1997, Lemma 1]). For the second term, let (X s , Y s ) be an f -coupling of p s Pr(X s = x s , Y s = y s ) Pr(θ(X s ) = p 2 |X s = x s ) ≥ x s ,y s ∈W Pr(X s = x s , Y s = y s ) Pr(θ(X s ) = p 2 |X s = x s ).
Adding the two inequalities and rearranging the terms we obtain: which yields the desired lower bound.
We now have the necessary ingredients for the Assouad's lower bound. The final step is to apply the classic Assouad's Lemma [Yu, 1997]: Theorem 10 (Assouad's Lemma). Consider a set of distributions P V indexed by the hypercube V := {±1} k . Using the same definitions as in Theorem 4, ∀i ∈ [k], let φ i : X s → {−1, 1} be test for p s +i and p s −i . Then for any estimatorθ: Note that the summand in (6) is the error probability of hypothesis testing between the mixtures p s +i and p s −i . Applying Theorem 9 completes the proof.

B.2 Detailed proof of Theorem 1
Proof. Using the construction of P V as in (5). For p v ∈ P V , let q v = θ(p v ) be the underlying discrete distribution over k symbols. Then for u, v ∈ V: This is because one different coordinate between q u and q v leads to l 1 distance of 12α/k. Therefore τ = 6α/k. Define the mixtures as: It is helpful to look at the underlying distribution of all samples from users.
Note that p s ±i , q s ±i are not necessarily product distributions. By [Acharya et al., 2020, Lemma 14 ], there exists a coupling (U sm , V sm ) between q sm +i and We construct X s = [X 1 , ..., X s ] and Y s = [Y 1 , ..., Y s ] using this coupling (each X i , Y i ∈ R k which is the count of each symbol).
For each realization of U sm , V sm , suppose there are l different coordinates, i.e. d h (U sm , V sm ) = l, we move all different coordinates to the front so that only the first l/m ≤ l/m + 1 users would have different data. Name the rearranged sequence as (U ) sm , (V ) sm . Then we let user u get data from the m(u − 1) + 1 to mu coordinates of (U ) sm and (V ) sm respectively and compute the counts of each symbol to obtain X s , Y s . Therefore: Rearranging the coordinates of U sm , V sm would not change the total count N , and hence (X s , Y s ) is an N -coupling. As a result: Choose α = min{ 0.1k 60s(ε+δ) , 1 3 }, we have: When ε + δ ≤ 0.07: Setting the left hand side to be at most α and rearranging the terms, we obtain the desired lower bound for s.

B.3 Fano's Lower bound
In this section we provide learning lower bound for pure differential privacy using Fano's method. First we provide a theorem for restricted estimators like the one we proposed for Assouad's, which might be of general interest.
Theorem 11 (ε-DP Fano's lower bound for restricted estimators). Given a family of distributions P over X parameterized by θ : P → Θ, and letθ be an f -restricted estimator. Let V = {p 1 , ..., p M } ⊆ P such that for all i = j: Proof. The first term of (7) follows from the non-private Fano's inequality. We just need to prove the second term.
Proof of Theorem 3. We apply Theorem with f as the identity mapping. In this case it is the same as [Acharya et al., 2020, Theorem 2].
Assume k is even. From Yu [1997], there exists V ⊆ {−1, 1} k/2 and a universal c 0 > 0 such that |V| ≥ exp(c 0 k/2), each pair at least k/6 apart in Hamming distance. Given α ∈ (0, 1/6), define a family of multinomial distributions P ν which consists of the following distributions indexed by ν = (ν 1 , ..., ν k/2 ) ∈ V: For v ∈ V, let q v = θ(p v ) be the underlying k-ary distribution. Thus for each pair of distributions p u , p v from this family we have 1 (θ(p u ), θ(p v )) = 1 (q u , q v ) ≥ 12α/k · k/6 = 2α. Furthermore: Since f is set to be the identity, we just need to design a coupling with appropriate Hamming distance for each pair p s u , p s v , u, v ∈ ν. To this end we need the following lemma from den Hollander [2012]: Lemma 5 (Maximal coupling, den Hollander [2012]). Given distributions q 1 , q 2 over some domain X , there exists a coupling (X s , Y s ) between q s 1 and q s 2 such that From Lemma 5 there exists a coupling (X s , Y s ) between p s u and p s v such that E[d h (X s , Y s )] = s · d T V (p u , p v ). Using Pinsker's inequality, we have: Then apply Lemma 11: Note that this holds for all α. Choose α = min{ 1 6 , k sm } and α = min{ 1 6 , c 0 k 200s √ mε } respectively we get: Given desired accuracy α, setting sup p∈P E[ 1 (p, p)] ≤ α gives the desired user complexity bound.

C Bounds on total variation between binomial distributions
We divide the proof of Theorem 5 into two parts. We prove the upper bound in Lemma 6 and the lower bound in Lemma 9. We first prove an upper bound on the total variation distance between binomial distributions in terms of the parameters.
Secondly, since 1 distance of product distributions is at most the sum of 1 distances, Finally, by Pinkser inequality and the fact that KL divergence of product distributions is the sum of individual KL divergences, where the last inequality follows by observing that D(Ber(q)||Ber(p)) = q log q p Combining (9), (10),and (11) yields the lemma.
Lemma 7. Let c be a constant. If mp < c and p ≤ 1/2, then Proof. By definition, We first consider the case q ≥ p. Simplifying the above bound, ≥ e −1.5c min(m(q − p), 0.5). x ≤ 1/2. (e) follows by the bound on p. For q ≤ p, (a) follows from the Bernoulli inequality: (1 + x) n ≥ 1 + nx for x ≥ −1. The last inequalities are similar to the last two inequalities for q ≤ p case. Combining the above two results, we get Lemma 8. Let c > 2, m ≥ 3, and p ≤ 1/2. If mp ≥ c, then Since q lies in between p and q, 1 (Bin(m, p), Bin(m, q)) ≥ 1 (Bin(m, p), Bin(m, q )). Furthermore, observe that By [Adell and Jodrá, 2006, Proposition 2.3], for any two binomial distributions, Similarly, Since m − k is an integer, m − k ≥ 1. In order to bound the above quantity further, we first lower bound Binomial coeffcients.

D.4 Proof of Theorem 8
Parameters: We first define few parameters. Let ε = ε 8 min(k,m) log 1 240 , and γ = mα 8k . Let c = 4/m. Algorithm: For every symbol we first calculate the probability using the algorithm in Theorem 6 with ε = ε , α = α and error probability β. If the estimated probability is less than 2/m, we use the algorithm from Lemma 3 with ε = ε , α = α , γ = γ, and error probability β. Let p be the output of the first step and the p be the output of Lemma 3. The error of the algorithm is Hence, for a sufficient large constant b, if Note that since k ≥ m, the above bound implies that s ≥ b √ m, hence the bound also satisfies conditions in Lemma 3.
Differential privacy: We first provide the privacy guarantee for this algorithm. First observe that since p , p →p is a Markov chain, by the postprocessing theorem it suffices to provide privacy guarantee for releasing p , p . Consider releasing one of them, say p . For any two neighboring datasets differ in at most min(m, k) symbols. Let these datasets be D and D and S(D, D ) be the set of symbols where they differ. For these datasets, Pr(p k |D) Pr(p k |D ) .
Hence it suffices to apply strong composition theorem for this subset of size min(m, k) and the rest of the proof is similar to that of [Kairouz et al., 2017, Theorem 3.4]). The proof is similar for p and hence the result. Utility: To analyze the utility, we divide the symbols into three sets A 1 = {i : p i ≥ 4 m }, A 2 = {i : 4 m ≥ p i ≥ 1 4m }, and A 3 = {i : p i ≤ 1 4m }. Utility-large: Consider the set A 1 with symbols whose probability is greater than 4/m, for such a symbol, by Theorem 6, with probability ≥ 1 − β, Hence p ≥ p − α p m > 2 m . Hence, for such a symbol with probability ≥ 1 − β, Utility-medium: Consider the set A 2 with symbols whose probability in [1/4m, 4/m]. For such a symbol, then with probability ≥ 1 − 2β, Utility-small: Finally consider symbols whose probabilities are smaller than 1/4m, for these symbols, with probability ≥ 1 − β, and hence p ≤ p + α m ≤ 3/2m ≤ 2/m. Hence only the second algorithm is used. Hence with probability ≥ 1 − 2β, the error is at most, Summing over all symbols yield, Hence, by the union bound, with probability with 1 − 20kβ, Therefore in expectation,

E Extensions
In this section, we modify our algorithms for the scenario when users have different number of samples. Let m max be a known upper bound on the number of samples a user has. For a value m, let s m be the number of users such that m u ≥ m. Letm := m median be the median values of m u . We first state the main result, which is an analog of Theorem 2.
Theorem 12. Let ε ≤ 1. There exists a polynomial time algorithm (ε, δ)-differentially private algorithm A such that First we use ε/2 privacy budget findm, a private estimate ofm, andŝ, an estimate of sm (the quantile ofm). We only keep the users with at leastm samples, and selectm samples from each of them. Hence we reduce the problem to the case when users have the same number of samples. Then we modify the algorithms for both the dense and sparse regimes so that they are differentially private even if the number of samples of a particular user changes. We use the remaining privacy budget for the modified algorithms. The privacy guarantee follows by the composition theorem.
We first provide the algorithm for privately estimatingm and the quantile of estimatedm, which serves as a stepping stone for extending our algorithms to variable number of samples per user.
By the tail bounds of Laplace distribution and the union bound, for each i with probability 1 − β, Furthermore, for any cumulative sets, Let D be a dataset of size sm drawn i.i.d. from P . Define the following quantities which serve as empirical estimates of P (W 1 ): P (W 1 ) :=τ := 1 s |{x ∈ D : x ∈ W 1 }|, Pm(W 1 ) := τm := 1 sm |{x ∈ D : x ∈ W 1 }|.
Let ζ > 0 be the approximation parameter. Consider the following function: Output a random hypothesisĤ according to the following distribution: 2ε .
Proof. We modify the algorithm for the sparse regime as follows.
Let Um be the users who have at leastm samples. Similar to (14), we findp such that, where Z = Lap(1/ε). So we have: From Lemma 10, with probability at least 1 − β, the first term is upper bounded by: