Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the mean estimation problem in the case that the users have heterogeneous sensitivities for local and central differential privacy. By sharing their data, the users receive payments, but lose both local and central privacy. A user’s goal is to maximize her total utility, while the platform’s goal is to minimize the sum of the mean squared error plus the total payments to all users with two constraints: incentive compatibility and individual rationality. The privacy loss is quantified by local Renyi DP and a generalized version of central Renyi DP, in which n different epsilons are given, one for each user. Each user’s “privacy sensitivity” is represented by a scalar $c_i$ in [0,1], which means that the weight of local DP loss for user i is $c_i$, and the weight of central DP loss is (1-$c_i$). The authors analyze the minimax lower bounds for the estimation error and propose a linear estimator that is order optimal. Then, they propose a data acquisition mechanism with the assumption that the server knows the agents’ privacy sensitivity distribution, and has both local and central privacy guarantees, and model it as a nonconvex optimization problem. Finally, they show that there is an approximately optimal polynomial time algorithm for the linear estimators. 
strengths_and_weaknesses: * Originality: This paper is related to central / local differential privacy and Bayesian data acquisition mechanisms. The authors propose a new privacy model, that each user has a privacy sensitivity, which determines whether they care more about central DP loss or local DP loss. Also, the users are allowed to have different epsilon values in both the local and central model. The problem is modeled by a nonconvex optimization problem, and approximate optimal polynomial time solutions are discussed. Based on the introduction and related work, the setting and solutions are novel. I do wonder if there are previous publications about users having different sensitivities for local and central DP, or different users having different central DP epsilons?

* Quality: The setting / notations are mostly ok. Some clarification questions:
  * Page 3, line 138, Is each $x_i$ a scalar? Or could it be a vector?
  * Page 3, line 141, Is $Z_i$ defined?
  * Page 3, line 142, “minimize the estimate’s error” What kind of estimate do you consider in this paper? Could it be arbitrary? From Page 4, line 173, seems you only consider estimating a scalar from user data?
  * Page 4, line 184, Is $\varepsilon_1^{(l)}$ defined before you use it?
  * Page 6, line 241 and 243, why is $\varepsilon_i^{(l)}: \mathcal{X} \rightarrow \hat{\mathcal{X}}$, but $\varepsilon_i^{(c)}: \mathbb{R_+^n} \rightarrow \mathbb{R_+}$? Shouldn’t both functions have the same input and output value range?

* Clarity: The writing and organization is mostly clear. Some comments:
  * Page 1, line 9, “The platform does not know the privacy sensitivity of users”. This might be misleading, because you do assume that the platform knows the distribution of users’ sensitivities (as stated in line 16). I suggest making the assumption clear in line 9.
  * Page 2, line 56, “be the more the second one” -> be more than the second one
  * Page 2, line 66, “The platform’s problem is to…” I suggest changing “problem” to “goal” or “target”. The same comment for other occurrences of this phrase.
  * Page 3, line 97, “in this literature” -> in the literature
  * Page 8, line 295-296, “This problem is still a functional optimization in terms …” -> This is still a functional optimization problem in terms …
  * Page 9, line 362, “a point-wise optimization problem hose…”, “hose” -> “whose”

* Significance: While the setting this paper proposes is new and kind of interesting, I wonder how practical it is to model privacy in a way that each user only has a “privacy sensitivity” in [0, 1] to determine the weight between central and local DP, and the platform got to determine every user’s epsilon value in both central and local DP. The idea is that a user is fine with arbitrarily large privacy loss, as long as they are paid according to some payment rule, which is hard to justify. If every user can have an upper bound epsilon, then the setting would be more meaningful.
questions: * Are there previous publications about users having different sensitivities for local and central DP, or different users having different central DP epsilons?
* There are some clarification questions about the setting / notations in “Strengths And Weaknesses” - “Quality”.
* Page 8, Proposition 1, it is claimed that it’s always optimal to add local noise. This is very counterintuitive, because usually local DP is much more expensive than central DP. What if every user only cares about central DP, but not local DP (all $c_i$ are 0). Does the conclusion still hold?

limitations: I don’t think the setting proposed in this paper is practical. See my comments in “Strengths And Weaknesses” - “Significance”.
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 addresses an important problem in the field that is to eliminate local and central differential privacy (DP) concerns with one unified framework. It also considers the heterogeneous differential privacy where different users have different privacy needs. The approach is relatively simple compared to state-of-the-art solutions. They use Renyi DP and find a minimax lower bound first. Then they establish a point-wise optimization problem to characterize the optimal data acquisition mechanism.
strengths_and_weaknesses: Strengths: This paper addresses an important problem for real-world applications and I found the simplicity of the approach very practical for those applications. It is well written and theoretically sounds. Although I am not an expert in the field, I found many parts of the paper easy to follow and understand.

