Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths: 1. The problem setting is interesting and well motivated by giving examples.
2. 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.

Weaknesses: 1. It would be better if the authors could highlight some theoretical results or theorems in the introduction section including the assumptions.

questions: 1. In Theorem 4.1, what would break if the third assumption does not hold? Is this necessary for achieving optimal rates? 
2. Is there an upper bound on the estimation rate for sub-Gaussian meta distribution? 
3. 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?
4. 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths
- 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.
- The problem formulation is general enough and should be relevant in many applications.
- The unbiased algorithm is nearly optimal among all unbiased estimators. 
- The writing is clear and well structured.

Weakness
- 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.
- The lower bound result seems to be restricted for $p\in[1/3, 2/3]$ (i.e., not to close to endpoints)
questions: Questions
- Regarding unbiased estimators: see the first item in the weakness section.
- 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]$?
- 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?

Typos
- Line 199 and 310, $\sigma_i$ should be $\sigma_i^2$?
limitations: Limitations and potential negative societal impact are adequately addressed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 


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.

Weaknesses: 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. 
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: 
- 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.

- 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.

- 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.

- 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.

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.
review_title: null

Meta-review: metareview: Addressing heterogeneity in differentially private aggregation and estimation is an practically important topic that shows up in many real world settings. This paper makes the first step in closing the gap between existing sophisticated algorithms that work under homogeneous setting and the practical scenarios with heterogeneous users. The reviewers agree that this is an important paper that opens up several exciting research directions. 
confidence: Certain
Decision: Accept