Mean Estimation with User-level Privacy under Data Heterogeneity
Authors: Rachel Cummings
Vitaly Feldman
Audra McMillan
Kunal Talwar
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
heterogeneous data
heterogeneous users
mean estimation
statistical inference
meta analysis

Abstract: A key challenge in many modern data analysis tasks is that user data is heterogeneous. Different users may possess vastly different numbers of data points. More importantly, it cannot be assumed that all users sample from the same underlying distribution.  This is true, for example in language data, where different speech styles result in data heterogeneity. In this work we propose a simple model of heterogeneous user data that differs in both distribution and quantity of data, and we provide a method for estimating the population-level mean while preserving user-level differential privacy. We demonstrate asymptotic optimality of our estimator and also prove general lower bounds on the error achievable in our problem.

Mean Estimation with User-level Privacy under Data Heterogeneity
Rachel Cummings
Vitaly Feldman Apple Cupertino, CA 95014
Department of Industrial Engineering and Operations Research
Columbia University
New York, NY 10027
rac22398colume www.io.lmmaaaa.c...ommmm edu
Audra McMillan
Kunal Talwar Apple Cupertino, CA 95014 ktalwarGapple. com
Apple Cupertino, CA 95014
audra. daaiaammmmmlaanappl...oomm
Abstract
A key challenge in many modern data analysis tasks is that user data is heteroge- neous. Different users may possess vastly different numbers of data points. More importantly, cannot be assumed that all users sample from the same underlying distribution. This is true, for example in language data, where different speech styles result in data heterogeneity. In this work we propose simple model of heterogeneous user data that differs in both distribution and quantity of data, and we provide method for estimating the population-lewe mean while preserving user- level differential privacy. We demonstrate asymptotic optimality of our estimator and also prove general lower bounds on the error achievable our problem.
Introduction
Many practical problems statistical data analysis and machine learning deal with the setting in which each user generates multiple data points. In such settings the distribution of each user's data may be (somewhat) different and, furthermore, users may possess vastly different numbers of samples. This issue is one the key challenges in federated learning (20) leading considerable interest in models and algorithms that address the issue.
As an example, consider the task of next-word prediction for keyboard. Different users typing keyboard may have different styles of writing, leading different distributions. There are aspects of the language that are common to all users, and likely additional aspects of style that are common to large groups users. Thus while each user has their own data distribution, there are commonalities to all the distributions, and additional commonalities amongst distributions corresponding to subsets of users. Modeling and learning such relationships between users' distributions crucial for building better global model, as well for personalizing models for users.
The focus of this work is on differrnnially private algorithms for such settings. We assume that there is an unknown global meta-distribution D. For each user i, personal data distribution D; is chosen randomly from D (for example, by sampling set of parameters that define D,). Each user then receives some number h; of i.i.d. samples from D, The goal is to solve an analysis task relative D. with an eye towards better modeling of each D; even when k;; is small. This abstract setting
Part of this work was completed while the author was Apple.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

can model many practical settings where the relationships between the Dj's take different forms. Indeed the standard loss in federated learning is the unweighted average over users of a per-user loss function [20] Sec. 3.3.2], which corresponds to learning D. Little theoretical work has been done in this setting and even the most basic statistical tasks are poorly understood. Thus we start by focusing on the fundamental problem of mean estimation in this setting. Specifically, in our model, D is distribution on the interval [0, 1] with unknown mean p and unknown variance oz Further, we assume that D, is simply a Bernoulli distribution with mean p; ~ D.
While the general Dj setting is of interest, there are many settings where users generate Boolean signals. For example, each sample from the Bernoulli distribution could represent whether or not the user has clicked on an ad. Another common example is model evaluation, where the user produces a Bernoulli sample by engaging or not engaging with feature (e.g., phone keyboard next word suggestion, crisis helpline link, search engine knowledge panels, sponsored link in search results, etc.). As a concrete example, language model is used to make the next word suggestions on phone keyboard. new version of this model would be first tested to measure the average suggestion acceptance rate over users. Each user would thus generate a set of independent Bernoulli r.v.' with each individual mean p; corresponding to the model accuracy for the user. Heterogeneity comes from different users typing differently (and hence model accuracy varying across users) and using the keyboard with different frequency. Note that the distribution of model accuracies among users is the meta distribution D in our work. More generally, measuring the average accuracy of a classification model among a large group of users is an important task in itself. Such models are deployed in privacy-sensitiv applications such health and finance. The resulting statistics may need to be shared with third parties or other teams within a company, raising potential user privacy concerns.
Our main contribution is differentially private algorithm that estimates p and Up in this setting. We first study this question in an idealized setting with known Op and no privacy constraints, Here the optimal non-private estimator for p; is simple and linear: it is weighted linear combination of the individual user means with weights that depend on the k 's and on oy. The variance of this estimate ideat = (E; min(ki, o, 2) This expression has a natural interpretation: this is the variance from using min(ki, op²) 2) samples from user and averaging all the Bernoulli samples thus obtained. The restriction on using at most op² samples from each user ensures that the estimator is not too affected by their individual mean pt-
Even in the case where it is known that of = O, the solution is non-trivial and, to the best of our knowledge, optimal private algorithm was previously known. In this case, each user samples from the same distribution, but there may be deviations in the number of samples that each user holds. In the absence of privacy constraints, this setting poses no additional complexity over the case where each user has a single data point, since the data points all come from the same distribution. However, with the requirement of user-level differential privacy, additional care needs to be taken hide all samples from any individual user. In this case, we already need to employ many of the technical tools developed in this work, as we show in Appendix C
We show that under mild assumptions, there is no asymptotic price to privacy (and to not knowing Tp). We provide differentially private estimator for p with variance O(oatea)) Interestingly, the estimator achieving this bound in the private setting is non-linear. Further, we show that ofdeal is near-optimal, under some mild technical conditions.
Our technical results highlight several of the challenges associated with ensuring user-level privacy when data is heterogeneous. For example, the optimal choice of weights for each user contribution itself depends on p and op that we are trying to estimate. Further, we show a novel approach to proving lower bounds for private statistical estimation in the heterogenous setting. Our approach builds on the proof of the Cramér-Ras Rao lower bound in statistics, and we show how privacy terms can be incorporated in this approach show near optimality of our algorithms for nearly every setting of k ss. These tools and insights should be useful for modeling and designing algorithms for more involved data analysis tasks.
Our work lays the foundation for similar model-driven exploration in other settings. There have been attempts to handle heterogeneity by phrasing the problem as meta-learning or multi-task learning 22C See 3.3.3], which implicitly makes some assumptions about the different distributions. Our goal is to start with a more principled approach that makes explicit the assumptions on the relationship between different distributions and use that to derive the algorithm. For example, if were to model the D,'s
2