Weaknesses: This approach is quite applicable to real-world problems. I'd like to see some empirical evaluation of the proposed approach to understand how useful it could be for real applications. Minor but I've noticed a few typos, e.g. hose in page 9, line 362, We (capital W) in  page 2 line 87.  
questions: As far as I know, local DP is stronger and when it is guaranteed, central DP is also guaranteed. Is that correct?  If that's the case why you add noise twice in the framework? 
limitations: Authors discusses the limitations in conclusion section. They mention that it is still an open problem to study the optimality of linear estimators. I don't have any other concern.
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 considers a heterogeneous population of users with respect
 to their privacy preferences. They consider the 'change'
 neighjbourhood for DP, which is natural for local DP. It first shows
 a lower bound on the linear estimation for the Gaussian-mechanism,
 and a matching upper bound.  linear estimator for individuals with
 $\epsilon_i$ preferences.  In the main paper, however, they consider
 relative privacy sensitivity to local and central mechanisms instead.

They then cast the case of MSE in parameter estimation, with incentive
compatibility and individual rationality constraints.
In some sense the result that it's optimal to only add local noise is
not extremely surprising, given the results about anonymity and local
DP.
strengths_and_weaknesses: It is a well written and interesting combination of a number of areas that have not been studied very much so far, even though the design of optimal mechanisms for privacy is important.

 Under the assumption of a monotonic increasing 'virtual cost' (it's ok if you
don't explain it, but it is not actually fully defined: what are $f_i,
F_i$?)

questions: What can you say about generalisation to other estimators or non-MSE loss?

It is a bit strange that you initially look at the case of heterogenous overall losses, and then only tradeoff between local and central losses. Why is that?

The obvious question here is elicitation: How can users be sufficiently informed as to be able to truthfully report in the first place? I realise that this is a general question in mechanism design, but it is typically easier to price a tangible item than relative privacy losses...

limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors study the design of optimal Bayesian data acquisition mechanisms for a platform interested in estimating the mean of distribution by collecting data from privacy-conscious users. The authors assume users have heterogeneous sensitivities for local and central differential privacy measures and the users share their data in exchange for a payment that compensates for their privacy losses. The authors establish minimax lower bounds for the estimation error and show that a linear estimator is (near) optimal. A Bayesian setting is considered to turn the design of an optimal data acquisition mechanism into a nonconvex optimization problem. 
strengths_and_weaknesses: The manuscript is well organized and includes enough information needed to support the claims it makes. The proposed method is novel in the sense that the authors consider the heterogeneous sensitivities of users, and use a Bayesian setting to cast the mechanism designing problem as an optimization problem.
questions: 1. From my point of view, the assumption that the distribution of users’ sensitivities is known may be a strict condition. Can the authors give some examples to show that the assumption may be satisfied in some cases?

2. I am a little confused about the privacy sensitivities (c_1, …, c_n). The authors mentioned that it should be unknown to the platform, however, in line 256, it is assumed that “the privacy sensitivity is c_i and she reports c’_i”, also, in algorithm 1, the privacy sensitivities are also assumed to be given. Have the sensitivities been reported by the users? If not, how to estimate the privacy sensitivities when optimization?

3. In line 330, a Gaussian mechanism is given. What is the sensitivity L_i for the linear estimation of the sample mean?

limitations: The authors have adequately addressed the limitations.
review_title: null

Meta-review: metareview: The reviewers all agreed that the problem setting is well-motivated, the proposed solution is novel, and that the paper is easy to understand and to follow. Though the authors' response addressed most of the reviewers' concerns, during the AC-reviewer discussion phase some reviewers still noted that:

* The method can add too much noise to data (vRjn);
* The setting where the server assigns different privacy levels ($\epsilon$) in exchange for payments may be unrealistic (Buzh);
* Prior knowledge of the distribution users' sensitivities may not be feasible in practice (BCdV).

Despite these issues remaining, the reviewers (and I) agree that the merits of the paper outweigh the relatively minor flaws above and that this paper would make a valuable addition to the conference. I encourage the authors to review the final version of their manuscript prior to publication.
confidence: Certain
Decision: Accept