Instance-Specific Asymmetric Sensitivity in Differential Privacy
Authors: David Durfee
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Statistics
Machine Learning
Primary area: privacy
TL;DR: We provide a new algorithmic framework for differentially private estimation of general functions that adapts to the hardness of the underlying dataset.

Abstract: We provide a new algorithmic framework for differentially private estimation of general functions that adapts to the hardness of the underlying dataset. We build upon previous work that gives a paradigm for selecting an output through the exponential mechanism based upon closeness of the inverse to the underlying dataset, termed the inverse sensitivity mechanism. Our framework will slightly modify the closeness metric and instead give a simple and efficient application of the sparse vector technique. While the inverse sensitivity mechanism was shown to be instance optimal, it was only with respect to a class of unbiased mechanisms such that the most likely outcome matches the underlying data. We break this assumption in order to more naturally navigate the bias-variance tradeoff, which will also critically allow for extending our method to unbounded data. In consideration of this tradeoff, we provide theoretical guarantees and empirical validation that our technique will be particularly effective when the distances to the underlying dataset are asymmetric. This asymmetry is inherent to a range of important problems including fundamental statistics such as variance, as well as commonly used machine learning performance metrics for both classification and regression tasks. We efficiently instantiate our method in $O(n)$ time for these problems and empirically show that our techniques will give substantially improved differentially private estimations.

Instance-Specific Asymmetric Sensitivity in Differential Privacy
David Durfee Mozilla Anonym f i1a. com
Abstract
We provide new algorithmic framework for differentially private estimation of general functions that adapts to the hardness of the underlying dataset. We build upon previous work that gives paradigm for selecting an output through the exponential mechanism based upon closeness of the inverse to the underlying dataset, termed the inverse sensitivity mechanism. Our framework will slightly modify the closeness metric and instead give simple and efficient application the sparse vector technique. While the inverse sensitivity mechanism was shown to be instance optimal, it only with respect to class of unbiased mechanisms such that the most likely outcome matches the underlying data. We break this assumption in order more naturally navigate the bias- blas-variance tradeoff, which will also critically allow for extending our method to unbounded data. In consideration of this tradeoff, we provide theoretical guarantees and empirical validation that our technique will be particularly effective when the distances the underlying dataset asymmetric. This asymmetry is inher- ent to range of important problems including fundamental statistics such as variance, as well as commonly used machine learning performance metrics for both classification and regression tasks. We efficiently instantiate our method in O(n) time for these problems and empirically show that our techniques will give substantially improved differentially private estimations.
Introduction
consider the general problem of estimattin aggregate functions or statistics of a dataset with differential privacy. The massive increase in data collection to improve analytics and modelling across industries has made such data computations invaluable, but can also leak sensitive individual information. Rigorously measuring such leakage be achieved through differential privacy, which quantifies the extent that one individual's data can affect the output. Much of the focus within the field of differential privacy is upon constructing algorithms that give both accurate output and privacy guarantees by injecting specific types of randomness. One of the most canonical mechanisms for achieving this considers the maximum effect one individual's data could have upon the output of a given function, referred to as the sensitivity of the function, and adds proportional noise to the function output. In general, the notion of sensitivity plays a central role in many differentially private algorithms, directly affecting the accuracy of the output.
While using the worst-case sensitivity across all potential datasets will ensure privacy guarantees, the utility can be improved by using variants sensitivity that are specific the underlying dataset. This notion was initially considered in Nissim et al. (2007), introducing smooth sensitivity, interpolation between worst-case sensitivity and local sensitivity of the underlying data, by which noise could be added proportionally. The smooth sensitivity adapts well to the underlying data and
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

was further extended to other commonly used variants of the original privacy definition Bun & Steinke
2019).
More aggressive methods were also considered with a data-indeeenddnn conjectured sensitivity parameter and more accurate results provided when the underlying data complies with the parameter. The propose- propose-test-releat test-release methods check that all datasets close to the underlying data have sensitivity below a parameter and add noise proportional when the criteria is met and fail otherwise Dwork & Lei (2009): Thakurta & Smith (2013). Preprocessing methods provide an approximation of the function with sensitivity below given parameter by which noise can be added proportionally and the approximation is accurate for underlying data with low sensitivity CCen & Zhou| (2013); Blocki et al. (2013); Kasiviswanathan et al. 2013); Cummings & Durfee (2020) Clipping techniques, commonly seen in differentially private stochastic gradient descent Abadi et al. (2016). are also a more rudimentary and efficient preprocessing method for ensuring sufficiently small sensitivity. The primary challenge with these approaches is the sensitivity parameter must be specified a priori and can add significant bias if the underlying data does not comply with the parameter.
In contrast, the inverse sensitivity mechanism directly improves upon the smooth sensitivity technique adapting even better to the underlying data. While several instantiations had been previously known in the literature, it was introduced in it's full generality in Asi & Duchi (2000)). Specificallyy, this framework considers all potential outputs based upon the closeness of their inverse to the underlying data and applies the exponential mechanism to select point accordingly. This exact methodology can even improve upon adding noise proportional to the local sensitivity of the underlying data, which generally violates differential privacy. Follow-up work gave approximations of this method that allow for efficient implementations of more complex instantiations Asi & Duchi (2020a). For both the exact and approximate versions, the inverse sensitivity mechanism is instance optimal and nearly instance optimal, respectively, under certain assumptions Asi & Duchi 2020a ())
1.1 Our techniques
We build upon the inverse sensitivity mechanism, particularly within the class of functions for which it was shown to be optimal. However, those guarantees only held for a class of unbiased mechanisms such that the most likely outcome matches the underlying data. The inverse sensitivity mechanism and smooth sensitivity techniques fit this characterization of unbiased. The methods that specify -att-indeeendent sensitivity parameter break this assumption by essentially fixing the variance through this parameter but adding significant bias if the variance parameter is set too low. Our method will also break the unbiased assumption but still adapt well to the underlying data to more naturally navigate the bias-variance tradeoff.
In particular, we similarly consider the distance from the underlying data to the inverse of each possible oulput, which can be considered the inverse sensitivity. However, we instead invoke the well-known sparse vector technique, originally introduced in Dwork et al. 22009, to select an output close to the underlying data. The iterative nature of sparse vector technique will create slight bias, while still adapting well the underlying data. By utilizing this iterative technique, we can also better take advantage when the sensitivities are asymmetric that allows us to reduce the variance, and we thusly term our method the asymmetric sensitivity mechanism. fact, the local sensitivity can be infinite with unbounded data and our technique can still naturally handle this setting for a wide variety of functions including our instantiations. We support this with theoretical utility guarantees that are asymptotically superior to previous work under these conditions.
Our notion of asymmetric sensitivities is inherent to a range of problems, and we first instantiate our method upon variance, a fundamental property of a dataset that is widely used in statistical analysis. Likewise, this property will also apply commonly used machine learning performance metrics: cross-entis cross-entropy loss, mean squared error (MSE), and mean absolute error (MAE). Model performance evaluation is an essential part of a machine learning pipeline, particularly for iterative improvement, so accurate and private evaluation is critical. We instantiate our method upon these functions as well, and give an extensive empirical study for each instantiation across a variety of datasets and privacy parameters. We show that our method significantly improves performance of private estimation for these important problems. We further complement our results with an approximate method that allows for more efficient implementations of general functions while still preserving the asymmetry that we exploit for improved estimations. This will allow us to give O(n) time implementations for each invocation of our method.
2

---