---

as having means coming from mixture of Gaussians, the estimation of cluster means would be necessary step an EM-type algorithm. Our choice of D; 's being Bernoulli is meant capture discrete distribution learning problems that have been extensively studied in private federated settings. Our techniques are general and would extend naturally to real-valued settings where, e.g., D; is a Gaussian with mean P; and known variance. While we make minimal assumptions on DD our results asymptotically match the lower bounds for the case of D being Gaussian with known variance. Our techniques also extend in natural ways to higher dimensions.
Our main results involve two estimators; non-realisable estimator Pideal that assumes that the mean and variance of DD are known the estimator, and a realisable estimator grealistic that is private with respect to the user's s samples, but not with respect to each user's ss number of samples k; Let Pj be the mean of the k; samples from user i. The estimator prealistic requires input initial, less accurate (e, 6)-DP mean and variance estimators , and vari ance..ó. The main results of this paper can be (informally) summarised follows:
Near optimality of P. Fideal [Theorem 5.1]. For any parameterized family of distributions p > Dy. if the Fisher information of pi is inversely proportional to the variance of pe for all i, and each pú sufficiently well concentrated
Suub-Gaussian is sufficient) then Pedeal is minimax optimal, up to logarithmic factors, among all unbiased estimators of p in the range p 11/3,2/3) The proof of this result involves Cramér-Rao style proof which may be of independent interest.
Near optimality of proaliatic [Theorem 4.1]. mean,,6 and vari a and assuming the max and and median k; are within a factor of (ne/ log n) - 1, then Var Var (realistic) = O(Var(( (Fideal).
Under mild conditions the accuracy of
Lower bound in terms of k; [Corollary 5.5). We give an explicit formula for the minimax optimal error in terms of the sequence k ".. kn and variance oz.
Our main algorithmic results require concentration of the meta-distribution D. We note that in practice, this is not an unreasonable assumption. For example, in the case of model evaluation, it may be be reasonable to assume that a general model has similar accuracy for the vast majority of users, or formally, that the model accuracy is well-concentrated.
1.1 Related Work
Frequency estimation the example-level privacy model has been well-studied the central [1)
and local models [8 [4] 7 I1 2]. Similarly, private mean estimation has been well studied in
both central 22 16 and local models p [S] of privacy. These works have focused on providing
example-level privacy (rather than user-level) in settings with homogeneous data, i.e., i.i.d samples.
23 recently studied the problem learning discrete distributions in the homogeneous cases (same distribution and same number of samples per user) with user-level differential privacy, and [22] extended such results to other statistical tasks. These works also consider the setting with different number of samples per user although only via reduction to same number of samples by discarding the data of users that have less than the median number of samples and effectively only using the median number of samples from all the other users. This approach can be asymptotically suboptimal for many natural distributions of k is and also likely to be worse in practice. Previously, [27 showed how to build a (user-level) differentially private recommendation system, and (55 showed how to train a language model with user-level differential privacy.
User-level differential privacy in the context of heterogeneous data distributions has been studied in the constant K; setting (31). Much of the complexity our setting arises from variation in the k;
values, which makes it challenging to maintain user-level privacy while leveraging the additional data points from users with a large number of data points. The challenges to optimization due to data heterogeneity have also been studied: [34, and Eichner et al. [133 study the approach of using different models for different groups from a convex optimization point-of-view. Mathematically; similar issues are addressed in meta-analysis 6 33), where the heterogeneity comes from different studies instead of different users. The non-private approach of inverse variance weighting that we recap in Section 3 is standard in that context.
3

---

2 Model and Preliminaries
Let D be distribution on [0, 1] with (unknown) mean and variance oZ. We assume a population of n E N users, where each user E [n] has hidden variable ~ DD and k; E N samples a!....,, a miid Ber(pt). That is, the samples of user are i.idd from Bernoulli distribution with parameter pi, which we will denote D; BBrr(p,). Assume without loss of generality that individuals are sorted by their k; so that 1 2 ... 2 kn- The samples of and hidden variables pt of each user unknown to the analyst, and we start with assuming that the k k's publicly known. In Appendix D we extend our results to the general case where the kj 's are also private.
The analyst's goal is to estimate the population mean p with an estimator of minimum variance in manner that is differentially private with respect to user data (p, and {xr }). Each user provides their own estimate of their p; to the analyst based on their data zz; P; = ,. شッー x?. The analyst can then aggregate these (possibly along with other information) into her estimate of p.
Let us first give some intuition for the distribution of these fú- Let D(k) be the distribution that first samples p; D, then samples " 22 Ber(p:) and finally outputs p. - Ty. The following lemma (proven in Appendix A) shows that the variance of P. is larger than og and transitions from p(1 10--)) p) to of k increases (equivalently as p. concentrates around p.).
Lemma 2.1. For all distributions DD supported on [0, with mean p and variance of of p(1 p)- Further, [})) = and Var(D(k)) = tb((1 - p) + (1 - +) oz.
We assume that k; and ps are independent, so the amount of data an individual has independent of her data distribution. This is crucial for the problem setup: in order for learning from the heterogeneous population to be advantageous, there must a common meta-distribution shared across all individuals in the population, rather than dnttadisttibuttin only for each fixed k.
2.1 Differential Privacy
Differential privacy (DP) 12 informally limits the inferences that can be made about an individual result of computations a large dataset containing their data. The definition of DP requires pairwise neighbouring relation between datasets, and DP algorithms ensure that differences between all pairs of neighboring datasets should be hidden by the private algorithm.
In our setting where users have multiple data points, we must distinguish between user-level and event-level DP. The former considers D and D' neighbours if they differ all data points associated with a single user, whereas the latter considers D and D' neighbours only if they differ on a single data point, regardless of the number of data points contributed by that user. Naturally, user-level DP provides substantially stronger privacy guarantees, and is often more challenging to achieve from a technical perspective. In this work, we will provide user-level DP guarantees.
Definition 2.2 (User-level (e, D)ffeffrrettt Privacy [21). Given & 2 0, 8 E [0, 1] and a neigh- bouring relation ~, randomized mechanism M
2 x x Xha + y is (e, 5) diffeerrettill Xhn, and all events E. C Y, Pr[M(D) E E < e Pr[M((D)) E E] + 5, where the probabilities are taken over the random coins of M. When 8 O, we refer to this as eddifferential privacy.
private if for all neighboring datasets D D' E 2
One standard tool for achieving e-differential privacy is the Laplace Mechanism. For given function / to be evaluated on a dataset D, the Laplace Mechanism first computes J(D) and then adds Laplace noise which depends on the sensitivity of f. defined for real-valued functions as f = maxp, neighbors ID) - f(D'). The Laplace Mechanism outputs ML(D, f(D) Lap(Af/e) /e) and is (c, DDP
3 A Non-Private Estimator
We begin by illustrating the procedure for computing an optimal estimator f in the non-private setting. The general structure of the estimator will be the same in both settings. The analyst will compute the

---

Algorithm 1 Non-private Heterogeneous Mean Estimation
Input: number of users nt, number of samples held by each user (ki,..., kn) (ki 2 k(t1), user-level estimates (P1,-.. p.
1: Initial Estimates
2: p Fiitial Li=9n/
9n/ z.
3: OF log nlog n 1-1) E Eedgeloon) -p)}²
4: Defining weights
5: for = log n to 9m/10do do
6: Compute 07- E
(
- (pinitial + (1 R, )0
1/32
1/83 7: Zygloga
8: Final Estimate
9:
return preallatic Di=logn WiPt
population-level mean estimate p as a weighted linear combination of the user-level estimates p. The key question how to derive the weights so that individuals with more reliable estimates (i.e., larger k;) have more influence over the final result.
Let of be the variance of pj. In idealized setting where the of are all known, the analyst can minimize the variance of the estimator by weighting each user's 's estimate P; proportionally to the inverse variance of their estimate. The weights normalised to ensure the estimate is unbiased. This approach yields the following estimator, which is optimal in the non non-private setting [17]
Fideal = - W where w
1/07
(1)
In practice, the oîs are unknown, so the analyst must rely on estimates assign weights. Fortunately, the user-level variance of can be expressed as function of k; and the population statistics and of as shown in Lemma 2.1
- (p-
)o
Now, and of are also unknown but since they are population statistics, we can use simple estimators to obtain initial estimates. These initial statisties can then used to define the weights, resulting in refined estimate of the mean p. Specifically, as outlined in Algorithm we split users into three groups. The log n individuals with the most data are used to produce an estimate of Var(D((1og which serves proxy for o.. The 1/10th of individuals with the least data are used produce an initial estimate of the mean p. The remaining 9n/10- log individuals
used to produce the final estimate. We split the individuals into separate groups to ensure the initial estimates and the final estimate are independent so we can easily obtain variance bounds on the final estimate. The specific sizes of the three groups are heuristic, the exact fraction 1/10 is not necessary. Under some mild conditions on D, and if n is large enough, the error incurred by prealistic is within a constant factor of the error incurred by the ideal estimator Fideal
4 A Framework for Private Estimators
We now turn to our main result, which is framework for designing differentially private estimators for the mean p of the meta-distribution D. We discussed in Section the need for initial estimates of and of to weight the contributions of the users. In the non-private setting, there canonical, optimal choices of these estimators; the empirical mean and empirical variance. In the private setting, these choices are not canonical, and different estimators may perform better in different settings. There a considerable literature exploring various mean and variance estimators for the homogeneous,
PIn the non non-privee privviie setting. this restriction is without loss of generality since the optimal estimator takes this form. In the private setting this is still netrmoptimal; see Section for more details.
"This can be observed by viewing the non con-private setting as a simplified version of the setting studied in Section R which proves near-optimality of (truncated) linear estimators for this problem.
5

---

single-data-poiee point-per per--serrrrrrreeee setting. As such, we leave the choice of the specific initial mean and variance estimators as parameters of the framework. This allows us focus on the nuances of the heterogeneous setting, not addressed in prior work. In Appendix F we give specific pair of private mean and variance estimators that provably perform well in our framework.
As in the previous section, we will define two estimators: a ideal estimator pideoa (only implementable all the of are known), and a realisable estimator prealisti, The main result in this section (Theorem 4.1 is that under some mild conditions and assuming is sufficiently large, there exists an (c, 5) estimator Drealistic (Algorithm 2 such that for some constant C, Var Var(Feellistio) I C Var(p.
4.1 The Complete Information Private Estimator
As in Section we begin with a discussion of the ideal estimator the or were known. This ideal estimator pedest has a similar form to gideal with some crucial differences. The first main distinction that Laplace noise is added to achieve DP, where the standard deviation of the noise must be scaled to the sensitivity of the statistic. A natural solution would be to add noise directly to the non non-private estimator pideal but the sensitivity of this statistic is too high. In fact, the worst case sensitivity of gideal is 1, which would result in the noise that completely masks the signal. Thus, the first change /iin we make is to limit the weight of any individual's contribution by setting ue; Σ min (1/3/////a)
for some truncation parameter T. Intuitively, the parameter T controls the trade-off between variance of the weighted sum of individual estimates (which is minimized by assigning high weight to low variance estimators) and variance of the noise added for privacy (which is minimized by assigning roughly equal weight to all users).
We make one final modification to lower the sensitivity of the statistic. Inspired by the Gaussian mean estimator of (21] we truncate the individual contributions iú into a sub-interval of [o, 1]. The truncation intervals [a:. b,] are chosen to be as small as possible (to reduce the sensitivity and hence the noise added for privacy), while simultaneously ensuring that P. E [[,, bi] with high probability (to avoid truncating relevant information for the estimation). order to achieve this, we need a tail bound on the distribution D. To maintain generality for now, we assume there exists known function fb (n, o 3) that gives high- high-probabiiity concentration guarantees of p. around p, and is defined such
that Pr Vi, I0: - pl S f (n, o B)) 2 1 B. Appendix G presents a more detailed discussion of the structure of these concentration functions and how they may be estimated if they are unknown to the analyst.
We can now describe the full information, ideal, estimator pideal:
cideal
E w/ p.l6: + Lap( max, wi lb (o)-),))),
Pe
where [il]; denotes the projection of iú onto the interval (a,, b,] and p p pki (n, o), B).
b fi (n, oi B), and w
min /o.) Σラ= min (1/3(1///.r/////
(4)
We would like to choose the truncation parameter T to minimise the variance of the resulting estimator:
Var = Ei ( + max; (lb
(5)
Although we do not know Var (p.(1) exactly, do know that p. p, with high probability, and thus we can approximate Var (p.()))))) with og, Throughout the remainder of the paper, we will assume that 3 is chosen such that of < Var((p]]:) Thus, we will approximate the optimal truncation parameter by
(w) 11 - 22
T = arg min (wt) Pot + max
2
arg min
("'ر min (iiinn//a.///)33 En
+ max, min(1/af T / lb. 1a.aa
(6)

---

We'll show in Section that under some conditions on the Fisher information of D(k), Pednall is optimal up to logarithmic factors among all private unbiased estimators for heterogeneous mean estimation.
Example 1. As simple example, suppose that p case, an asymptotically optimal non non-private estimator averages all the > = (n n log n) available samples. It can be shown that this gives us an unbiased estimator with standard deviation O Vn log A naive sensitivity- -based noise addition method will give us privacy error O ( ) since the weight of the first user in this average (L/ log Our truncation based algorithm will truncate the ith user's contribution to a range of width / us privacy error O (eenloogn) In other words, for constant E, privacy does not have an asymptotic cost. We remark that in this case, any uniform weighted average will incur asymptotically larger standard deviation (2 ).
(2.3), o - 1/ and k; = [1]. In this
log k.
V Applying our algorithm would then give
4.2 Realizable Private Heterogeneous Mean Estimation
Our goal in this section is design realizable estimator Proalistic that is competitive with the ideal estimator pideal, As in the non-private setting, divide the individuals into three groups. The first group, consisting of the n/ 10 individuals with the lowest A; will be used to compute the initial mean estimate phnitial, The log n individuals with the largest k; will be used to compute the initial variance estimate 23- These initial estimates will be plugged into expressions to compute o?. 0g and by for the remaining individuals log n + S I 9n/10. As in the non-private setting, the specific sizes of these groups heuristic. The important thing is that the size of the first two groups are large enough that the resulting mean and variance estimates are sufficiently accurate, and the last group contains (n) -users whose k; is above the median.
Since the estimate pinitial used in d; and b, may had additional enror up to a, shift these estimates by an additive a to account for this error. Next, all of these intermediate estimates and the lser- mean estimates pú from users log cutoff T the optimal weights Wi for each user log + S i S 9n/10, 10, and finally the estimator grealistic as weighted sum of the truncated user-level estimates pilla plus Laplace noise. This procedure is presented in full detail in Algorithm 2
i < 9n/10 /10 will be used compute the optimal weight
For the remainder of this section, we turn to establishing the accuracy requirements of mean, s and variance,, , that ensure that the error of grealistic is within a constant factor of the error of p gideal Theorem 4.1. For any c >> 0, E [0, 1). Algorithm is (c, 8)-D. If.
mean..5 is such that given n/ 10 samples from D, with probability 1 1 3 Ip pinitial 1hr (n, 8) and Pinitial (1 pinitial)
<
[1p(1 - p), 3p p)].
variance,, is such that given log n samples from D(k), with probability 1 - 8, o7 E [Var(D(k)), (Var(D())),
the kis are such that by ka/2
<
n/2-Ingn
log n
then with probability 1 23, Var S.C. C. Var(Ffdeal) for some absolute constant C.
full proof of Theorem 4.1 is given in Appendix B we present intuition and a proof sketch here. The first two conditions of Theorem [.J ensure that the mean and variance estimates are sufficiently accurate to use in the remainder of the algorithm. Notice that the initial estimates do not need to be especially accurate. In fact, provided p not too close to 0 or 1, the DP mean estimator that simply adds noise to the sample mean achieves the right accuracy (see Lemma F.1 for details). In Appendix[] we also give a DP variance estimator that achieves the desired accuracy guarantee using only log n samples, under some mild conditions (Lemma F.4). Thus the set of mean and variance estimators that satisfy the accuracy requirements of Theorem 4. are non-empty. We note that the constants 1/2,3/2 3/2 and 8 in Theorem 4.1 are not intrinsic; any constant multiplicative factors will suffice. We also note that the specific sizes of the three groups outlined in Algorithm 2 are heuristic and can be varied to ensure that the initial estimator achieves the required accuracy.
[
7

---

Algorithm 2 Private Heterogeneous Mean Estimation
Input: (e, 0)DP mean estimator , (e, 0)-P) variance estimator variance,, number of users number of samples held by each user (ki..... hn s.t. k; 2 k(+1), user-level estimates
(Fi.-.. .P)). error guarantee on m > 0, and desired high probability bound 3 E [0, 1].
1: Initial Estimates
2: pinitill mean, ( 9n xx)
3: og v (F1 Plogn)
4: Defining weights and truncation
5: for log n + to 9n/10 10 do
6: Compute 07 E; (piniiial (penitial (2) []} (1 - 10
7: á Pe Ainitial a - 1 (n, 3)
8: bj Pe
pinitial + a + 1 (n, o
9:
9n/10 ( 1ox n4 min( xf
T + 4155000
min(1/2 12
10: T = arg mint
E EEmiig m
11: for log + 1 to 9n/ /10 do
min (1/8 8
12:
j min 1//9..7-/8)
13: Final Estimate
min(1/37 F- (0,) 6,
14: A = max 9,/11000
D min 1183. 18:
15: Sample Y ~ Lap (
16: return Prealistic
9n/10 >
lii-oogne logn41
n+1
Pila; +Y
The final assumption ensures that the log n users with the most data can not estimate the mean of meta-distribution alone. Note that up to logarithmic factors, this condition simply requires that the number of data points held by the user with the most data is at most n times the number of data points of the median user. If n is large, then this is unlikely to be limiting factor.
The main distinction between gideal and prelistiic the use of the output of the estimators mean, and variance,, 5 estimate of. a; and b, Thus, the main component of the proof of Theorem 4.1 is to show that the conditions stated in the theorem are enough to ensure that o,² ā. and b, are sufficiently accurate.
Lemma 4.2. Given Piuitial og. and kú, define o.² Finitial (1 piuitial) + 1--1 G Under the h;
F. D.
conditions of Theorem 4.1 for all i logn, we have o:² E , 9.50 and (b. a.l < 4|b: ail-
detailed proof of Lemma i.2 presented in Appendix B Lemma 4.2 implies that the individual variance estimates used in the weights, and the truncation parameters are accurate up constant multiplicative factors. The main ingredient left then is to show that using only a subset of the population in the final estimate only affects the performance up to multiplicative factor. Under the assumption that Emedd
a/2 a/2-loge
where of Var(şi) and o2 Rmed
Var(Pn/2) then
log n
kmnc p(1 p) + kieed )0
a/2-1ogg log
O Oemaxe"
We this to show that for any truncation parameter
T. Σ ( 2)
4 Σ
I Using this, along with the bounds on estimated quantities from Lemma 4.2 we show that with high probability, the variance of the our estimator grealistic is within constant
9m/10
s=log n+1 mint o7 o,
factor of Var(5)dea)), as given in Equation (5).
We remark that this framework is amenable to being performed in federated manner if one has private federated mean and variance estimators. Steps (6) (8) and Step (12) can be performed locally.
Steps (IO) and the final sum in Step (16) would need to be altered to fit the federated framework.
8

---

We'll see in Appendix D that it is sufficient to replace Step (TO) with an estimate of __ (the inverse standard deviation of the user with the log n-th most data). The final step is then simple addition
olog
with output perturbation, which can be performed in a federated manner (e.g., 124 20
In Appendix DJ we extend this result to the case where k;s are private and unknown to the analyst (Algorithm 3 Theorem D.Ip. We'll need considerably more machinery in this setting where both the sensitivity of the final estimator and the truncation parameter T are data dependent.
5 Near Optimality and Lower Bounds
In Section 4
we showed that the variance of our realisable private estimator pa Proalistic is within a constant of that of the complete information estimator Pideal In this section, we will show that in fact, Preulistic performs as well (up logarithmic factors) the true optimal private estimator. We'll Illl also give a lower bound on the performance of the optimal estimator in terms of the kg This will give us some intuition into the types of distributions of kg that benefit from this refined analysis.
5.1 Minimax Optimality of prealistic
The goal of this section is to show that the estimator prealistic discussed in Section 4.2 is minimax optimal up to logarithmic factors. In light of Theorem 4.1] it suffices to show that the estimator pideal is minimax optimal up to logarithmic factors. Let P be parameterized family of distributions p - Dp, where E[Dy] = p and D, is supported on [o, 1]. For p E [0, 1] and k E N, let pp.a be the probability density function of (k).
Our lower bound will show that the estimation error must consist of a statistical term and privacy term. Such a lower bound thus must generalize a statistical lower bound. We will rely on the Cramer-Rao approach to proving statistical lower bounds; as we show, is particularly amenable to incorporating privacy term. This approach relates the variance of any unbiased estimator of the mean of a distribution to the inverse of the Fischer information; the proof naturally extends the case where we are given samples from set of distributions with the same mean but different variances, as is the case in our setting. For many distributions of interest, e.g., Gaussian and Bernoulli, the Fischer information of single sample is the inverse of the variance, and we make that assumption for D,. We also assume that the D, has sub-Gaussian tails. Thus, as long as the set of permissible meta-distributions includes distributions with this property, e.g., included truncated Gaussians, lower bound applics.
Theorem 5.1. Let P be parameterized family of distributions p + Dr and suppose that for all p E [0, and k E N, the Fisher information of 6p & is inversely proportional to the variance, (k)));
[( a log (1)) (x) 0( v(r(2)
(8)
and for all p. n
and 3 E 1133. $b, (n, .3.1)) 9) O(Var(D)(())), then VaIvie(n) (Rideal) = Ō min De 1/3.2/33
max
(arreejj) (M)))
M, unbiased Pe 113322333
Further, under the conditions of Theorem 4.1
max [aarvietnl,er (Tr
(realistic
min M, unbiased pc 11/3,22/33
max [Var
pE(L (
We will prove Theorem 5.1 in three steps. The following class of noisy linear estimators, NLE, will act as intermediary in our proof. The notation o; denotes Var(z,), which accounts for the randomness in generating Ti.
NLE
{My (x; w) Er W + Lap( max; wyrz) |ww [0, Em wa = 1}.
Similar to gideal this class of estimators is not realizable since only have access an estimate of o; Var (D, (k:)). Additionally, the estimators in NLE are not necessarily c-DP.
The proof Theorem 5.1 has three main steps outlined below. The proof of each Lemma is contained in Appendix F. The first step is shown in Lemma 5.2 which shows that the weights used gldaa are optimal (i.c., variance-minin minimizing) among all estimators in the set NLE.

---

Lemma 5.2. Given Ps Dp(ki) with variance of for all i E [n]] and w E [0. such that
Ei=1 w, let Di=1 W;P; + Lap( max, wios ) The variance of p minimized by the following
min 11/0 1/1 /o.} for some
weights: "i Σj= min mwnml/a/ma000. (1/a)//////))))
Since the threshold 7 in Pedeal was chosen to minimize Var(fedeal), then we know that the weights W. in ddeel are optimal.
Now, let us turn to the second and main component of the proof of Theorem 5.1 Lemma 5.3
formalises the statement that an estimator inside the class NLE minimax optimal among unbiased estimators. That is, for any unbiased estimator M, there exists estimator Mm. E NLE with lower worst-case variance.
Lemma 5.3. Let be a parameterized family of distributions p H D, and suppose that M 10, + [00, is an e-DP estimator such that for all p E [1/3, 2/3], (1) M is unbiased, pa pmr(p) and (2) the Fisher information of &p.k: . is inversely proportional to the variance Var Var(DD((i))
[6 log Pp.k. (I:))² (xt)dr; = 0 (av( ) then there exists an estimator Msl E NLE such that
(1/33/11/32/// Varvie[n),
(Mx))] - 0 O/maxpe(1/3.2/)) (at
The final component needed for the proof of Theorem 5.1 is a translation from the estimators in NLE, which are not e-DP to the corresponding e-DP estimator. For any weight vector w, we can define an e-DP estimator by truncating the data point I; and calibrating the noise appropriately:
pt (m. Lapp( max, 2 fD' (n.o
(1 Inii w) Ei
wi wil
p---p (n,07.9)
Provided f (n, 3). = Var(D(k:)), the estimators MTL have approximately the same variance as the corresponding element of NLE, but are slightly biased. This is formalized in the following lemma.
Lemma 5.4. For any distribution D, n (DVar(D(k)) then for any w E [o, 11"h such that Σ,= wn = 1, we have Var M (Tr :w) =
and B E [0, 1], if for all ke, f (n, 3p:33)
Var(M
O(Var(Mall :w)). Further, the bias of Mrm. is at most 3.
Finally, we have the tools to prove the main theorem in this section, Theorem 5.1
min max [VarD, (M)) 2( min MENLE pE(L/3,2/3)
(MI))) Ω
max
Varn, (p(l)))
unbiased pE(1/3/2/3]
pe [1/3,2/3]
Ω max
(Fideal)) Var (Pr
Pel pE(1/3,2/3)
= ς max PE[L/3.2/3)
Vary, (Pe
prealistie
where M. NLLE has the same weights as Pideal The equalities follow from Lemmas
5.3 5.2 5.4
and Theorem respectively.
5.2 Minimax Lower Bound on Estimation Rate
In addition to establishing the near optimality of prealistic we will also give a lower bound on minimax rate of estimation in terms of the parameters ... ,,, and of. Note that we can view the truncation of the weights w; as establishing an effective upper bound on k; Given ki, .., ,k N, and > 0,
A + min(ka..))
let k- = arg mink (> m)) Intuitively, in the case that or = 0, we want to use as many samples possible, but one user contributing many samples leads to larger sensitivity and thus privacy cost. Limiting to himax the number of samples per user allows us to limit the sensitivity to be about Wmaz (1/ Viime)) ). Since w; is proportional to the number of samples used, the variance when using at most k samples per user is the above expression being minimized. Our lower bound below is close to this value for reasonable k ss.
Corollary 5.5. Given k1, knn N. and o.. there exists family of distributions Dp such that
6" -n min(ks,k') 0²
min max M, unbiased pE (E/33.2//3]
... xx)] 2 Ammin
Er /ey 3y² }).
10

---

References
[1] Jayadev Acharya and Ziteng Sun. Communication complexity in locally private distribution estimation and heavy hitters. arXiv preprint arXiv:/905: /888, 2019.
[2] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Hadamard response: Estimating distributions privately, efficiently, and with little communication. volume 89 of Proceedings of Machine Learning Research, pages 1120-1129. PMLR, 16-18 Apr 2019.
[3] Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan. Differentially private simple linear regression, 2020.
[4]
Hilal Asi and John C Duchi. Instancc-optimmality in differential privacy via approximate inverse sensitivity mechanisms. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin,
editors, Advances in Neural Information Processing Systems, volume 33, pages 14106-14117 Curran Associates, Inc., 2020. URL https: htttps::/procceeingss wtw.eeeeddnnnn....r........ee.ee wtw.rippssccppppee//ae/eepppeeep Paper .df.
file/ a220119666441110002722eeeaaaaaaa
[5] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protec- tion against reconstruction and its applications in private federated learning, 2019.
[6] Michael Borenstein, Larry V Hedges, Julian PT Higgins, and Hannah R Rothstein. Introduction to meta-analysis. John Wiley & Sons, 2021.
[7] Wei-Ning Chen, Peter Kairouz, and Ayfer Özgür. Breaking the communication communictioo-pivaay-ccuaayyy trilemma. arXiv preprint arXiv:2007.1 17007, 2020.
[8] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirly-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1191-119,, Phoenix, USA, 25-28 Jun 2019. PMLR. http:http://rroeeeee
mmlr
1uc.ii99.hhhmll]] html
[9] John C Duchi, Michael Jordan, and Martin J Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182-2)) 2018.
[10] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the Forty-Firs Annual ACM Symposium on Theory of Computing, STOC '09, page 371 371-380, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781 10888555550...
[11] Cynthia Dwork and Aaron Roth. The Algorithmic Foundaatoons of Differential Privacy, volume 9. 2014. URL /tttp://dx... www.dd.........oooooooooooo 1ttg//0..1511/04000000443
[12] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. volume Vol. 3876, pages 265-284, 01 2006. doi: 10.1007/ 11681878 14.
[13] Hubert Eichner, Tomer Koren, Brendan Mcmahan, Nathan Srebro, and Kunal Talwar. Semi- cyclic stochastic gradient descent. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pages 1 1764-1773. PMLR, 09-15 Jun 2019.
[14] Úlfar Erlingsson, Vasyl Pihur, and Alcksandra Korolova. RAPPOR: randomized aggregat- able privacy-preserving ordinal response. In ACM SIGSAC Conference on Computer and Communications Security, pages 1054-1067, 2014.
[15] Filip Hanzely and Peter Richtárik. Federated learning of mixture of global and local models. arXiv preprint arXiv:2002.055 16, 2020.
[16] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC '10, page 705-714, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 978 450300000
11

---

[17] Joachim Hartung, Guido Knapp, and Bimal Sinha. Statistical meta aecaa-analysis with applications. 08 2008. doi: 10.1002/97804773866447
[18] Justin Hsu, Sanjeev Khanna, and Aaron Roth. Distributed private heavy hitters. In International Colloquium on Automata, Languages, and Programming, pages 461-472 Springer, 2012.
[19] Aaron Johnson and Vitaly Shmatikov. Privacy-preserving data exploration in genome-wide association studies. In Proceedings of the 19th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '13, page 1079-1087, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 978 1750331177
[20] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael L. D'Oliveira, Hubert Eichner, Salim EI Rouayheb, David Evans, Josh Gardner, 7achary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, 7aid Har- chaoui, Chaoyang Hc, Lie Hc, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song. Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1 12200, 2021. ISSN 1935-8237. doi: 10.1561/2200000083, URL http::/dx.doi... org/ / 10. 15 /200000888
[21] Vishesh Karwa and Salil P. Vadhan. Finite sample differentially private confidence intervals. volume abs/1711.0300000 of Innovations in Theoretical Computer Science '18, 2018.
[22] Daniel Levy. Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. In Neural Information Processing Systems (NeurIPS 2021), 2021.
[23] Yuhan Liu, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Michael Riley, Learning discrete distributions: user vs item-level privacy. In H. Larochelle, M. Ranzato, R. Had- sell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, Curran Associates, Inc., 2020. URL https://procceddnng Paper Paff pdf
volume 33, pages
[24] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communiiationn-Fffiieeen Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 1273-1282, Fort Lauderdale, FI., USA, 20-22 Apr 2017. PMLR.
[25] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: //perrevee///
met/forummiddBJJom 120b
[26) Audra McMillan, Adam Smith, and Jon Ullman. Instance Optimal Differentially Private Estimation. preparation, 2022.
[27] Frank McSherry and Ilya Mironov. Differentially private recommender systems: Building privacy into the netflix prize contenders. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 627-636, 2009.
[28] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS pages 94-103, 2007. doi: 10.1 N..1109/FOCS,2000 2007000006666 .66..
[29] Ion Mihoc and Cristina Fātu. Fisher's information measure and truncated normal distributions
(i). Revue d' Analyse Numérique et de Théorie de l'Approximation, 32, 01 2003.
12

---

[30] Frank Nielsen. Cramér-Rao Lower Bound and Information Geometry, pages 18-37. Hindustan Book Agency, Gurgaon, 2013. URL https:://oi...... org/ 1907/900-77980 - 56-922
[31]
Kaan Ozkara, Antonious Girgis, Deepesh Data, and Suhas Diggavi. A generative framework for personalized learning and estimation: Theory, algorithms, and privacy, 07 2022.
[32] Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Shai Shalev-Shwartz and Ingo Steinwart, editors, Proceedings of the 26th Annual Conference Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 819-850, Princeton, NJ, USA, 12-14 Jun 2013. PMLR.
[33] Wikipedia contributors. Meta-analysis - Wikipedia, the free encyclopediaa, 2021. URL https 7/en. wikipedia. org/ w/ index.iddxxxeee http:a/eeeeeettaaaaaaaaaaaaaaaaa line; accessed May 2021].
[On-
stochastic [34] Fan Zhou and Guojing Cong. On the convergence properties of a k-step stochaaii gra- dient descent algorithm for nonconvex optimization. In Proceedings of the Twenty-Seventh Inter- national Joint Conference on Artificial Intelligence, IJCAI-18, pages 3219-3227. International Joint Conferences on Artificial Intelligence Organization, 2018. doi: 10.24963/jjcii.011133 201444477. https//d/dd org 24963// iicai/i/jjai.. 2018/447
13


Reviews:
[{"review_id": "syNATuOn9I_", "reviewer": "Reviewer_8HMZ", "summary": "This paper proposes a method to estimate the population level mean under user-level differential privacy constraints when the user data is different in both distribution and quantity for different users. The main contribution is to build a differentially private method that estimates the mean and variance of the data distribution in a setting where there is an unknown global meta-distribution D and for each user i, a personal data distribution D_i. There is an additional assumption that D_i is simply a Bernoulli distribution. \n\n", "questions": "Could authors explain why the given example (next-word prediction for a keyboard.) is important for privacy perspective? What other applications can be given as example? I'm curious because since there is no empirical evaluation of the proposed method, it is hard to imagine how the proposed approach is applied for different problems.", "limitations": "Between lines 250-253, the authors discuss one limitations of the proposed method. The issue issue when n is not large enough (that is not specified), the log n users with the most data can not estimate the mean of meta-distribution alone. Up to some logarithmic factors, this condition simply requires that the number of data points held by the user with the most data is at most n times the number of data points of the median user. To me, the n could be specified for a better understanding and it could be discussed how that issue can be soled.\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The problem defined in paper where there is distributed datasets from different distributions is an important problem that needs to be addressed. The paper theoretically sounds and mostly well written.\n\nWeaknesses: In my opinion, the discussion in the paper needs to be extended. It is not so clear to me if this problem has been studied before and what are the differences of the proposed approach. The application field can be discussed more broadly as well. In addition to that, the utility analysis of the proposed method is not provided and I'd be curious to see that. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XEIkoDiejG", "reviewer": "Reviewer_Tq3t", "summary": "This paper considers the mean estimation under use-level differential privacy. Specifically, each user data is sampled from the Bernoulli distribution with a different mean p_i and p_i is sampled from a meta-distribution with unknown variance. The goal is to estimate the mean of the meta-distribution with minimal variance. In the ideal setting where the variance of each user's Bernoulli distribution is known, the optimal estimator is given by the average of each user's sample mean weighted by the inverse variance of each user. In the realistic setting, the authors propose an algorithm to estimate the variance of each user first and then apply the inverse variance method.  In the private setting, the authors assume there exists a known concentration function of the meta-distribution (variance is still unknown). To lower the sensitivity, the authors propose to use this concentration function to truncate the sample mean of each user and use some threshold to truncate the weight of each user too. Finally, the authors show that, for sub-Gaussians, the proposed estimator is nearly optimal up to logarithmic factors and does not have extra privacy costs if epsilon is a constant.", "questions": "1. In Theorem 4.1, what would break if the third assumption does not hold? Is this necessary for achieving optimal rates? \n2. Is there an upper bound on the estimation rate for sub-Gaussian meta distribution? \n3. In the initial variance estimator, it seems that we need to know the \\sigma_min, \\sigma_max, and third moment as prior information. Is it possible to avoid this? Can you use the concentration function to help you estimate the variance?\n4. I understand the non-private estimator is unbiased. But in the private setting, the truncation would cause some bias. What is the bias and how is it compared to the variance?", "limitations": "This paper is theoretical and does not have a direct negative societal impact.\n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: 1. The problem setting is interesting and well motivated by giving examples.\n2. The presentation of this paper is clear. The authors start by giving an algorithm under a non-private and ideal setting and then progressively modify the algorithm for the realistic and private setting. I enjoyed reading this paper.\n\nWeaknesses: 1. It would be better if the authors could highlight some theoretical results or theorems in the introduction section including the assumptions.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KbTp0U4OndS", "reviewer": "Reviewer_mEcE", "summary": "This work studies user-level differentially private mean estimation with heterogeneous user data. The problem is as follows: each user receives $k_i$ i.i.d. samples from $Ber(p_i)$, and $p_i$ is drawn from some global distribution with mean $p$ and variance $\\sigma_p^2$. The authors design an unbiased estimator which achieves the near-optimal min-max rate among all unbiased algorithms. The algorithm can be extended to higher dimensions and private $k_i$'s.", "questions": "Questions\n- Regarding unbiased estimators: see the first item in the weakness section.\n- Is it possible to remove the restriction $p\\in[1/3, 2/3]$ in the lower bounds? Do you think the proposed algorithm is min-max optimal for $p\\in[0, 1]$?\n- Could the authors elaborate a little bit on the extension to higher dimensions and the corresponding guarantees? Say the dimension is $d$, and $p_i\\in R^d$, there might be two possible generalizations of the original problem formulation: 1. each coordinate of $p_i$ is independent 2. $p_i$ is drawn from a distribution over the $d$-dimensional probability simplex. I assume that we could simply algorithm the algorithm independently to each coordinate, but what would be the guarantee and optimality in these two cases?\n\nTypos\n- Line 199 and 310, $\\sigma_i$ should be $\\sigma_i^2$?", "limitations": "Limitations and potential negative societal impact are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Understanding user-level privacy with heterogenous user data is a highly important problem in federated learning in both theory and practice. The problem considered in the paper is highly relevant to the FL and DP community.\n- The problem formulation is general enough and should be relevant in many applications.\n- The unbiased algorithm is nearly optimal among all unbiased estimators. \n- The writing is clear and well structured.\n\nWeakness\n- The authors mainly consider unbiased estimators. Is it possible that biased estimators achieve better performance than unbiased ones? For example, in the homogenous setting where all $k_i=k$,  $p_i=p$ and $p<1/k$, the algorithm in [22] is biased (but probably not by too much) but min-max optimal up to log factors.\n- The lower bound result seems to be restricted for $p\\in[1/3, 2/3]$ (i.e., not to close to endpoints)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9h4aFN6RVba", "reviewer": "Reviewer_mJEC", "summary": "The paper proposes an approach to estimate the population-level mean in a heterogenous data setting without compromising user privacy. The core objective is to solve the global task for utility with better privacy for local data of each user.  The main result is that a non-private optimal estimator is linear while private estimator has to be non-linear.", "questions": "Provide an example where the exact proposed algorithm satisfying the assumptions will be used in any application.", "limitations": "There is no section clearly identifying or discussing the limitations of the paper and ways to address them. The required assumptions that can be seen as limitations if not satisfied are spread throughout the paper making it difficult to understand their impact on the results.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n- The paper does not provide sufficient motivation or real-world scenarios where private estimating the mean will be useful in a heterogenous setting. The example of clicking on ads satisfies the assumption of Bernoulli distribution but the importance of estimating the mean privately in such a setting is not clear.\n\n- The paper is a purely theoretical paper and does not provide experiments to demonstrate the effectiveness of the proposed algorithm for real datasets. The empirical privacy-utility trade-off is an important factor to understand for any new differentially private algorithm to evaluate their impact.\n\n- The presented results are limited to binary problems but the abstract and intro motivates heterogeneity in complex data types such as speech and language data.\n\n- There are many assumptions made in the paper. It is not quite clear if these assumptions are rational and hold true in practice or are only considered for better theoretical analysis but may not be possible in reality. Please state all the assumptions upfront and their feasibility clearly.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept