Instance-Specific Asymmetric Sensitivity in Differential Privacy

Summary

In this paper, authors propose a new instance specific sensitivity based method for differentially private queries. In differentially private literature, sensitivity of the query (or the function of interest) is an important quantity, which affects the amount of noise we need to add in order to guarantee DP. In majority of DP mechanisms, the sensitivity is considered as the maximum change of the query when a single data point is changed in the data. Scaling the noise level with this global sensitivity might lead to large amount of noise added which then negatively affects the utility of the method. Instead of using this global sensitivity, another line of work is to use so called smooth sensitivity which calibrates the noise based on the data set at hand, leading to lower level of perturbation and better utility. In this paper, authors extend this line of work with their new sensitivity definition called *reflective inverse sensitivity* and the corresponding release method *asymmetric sensitivity mechanism* which is based on earlier AboveThreshold mechanism. Authors prove privacy and utility guarantees for the proposed method, and empirically demonstrate its benefits over the earlier smooth sensitivity based methods providing up to a magnitude difference in the accuracy.

Strengths

The sensitivity of a function is typically hard to bound without some strong prior knowledge on the private data set. Hence majority of the DP works resort to some ad-hoc bounds, e.g. through clipping of the function or the data, to limit the sensitivity of the function. This can create bias to the output, and analyzing the bias before the application is difficult. Hence the proposed method, which does not suffer from this limitation, is interesting. While the proposed solution builds on top of existing literature, the novelty of this works contribution clearly separates them from prior literature. The theoretical analysis seems sound to me, and the utility result is an important finding. However, I think the exposition of this result could be further improved and will come back to this in the weaknesses. I also believe that the proposed mechanism has broad application potential. For example tuning classifiers trained with public data based on their accuracy on the private data. The experiments in such tasks demonstrate significant benefits over the prior works.

Weaknesses

In general the paper reads well, but it took me a while to parse the main story together. I would suggest authors to simplify some parts of the introduction to make the paper easier to approach. For example, I was rather confused by the use of "inverse of a function" in the introduction, since I don't think it is clear at this point what kind of functions the paper talks about. Therefore it was unclear to me what would be the argument of the function to take the inverse from. This becomes very clear later in the paper, but perhaps some motivating example. to introduce reader to the topic of inverse sensitivity, would be beneficial. I also think the utility result, Lemma 4.1, could be better discussed. There is some further discussion about the result in the appendix, but I would suggest moving some of that to the main paper. It would be very important to at least discuss, what is the key take-away of the utility guarantee. Otherwise it is somewhat hard to appreciate it.

Questions

- Can you clarify what is the motivation for subsampling 1000 samples from each data set in your variance experiments? Is the full data variance task too easy to show any difference between the methods? Or does the O(n) runtime become a bottleneck for running the experiments on the full data? - typos * "... in it’s full generality ..." * in the end of page 6.: "even if $U_1^k(x) = \infty$", I guess it should be $U_f^1(x)$?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

I believe the limitations are properly discussed.

Summary

This paper proposes a new instance specific asymmetric sensitivity under differential privacy by building on the well-studied inverse sensitivity mechanism which adapts to the hardness of the local data according to the inverse closeness to the underlying ground dataset. It also develops some theoretical guarantee and performs empirical validation.

Strengths

The paper deals with an important question in differential privacy.

Weaknesses

(1) The paper is not well-written and is very hard to follow. The abstract and introduction mentions the notion of asymmetric sensitivity without any intuitive explanation. Due to the lack of this important intuition, it is very difficult to understand well the contributions of this paper although the authors list their works in Section 1.3. (2)The important definition of asymmetric sensitivity mechanism (Line 187) is very unclear. The benefit of asymmetrcity compared with the (symmetric) inverse sensitivity mechanisms in (Asi and Duchi 2020. (3)The paper fails to provide the motivations and explanations for theoretical results in a clear and convincing way. The authors consider many concepts and notions but don’t provide their clear logical connection to the main topic of the paper. (4)The citations usually appear in the main text not in the footnote (like in Page 7).

Questions

(1)Line 208: Why the computation time is O(log n? (2)In Definition 3.1, why 1/2? Can we replace it with 0 or 1? (3)Could you please rewrite the definition of asymmetric sensitivity mechanisms in the form of sparse vector technique or in the form of DP mechanisms? What is the benefit of asymmeticity? Could you provide a concrete example where the sensitivity is asymmetric and explain how your techniques can be applied to it? (5)Use the above example to illustrate the variance-bias tradeoff. (6)What is the advantage of asymmetric sensitivity mechanisms in this paper over inverse sensitivity mechanisms in the literature?

Rating

6

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

yes

Summary

The paper introduces a new notion of instance-dependent sensitivity, asymmetric sensitivity, to release general function queries. Compared with inverse sensitivity, it can better capture the underlying instance’s asymmetry, i.e. when changing a data point causing the function value to increase or decrease at different magnitudes. The authors also design an implementation framework for asymmetric sensitivity based private query release using the sparse vector mechanism. Proofs of privacy and utility guarantees as well as empirical evaluation are provided to support the advantage of this algorithm.

Strengths

* The proposed asymmetric sensitivity and the query-releasing framework built upon it are novel and will benefit future research. * The paper is well-written, providing clear intuition of the methods, theoretical guarantees, and empirical evaluation.

Weaknesses

As the author noted in the paper (lines 178-179), the proposed method may not yield significant improvements when applied to vector-valued queries due to the structure of high-dimensional space. typo: L^{\log k}} instead of L_f^{\log k}} in Lemma 4.1 and its proof.