1.2 Additional related works
While the most closely related literature was discussed in more detail previously, we provide additional related works here. Recent work considered destance-optimaliyy but for estimators population quantities McMillan et MMMillan
(2022), which differ from the empirical quantities studied here and in the other previously mentioned work. Additional work formally considered the bias-variance privacy trade-off particularly for mean estimation Kamath al. (2023), but considers bias in the more classical sense. Interestingly, it's also been seen in the work for obtaining (asymptotically) optimal mean estimation for subgaussian distributions Karwa & Vadhan (2018); Bun Steinke
(2019) and distributions satisfying bounded moment conditions Barber & Duchi (2014) Kamath
ct al. 2020), that adding bias was necessary. This fits with our results where bias, albeit a different type, was needed to improve instance-specific differential privacy.
1.3 Our contributions
We summarize our primary contributions as the following:
We introduce a new algorithmic framework for private estimation of general functions, which we refer to the asymmetric sensitivity mechanism, along with more computa- tionally efficient approximate variant (see Section 3
2. We provide theoretical utility guarantees that asymptotically confirm method's s ad- vantage when the sensitivilies are asymmetric and further give inluition and empirical support of this asymmetric advantage (see Section 4)
3. We efficiently instantiate our method for private variance estimation, and provide an extensive empirical study showing significantly improved accuracy (see Section
4. We further invoke our method upon model evaluation for both classification and regres- sion tasks with corresponding efficient implementations and empirical sludies showing improved estimations (see Section c
Additional and supplemental analysis, results and empirical studies are pushed to the appendix.
Preliminaries
For simplicity and ease of comparison we borrow much the notation from Asi & Duchi (2020a b). Definition 2.1. Let x be datasets of our data universe X We define dhan x') Hi * x/] to be the Hamming distance between datasets. dxan x') ) S 1 then x, are neighboring datasets.
Note that we assume the swap definition of neighboring datasets but will also discuss how our results apply to the add aud-subtract definition in Appendix [B.3 We further define the (global) sensitivity. Definition 2.2. f : x" + R has sensitivity A if for any neighboring datasets [f(x) - fx'') S A
We will be using the classical (pure) differential privacy definition, but will also discuss how our methods apply to other definitions with improved guarantees.
Definition 2.3. Dwork et al. (2006bla) A mechanism M x" - is (c. (f.o))dffferentially--rvaa (DP) if for any neighboring datasets x, x e X' and measurable _ T:
Pr[M(x) $) < e
If 8 then M cDD.
2.1 Sparse vector technique
We define the fundamental sparse vector technique introduced in Dwork et al. (2009) and often considered to apply Laplacian noise Lyu et al. (2017). However, recent work showed the noise instead be added from the exponential distribution at the same parameter for improved utility Durfee (2023). Let Expo(b) denote a draw from the exponential distribution with scale parameter b. The sparse vector technique iteratively calls the following algorithm.
This technique can further see improvement when the queries are monotonic which will apply to most of our instantiations of our method.
3

---

Algorithm 1 Threshold
Require: Input dataset x, stream of queries {f x R] with sensitivity A, and threshold
Set f'= Expo(A/e1)
2: for each query i do
3: V; = Expo(A/e))
4: f(x)++;; + 2 T then
Output and halt
6: else
Output
8: end
end for
Definition 2.4. We say that stream of queries {ff X" - R3 with sensitivity A is monotonic if for any neighboring x,x' X" we have either fi(x) fi(x') for all or f((x) f(xx) for all
This allows for the following differential privacy guarantees from Durfee (0023).
Proposition 2.5. Algorithm is (e1 + 2ep) in general and (e) + D2 for monotonic queries
2.2 Inverse sensitivity mechanism
The inverse sensitivity mechanism had seen several previous instantiations but introduced in it's s full generality in Asi & Duchi (2020b). We first introduce the exponential mechanism.
Definition 2.6. |McSherry & Talwar (0077) The Exponential Mechanism is randomized mapping M : X - such that
E (xx,)
Pr [M(x) = exp
2A
where q 2 T has sensitivity Proposition 2.7. McSherry & Talwar (2007) The exponential mechanism i-
We then define the distance of potential output from the underlying dataset be the Hamming distance required to change the data such that the new data matches the output.
Definition 2.8. For function f X T and X let the inverse sensitivity of T be
(xn)(x;t) del inf(dhan(x, xx)(('))) =1
x
By construction this distance metric for any output cannot change by than between neighboring datasets due to the triangle inequality for Hamming distance.
Corollary 2.9. For any neighboring datasets x, x' x and im(f) where im(f) C T the image of the function, we have (x; ( (x';(xxx)))
:1) :))s 5
The inverse sensitivity mechanism then draws from the exponential mechanism instantiated upon the distance metric giving the density function
e 1en((x=))/22
(x)
(M.1)
J leny(xa)e/2dd
and mechanism M.1 e-DP by Proposition 2.7 and Corollary 2.9
Asymmetric Sensitivity Mechanism
In this section introduce our general methodology for instance-specine differentially private estimation, which we term the asymmetric sensitivity mechanism. We first give the exact formu-
lation which will fit extensive class of functions focused upon in Asi & Duchi (202bb). Next

---

we provide simple framework by which our method can be implemented. The efficiency of this implementation is highly dependent upon the function of interest, but we supplement these results with approximate method. This can allow for broader efficient implementations and also extends our methodology to general functions. While this section will set up and provide the necessary rigor for our techniques, we also point the reader to Appendix C for more intuitive explanation of our approach compared to the inverse sensitivity mechanism.
3.1 Exact asymmetric sensitivity mechanism
Our method will similarly consider the distance for cach oulput from the underlying data with the goal being to select an output with distance close to zero. The inverse sensitivity mechanism does this through the exponential mechanism, but we will instead apply the sparse vector technique. In order to better apply the sparse vector technique, we will first modify the inverse sensitivity such that is negative for outputs that are less than output from the underlying data.
Definition 3.1. For f x R and E x", let the reflective inverse sensitivity of E R be
(x(x;) def sgn(t - f(x)) ((x)) (Ien;(x:1)- - !
Intuitively, the goal of applying the sparse vector technique will be to identify when the reflective inverse sensitivity crosses the threshold from negative to positive. While there are reasonable methods of extending our approach to higher dimensions, it will both become computationally inefficient and the notion of asymmetry, which gives our method the most significant improvement, less inherent in higher dimensions. Initially, we focus upon a general class of functions considered in Asi & Duchi 2020b) that was shown to include all continuous functions from convex domain.
Definition 3.2 (Definition 4.1 in Asi & Duchi (2020b)). Let f N + R. Then f is sample- monotone if for every E X and s,t E R satistying f(x) S t ort S f(x), we have [en & (x;)
For this class of functions, we show that the reflective inverse sensitivity of an output maintains closeness between neighboring datasets. Accordingly, we can apply the sparse vector technique to a stream of potential outputs in order to (noisily) identify when the reflective inverse sensitivity crosses the threshold from negative to positive. This gives the asymmetric sensitivity mechanism for a stream of potential outputs {t:} that calls AboveThreshold and returns & when
(M.2)
To be effective, this stream of potential outputs should be increasing (or decreasing if we flip the sign of sy) but will still achieve the desired privacy guarantees regardless which is shown in Appendix(A.. A.2
Theorem 3.3. Given sample- f X - R and any stream of potential outputs {4,, we have that mechanism M.2 is (E: + 282)-DP in general and (e, + DDD if is monotonic.
We further detail in Appendix Ba simple, general, and robust strategy for selecting potential outputs that provides a reasonable limit on the number of queries.
3.2 Implementation framework
The primary bottleneck in efficiently implementing both our asymmetric sensitivity mechanism and the inverse sensitivity mechanism is the computation of the inverse sensitivity. In particular, it will require computing upper and lower output bounds for different Hamming distances from our underlying data.
Definition 3.4. For function f 2 R, we define the upper and lower output bounds for Hamming distance f as
U)(x) suplf(x') : dxan(xx x') S t
de
x
and
(x) def infi inf(f(x') xx, S S}
5

---

The complexity of computing these depends upon the function, but we can use the upper and lower output bounds get the inverse sensitivity with the following lemma proven Appendix A.2 Lemma 3.5. f is sample-monoie
then (eny(x;1) inf(e (1((x) S < for all R
we then assume access to the array 1., 4 we can compute (x;)(x;4) in O(lg(()) time with a simple binary search. Alternatively, we could also take O(n) amortized time by maintaining pointer and iteratively increasing the index for each new potential output if we assume the stream of potential outputs are non-decreasing. This gives the general implementation framework:
for any potential output
Compute upper and lower output bounds Uf(x) and 1x(x) for all re [n]
2. Use the output bounds to efficiently run AboveThreshhold(x (x) =0)
3.3
Approximate asymmetric sensitivity mechanism
In Section A show how extend our asymmetric sensitivity mechanism to general functions x - and provide more efficient implementations. will follow closely with our exact version above.
4 Asymmetric Sensitivity Advantage
In this section, we first connect our definitions with the corresponding definitions in the previous work, by which utility guarantees provided. Then we discuss the notion of asymmetric sensi- tivities and provide our utility guarantees that exploit this asymmetry to asymptotically improve upon the previous work under those conditions.
4.1 Connection to previous work
An essential quantity for our method and both inverse and smooth sensitivity mechanisms is the amount function output can change if k individuals change their data. This is quantified in Equation 3 from Asi & Duchi (2020b) which can be translated to our definitions (in the case when T = R) as
(x;kk) def max{lf(x) ((xx
Note that ifk = then this is the local sensitivity of the function. It's then shown in Asi & Duchi (2020b) (Corollary 4.2 and Equation 13, respectively) that the general utility guarantees of both inverse sensitivity mechanism and smooth sensitivity mechanism are bounded with respect to this quantity. More simply, the accuracy guarantees degrade as the local sensitivity increases and there is no utility bound local sensitivity is infinite.
4.2 Asymmetric accuracy guarantees
To understand the advantages of our method, will consider the sensitivities to be asymmetric [f(x) -
((x))))(x)) (x)) >> 1f(x) (x)) for most (or vice versa), which is to say that changing an individual's 'ss data can generally increase the function more than decrease it. general, we expect any lower bounded function to inherently limit the amount changing
individual's data can decrease the function compared to increasing the function. Each instantiation in our empirical study is non-negative function which then fits this characterization. For simplicity, we will restrict our consideration to non non-negatin -egaatiee functions for our utility guarantees, but can easily apply these to other settings.
The goal for our method is to exploit the asymmetric sensitivities by instead applying the sparse vector technique. The iterative nature of this technique biases the output towards being less than fx), but more importantly the (x) values will have little effect upon the accuracy. Specifically, once the threshold crossed becomes increasingly unlikely that the sparse vector technique will proceed. Explicitly connecting this with our mechanism, even if U (x) and so the local

---

sensitivity is infinite, we still have (x(x;t) 1/2 for all > f(x) and assuming & is increasing it is increasingly unlikely that we output larger 4 > f(x).
We formalize this intuition by providing theoretical utility guarantee that does not depend upon the upper bound values. Essentially, we able replace the - (/((x) in 0y(x; with relative error bound based upon parameter that we fix across all our empirical instantiations. Accordingly, as (x( - co and thereby asymmetry increases and also local sensitivity increases, our utility guarantees are asymptotically superior to both inverse and smooth sensitivity mechanisms.
Lemma 4.1. Let M denote the mechanism from M.2 with = f where B > and we lete = E1 + 28 with E in the call Algorithm Given non-negative sample monotone f X" R we have
Pr [IM f(x) < mxx plogk+1 -x)) 1)(f(x)+
-D]
>1
kee/6
for any E x such that f(x) S 800)
provide the proof in Appendix C along with further intuition and empirical evidence of our asymmetric advantage. We also extend these results to general non-negative functions in Corol- lary C.4 by applying our approximate variant achieve the same guarantees. We set / 1.005 in all our empirical studies and also note that our method is robust to reasonable choices of the B parameter (Appendix B.2)
Private Variance Estimation
In this section, we instantiate our asymmetric sensitivity mechanism upon variance, fundamental property of a dataset that is widely used in statistical analysis.
Definition 5.1. Let X' = R and for x E X we let x = E x and define
Var [x]
Σ
[x] - x)²
There has been extensive work in the privacy literature upon covariance estimation for univariate and multivariate Gaussians with a focus upon optimizing asymptotic performance Our focus here will be practical methods for general data, so rigorous comparison to all these methods for Gaussians untenable and outside the scope of this work.
We first show how the variance instantiation of asymmetric sensitivity can be implemented effi- ciently and give intuition upon why expect asymmetric sensitivities for this function. Next we give a detailed empirical study that confirms this intuition, showing that our method will substantially outperform inverse sensitivity the task of variance estimation.
Efficient variance instantiation
As seen in Section 3.2 we need to efficiently provide upper and lower output bounds in order to achieve an efficient implementation. We first consider the lower output bounds and can provide the exact bounds from Definition 3.4 which we prove in Appendix D
Lemma 5.2. Given x R", if S S Xa are ordered then we have lower output bounds
Var (x) n- min Var [x(er)-en-]]
0515t
del
where we let [(44--i---1 (01111 ii xp-i)
'ee Karwa & Vadhan (2018) Du et al. 2020 Biswas et al. 2020 Kamath et al
2019 Bun et all 2019
Aden-Ali
Aliee et al. (202 Ashtiani & Liaw 2022 Kothari et al 2022 Tsfadia et al. (2022 Liu et al. 2202 Kamath
al. (222))
7

---

While the formula above immediately suggests an O(n") time computation of all the lower output bounds, we will further prove in Appendix(] that we can use our approximation to get a more efficient implementation. In particular, consider data independent fixed distance and only compute the exact bounds outputs closer to the underlying data to still ensure accurate estimations.
Lemma 5.3. Given x E R" and c 2 0, we can compute all approximate output bounds (r) Var (x) for S and (ar for <> in O(n c²) time.
Next we consider the upper output bounds, but if the data is unbounded then we must have Var (x) = co. It precisely for this reason that asymmetric sensitivities are inherent for variance. Our method can naturally handle this setting and we show in Appendix B.1 that unbounded upper output bounds barely affects our accuracy. However, applying the inverse sensitivity mechanism re- quires reasonable bounds upon each data point that should be iata-independent and also sufficiently loose to not add bias from clipping data points.
Lemma 5.4. we restrict all values to the interval b] then given x E [[a b]" we can give approximate upper output bounds
Ab a)
(xr Var [x]
n
To our knowledge, there is efficient method for computing the exact upper output bounds for general data (contained in a range), so to maintain practicality we provide approximate bounds, proven in Appendix D
Algorithm 2 Variance instantiation of asymmetric sensitivity mechanism
Require: Input datasel x, and parameter B
Compute all (x) with c 100 (Lemma 5.3
2: Compute all (x) if domain is restricted to [a, (Lemma 5.4
3: {1K-1 T] - AboveThreeshold(x (57))) 1)), T 0)
output 8 -1
Theorem 5.5. Algorithm 2 is (e: + 2D2 and has a runtime of + q) where q is the number of queries in AboveThreshold
Proof. If we assume the domain is restricted to bj" then the privacy guarantees follow from
Lemma 5.3 and Lemma 5.4mmm5.44 applppd to Theorem A.4 not then we apply Lemma 5.3 and U (x) oo to Theorem A.4 to get our privacy guarantees.
For the runtime, computing all (x) is O(n) time by Lemma 5.3 and fixing c = 100, and computing all Var(x) is O(n) time. Finally, we can run Above Threshold in O(n + q) time as seen Section 3.2
In our implementations we'll more reasonably assume B 2 1.001, so 850000 > 10 and we'll simply terminate AboveThreshol after most 50,000 queries for all datasets without affecting the privacy guarantees. This then gives a runtime of O(n).
5.2 Empirical study of variance estimation
For our instantiations of machine learning model evaluation will be using the following datasets for regression tasks: Diamonds dataset containing diamond prices and related features Wickham (2016); Abalone dataset containing age of abalone and related features Nash et al. (1955; ; and Bike dataset containing number of bike rentals and related features Fanaee-T (2013). We will also use the labels from these datasets to test our variance invocation. We also the Adult dataset, Becker & Kohavi (1996), for model evaluation of classification tasks so we will borrow two of the features, age and hours worked per week, test our variance invocation.
While our method does not require any bounds on the data to still maintain high accuracy (see Appendix B.1. it is necessary for the other mechanisms. All of our data is inherently non-negative

---

Varaate entasate dey
adiration Dara
Ayereric beattry Pactaris
San dy Necarae
be Haclasie
13
14T
Valance ectivatin addt (heard
Variacce actiraation sduff (anel
Recianse
fesdivyy tei man
Figure 1: Plots comparing each method for estimating variance. For each privacy parameter we sample 1,000 datapoints from the dataset and call each mechanism 100 times, plotting the average absolute error with 0.9 confidence intervals.
and some data has innate upper bounds. If not, we use reasonable upper bounds, which should be data independent, to avoid adding bias from clipping the data. We use the following bounds: [0,50000] for diamond prices; [0,50] for abalone ages; [0,5000] for city bike rentals; [0,168] for hours; and [0,125] for age. Our algorithm (Algorithm 2 in Appendix D will have a parameter B which we fix 1.005 and will maintain this consistency across all experiments. We further show in Appendix B.2 that our method is robustly accurate across reasonable B choices.
For each privacy parameter, we repeat 100 times: sample 1,000 datapoints from the dataset and call each mechanism on the sampled data for estimates. We plot the average absolute error for each method along with confidence intervals of 0.9 in Figure 5.2] As expected, see that approach of variance estimation sees substantially less error across privacy parameters and datasets.
Private Machine Learning Model Evaluation
In this section, we invoke our asymmetric sensitivity mechanism upon commonly used metries for machine learning model evaluation for both classification and regression tasks. In particular, we consider cross-entropy loss for classification tasks, and mean squared error (MSE) and mean absolute error (MAE) for regression tasks. Note that combining our improved estimation for variance in Section 5 with the improved estimation for MSE also implies an improved estimation of the coefficient of determination, R², also commonly used for evaluating regression performance.
We provide full definitions along with technical analysis in Section
E
6.1 Empirical study of model evaluation for classification
For our empirical study of model evaluation for classification tasks we will consider two labular datasets with binary labels, the Adult dataset Becker & Kohavi (1996) and Diabetes dataset Efron et al. (2004), along with two computer vision tasks with 10 classes, the mnist dataset LeCun et al. (2010) and cifar10 dataset Krizhevsky et al. (2009). Our focus here is upon the accuracy of our evaluation, not optimizing the quality of the model itself. As such, we will be using reasonable choices for models for simplicity but certainly not state-of-the
models.
For the tabular data, we partition into train and test with an 80/20 split and train with an xgboost classifier with the default parameters. For the mnist data which is already partitioned, we use a simple MLP with one inner dense layer of 128 neurons and relu activation, and the final layer of 10 neurons has a softmax activation. We train this model for 5 epochs. For the cifar10 data, which is already partitioned, we use relatively small CNN with several pooling and convolutional layers,

---

Ores Haapy
Den Men
the byro Sonelr Miccee
Figure 2: Plots comparing each method for estimating cross entropy loss. For each privacy parameter we both sample 1,000 datapoints from the test set and call cach mechanism 100 times, plotting the average absolute error with 0.9 confidence intervals.
and several dense layers at the end with relu activation and final layer with softmax activation. We train this model for 10 epochs.
Again our method does not require any bounds on the data to maintain high accuracy, but it is necessary for the inverse sensitivity mechanism. Given the softmax activation for our models, the outputs are unbounded, but we will provide reasonable bounds. We will use the bounds [-10,10] of the model output for binary classification tabular data, and bounds [-25, 25 of the model output for the clsti-classifiiation vision data. Once again, we fix our parameter / = 1.005.
6.2 Empirical study of model evaluation for regression
As discussed in Section 5 our machine learning model evaluations for regression will use the following datasets: Diamonds dataset containing diamond prices and related features Wickham (2016]; Abalone dataset containing age of abalone and related feature Nash et al. (1995); and Bike dataset containing number of bike rentals and related feature Fanaee-T 2013). We also use the same parameters from Section 5 for these datasets. Once again, our goal here is to accurately assess the quality of the model and not optimize performance, As such we simply train with xgboost regressor under default parameters after partitioning each dataset into train and test with an 80/20 split.
Meas squared eree for clarends data
Nea1 squared enter for bile daya
tn diy rachaai's
dy Mac Wel
Seeriwitt Michurtsss
130
30-
We first consider mean squared error estimation and repeat 100 times for each privacy parameter: draw 1,000 datapoints from the test set and call each mechanism 100 times for estimates. We then plot the average absolute error along with confidence intervals of 0.9. We repeat this process for mean absolute error.
Nean abodite erorr clamords
Mear dookis urte for dodate
Hean abacide everr bike data
12"
Sonaiiity Nechur tevere Stan Mecherer
Braliniiy Bo
teeres Serato's Mechermm Serviityy
Tynnss pwwomndteee (2)
10

---

References
Abadi, M., Chu, A., Goodfellow, 1,, McMahan, H. B., Mironov, I,, Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pp. 308-318, 2016.
Aden-Ali, L, Ashtiani, H., and Kamath, G. On the sample complexity of privately learning unbounded high-dimensional gaussians. In Algorithmic Learning Theory, pp. 185-216. PMLR, 2021.
Ashtiani, H. and Liaw, C. Private and polynomial time algorithms for learning gaussians and beyond. In Conference on Learning Theory, pp. 1075-1076. PMLR, 2022.
Asi, H. and Duchi, C. Instance- -ottimlllpp in differential privacy via approximate inverse sensitivity mechanisms. Advances in neural information processing systems, 33:14106- 14117, 2020a.
Asi, H. and Duchi, C. Near instance-optimality in differential privacy. 17Xiv:2005110600 2020b.
arXiv preprint
Barber, R. F. and Duchi, J. C. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv:1412. 4451, 2014.
Becker, B. and Kohavi, R. Adult. https//ddboorg//02244////XX
UCI Machine Learning Repository, 1996. DOL:
Biswas, S., Dong, Y., Kamath, G., and J.lman. Coinpress: Practical private mean and covariance
estimation. Advances in Neural Information Processing Systems, 33:14475-14485, 14485, 2020.
Blocki, J.. Blum, A., Datta, A., and Sheffet, O. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings the 4th conference on Innovations in Theoretical Computer Science, pp. 87-96, 2013.
Bun, M. and Steinke, T. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. Advances in Neural Information Processing Systems, 32, 2019.
Bun, M., Kamath, G., Steinke, T., and Wu, Z. Private hypothesis selection. Advances in Neural Information Processing Systems, 32, 2019.
Chen, S. and Zhou, S. Recursive mechanism: towards node differential privacy and unrestricted joins. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 653-664, 2013.
Cummings, R. and Durfee, D. Individual sensitivity preprocessing for data privacy. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 528-547. SIAM, 2020.
Du, W., Foot, C., Moniot, M., Bray, A., and Groce, A. Differentially private confidence intervals. arXiv preprint arXiv:2001.02285, 2020.
Durfee, D. Unbounded differentially private quantile and maximum estimation. arXiv preprint arXiv:2305.01117, 2023.
Dwork, C. and Lei, J. Differential privacy and robust statistics. In Proceedings of the forty-firs annual ACM symposium on Theory of computing, pp. 371-380, 2009.
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, and Naor, M. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology-EUROCRYPPP 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg. Russia, May 28-June 1, 2006. Proceedings 25, pp. 486-503. Springer, 2006a.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284 Springer, 2006b.
Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., and Vadhan, S. On the complexity of differentially private data release: efficient algorithms and hardness results. Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 381-390, 2009.
11

---

Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and
Trendse Theoretical Computer Science, 933-4))211-477, 2014.
Efron, B., Hastic, T., Johnstone,, I,, and Tibshirani, R. Diabetes dataset. https://web.stante
htap:h/stteeappeee///////sssssap 2004.
Fanace-T, H. Bike Sharing Dataset.
UCI Machine Learning Repository, 2013. DOE:
http://ddb..rrg11122444////////
Kamath, G., J., Singhal, V., and Ullman. Privately learning high-dimensional distributions. In Conference on Learning Theory, pp. 1853-1902. PMLR, 2019.
Kamath, G., Singhal, V., and Ullman, J. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, pp. 2204-2235, PMLR, 2020.
Kamath, G., Mouzakis, A., Singhal, V. Steinke, T., and Ullman, J. A private and computationally-
efficient estimator for unbounded gaussians. In Conference on Learning Theory, pp. 544-572. PMLR, 2022.
Kamath, G., Mouzakis, A., Regehr, M., Singhal, V., Steinke, T., and Ullman, J. A bias-variance-privacy trilemma for statistical estimation. arXiv preprint urXiv:2301.13334 2023.
Karwa, V. and Vadhan, S. Finite sample differentially private confidence intervals. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-ZZnnte fuer Informatik, 2018.
Kasiviswanathan, P., Nissim, K., Raskhodnikova, and Smith, A. Analyzing graphs with node differential privacy. In Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, pp. 457-476. Springer, 2013.
Kothari, P., Manurangsi, P., and Velingker, A. Private robust estimation by stabilizing convex relaxations. In Conference on Learning Theory, pp. 723-777. PMLR, 2022.
Krizhevsky, A., Nair, V., and Hinton, G. Cifar-10 (canadian institute for advanced research, cifar-10 toronto. wttp:ntt...ddekkii/iiiiaarar html 2009.
dataset). https://wwwt
LeCun, Y., Cortes, C., and Burges, C. Mnist handwritten digit database. AT&T Labs [Online]. Available: http://yann. lecun. com/exdb/mmnis 2010.
Liu, X., Kong, W., and Oh, Differential privacy and robust statistics in high dimensions. In Conference Learning Theory, pp. 1167-1246. PMLR, 2022.
Lyu, M., Su, D., and Li, Understanding the sparse vector technique for differential privacy. Proceedings of the VLDB Endowment, 10(6), 2017.
McMillan, A.. Smith, and Ullman, Instance-optimal differentially private estimation. arXiv preprint arXiv:2210. 15819, 2022.
McSherry, F. and Talwar, K. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp. 94-103. IEEE, 2007.
Nash, W., Sellers, T., Talbot, S., Cawthorn, A., and Ford, W. Abalone. UCI Machine Learning Repository, 1995. DOL: https://doi.or//1..2222 watpr//g....4444.. 24442/255C77
Nissim, K., Raskhodníkova, S., and Smith, A. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 75-84,20 2007.
Smith, A. presevipr statistical estimation with optimal convergence rates. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 813-88 822, 2011.
Thakurla, A. G. and Smith, A. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, pp. 819-850. PMLR, 2013.
12

---

Tsfadia, E., Cohen, E., Kaplan, H., Mansour, Y., and Stemmer, U. Friendlycore: Practical differentially private aggregation. In International Conference on Machine Learning, pp. 21828-21863, PMLR, 2022.
Wickham, H. ggplot2: Elegant Graphics for Data Analysis. Springer-Verlag New York, 2016. ISBN 278-3-919-44277-4. URL
13

---

A Additional Analysis of Asymmetric Sensitivity Mechanism
In this section, we give full details upon extending our asymmetric sensitivity mechanism to general functions f X + R and provide more efficient implementations. We also provide all missing proofs from Section
A.1 Approximate asymmetric sensitivity mechanism
As noted in Section g computing the upper and lower outputs bounds can be inefficient or even infeasible, which is necessary for method, inverse sensitivity method, and smooth sensitivity method. As such we provide approximation of these bounds that is slightly more granular version of the approximation method provided in Asi & Duchi (2020a) and also applies the inverse sensitivity mechanism.
R, we define approximate upper and lower sensitivity bounding functions of Hamming distance f to be U, X - R and ry x" R, if for all 2 and any neighboring datasets x, x we have (x(x) 2 Uf(x) and U (x) s U (x') along with Tx(()) 11)(x) and [1((x) (x)
Definition A.1. For a function f A -
In particular, this definition separates the approximation for the upper vs lower bounds opposed to treating them symmetrically. This maintains asymmetry which is precisely where our technique excels most. We then define variant of closeness for each output to the underlying data which utilizes these approximate upper and lower bounds.
Definition A.2. For function I E R, we let
x" - R along with Uy : x² - R and I x - R, for any
(x;1( def inffe [2(x)) (((s)sssU(()
Outputs can only be closer to the underlying data under this approximate definition which could hurt accuracy, but will still give the desired privacy for inverse sensitivity mechanism. We then extend this definition equivalently for our reflective inverse sensitivity.
Definition A.3. For function I E IR, we let
xm along with UT : x R and E, X2 for any
(x;;)) sgn(t f(x)) [Len((x:t)) -
We will then be able to show in general that the approximate reflective inverse sensitivity of an output maintains closeness between neighboring datasets. This gives the approximate asymmetric sensitivity mechanism for a stream of potential outputs {t} that calls AboveThreshold and returns & when
AboveThreeholld(x (s7x
(1
(M.3)
This will then achieve the same privacy guarantees which is shown in Appendix A.3
Theorem A.4. Given - R and any stream of potential outputs {t), we have that mechanism
- M.3 (e, + 2DP in general and (e, + e2) sy is monotonic.
A.2
Analysis for exact asymmetric sensitivity mechanism
We first prove a helper lemma regarding the closeness of the reflective inverse sensitivities for neighboring datasets.
Lemma A.5. Given sample-me himple-monotoneff f x - R, we must have (m(f) is a convex set, and for any neighboring datasets x, x' e x and E im( we have (x; sy(x';t)l
Proof. first show the image is convex. For any a, E f), there must be datasels xa, xy E X such that f(x,) = and f(x)) b. Furthermore, by Definition 2.1 we know (x,, xb) S
14

---

len b) n. Without loss of generality assumee a S b, then by Definition 3.2 for any E [ we must have (xny(xx;c)) n which implies E im(s).
Next we show the closeness between neighboring datasets. First consider the case when t > fx)) f(x)) or I < (x), f(x)]. This implies sgn(t - f(x) sgn(t - f(x)) and the
bound follows from Corollary 2.9 Without loss of generality, assumee f(x) 2 f(x) and consider
the other case when f(x)
fxx). Due the fact that they're neighboring leny(x; f(x)) &
and [x'; f(x) & 1. Applying Definition 3.2 (x; I and (xn)(x';1) )) I which implies
(sy()::)) 1/2 and (x);))))) s 1/2 giving the desired bound.
With this lemma we can prove Theorem 3.3
Proof of Theorem 3.3 For 4 () know the sensitivity is most from Lemma A.5 Further t; $ im then by the convexity of im(() from Lemma A.5 we know that either 4 < f(x) and so
sy(x, = -oo for all E 2" or f(x) and sy(x,t) oo for all x E &". 'he privacy guarantees then follow from Proposition 2.5
We also provide a proof of Lemma 3.5 connecting the inverse sensitivities to the upper and lower output bounds for sample-monone monotone functions.
Proof of Lemma 3.5
First consider the case when < (x) or (x),), which implies inf[
(x) St (x) because the infimum of the empty set infinity. This also implies that
im(() so (x;1) = co for the same reason. Next, consider the other case when (x) S S (x) and let k = inf(( (x(x) < Uf(x)), there exists x' such that f(x) = I and d x)) = K < k.
then this would imply Ly (x) S 1 S Uy (x), so inf(e 1)(x)) SIS Uf(x)3 < giving contradiction. Thus we must have (x;; ) 2 Furthermore, the sample-monotone definition implics that (x; S k because 12 (x) S & Ux)x). Therefore, we also have (x; k.
A.3 Analysis for approximate asymmetric sensitivity mechanism
We again prove a helper lemma regarding the closeness the approximate inverse sensitivities for neighboring datasets.
Lemma A.6. Given X" + R. for any neighboring datasets x' x" and infx(f(x)) S (x)) we have (x; - (x'; $
sup=(f(x)) because the Hamming distance between any datasets is always at most n. Thus we must have (x; S and (x') Without loss of generality, assume (x;) s (x') and (x; = f. By Definition A.1 we then have I75 (x') < tt (x)((x))))))))))))))))))())))( so (x': :t) $ ++ 1, which implies our desired inequality.
Proof. By construction, (x) (x)) and (xxx)
We then extend this closeness the approximate reflective inverse sensitivities for neighboring datasets.
Lemma A.7. Given f X + R. for any neighboring datasets x, x' e x" and infx(f(x)) S 1 sup, (x)) have (x):)) 57 11
Proof. First consider the case when 1 (x) or << f
This implies
sgn(t - fx)) = sgn(t - fxx)) and the bound follows from Lemma A.6 Without loss of generality, f(x') and consider the other case when f(x) 2 2 f(x). Due to the fact that
assume f(x)
they're re neighboring and Definition A.2 we have (x; < 1 and len (x':t it $ This implies (5)(x;1) 5 1/2 and (x);)))) S 1/2 giving the desired bound.
With these lemmas now prove Theorem A44
15

---

Proof of Theorem A.4 For such that infx(f(x)) S t S sup,if(x)) we know the sensitivity is at
most from LemmalA.) Otherwise either 4 < f(x) and so (x = -co for all x E x or > f(x)
and so 1x = for all x é x². The privacy guarantees then follow from Proposition 2.5
B Supplemental Results
In this section we provide supplemental results and experiments to our main results. We first show that the asymmetric sensitivity mechanism naturally handles unbounded data for our instantiations with negligible accuracy loss. Next we provide a simple, general, and robust stralegy for selecting potential oulputs for our method and provide a corresponding empirical study. Finally, we discuss how our methods can also apply to the add-subtrae definition of neighboring datasets.
B.1 Naturally handling unbounded data
As previously discussed in our instantiations from Sections 5 and 6 the functions considered will have infinite upper output bounds if the data is unbounded. Given the iterative nature of the sparse vector technique, we will be able naturally handle this setting with negligible accuracy loss. In particular, Algorithm 1 oulputs the first query above the threshold, and we see from our Definition A.3 that even if (x) = co then we will have that the reflective inverse sensitivity is 1/2 for all possible outputs greater than f(x). Thus each query of potential outputs greater than f(x) is more likely than not to terminate the algorithm. The probability of termination increases even more if the reflective inverse sensitivity is greater than 1/2 but will have minimal effect.
We test this upon our variance instantion by using the bounds from Section 5 and also considering the unbounded case. We also use the same parameters and datasets from Section 3 From Figure 3 we see that the difference in performance for the unbounded setting is slim and thus our method can inherently consider unbounded data.
Vartance ectirusion damonde
Varlance ectimattce
Varaecee rstimation for
Prinyy powmeter 51
Vallance estination for adult Dours) daz
Variance est mation For adult Lagel data
anded
Figure 3: Plots of the absolute error for variance estimation with both reasonable bounds on the data and unbounded data.
While this works for our instantiations, this is aided by each function being non-negative by construction, and applying our method generally to unbounded data will often require an innate lower or upper bound on the function output. In contrast, efficient implementations of the inverse sensitivity mechanism require both upper and lower bounds on the function output, and often further require bounded data for reasonable accuracy such as in our instantiations. More specifically, the inverse sensitivity mechanism uses the upper and lower oulput bounds from Definition 3.4 to construct intervals and draws an interval from the exponential mechanism and uniformly selects a point from the chosen interval. But this requires setting a data independent upper and lower bound from the function for efficient implementation. This efficient approach was first seen in
16

---

an instantiation of a close variant of the inverse sensitivity mechanism for privately computing quantiles /mith 20011.
B.2 Robust and efficient potential output selection
In order to handle both fully unbounded and partially unbounded functions, we provide an efficient and robust potential output selection method that also borrows from the private quantile literature Durfee (023). which instantiates a close variant of our asymmetric sensitivity mechanism. In Algorithm 2 We provided the explicit approach for selecting potential outputs when the outputs are non nog-negative. This same approach can be shifted to handle any other lower bounded functions and symmetrically applied to upper bounded functions. The exponential nature of the potential outputs implies that they will become incredibly large or small within a reasonable number of queries which limits the running time. Specifically, if we set reasonably assume ß 2 1.001, then f50m > 10 and we can simply terminate AboveThreshone after at most 50,000 queries for all datasets without affecting the privacy guarantees.
the function has no innate bounds then we can call sparse vector technique with two iterations, searching through the positive numbers first, and then searching through the negatives if the first iteration immediately terminated. If the function has both innate upper and lower bounds then we can uniformly select the potential outputs from these bounds.
Vettence votinaion for deererch
Nereecxiiiimatoo abalame
Veriece estimaioon lor
39
30
1P
Plaay
Vaturco salirndion hours
Veruence mation for lagel
$01.0
Figure 4: Plot of variance estimation using our method for different / parameters
While this methodology introduces a new parameter / that must be selected independent of the underlying data, we were able to fix B = 1.005 as a default and still see high performance across different invocations and datasets. Furthermore, we show here that we could consider other reasonable settings of ß and still see robustly accurate performance from our methodology. In fact, from our experiments we can see that our empirical results could have been further improved by setting / = 1.01
B.3 Add-subtract neighboring
In Definition 2.1 we made the notion of neighboring datasets follow the swap definition. Another commonly used notion of neighboring datasets in the differential privacy literature is the add- subtract definition where a users data is added or removed between neighbors. Our asymmetric sensitivity mechanism can naturally extend to this notion of Hamming distance well.
The primary difference would be that all datasets in the data universe would no longer be at most distance n from one another the size of the dataset could vary. As such, the list of upper and lower oulput bounds could be infinite, but we can circumvent this with minimal practical impact. Potential outputs far from the underlying data are already incredibly unlikely to be selected so
17

---

relaxing the bounds will barely affect the output distribution. As such, we can set the approximate upper and lower bounds to be positive and negative infinity, respectively. which is essentially identical to what was done in Lemma 5.3 To account for this changed definition we would also need to update the upper and lower output bounds for our instantiations.
C Intuition and Asymmetric Advantage
In this section, we first give sensitivity mechanism. We then provide strong intuition upon why our method will substantially improve the estimation accuracy when the sensitivities asymmetric by the bias-variance tradeoff. We further supplement this intuition with a formal metric that quantifies the asymmetry of the sensitivities, and we empirically validate that increased asymmetry directly corresponds to improved relative performance of our method. Finally, we give the missing analysis of Lemma 4.1 our theoretical utility guarantees.
visual explanation of methodology compared to the inverse
naturally balancing
C.1 Visualization of both methods
Recall that the inverse sensitivity method considered the distance metric of any output from the underlying data in Definition 2.8 We then proposed variant of that definition better suited to applying the sparse vector technique in Definition 3.1
Figure 5: We provide here an informal visualization of the inverse sensitivity and reflective inverse sensitivity. For most functions of interest we can just plot these step functions using the upper and lower output bounds from Definition 3.4 In the plot, denote [²(x) and (x) with Lk and Uk, respectively. We will go into further detail in the next section but note that the sensitivities are perfectly symmetric in this example.
-23
14 LOME
Both of these functions essentially shift between neighboring datasets which allows for maintaining closeness between outputs for each metric. We further note that unlike the inverse sensitivity, shift in the reflective inverse sensitivity will monotonic because of it's increasing nature, allowing for improved privacy guarantees for many instantiations. Given the closeness between outputs for neighboring datasels, we can apply the exponential mechanism or sparse vector technique. Applying our method entails considering increasing stream of potential output {4} and (noisily) identifying when the reflective inverse sensitivity crosses from negative to positive by calling the sparse vector technique.
Figure 6: We provide here an informal visualization of the approximate PDFs for inverse sensitivity mechanism (ISM) and asymmetric sensitivity mechanism (ASM) when the sensitivities are perfectly symmetric. We slightly alter our mechanism M.3 to uniformly draw output in [tt-1, 4 for easier visualization, which implies our PDF will be a step function between the potential outputs.
The iterative nature of the sparse vector technique will most often lead our method being slightly more likely to find output less than the true output. This introduces bias into our mechanism but we still remain competitive with inverse sensitivity even in the perfectly symmetric setting.
C.2 Naturally navigating the bias-variane tradeoff
In Figure G we assumed that the sensitivities were perfectly symmetric. More specifically, for {> we let xf) def (x) Lx( and (f) def Uf(x) -5(x))UFF (x), which are the amount the function can marginally decrease and increase, respectively, by changing the S individual's
18

---

data. Note that for (= these quantities correspond to the local sensitivity. We then say that the sensitivities are perfectly symmetric if Ai(f:x) = xf:x for all f >> O, which held by construction for our examples in the previous section.
Informally, we will say that the sensitivities are asymmetric if Mf(f=) << :f(f:) (or the reverse) for most particularly those closer to 0. We now consider an example in which the upper and lower outputs bounds imply asymmetric sensitivities and compare the approximate PDFs for each method.
Figure 7: We provide here an informal visualization of the approximate PDFs but with asymmetric sensitivities. We re- move the labels for 1x)(x), (x)x and 1x)(x) as they become too condensed around f(x) but we keep their tick marks the x-axis. We again slightly alter our mechanism [. to uniformly draw an output in [4-11, 4e] for easier visualiza- tion, which implies our PDF will be step function between the potential outputs.
For more encompassing discussion on the bias-variance trade-off, we first consider applying the smooth sensitivity framework to this example. Smooth sensitivity is unbiased in the classical sense (the expected output matches the underlying data) but the noise is added proportional to at least the local sensitivity which would be (f) here. The inverse sensitivity mechanism weakens the unbiased definition to better take advantage of the asymmetry from xf(f:x) << xf(f:x) and we see in Figure 7 that the probability mass of outputs less than f(x) becomes much more closely concentrated around f(x). However, using their notion of unbiased still limits the extent that it can improve the private estimation. In contrast, a variant of the preprocessing method from Cummings & Durfce (2020) could be applied here and potentially be both unbiased and have low variance if the priori sensilivity parameler closely matches the x((f:x) for & close to zero. However, applying this same reduced sensitivity parameter, which essentially fixes the variance and must be data independent, would lead to significant bias in 6
By adding the slight bias towards early stopping from the iterative nature of the sparse vector technique, we can take full advantage of the tighter grouping of the lower output bound to signif- icantly reduce the variance. More specifically, if we map Figure to these lower output bounds, then the reflective inverse sensitivity will be much steeper right below f(x), which has the biggest impact upon when sparse vector technique terminates. In fact, we could set the upper output bounds to be infinite and this would only slightly decay the accuracy of our method. This allows us naturally consider unbounded data for variety functions, and we specifically examine the effects upon variance estimation in Appendix B.1 with empirical results showing negligible impact upon accuracy. While our method does still have dependence upon the data fata-independent stream of potential outputs iti), we provide a simple and general strategy for this selection in Appendix B that robustly maintains accuracy across different invocations and datasets. As result, the slight bias from our method can utilize the asymmetry for significant improvement while also remaining competitive under perfect symmetry, giving a more inherent optimization of the bias-variance trade-off.
C.3 Formalizing asymmetry of sensitivities
We previously defined asymmetric sensitivity to informally be a consistent mismatch between xf(f:x) and xf) for most f. Additionally, this mismatch has the highest impact when / is closest to 0, as the outputs farther away from the underlying data are far less likely to be selected. However, the level of privacy further affects this likelihood where smaller implies mismatched xf(f.x) and x)) have a higher impact upon symmetry for larger f. Therefore, to obtain a formal measurement of asymmetry, z but with higher weight given to smaller f and this weighting should be further scaled by the privacy parameter. We observe that the inverse sensitivity mechanism uniformly draws from [T. 1.f-1 and [U with probability proportional to Af(f:x) exp(-e-x/2 and Aff;x) exp(-e- 8 E/2), respectively, by construction of the exponential mechanism. This then precisely fits with our desired weighting and the probability that the inverse sensitivity mechanism selects an output greater than
should consider averaging of xf((f;x) vs (f:x) over all
19

---

f(x) is simply normalization of -xxx((t))) With this connection of our informal notion the inverse sensitivity mechanism, we then give formal definition for measuring the asymmelry of the sensitivities.
exp(-t-e/2).
Definition C.1. Given function f d" 7 R, we measure the asymmetry of the sensitivities by
Pr [M)n f(x)]
based upon the probability distribution from M.1
Accordingly, we have that the sensitivities are symmetric if f(x) is the median of the inverse sensitivity mechanism. But this property does not imply accurate estimation as the variance could still be quite large. However, it is not surprising that it will perform relatively worse than our method for more asymmetric sensitivities. We empirically test this conjecture across different levels of sensitivity symmetry, which we also vary by toggling the level of privacy.
rrverse vity vecterian Asymeeetic Senn Mecvarsin
Figure 8: We consider a range of randomly sam- pled output bounds and privacy parameters and compute the absolute error of our asymmetric sensitivity mechanism (ASM) and the inverse sen- sitivity mechanism (ISM) over a small number of random draws. We plot the (error ISM) (error ASM) corresponding to the asymmetry of the sen- sitivities for the given oulput bounds and privacy parameter.
30h
Roymennity Jond
For our simulations we uniformly distribute the lower and upper output bounds and toggle the range of the upper output bounds to vary the level of asymmetry. We also consider upper output bounds that are more heavy tailed and toggle the level of privacy, thereby determining the impact of the tail, to vary the asymmetry of the sensitivities. For each simulated output bounds and privacy parameter, we compute the asymmetry of the sensitivities and we make several calls to both methods for private estimations and compute the average absolute error of each. While these simulations are not all-encompassing, they empirically validate our provided intuition, and we will further see in our instantiations of functions with inherent asymmetry that our methodology gives substantially improved estimates.
C.4 Analysis of theoretical utility guarantees
In this section we provide the proof of Lemma 4.1 Our proof will first bound the probability that we output value that's 's too small and then bound the probability that we output a value that's too large. As a result, provide two helper lemmas for each direction that are close variants of Theorem 3.24 in Dwork et al. 2014).
Lemma C.2. For any sequence of queries fi.... fm with sensitivity such that (fi S m f(x) 2 T - all = 0, then Algorithm] 7 (where we set E E2 and E1 + 28z) will terminate during these queries with probability at most m m-e-ar) -a/3
Proof. We know that exponential noise is non-negative, so to terminate at query i, the noisy result must exceed the threshold. By the CDF of the exponential distribution and our assumption, we have - [f(()) + v; > T] s m//3 Applying union bound over all m queries gives our desired result.
Lemma C.3. For any sequence of m queries fj. with sensitivity 1 such that Hi E (j.j m) flx) < T + atl 0, then Algorithm (where set E2 and e1 + 20z) will terminate at query j or later with probability most e -4/3 /2/33/m /
20

---

Proof. In order to terminate at query j m or later we need that the noisy threshold is above all previous noisy queries. Let Vy Expo(3/e) and V Expo(3/e). There are m indices in (j. +)) so by independence we have
1
Pr
VT
max
Vi
m
(EU.++m)
and furthermore by change of variable and the PDF of the exponential distribution
cre/prr VT a
Vr
max Vi (...).m)
max Vi (cU.+m))
Due to our assumption that f(x) 2 T + for alli (j. we see that Pr [VT a > max vi] an upper bound on the probability of still continuing at step j + m. This implies our desired claim.
Proof of Lemma 1.1 We first show Pr [M(x) < (x)) C/ke for constant C. By Defini- tion 3.1 and Lemma 3.5 we know that for any L [lnk+((x)) (x) we have (x;;;; T-lIkk Furthermore, we assumed that f(x) f for a constant C and = B -1 so lc f(x) 2 (x). We then apply Lemma C.2 with 0 lnk and m = C, which implies Pr [M(x) < (x)) <C/ket/6 for constant
Cas desired.
Next, we want to show that Pr [M(x) > (f(((x) 1) < C/ke*/s /6 for a constant C. Using the fact that f(x)+1 > there are at least k- values of such that E (f())) By Definition 3.1
and Lemma 3.5 we know that for any 4 [fx)) f (f(x) 1)] we have (x(x;)) 1/2. We
then apply Lemma C.3 with a 1/2 and m get that Pr [M(x) (*((x) 1)] 1/ke as desired.
Combining these inequalities gives desired
Pr [lM(x) - f(x)) < max(lf(x) [lo (D(F)))) > 11-0
kee/
Corollary C.4. Let M denote the mechanism from M.3 with 4, B - where B >> 1 and we let
== El + 28z with e = Eg in the call to Algorithm| I Given non-negative f x.- we have
Pr [I(()) f(x)) < maxilf(x)) logk (bb))((((()__b))))))))))))))) (ft 1)(f(x)++++))) 1)1] >1 1-0
ker/6
when f S BO0).
Proof. The proof follows identically but instead of applying Lemma 3.5 we can directly use Defini- tion A.2 and note that setting Lł I, satisfies Definition A.1
D Additional Analysis of Variance Invocation
In this section we provide the necessary proofs for the efficient variance instantiation of our method. Most of the analysis could be considered folklore properties of variance it is such well-studied statistical property, but we duplicate some of these properties for completeness. We first provide known alternative definition of variance.
Definition D.1. Let X = R and for E X",
equivalently define variance
Var [x]
def
(xi x1)
n
21

---

We will also add some helpful notation where for any S S [n] we let xs {xy : E S} and similarly for any < a b Σ we let x[abb] (xas Xt).
D.1 Analysis for Lemma 5.2
We first prove helper lemma that if individuals data is changed in order to minimize variance, then those values should be be the mean of the remaining values.
Lemma D.2. For any
x and any S c [n], have that
inf Var [x]
Var [x]]]ss]
Proof. By least squares minimization know that Eiern y) is minimized by setting
1
Σ tE(n
y
we x; K| for all S, then we have R and we have Exs(x x)² which must be minimal by the non-negativity of squared error. Combining these properties we get
inf Var [x] =
Σ (x {) [
Xs
We can then apply our Definition
5.1 to gel our desired result.
With this helper lemma we can then provide the proof of our lower output bounds through a proof by contradiction.
Proof of Lemma 5.2 By Lemma D.2 we have that
(x)
min [S
n
Var [x]NNs]]
We will then give our desired claim through a proof by contradiction. Suppose this is minimized by S C [n] with some S such that there exists j.k é where x, <; Xg. Let Sj (S ()) and
S = (S u To obtain our contradiction it then suffices to show that
min Var (x) Var [s Var X
Applying our alternative formulation of variance from Definition D.1 we have
Var [x]])]]
Σ
Σ
(x. xb)²
S bein]ss
Through cancellation like terms have
Var [x) Var [x]])s]
Σ (x, x, deIn|N(S,u0
Σ (x, x,)²
ae(n|(SU))
By construction we have (s, u = (S (), j), so by the convexity of least squares minimization and the fact that x, X;, we have that this inequality holds if x; (su)) Equivalently, we have
2 {()((ss)) Var (x < Var [x]])]]
22

---

Further, we know that ( > ((n)((s.)) because x, < x/. Therefore we must have either xi I (su) or x; 2 FlaNssub which implies
min { Var [x Var [MInNs Var [x]ass]
and gives our desired contradiction.
D.2 Analysis for Lemma 5.3
In this section we prove that the approximate lower output bounds fit Definition A.1 and can be efficiently computed. We note that these lower output bounds will still maintain high accuracy because the bounds further away from the underlying data have far less effect upon the mechanism and accordingly, loose bounds will have little effect.
Proof of Lemma 5.3 Recall that we assumed a fixed constant, and defined (ar = Var (x) for IS c and Var = for f> c. By construction, we know that variance non-negative, so we must have Varr(()) (x) 2 0 for all This then implies [x(()) S (x(x) for all Furthermore, if / c
then we immediately have [1(x)) 2 (x') Otherwise 1,(xx) = (x) and we know by definition that 11(()) 2 (x') which implics [,,()) 2 [x))(x))
For the runtime, by Lemma 5.2 see that it suffices to compute Var [x]e-=-:--]]] for all 0 < S c, where we assume x; S S x,. However, this ordering only matters the largest and smallest values, we compute these in O(n + log(c)) time. Further, O(n) time and will utilize the well-known fact that variance can computed in O(1) time with these quantities. We can then just iterate through all i, such that 0 S i S updating the sum of variables and squares compute each Var [x((-1-in-1]] in 0(1) time taking total of O(c") time.
compute Σ x; and Σ xf in
D.3 Analysis for Lemma 5.4
Proof of Lemma We first show that for any neighboring datasets x, we have U Var Te1 (x'). By construction, this reduces to showing that Var [x] S Var [x'] + (b - (b-a)3/a n.. Let i be Var
the index such that x, xt. Applying the alternative variance formulation in Definition D.I and cancelling like terms reduces this showing
n -x1-xx)) a)
Σ (x x,)=
n
n
We assumed that all datasets were restricted bj" must then have (x, (x-xx)) n(b-a)? which then implies our desired inequality by the non-negalivy of squared error.
Next we show that U (x) S (x). It suffices to show that for an arbitrary x' such that chan(x, x') = f we have Var [x'] S Var [x]+ (b-o)) We previoooull showed that Var [x] 2 Var [x]++ (b - a)2 for any x, such that (x,) = 1, so our claim then follows inductively.
Therefore, our construction of Var satisfies Definition A.1 as desired.
E Additional Analysis of Model Evaluation Invocations
In this section, provide the definitions and implementation details for applying our method to machine learning model evaluation functions. We further unify this analysis by considering applying our methodology to linearly separable functions.
23

---

We now define our datasets as (x, x and we set dnan((x, (x'))))))))))))))))))))))))))))) Hi x or * yf to the Hamming distance between datasets. We will be considering binary classification and multi-class classification, we define cross-entropy loss for both.
Definition E.1. Given machine learning model for binary-caasiffcation @ : X + R and assume all y {0, 1}, let
wlx)
(x Σ yi log ( e - -(1 - (1-y)log
1 + e e-xxx
Similarly, given machine learning model for multi-classifictiion @ & R with c classes and assume all y/ E [c]. let
caoxidy
(x, =- Σ log 1=1 E embxi))
We also define the mean squared error and mean absolute error. Definition E.2. Given dataset (x, y) and machine learning model & - R, we define
(x, Σr (w(() - yt
and
MAE En lo(xx) Vil
n
E.1 Application to linearly separable functions
In this section we consider all linearly separable functions f : x²" such that
f(x) Σ ((x))
where X R. We could also extend our results here that are specific the index, but for simplicity we will restrict our consideration. Without loss of generality assume the indices are ordered such that [(x)) ((x+1). We first provide lower output bounds for these functions.
Lemma E.3. Given a linearly separable function
X R, then
l)(x)= = Σ ((x)+ t inf (C(xx) x1E2
Proof. Changing any individual's data only change their contribution to the sum by the linearly separable property. Therefore, decreasing the indiiiiuslss with the highest contribution to the sum must minimize the function for datasets with Hamming distance l from the underlying data. O
Similarly, we provide upper output bounds for linearly separable functions. Lemma E.4. Given a linearly separable function f X R, then
Uf(()) Σ ((x)+ c(p))(x;)}
x
Proof. Follows equivalently to the proof of Lemma E.3
We then provide approximate relaxations of these bounds that will allow for easier application.
24

---

Lemma E.5. Given a linearly separable function f : A' - R, then approximate upper and lower
sensitivity bounding functions U x and L X" R satisfy Definition A. for
n-
[x(x)
+(x)+
and
0x(x)= Σ +
ifa S infxex(((xx)) and 2 sup (xxx(((()))
Proof. We show this the approximate lower output bounds and the upper follow equivalently. We first have I2((x) s (x) by construction. Next, for neighboring, x, x,x',el let be the index at which xj x/. We assumed an ordering to the indices for simplicity, but we equivalently have
(x(x
min { ((x)) + +c- SE|n)-1S--n-e
BES
For some given f, Se be the subset of indices that minimizes this for (2(x). If @ Sy then we have [f(x) 2 (x'), so rj(x)= 2 (x'). Otherwise, we know that
(x')
min (5
E
E(x)) + (f+1).as Σ ((x,) + (f+ 1)
IES
and because a [(x,) then this implies 12(x) 2 2 (x)
We further show that our approximate bounds allow for monotonic reflective inverse sensitivities which implies improved privacy guarantees.
Lemma E.6. Given a linearly separable function f X R, along with approximate upper and lower sensitivity bounding functions UG x - R and 12 x R such that
[x,(x) = a-1
c(x)++
and Uf(x) = Σ c(x)+
where a & infx, exf(x))(((xx)) and 2 sup mex ((xx)) For any neighboring datasets x, x' we have that either eithers,(x;11) S 1));;;1 for allt or (x; t) 2 s7(x';) :t) for allt e R
Proof. Without loss of generality, assume f(x) < f(x') and we will show sy(x;)) st(x:t) for all
t e R.
We first consider e f(x)) Given that the datasets are neighboring, we must have L)(x) <
I s U)(x) and L)x')) s U) (x'). By Definition A.1 and Definition A.2 we have that (x;t) S
and (x':1) < 1. Given that i [(x)) this then implies (x; 1) E 03 and 57(x;1)
{-//2, 03. Therefore 1);x;)) 2 57(x)tt)
Next consider the case when t < (x)) This implies sga(t - fxx)) = sgn(t - f(x)) = -1 and also
that (xn)(x;t) and (xn, 1. By Lemma E.7 we have that [2(xx) $ (xx) for all f
which implies (x; < (x';t) and therefore (x;;)) 2 sy(x';t).
Finally considert > f(x'). This implies sgn(t-f(xx) = son(t-f((xx
and also that (x; 2
and (xn,(x';1) 2 1. By Lemma E.7 we have that (x(x)) s (x') for all 2 0, which implies (x: 2 Ixny(x': and therefore sy(x;)) st(::)t)
We will also require the following helper lemma in order prove Lemma E.6
25

---

Lemma E.7. Given a linearly separable function f X' - R, along with approximate upper and
lower sensitivity bounding functions U x R and Dj x R such that
(x)x = Σ [(x)) +e.
and Uf(x)= = Σ ((x)+ + +
wherea S inf infxex(((xx) andb 2 ((()))) For any neighboring datasets x', iff(x) - f(x) then 12(x)) < 111xx') and (x( s (x'(x') ( for all
Proof. Let j be the index at which x; x', which implies [(x,) S L(xx) because of our linearly separable property. We assumed an ordering the indices for simplicity, but we equivalently have
[j(x)=
min SS-a-t
<(x)) + a-a
N&
For given llet Sx denote the set of indices that minimizes 1f(x') If E Sx then we have
11(x)= = L(x))+ +
Σ
[(x:) + +. (xx))
E [(x)) + a- a= [(xx) + +- (x)
RS
16
Similarly, if Sx then
1,(x)= = Σ e(xx)
+ e. 12(x)
165
The proof for U7(x) S xx((') follows equivalently.
E.2 Efficient cross-entropy loss instantiation
We will provide the efficient instantiation for multi-class cross entropy loss as this can easily be extended binary cross entropy loss. Without loss of generality, assume the indices are ordered such that
log
S 5 log
Σg jml elabtid
Ejm1 eiulxeaal
We can then provide the lower output bounds for cross entropy loss Lemma E.8. Given dataset yx and machine learning model as X - R then
L's (x = Σ log
E eaotxn)
Proof. We apply Lemma E.3 and Lemma
E.5 and we observe that
en(xi,
inf
log
20
Σ j=l paltst)
X.Ji
As seen with variance Section 5 we have that U3 (x.y) = 00 which implies that cross-entropy loss has inherently asymmetric sensitivities. Similarly, we will need to restrict the range of these values order apply inverse sensitivity mechanism even though our method could easily handle the unbounded setting. We provide proof for these upper output bounds in Appendix E
26

---

Lemma E.9. Given a dataset y) and machine learning model @ : & - R where we restrict dxx)) [a, bl for all then
ca-b
CE, (x.
f-log
log
ca-b +
Σj= euiltel
Proof. We apply Lemma E.4 and Lemma E.5 and we observe that with restricted bounds have
ealxidg
}
ea
sup X,91
log
Σ j=1 ealxity -log
e --
+c
The corresponding algorithm for instantiating cross-entropy loss with our method similar to Algorithm 2 The privacy guarantees from Theorem 5.5 also follow equivalently, but can additionally improve the privacy to be (6i + +DD by applying Lemma E.6 to achieve monotonicity. We also achieve O(n log(n) + q) runtime by computing all of our approximate upper and lower bounds, but we could also easily employ the same strategy of setting these bounds to be infinity and zero, respectively, for all e where we set c 100. This then gives the linear runtime, where we also utilize the fact that we will never run AboveThreshold from more than 50,000 queries.
E.3 Efficient implementation for regression evaluation
will only provide the efficient implementation for MSE in this section as MAE will follow identically. Without loss of generality, assume the indices are ordered such that (w(x)) y)) (w(x+1) - )
Lemma E0 Given a dataset (x. y) and machine learning model a X R, then
E (x,y) (xxxx))))
n
Proof. We apply Lemma E.3 and Lemma
E.5 and observe that
(nf((())) - y))² 20
As seen with variance in Section we have that UÍsE, (x, which implies that MSE has inherently asymmetric sensitivities. Similarly, we will need to restrict the range of these values in order to apply inverse sensitivity mechanism even though our method could easily handle the unbounded setting.
Lemma E.11. Given dataset (x.y) and machine learning model @ X + R where we restrict ((x)) [a, b] and y; [a, b) for alli, then
U (x. y) (b a) + Em (wxx;) - )
Proof. We apply Lemma E.4 and Lemma E.5 and we observe that for our bounded setting
and
suplo(x,) y,) (b a)²
27

---

The corresponding algorithm for instantiating MSE with our method is identical to Algorithm 2 also
The privacy guarantees from Jls follow equivalently, but we can additionally improve the privacy to be (e, + e2) by applying Lemma R.6 to achieve monotonicity. We can also achieve O(n log(n) 9) runtime by computing all of our approximate upper and lower bounds, but we could also easily employ the same strategy of setting these bounds to be infinity and zero, respectively, for all e > where we set = 100. This then gives the linear runtime, where we also utilize the fact that we will never run Above T Threshold from more than 50,000 queries.
28

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We enumerate the main claims made in the abstract and introduction at the end of the introduction with pointers to each section that contains their support.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide an approximate variant of our method overcome the limitations of the exact method which are discussed. We also give theoretical and empirical details upon when our method is advantageous.
Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions for each theoretical claim is contained in the claim and all proofs are the appendix.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide full details on datasets, parameters, and experimental setup for all empirical results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described supplemental material?
Answer: [No]
Justification:
The data is open source and the code is straightforward to reproduce as all algorithms are simple, but we have not open sourced the code. We'd be happy to provide all code used upon request.
6. Experimental Setting/eetaile
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: For each empirical study and dataset specify all parameters, training/test splits and models used from open source packages.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appro- priate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All figures from empirical results contain confidence interval error bars.
8. Experiments Compute Resources
29

---

For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Our algorithms are lightweight so we just used basic colab notebooks run the different empirical studies, but this was not specified in the paper.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We believe this work conforms the Code of Ethics
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work only provides improved methods in differential privacy to give improved estimation for the same level of privacy.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We don't propose any algorithms models that could be considered high risk
12. Licenses for existing assets
Are the creators original owners of assets (e.g,, code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide citations for datasets used.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: We don't introduce new assets.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicabl,,, well as details about compensation (if any)?
Answer: [NA]
Justification: This paper doesn't involve crowdsourding or research with human subjects. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper doesn't involve crowdsourding or research with human subjects.
30


Reviews:
[{"review_id": "7lbwShG1gO", "reviewer": "Reviewer_GRDP", "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.", "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.", "limitations": "The authors have adequately addressed them.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "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.\n\nBy 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review of our work and their helpful feedback.\n\n\n$\\textbf{Weaknesses:}$\n\n\nWe greatly appreciate the reviewer's desire for intuition and strongly agree. Unfortunately we decided to put our main intuition section in the appendix (Section C) due to space considerations and are disappointed in our decision in retrospect. It is unreasonable to ask the reviewer to read this section, so we will briefly discuss here how it addresses the reviewer's concerns.\n\n\nFirst, the bias in the PDF from our method is actually towards selecting outputs below f(x) and not above as the reviewer seems to suggest (see Figure 6).  As a result, when the sensitivities are asymmetric then the bias in the PDF is beneficial for our method (see Figure 7). We explicitly define this asymmetry (Definition C.1) and then empirically test this more generally (Figure 8) to show that higher asymmetry of sensitivity clearly correlates with better relative performance of our method, and this is theoretically supported by our Lemma 4.1\n\n\nConnecting this to one of our use cases, variance, the reviewer is absolutely correct that non-negativity contributes to improved performance but the root cause is that changing one individual's data will most often increase variance more than decrease it (section D.1 has full details). In particular, if the data is unbounded then one individual can infinitely increase the variance by changing their data. This is also true of our other use cases (section E has full details) and in general we expect this to be the case for functions with inherent lower bounds (like non-negativity as the reviewer suggests) or inherent upper bounds.\n\n\nWe're more than happy to explain further and provide additional pointers if it would help.\n\n\n$\\textbf{Question:}$\n\n\nThis is a great question and is definitely a close variant of our approach. But it does seem that the process the reviewer is suggesting (continual querying until a threshold is exceeded) matches more with SVT / AboveThreshold as opposed to using propose-test-release which only tests one value and releases if the test passes. \n\n\nThis type of method using SVT would work and we agree with the reviewer that it's kind of a symmetric version of our method. But our intuition is then that this would only potentially be more effective with symmetric sensitivities and would also still be worse than inverse sensitivity in that setting.", "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": "", "extra_scores": {}}, {"review_id": "Oe2muaTGZZ", "reviewer": "Reviewer_Zw6m", "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.", "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)?", "limitations": "See weaknesses.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "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. \n- 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$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review of our work and their helpful feedback.\n\n\n$\\textbf{Weaknesses:}$\n\n\nCould the reviewer please explain further why they would classify our bounds as \"vacuous\" in reasonable settings? We certainly agree with the reviewer that asymptotic bounds can sometimes be loose in practice, but we feel this applies to the previous work as well. For the scenario the reviewer brings up, $f(x) << 1$, our upper bound essentially becomes absolute error (of approximately $\\beta^k - 1$) instead of relative error, but this is still non-trivial. Additionally, it is still true in this setting that our bounds are superior to previous work as $U_f^1(x) \\rightarrow \\infty$.\n\n\n\n\n$\\textbf{Question:}$\n\n\nAs was originally pointed out in the smooth sensitivity paper, unfortunately there are functions where computing even just local sensitivity is computationally infeasible, which is required for exact smooth sensitivity, inverse sensitivity, as well as our asymmetric sensitivity. Computing efficient and meaningful approximations of local sensitivity is then still highly dependent upon the function of interest for all of these methods.", "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": "", "extra_scores": {}}, {"review_id": "IW5INc1Vva", "reviewer": "Reviewer_J6Z2", "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.", "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?", "limitations": "The authors provide this part in the checklist", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The proposed asymmetric sensitivity and the query-releasing framework built upon it are novel and will benefit future research. \n* 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.\n\ntypo: L^{\\log k}} instead of L_f^{\\log k}} in Lemma 4.1 and its proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review of our work, helpful feedback, and catching an important typo.\n\n\n$\\textbf{Question:}$\n\nThis is a phenomenal question and a great catch by the reviewer. To answer it really requires digging deep into the intuition upon why our method performs better with asymmetric sensitivities. A brief summary is that:\n\n1. Greater asymmetry of the underlying instance correlates to better relative performance of our method (see Figure 8) and explicitly quantifying asymmetry not only depends on the underlying instance but also the privacy parameter (Section C.3 has full details)\n\n2. For variance and model evaluations, we generally have that the asymmetry of the underlying instance increases for higher privacy parameters.\n\n\n$\\textbf{Longer explanation of 1. (Section C.3 has full details):}$\n\n\nRecall in line 234 that we informally consider the sensitivities to be asymmetric if $|f(x) - U_f^k(x)| >> |f(x) - L_f^k(x)| $ for most $k$ (or vice versa), which is to say that changing an individual's data can generally increase the function more than decrease it. In order to explicitly quantify this we need to average this magnitude of difference over all $k$. However, this averaging should not be uniform because the mechanisms are more likely to select outputs closer to $f(x)$, i.e. within $[L_f^k(x), L_f^{k-1}(x)]$ or $[U_f^{k-1}(x), U_f^k(x)]$ for smaller $k$ values (this is a slight oversimplification). Essentially, the more likely the mechanism is to select outputs closer to $f(x)$, the more important the magnitude of difference is for small $k$. The privacy parameter directly affects this likelihood, so for higher privacy parameters the magnitude of difference for larger $k$ is more impactful in the quantification of asymmetry. We empirically confirm this intuition in our experiments for Figure 8.\n\n\n\n\n$\\textbf{Longer explanation of 2:}$\n\n\nThe summary here is that for variance and model evaluations we generally have that the magnitude of difference between $|f(x) - U_f^k(x)|$ and $|f(x) - L_f^k(x)| $ becomes larger as $k$ increases. As such, for higher privacy parameters the asymmetry of sensitivities increases and our method sees increased relative advantage.\n\n\nTo understand this we'll restrict to the variance instantiation for simplicity and assume the data is Gaussian. Changing one individual's data to minimize variance takes the min or max data point and moves it to the mean, and similarly to maximize the variance takes the data point closest to the mean and moves it to the boundary (note this is a slight oversimplification). This generalizes to changing $k$ individual's data. Due to the bell curve shape of the Gaussian, there are far fewer outliers compared to points close to the mean. As such, the amount we can decrease the variance lessens much more quickly with respect to $k$. This then results in the magnitude of difference between $|f(x) - U_f^k(x)|$ and $|f(x) - L_f^k(x)| $ becoming larger as $k$ increases.\n\n\nWhile the real data we use is not necessarily Gaussian, we still generally expect it to be somewhat concentrated as opposed to uniformly spread and the same notion holds. This same idea applies to model evaluation where we expect more errors to be closer to zero as opposed to very large.", "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": "", "extra_scores": {}}, {"review_id": "3okijXqJlN", "reviewer": "Reviewer_55Ug", "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.", "questions": "(1)Line 208: Why the computation time is O(log n?\n(2)In Definition 3.1,  why 1/2? Can we replace it with 0 or 1?\n(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?\n(5)Use the above example to illustrate the variance-bias tradeoff. \n(6)What is the advantage of asymmetric sensitivity mechanisms in this paper over inverse sensitivity mechanisms in the literature?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "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.\n(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. \n(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. \n(4)The citations usually appear in the main text not in the footnote (like in Page 7).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We know that the reviewing burden can be significant and are very sorry to have added to this burden by not presenting our results more clearly. It's clear that we attempted to fit in too many of our results in the main body and neglected better explaining the intuition of our methodology. In particular, we relegated our main intuition section to the appendix (Section C) and are very disappointed in ourselves for this decision in retrospect.\n\n\n$\\textbf{Questions:}$\n\n\nWe greatly apologize for not better clarifying these questions the reviewer raises. We attempt to do so $\\textit{concisely}$ here, but are more than happy to give further detail. \n\n\n$\\textit{Question 1 response.}$ The array $L^n_f(x),...,L^1_f(x), f(x), U^1_f(x),...,U^n_f(x)$ is ordered due to construction of Definition 3.4, and so inserting $t$ into this ordered array takes $O(\\log n)$ time. Where $t$ lands in this array then immediately implies the value of $len(x;t)$ by Lemma 3.5. For example, if $L^i_f(x) < t < L^{i-1}_f(x)$ then $len(x;t) = i$.\n\n\n$\\textit{Question 2 response.}$ This is best understood through Figure 5 where the reflective inverse sensitivity is a step-function and each step must be at most distance 1 apart to give the privacy guarantees (Lemma A.5). Subtracting 1/2 ensures this desired property (we're happy to give further detail).\n\n\n$\\textit{Question 3 (a) response.}$ We apologize for not clarifying, but sparse vector technique essentially just iteratively calls AboveThreshold (see section 3.6 of The Algorithmic Foundations of Differential Privacy). Given that we only need one call, we directly called AboveThreshold (which is in our preliminaries), but our mechanism is then essentially already written in the form of a simple call to sparse vector technique.  Intuitively, if we consider Figure 5 again, our mechanism considers outputs in increasing order and tries to identify when the reflective inverse sensitivity crosses from negative to positive, ie exceeds the threshold of 0 which occurs at f(x), by applying sparse vector technique.\n\n\n$\\textit{Question 3 (b) response.}$ We view the benefit in terms of the relative advantage of our method (answered in question 6)\n\n\n$\\textit{Question 3 (c) response.}$ To be clear, our technique can be generally applied and is just more effective than other methods when the sensitivities are asymmetric. An example of asymmetric sensitivities is for variance. If we change one individual's data point the amount the variance decreases is bounded, but the amount it increases can be infinite (section D.1 has full details).\n\n\n$\\textit{Question 6 response.}$ The benefit of our method comes when the sensitivities are asymmetric (changing an individual's data increases the function more than decreasing it). To best understand this we plot the PDF of both for perfectly symmetric sensitivities in Figure 6. As you can see, our method biases the output to be slightly below the true value. We then plot the PDF with asymmetric sensitivities in Figure 7 and see that our method has more probability mass around the true value in this setting. This intuition is discussed further in Section C and validated empirically with our instantiations in section 5 and 6, and theoretically shown in section 4.\n\n\n$\\textit{Question 5 response.}$ Our method is biased towards selecting outputs below the true value (discussed in question 6) and so the sensitivity of decreasing the function has more impact than the sensitivity of increasing the function on the variance of our estimate. Connecting to example in 3(c), for the unbiased estimators, smooth sensitivity and inverse sensitivity, the noise added is infinite (so infinite variance) because the local sensitivity is infinite. In contrast, adding some bias allows us to have variance that is proportional to the sensitivity of decreasing the function (which is bounded) and we still achieve high utility (for example, see Figure 3)", "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": "", "extra_scores": {}}, {"review_id": "cWANGUcOhb", "reviewer": "Reviewer_v2LJ", "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.", "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?\n\n- typos\n    * \"... in it’s full generality ...\"\n    * in the end of page 6.: \"even if $U_1^k(x) = \\infty$\", I guess it should be $U_f^1(x)$?", "limitations": "I believe the limitations are properly discussed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nThe 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.\n\nI 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.\n\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review of our work and incredibly helpful feedback. In retrospect, we are disappointed with our decision to relegate much of the intuition to the appendix in deference to including more of the concrete results and will be sure to better incorporate aspects of this discussion into the main body.\n\n\n$\\textbf{Questions:}$\n\n\nThe decision to subsample 1000 samples was entirely following from previous DP papers we had read that did this method for their empirical studies. Their justification was that this bootstrapping better simulates new draws from the underlying distribution of the original data. As a result, it better ensures that the proposed method does not happen to only perform well on that specific dataset, but performs well generally on datasets drawn from the underlying distribution. The specific amount of 1000 was likely just a result of being a \"clean\" number (power of 10) and less than the total data size for most datasets. There are no computational difficulties with using larger datasets (within reason).\n\n\nThanks for catching the typos! The reviewer is absolutely right in their correction of the second typo (our apologies for the confusion).", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a new framework for differentially private computation of functions. The reviewers were all positive about the paper. While the reviewers pointed out some shortcomings of the exposition, overall these seem like minor revisions that can be addressed by the authors.
Decision: Accept (poster)