Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem of bridging the gap between central DP, where overall epsilon is released, versus personalized epsilon, that is privacy of individual data points that may or may not have been part of a dataset analyzed with central DP.
The paper considers central DP of specific function: objective perturbation mechanism, this setting of achieving central DP is less common that others.
The paper makes an observation that naively computing personalized epsilon and releasing it will violate privacy of central DP (as this computation depends on private data) as anyone can use such an oracle to determine the real value that central DP is trying to hide.
Since the paper considers a specific DP mechanism its results are applied only to private empirical risk minimization problems (ie function computed on the private dataset).

The proposed mechanism works by computing personalizes privacy loss (es-post pDP) directly (since it considers convex problems it is possible). It then adds noise to computed result because otherwise this metric cannot be released. However the paper also derives data-independent upper bounds for pDP that do not incur additional noise.

main_review: This is a very nice paper and I really enjoyed reading it.

My main concern is with it applicability to other DP settings (e.g., Laplace mechanism) and other mechanisms that rely on Gaussian noise and do not build on optimization function perturbation.

Experimental section could  additional experiments, including experiments showing distinction between the data independent bound and the bound that contains additional Gaussian noise added, and real datasets.


limitations_and_societal_impact: Limitations are pointed out in one sentence in conclusion.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper considers the problem of publishing the per-instance privacy loss of a trained learning model to each individual while protecting the privacy of other participants. The paper focuses on training a convex, smooth model using objective perturbation. By deriving bounds on the per-instance ex-post privacy loss, the paper develops algorithms that publish the Hessian matrix privately, which can be used by each individual to evaluate their per-instance privacy loss.

The paper shows that under certain regimes, the algorithm can provide an approximation of the per-instance privacy loss up to constant factors. The paper also provides empirical experiments which show how the derived method provides an approximation of the per-instance privacy cost and how it compares to the worst-case bound.
main_review: Main comments:

1. The main technical contribution of the paper is a per-instance DP analysis of the objective perturbation algorithm for empirical risk minimization. The result is OK but the analysis seems to be limited to the objective perturbation algorithm. For publishing privacy loss, the proposed algorithm (Algorithm 2) is limited to generalized linear models. How the technique can be generalized to other problems is less clear.

2. The motivation for publishing the per-instance privacy cost needs some more justification. Since this privacy loss is only observed by the user, it is cannot be used for privacy budgeting or utility improvement. It would be nice if the authors can provide some more motivation or a practical scenario where the technique can be most beneficial.

3. In the experimental results, is the privacy cost for sharing the per-instance DP loss considered in the plot? How would this affect the accuracy of the approximation? 

Minor comments:
1. Line 285: I believe it should be z_n at the end.

The paper is nicely written overall and has some nice ideas. I am tending towards a rejection due to the above reasons. I am happy to increase my score if the comments can be addressed.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper builds upon a recent work of Wang that introduced per-instance differential privacy, a refinement of the usual approximate differential privacy which captures the effect of a specific data point in the context of a specific dataset on a DP analysis. In particular, the paper proposes ways of reporting per-instance DP losses in a privacy-preserving manner (satisfying joint DP, essentially), focusing on convex ERM with objective perturbation.
main_review: The paper has two main contributions: the first one is evaluating per-instance privacy losses for objective perturbation, and the second one is designing mechanisms for reporting such losses. The motivation for making such reports lies in the fact that the overall DP parameter can be a conservative overestimate of the per-instance privacy loss. While the paper does a good job of emphasizing this gap between per-instance and overall DP, as well as explaining that per-instance parameters are sensitive, I think it could be more convincing in describing why we would want to make these reports in the first place. It’s certainly nice to be able to report these values to participants, but it felt like a bit of a niche objective without more motivation.

In terms of the results, I have various specific comments and questions. The presentation is not completely clear at times; some notation is never defined and I had trouble understanding certain statements.