Questions

From empirical evaluation (Figures 1, 2, and 3), the improvement of the asymmetric sensitivity mechanism upon the inverse sensitivity mechanism seems to be higher in the high privacy regime than in the low privacy regime. Can the authors comment on this?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors provide this part in the checklist

Summary

The paper proposes an asymmetric sensitivity mechanism for the private estimation of functions with asymmetric outputs, such as variance. This mechanism combines the inverse sensitivity mechanism with the sparse vector technique to handle asymmetric sensitivities effectively. The proposed method is efficient and demonstrates superior performance in variance estimation and model evaluation tasks (e.g., for regression and classification models) compared to existing methods like inverse sensitivity mechanisms and smooth sensitivity mechanisms.

Strengths

- This paper utilises the asymmetric sensitivity property (e.g. "changing an individual's data can generally increase the function more than decrease it"). This property holds for many problems. - The proposed method is of practical relevance and has efficient implementations for many applications.

Weaknesses

The theoretical guarantee can be vacuous in some reasonable settings. For example, the upper bound in lemma 4.1 can be loose when $f(x)\ll 1$ for all $x$.

Questions

Is there a general recipe for efficiently implementing the asymmetric sensitivity mechanism beyond the specific examples provided (i.e., variance estimation and model evaluations)?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

See weaknesses.

Summary

This paper provides a new algorithmic framework for differentially privately computing general functions that adapts to the "local" sensitivity of the underlying dataset. It follows previous work's paradigm which is to sample outcomes with probabilities exponentially decreasing in how "far away" the current dataset is from one that produces that particular outcome. The mechanism works by finding the reflective inverse sensitivity which is slightly different from the conventionally used inverse sensitivity; then it tests a series of monotone outcomes and outputs the first one whose reflective inverse sensitivity passes the threshold of 0. The result is a potentially biased mechanism hence the known performance guarantees for related mechanisms such as inverse sensitivity mechanism do not directly apply. Since the evaluation of the reflective inverse sensitivity can be inefficient, the paper then discusses practical tactics for approximating it. The mechanism is carried out on the private variance problem and the experiments show promising results where the new mechanism beats previous ones with a significant lead.

Strengths

The mechanism used in the paper is original in that the defined variant of inverse sensitivity is asymmetric, and it does improve the performance in the case study of private variance estimation. The paper is organized well, the writing rather clear. The mechanism could be a preferrable alternative to the state-of-the-art, its practical use mostly depending on whether we can easily find approximate functions for the asymmetric inverse sensitivity that are efficient to compute but that can be said of most exponential mechanisms.

Weaknesses

The greatest weakness of this paper is perhaps the lack of justifications of why the proposed mechanism should work better; especially the asymmetric part. What it does is skip the t's smaller than f(x) and only look at bigger ones, hence we are moving the mass probability from one side of the distribution and put it on the other. The paper provides some intuition but I still fail to see why it should help. I am inclined to believe that in the private variance computation it helps because we know variances cannot be negative. By and large I think it is pointing out a phenomenon noticeable in practice, and I don't doubt that it could be applicable to more cases than have already been observed. Still there is the missing piece of puzzle of why we are observing this and how to extend this knowledge to other related problems. The community could benefit greatly from that missing theoretical analysis and it will complete the story.

Questions

How does the performance of this algorithm compare to, say, running propose-test-release by testing for a series of fixed number of t's and test $\{len_f(x;t)\}$ by comparing them one by one to some threshold (maybe 1/2) as used here and return the first t that passes this test? It seems close to this mechanism in nature, since mostly it's just aiming at picking the smallest t to get a positive $len_f(X;t)$; further the result is also sort of like an exponential mechanism. Do the authors have any intuition of this? It is perhaps a symmetric version of this.

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

The authors have adequately addressed them.

I will rasie my evaluation

Thank you for your rebuttal. I am satisfied with the answers. I will raise my evaluation to 6.