1. The data-independent bound on pDP is just a bound on personalized DP of Ebadi, Sands, Schneider (2015), right? You’re not really doing anything “per-instance” there? Note that personalized DP immediately satisfies joint DP.
2. Related to the previous point, in the experiments you only plot the data-independent bound. Can you demonstrate empirically that it makes sense to go through the effort of providing a data-dependent bound? Again, for me per-instance differential privacy means that you’re data-dependent; otherwise you’re reporting personalized DP.
3. I didn’t understand Figure 1 and its setup. In the lines starting with 213, there is a setup where I don’t see any randomization (denoted by b previously) in how the solution is computed. I don’t understand how what’s done there satisfies DP, what the purpose of the rotation is, and how the figure relates to Corollary 7. I might be missing something obvious.
4. In statements such as Theorem 6, what do you mean by $\pm$? You mean whichever sign would maximize the expression?
5. In line 223, what do you mean by “hidden in this analysis are the delta’s of Algorithm 1”? I don’t see any delta in Algorithm 1.
6. What is the function b(…) in Theorem 6 and Theorem 8? It’s never defined.
7. What is $F^{-1}_{\lambda(GOE(d))}$ in Algorithm 2? I don’t think it’s defined anywhere.
8. I’m not sure the $D_{\pm z}$ notation works. In Definition 3, for example, say D doesn’t contain z. Then, you’re only bounding one direction of the divergence, when $\mathcal{A}(D)$ is in the numerator and $\mathcal{A}(D_{\pm z})$ in the denominator. You’re not bounding the other direction.
9. In line 161, why does it say “simplified version”? I don’t see the difference between Algorithm 1 and equation (1).
10. I don’t understand the expression “privacy target z” in Theorem 6/Corollary 7.
11. I don’t understand the comment in line 168 that says “chooses a regularization strength to ensure that the objective function is strongly convex”. The objective in equation (1) is strongly convex for any non-zero lambda since all other functions are convex as well.
12. In line 290, is theta $N(0, \mathbb{I})$ (it’s not 1-d)?
13. In line 291, what do you mean by Y being a deterministic function of X and theta such that …? I’m confused by several things here. First, how is Y deterministic if you’re defining Pr[Y=1]? Second, how is the probability equal to something + noise matrix? What are the dimensions of E, X, theta here?
14. Could you clarify what result you’re referring to in the Bassily et al reference in line 281?
15. In line 155, you could clarify which norm you’re considering (e.g., $\ell_2$).
16. In line 275, is it supposed to be $\tilde \epsilon$ between $\epsilon_1$ and $12\epsilon_1$?

------------------------------------------------------------------------------------------------

Thank you for your response. It was indeed very helpful in clarifying various technical specifics and notation, so I'm happy to increase my score. That said, I'm still a bit confused about the motivation. I don't see why joint DP is the right requirement if we want to handle the "accuracy first" setup or justifying large global epsilons (in addition, as you described the accuracy first setup it sounds like there would be privacy leakage through the noise level, which your results might not handle). It's a nice feature to have the possibility of making these joint DP reports, but perhaps I still see it as a bit of a niche objective. I can see how building on these results you might be able to improve data-dependent approaches like propose-test-release, as you suggested, and I think this is a very promising direction and I'm eager to read these results. Unfortunately, the current submission does not give any indication of how this could be done, which is why I'm hesitant to increase my score further.
limitations_and_societal_impact: Some limitations are addressed in the conclusion section. The paper makes a contribution to the theory of differential privacy, which as a general research topic is of great societal relevance. I do not see potential negative societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper looks at how to release per-instance differentially private (pDP) privacy bounds, focusing on empirical risk minimization (ERM) with a convex loss function. The paper proposes methods for releasing either a looser data independent estimate or a tighter data-dependent one. Without properly checking the proofs, the paper seems sensible and interesting.
main_review: ** update after rebuttals & discussion
I lower my score a bit due to concerns raised by other reviewers (see the other reviews for more specific points). However, I still think this is a nice paper and ready to be published.
**

The paper focuses on pDP, basically a datapoint-specific measure of privacy, for ERM with convex losses using objective perturbation for privacy. With pDP the privacy guarantees depend on the sensitive data, and therefore cannot be released without some further privacy mechanism. The authors propose methods for releasing the pDP privacy values: a looser bound holds independent of the actul data, while under some additional assumptions a tighter data-dependent bound can be used. 
The paper is mostly clear and easy to read. In short, I have some questions for the authors, but overall the introduced methods seem novel and interesting.

Questions/comments for the authors:
1) It is unclear to me how the different epsilon values relate to each other, i.e., based on the paper I am not sure if plotting epsilons from standard DP vs pDP makes sense (are they on the same scale, are the privacy guarantees somehow comparable when the epsilons are equal, or how should I interpret the difference in epsilons). Can you elaborate a bit?

Minor comments:
* Definitions 1 & 2 using input space of fixed size n seems a bit weird considering the neighbourhood relation.
* I especially liked the connection to existing statistical theory pointed out in the form generalized leverage score.
limitations_and_societal_impact: There is not much discussion on the limitations, although the limiting assumptions are stated clearly enough. I do not think this paper needs a separate discussion on societal impact.
review_title: null

Meta-review: The authors thought that data dependent privacy properties are an interesting direction of study. The main concern in discussion was the motivation for the results. The reviewers questioned when this notion of privacy would be useful, commenting (among other things) that it could not be directly used by the algorithm designer, only reported to the users. There were also comments about the readability, which could be improved. The paper otherwise seems solid.

As this is a relatively new and underexplored notion, I am OK with accepting the paper even if it doesn't fulfil the full promise discussed at the start of the intro. However, by the same token that this is a new notion, it is very important that the authors address this motivation better than done in the current submission: for instance, identifying and commenting on the strengths and weaknesses of the result (or any results of this form). The should also be better discussion of related work, how this notion differs from very similar ones, relative advantages, etc.: it may be tough for an outsider to distinguish between the several similar sounding notions. I expect that the authors will do all this in their final version of this paper.
Decision: Accept (Poster)