Instance-Specific Asymmetric Sensitivity in Differential Privacy

Authors: david  durfee
mozilla  anonym
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 01:32:13

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.

Main paper: 
 introduction: 
 We consider the general problem of estimating 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 can 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 of sensitivity that are specific to the underlying dataset. This notion was initially considered in Nissim et al. (2007) , introducing smooth sensitivity, an 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 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-independent conjectured sensitivity parameter and more accurate results provided when the underlying data complies with the parameter. The propose-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 a given parameter by which noise can be added proportionally and the approximation is accurate for underlying data with low sensitivity Chen & 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 (2020b) . Specifically, this framework considers all potential outputs based upon the closeness of their inverse to the underlying data and applies the exponential mechanism to select a 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,b) .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 a data-independent 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 output, which can be considered the inverse sensitivity. However, we instead invoke the well-known sparse vector technique, originally introduced in Dwork et al. (2009) , to select an output close to the underlying data. The iterative nature of sparse vector technique will create a slight bias, while still adapting well to 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. In 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 to commonly used machine learning performance metrics: 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 𝑂(𝑛) time implementations for each invocation of our method.While the most closely related literature was discussed in more detail previously, we provide additional related works here. Recent work considered instance-optimality but for estimators population quantities McMillan et al. (2022) , which differ from the empirical quantities studied here and in the other previously mentioned work. Additional work formally considered the bias-varianceprivacy trade-off particularly for mean estimation Kamath et 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 et 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.We summarize our primary contributions as the following:1. We introduce a new algorithmic framework for private estimation of general functions, which we refer to as the asymmetric sensitivity mechanism, along with a more computationally efficient approximate variant (see Section 3). 2. We provide theoretical utility guarantees that asymptotically confirm our method's advantage when the sensitivities are asymmetric and further give intuition 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 5). 4. We further invoke our method upon model evaluation for both classification and regression tasks with corresponding efficient implementations and empirical studies showing improved estimations (see Section 6).Additional and supplemental analysis, results and empirical studies are pushed to the appendix. 
preliminaries: 
 For simplicity and ease of comparison we borrow much of the notation from Asi & Duchi (2020a,b) . Definition 2.1. Let 𝒙, 𝒙 ′ be datasets of our data universe  𝑛 . We define 𝑑 ham (𝒙, 𝒙 ′ ) = |{𝑖 ∶ 𝒙 𝑖 ≠ 𝒙 ′ 𝑖 }| to be the Hamming distance between datasets. If 𝑑 ham (𝒙, 𝒙 ′ ) ≤ 1 then 𝒙, 𝒙 ′ are neighboring datasets.Note that we assume the swap definition of neighboring datasets but will also discuss how our results apply to the add-subtract definition in Appendix B.3. We further define the (global) sensitivity. Definition 2.2. 𝑓 ∶  𝑛 → ℝ has sensitivity Δ if for any neighboring datasets |𝑓 (𝒙) -𝑓 (𝒙 ′ )| ≤ Δ 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. (2006b,a) A mechanism 𝑀 ∶  𝑛 →  is (𝜀, 𝛿)-differentially-private (DP) if for any neighboring datasets 𝒙, 𝒙 ′ ∈  and measurable 𝑆 ⊆  :Pr[𝑀(𝒙) ∈ 𝑆] ⩽ 𝑒 𝜀 Pr[𝑀(𝒙 ′ ) ∈ 𝑆] + 𝛿. If 𝛿 = 0 then 𝑀 is 𝜀-DP.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 can instead be added from the exponential distribution at the same parameter for improved utility Durfee (2023) . Let Expo(𝑏) denote a draw from the exponential distribution with scale parameter 𝑏.This technique can further see improvement when the queries are monotonic which will apply to most of our instantiations of our method.Algorithm 1 AboveThreshold Require: Input dataset 𝒙, a stream of queries {𝑓 𝑖 ∶  𝑛 → ℝ} with sensitivity Δ, and a threshold 𝑇 1: Set T = 𝑇 + Expo(Δ/𝜀 1 ) 2: for each query 𝑖 do 3:Set 𝜈 𝑖 = Expo(Δ/𝜀 2 )4:if 𝑓 𝑖 (𝒙) + 𝜈 𝑖 ≥ T then 5:Output ⊤ and halt 6:else 7:Output ⊥ 8:end if 9: end for Definition 2.4. We say that stream of queries {𝑓 𝑖 ∶  𝑛 → ℝ} with sensitivity Δ is monotonic if for any neighboring 𝒙, 𝒙 ′ ∈  𝑛 we have either 𝑓 𝑖 (𝒙) ≤ 𝑓 𝑖 (𝒙 ′ ) for all 𝑖 or 𝑓 𝑖 (𝒙) ≥ 𝑓 𝑖 (𝒙 ′ ) for all 𝑖.This allows for the following differential privacy guarantees from Durfee (2023) . Proposition 2.5. Algorithm 1 is (𝜀 1 + 2𝜀 2 )-DP in general and (𝜀 1 + 𝜀 2 )-DP for monotonic queriesThe inverse sensitivity mechanism had seen several previous instantiations but was introduced in it's full generality in Asi & Duchi (2020b) . We first introduce the exponential mechanism. Definition 2.6. McSherry & Talwar (2007) The Exponential Mechanism is a randomized mapping𝑀 ∶  𝑛 →  such that Pr [𝑀(𝒙) = 𝑡] ∝ exp ( 𝜀 ⋅ 𝑞(𝒙, 𝑡) 2Δ )where 𝑞 ∶  𝑛 ×  → ℝ has sensitivity Δ. Proposition 2.7. McSherry & Talwar (2007) The exponential mechanism is 𝜀-DPWe then define the distance of a potential output from the underlying dataset to be the Hamming distance required to change the data such that the new data matches the output. The inverse sensitivity mechanism then draws from the exponential mechanism instantiated upon the distance metric giving the density function 𝜋 𝑀 inv (𝒙) (𝑡) = 𝑒 -len 𝑓 (𝒙;𝑡)𝜀/2 ∫  𝑒 -len 𝑓 (𝒙;𝑠)𝜀/2 𝑑𝑠 (M.1) and mechanism M.1 is 𝜀-DP by Proposition 2.7 and Corollary 2.9. 
asymmetric sensitivity mechanism: 
 In this section we introduce our general methodology for instance-specific differentially private estimation, which we term the asymmetric sensitivity mechanism. We first give the exact formulation which will fit an extensive class of functions focused upon in Asi & Duchi (2020b) . Next we provide a 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 an 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 a more intuitive explanation of our approach compared to the inverse sensitivity mechanism.Our method will similarly consider the distance for each output 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 it is negative for outputs that are less than output from the underlying data. Definition 3.1. For 𝑓 ∶  𝑛 → ℝ and 𝒙 ∈  𝑛 , let the reflective inverse sensitivity of 𝑡 ∈ ℝ bes 𝑓 (𝒙; 𝑡) def = sgn(𝑡 -𝑓 (𝒙)) ( len 𝑓 (𝒙; 𝑡) - 1 2 )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, is 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 a convex domain. 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 {𝑡 𝑖 } that calls AboveThreshold and returns 𝑡 𝑘 when AboveThreshold(𝒙, {s 𝑓 (𝒙; 𝑡 𝑖 )}, 𝑇 = 0) = {⊥ 𝑘-1 , ⊤} (M.2)To be effective, this stream of potential outputs should be increasing (or decreasing if we flip the sign of s 𝑓 ) but will still achieve the desired privacy guarantees regardless which is shown in Appendix A.2. Theorem 3.3. Given sample-monotone 𝑓 ∶  𝑛 → ℝ and any stream of potential outputs {𝑡 𝑖 }, we have that mechanism M.2 is (𝜀 1 + 2𝜀 2 )-DP in general and (𝜀 1 + 𝜀 2 )-DP if s 𝑓 is monotonic.We further detail in Appendix B a simple, general, and robust strategy for selecting potential outputs that provides a reasonable limit on the number of queries.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. In Section A, we show how we can extend our asymmetric sensitivity mechanism to general functions 𝑓 ∶  𝑛 → ℝ and provide more efficient implementations. It will follow closely with our exact version above. 
asymmetric sensitivity advantage: 
 In this section, we first connect our definitions with the corresponding definitions in the previous work, by which utility guarantees are provided. Then we discuss the notion of asymmetric sensitivities and provide our utility guarantees that exploit this asymmetry to asymptotically improve upon the previous work under those conditions.An essential quantity for our method and both inverse and smooth sensitivity mechanisms is the amount a function output can change if 𝑘 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  = ℝ) as𝜔 𝑓 (𝒙; 𝑘) def = max{|𝑓 (𝒙) -𝐿 𝑘 𝑓 (𝒙)|, |𝑓 (𝒙) -𝑈 𝑘 𝑓 (𝒙)|}Note that if 𝑘 = 1 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 if local sensitivity is infinite.To understand the advantages of our method, we will consider the sensitivities to be asymmetric if |𝑓 (𝒙) -𝑈 𝑘 𝑓 (𝒙)| >> |𝑓 (𝒙) -𝐿 𝑘 𝑓 (𝒙)| for most 𝑘 (or vice versa), which is to say that changing an individual's data can generally increase the function more than decrease it. In general, we expect any lower bounded function to inherently limit the amount changing one individual's data can decrease the function compared to increasing the function. Each instantiation in our empirical study is a non-negative function which then fits this characterization. For simplicity, we will restrict our consideration to non-negative 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 𝑓 (𝒙), but more importantly the 𝑈 𝑘 𝑓 (𝒙) values will have little effect upon the accuracy. Specifically, once the threshold is crossed it becomes increasingly unlikely that the sparse vector technique will proceed. Explicitly connecting this with our mechanism, even if 𝑈 𝑘 1 (𝒙) = ∞ and so the local sensitivity is infinite, we still have s 𝑓 (𝒙; 𝑡 𝑖 ) = 1/2 for all 𝑡 𝑖 > 𝑓 (𝒙) and assuming 𝑡 𝑖 is increasing it is increasingly unlikely that we output larger 𝑡 𝑖 > 𝑓 (𝒙).We formalize this intuition by providing a theoretical utility guarantee that does not depend upon the upper bound values. Essentially, we are able to replace the |𝑓 (𝒙) -𝑈 𝑘 𝑓 (𝒙)| in 𝜔 𝑓 (𝒙; 𝑘) with a relative error bound based upon a parameter that we fix across all our empirical instantiations. Accordingly, as 𝑈1 𝑓 (𝒙) → ∞ 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 𝑀 denote the mechanism from M.2 with 𝑡 𝑖 = 𝛽 𝑖 -1 where 𝛽 > 1 and we let 𝜀 = 𝜀 1 +2𝜀 2 with 𝜀 1 = 𝜀 2 in the call to Algorithm 1. Given non-negative sample monotone 𝑓 ∶  𝑛 → ℝ we havePr [ |𝑀(𝒙) -𝑓 (𝒙)| < max{|𝑓 (𝒙) -𝐿 log 𝑘+1 (𝒙)|, (𝛽 𝑘 -1)(𝑓 (𝒙) + 1)} ] > 1 -𝑂 ( 1 𝑘𝑒 𝜀/6 )for any 𝒙 ∈  𝑛 such that 𝑓 (𝒙) ≤ 𝛽 𝑂(1) .We 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 Corollary C.4 by applying our approximate variant to 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 𝛽 parameter (Appendix B.2). 
private variance estimation: 
 In this section, we instantiate our asymmetric sensitivity mechanism upon variance, a fundamental property of a dataset that is widely used in statistical analysis.Definition 5.1. Let  = ℝ and for 𝒙 ∈  𝑛 we let x = 1 𝑛 ∑ 𝑛 𝑖=1 𝒙 𝑖 and defineVar [𝒙] def = 1 𝑛 𝑛 ∑ 𝑖=1 (𝒙 𝑖 -x) 2There has been extensive work in the privacy literature upon covariance estimation for univariate and multivariate Gaussians with a focus upon optimizing asymptotic performance 1 . Our focus here will be practical methods for general data, so a rigorous comparison to all these methods for Gaussians is untenable and outside the scope of this work.We first show how the variance instantiation of asymmetric sensitivity can be implemented efficiently and give intuition upon why we 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 on the task of variance estimation.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 𝒙 ∈ ℝ 𝑛 , if 𝒙 1 ≤ ... ≤ 𝒙 𝑛 are ordered then we have lower output bounds𝐿 𝓁 Var (𝒙) = 𝑛 -𝓁 𝑛 min 0≤𝑖≤𝓁 Var [ 𝒙 [𝓁+1-𝑖∶𝑛-𝑖]]where we let 𝒙 [𝓁+1-𝑖∶𝑛-𝑖] def = (𝒙 𝓁+1-𝑖 , ..., 𝒙 𝑛-𝑖 )While the formula above immediately suggests an 𝑂(𝑛 2 ) time computation of all the lower output bounds, we will further prove in Appendix D that we can use our approximation to get a more efficient implementation. In particular, we consider a 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 𝒙 ∈ ℝ 𝑛 and 𝑐 ≥ 0, we can compute all approximate output bounds 𝐿 𝓁 Var (𝒙) = 𝐿 𝓁 Var (𝒙) for 𝓁 ≤ 𝑐 and 𝐿 𝓁 Var (𝒙) = 0 for 𝓁 > 𝑐 in 𝑂(𝑛 + 𝑐 2 ) time.Next we consider the upper output bounds, but if the data is unbounded then we must have 𝑈 1 Var (𝒙) = ∞. It is 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 requires reasonable bounds upon each data point that should be data-independent and also sufficiently loose to not add bias from clipping data points. Lemma 5.4. If we restrict all values to the interval [𝑎, 𝑏] then given 𝒙 ∈ [𝑎, 𝑏] 𝑛 we can give approximate upper output bounds𝑈 𝓁 Var (𝒙) = Var [𝒙] + 𝓁(𝑏 -𝑎) 2 𝑛To our knowledge, there is no 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. In our implementations we'll more reasonably assume 𝛽 ≥ 1.001, so 𝛽 50000 > 10 21 and we'll simply terminate AboveThreshold after at most 50,000 queries for all datasets without affecting the privacy guarantees. This then gives a runtime of 𝑂(𝑛).For our instantiations of machine learning model evaluation we 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. (1995) ; 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 use 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, to 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 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 𝛽 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 𝛽 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, we see that our 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 metrics 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, 𝑅 2 , also commonly used for evaluating regression performance.We provide full definitions along with technical analysis in Section E.For our empirical study of model evaluation for classification tasks we will consider two tabular 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-art 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 a relatively small CNN with several pooling and convolutional layers, 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 each 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] 10 of the model output for the multi-classification vision data. Once again, we fix our parameter 𝛽 = 1.005.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.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.In this section, we give full details upon extending our asymmetric sensitivity mechanism to general functions 𝑓 ∶  𝑛 → ℝ and provide more efficient implementations. We also provide all missing proofs from Section 3.As noted in Section 3, computing the upper and lower outputs bounds can be inefficient or even infeasible, which is necessary for our method, inverse sensitivity method, and smooth sensitivity method. As such we provide an approximation of these bounds that is a slightly more granular version of the approximation method provided in Asi & Duchi (2020a) and also applies to the inverse sensitivity mechanism. In particular, this definition separates the approximation for the upper vs lower bounds as opposed to treating them symmetrically. This maintains asymmetry which is precisely where our technique excels most. We then define a variant of closeness for each output to the underlying data which utilizes these approximate upper and lower bounds.Definition A.2. For a function 𝑓 ∶  𝑛 → ℝ along with 𝑈 𝓁 𝑓 ∶  𝑛 → ℝ and 𝐿 𝓁 𝑓 ∶  𝑛 → ℝ, for any 𝑡 ∈ ℝ, we let len 𝑓 (𝒙; 𝑡) def = inf{𝓁 ∶ 𝐿 𝓁 𝑓 (𝒙) ≤ 𝑡 ≤ 𝑈 𝓁 𝑓 (𝒙)}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. 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 {𝑡 𝑖 } that calls AboveThreshold and returns 𝑡 𝑘 when AboveThreshold(𝒙, {s 𝑓 (𝒙; 𝑡 𝑖 )}, 𝑇 = 0) = {⊥ 𝑘-1 , ⊤} (M.3)This will then achieve the same privacy guarantees which is shown in Appendix A.3.Theorem A.4. Given 𝑓 ∶  𝑛 → ℝ and any stream of potential outputs {𝑡 𝑖 }, we have that mechanism M.3 is (𝜀 1 + 2𝜀 2 )-DP in general and (𝜀 1 + 𝜀 2 )-DP if s 𝑓 is monotonic.We first prove a helper lemma regarding the closeness of the reflective inverse sensitivities for neighboring datasets.Lemma A.5. Next we show the closeness between neighboring datasets. First consider the case when 𝑡 > max{𝑓 (𝒙), 𝑓 (𝒙 ′ )} or 𝑡 < min{𝑓 (𝒙), 𝑓 (𝒙 ′ )}. This implies sgn(𝑡 -𝑓 (𝒙)) = sgn(𝑡 -𝑓 (𝒙 ′ )) and the bound follows from Corollary 2.9. Without loss of generality, assume 𝑓 (𝒙) ≥ 𝑓 (𝒙 ′ ) and consider the other case when 𝑓 (𝒙) ≥ 𝑡 ≥ 𝑓 (𝒙 ′ ). Due to the fact that they're neighboring len 𝑓 (𝒙; 𝑓 (𝒙 ′ )) ≤ 1 and len 𝑓 (𝒙 ′ ; 𝑓 (𝒙)) ≤ 1. Applying Definition 3.2, len 𝑓 (𝒙; 𝑡) ≤ 1 and len 𝑓 (𝒙 ′ ; 𝑡) ≤ 1 which implies |s 𝑓 (𝒙; 𝑡)| ≤ 1/2 and |s 𝑓 (𝒙 ′ ; 𝑡)| ≤ 1/2 giving the desired bound.With this lemma we can prove Theorem 3.3.Proof of Theorem 3.3. For 𝑡 𝑖 ∈ im(𝑓 ) we know the sensitivity is at most 1 from Lemma A.5. Further if 𝑡 𝑖 ∉ im(𝑓 ) then by the convexity of im(𝑓 ) from Lemma A.5 we know that either 𝑡 𝑖 < 𝑓 (𝒙) and so s 𝑓 (𝒙, 𝑡) = -∞ for all 𝒙 ∈  𝑛 or 𝑡 𝑖 > 𝑓 (𝒙) and so s 𝑓 (𝒙, 𝑡) = ∞ for all 𝒙 ∈  𝑛 . The 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-monotone functions.Proof of Lemma 3.5. First consider the case when 𝑡 < 𝐿 𝑛 𝑓 (𝒙) or 𝑡 > 𝑈 𝑛 𝑓 (𝒙), which implies inf{𝓁 ∶ 𝐿 𝓁 𝑓 (𝒙) ≤ 𝑡 ≤ 𝑈 𝓁 𝑓 (𝒙)} = ∞ because the infimum of the empty set is infinity. This also implies that 𝑡 ∉ im(𝑓 ) so len 𝑓 (𝒙; 𝑡) = ∞ for the same reason. Next, consider the other case when 𝐿 𝑛 𝑓 (𝒙) ≤ 𝑡 ≤ 𝑈 𝑛 𝑓 (𝒙) and let 𝑘 = inf{𝓁 ∶ 𝐿 𝓁 𝑓 (𝒙) ≤ 𝑡 ≤ 𝑈 𝓁 𝑓 (𝒙)}. If there exists 𝒙 ′ such that 𝑓 (𝒙 ′ ) = 𝑡 and 𝑑 ham (𝒙, 𝒙 ′ ) = 𝑘 ′ < 𝑘, then this would imply 𝐿 𝑘 ′ 𝑓 (𝒙) ≤ 𝑡 ≤ 𝑈 𝑘 ′ 𝑓 (𝒙), so inf{𝓁 ∶ 𝐿 𝓁 𝑓 (𝒙) ≤ 𝑡 ≤ 𝑈 𝓁 𝑓 (𝒙)} < 𝑘 giving a contradiction. Thus we must have len 𝑓 (𝒙; 𝑡) ≥ 𝑘. Furthermore, the sample-monotone definition implies that len 𝑓 (𝒙; 𝑡) ≤ 𝑘 because 𝐿 𝑘 𝑓 (𝒙) ≤ 𝑡 ≤ 𝑈 𝑘 𝑓 (𝒙). Therefore, we also have len 𝑓 (𝒙; 𝑡) = 𝑘.We again prove a helper lemma regarding the closeness of the approximate inverse sensitivities for neighboring datasets. Proof. By construction, 𝐿 𝑛 𝑓 (𝒙) = inf 𝒙 {𝑓 (𝒙)} and 𝑈 𝑛 𝑓 (𝒙) = sup 𝒙 {𝑓 (𝒙)} because the Hamming distance between any datasets is always at most 𝑛. Thus we must have len 𝑓 (𝒙; 𝑡) ≤ 𝑛 and len 𝑓 (𝒙 ′ ; 𝑡) ≤ 𝑛. Without loss of generality, assume len 𝑓 (𝒙; 𝑡) ≤ len 𝑓 (𝒙 ′ ; 𝑡) and len 𝑓 (𝒙; 𝑡) = 𝓁. By Definition A.1 we then have 𝐿 𝓁+1 𝑓 (𝒙 ′ ) ≤ 𝑡 ≤ 𝑈 𝓁+1 𝑓 (𝒙 ′ ) so len 𝑓 (𝒙 ′ ; 𝑡) ≤ 𝓁 + 1, which implies our desired inequality.We then extend this closeness to the approximate reflective inverse sensitivities for neighboring datasets.Lemma A.7. Given 𝑓 ∶  𝑛 → ℝ, for any neighboring datasets 𝒙, 𝒙 ′ ∈  𝑛 and inf 𝒙 {𝑓 (𝒙)} ≤ 𝑡 ≤ sup 𝒙 {𝑓 (𝒙)} we have |s 𝑓 (𝒙; 𝑡)s 𝑓 (𝒙 ′ ; 𝑡)| ≤ 1Proof. First consider the case when 𝑡 > max{𝑓 (𝒙), 𝑓 (𝒙 ′ )} or 𝑡 < min{𝑓 (𝒙), 𝑓 (𝒙 ′ )}. This implies sgn(𝑡 -𝑓 (𝒙)) = sgn(𝑡 -𝑓 (𝒙 ′ )) and the bound follows from Lemma A.6. Without loss of generality, assume 𝑓 (𝒙) ≥ 𝑓 (𝒙 ′ ) and consider the other case when 𝑓 (𝒙) ≥ 𝑡 ≥ 𝑓 (𝒙 ′ ). Due to the fact that they're neighboring and Definition A.2 we have len 𝑓 (𝒙; 𝑡) ≤ 1 and len 𝑓 (𝒙 ′ ; 𝑡 ≤ 1. This implies |s 𝑓 (𝒙; 𝑡)| ≤ 1/2 and |s 𝑓 (𝒙 ′ ; 𝑡)| ≤ 1/2 giving the desired bound.With these lemmas we can now prove our Theorem A.4.Proof of Theorem A.4. For 𝑡 such that inf 𝒙 {𝑓 (𝒙)} ≤ 𝑡 ≤ sup 𝒙 {𝑓 (𝒙)} we know the sensitivity is at most 1 from Lemma A.7. Otherwise either 𝑡 𝑖 < 𝑓 (𝒙) and so s 𝑓 (𝒙, 𝑡) = -∞ for all 𝒙 ∈  𝑛 or 𝑡 𝑖 > 𝑓 (𝒙) and so s 𝑓 (𝒙, 𝑡) = ∞ for all 𝒙 ∈  𝑛 . The privacy guarantees then follow from Proposition 2.5.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 strategy for selecting potential outputs for our method and provide a corresponding empirical study. Finally, we discuss how our methods can also apply to the add-subtract definition of neighboring datasets.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 to naturally handle this setting with negligible accuracy loss. In particular, Algorithm 1 outputs the first query above the threshold, and we see from our Definition A.3 that even if 𝑈 𝓁 𝑓 (𝒙) = ∞ then we will have that the reflective inverse sensitivity is 1/2 for all possible outputs greater than 𝑓 (𝒙). Thus each query of potential outputs greater than 𝑓 (𝒙) 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 5. 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. 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 output 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 an instantiation of a close variant of the inverse sensitivity mechanism for privately computing quantiles Smith (2011) .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 (2023) , 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-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 𝛽 ≥ 1.001, then 𝛽 50000 > 10 21 and we can simply terminate AboveThreshold after at most 50,000 queries for all datasets without affecting the privacy guarantees.If 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.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 𝛽 = 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.01In 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 addsubtract definition where a users data is added or removed between neighbors. Our asymmetric sensitivity mechanism can naturally extend to this notion of Hamming distance as well.The primary difference would be that all datasets in the data universe would no longer be at most distance 𝑛 from one another as the size of the dataset could vary. As such, the list of upper and lower output 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 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.In this section, we first give a more visual explanation of our methodology compared to the inverse sensitivity mechanism. We then provide strong intuition upon why our method will substantially improve the estimation accuracy when the sensitivities are asymmetric by more naturally balancing 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.Recall that the inverse sensitivity method considered the distance metric of any output from the underlying data in Definition 2.8. We then proposed a 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 as step functions using the upper and lower output bounds from Definition 3.4. In the plot, we denote 𝐿 𝜅 𝑓 (𝒙) and 𝑈 𝜅 𝑓 (𝒙) with 𝐿𝜅 and 𝑈 𝜅, respectively. We will go into further detail in the next section but note that the sensitivities are perfectly symmetric in this example.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, a shift in the reflective inverse sensitivity will be monotonic because of it's increasing nature, allowing for improved privacy guarantees for many instantiations. Given the closeness between outputs for neighboring datasets, we can apply the exponential mechanism or sparse vector technique. Applying our method entails considering an increasing stream of potential output {𝑡 𝑖 } 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 our asymmetric sensitivity mechanism (ASM) when the sensitivities are perfectly symmetric. We slightly alter our mechanism M.3 to uniformly draw an output in [𝑡 𝑘-1 , 𝑡 𝑘 ] 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 to our method being slightly more likely to find an 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.In Figure 6 we assumed that the sensitivities were perfectly symmetric. More specifically, for 𝓁 > 0 we let Δ 𝓁 𝐿 (𝑓 ; 𝒙) def = 𝐿 𝓁-1 𝑓 (𝒙) -𝐿 𝓁 𝑓 (𝒙) and Δ 𝓁 𝑈 (𝑓 ; 𝒙) def = 𝑈 𝓁 𝑓 (𝒙) -𝑈 𝓁-1 𝑓 (𝒙), which are the amount the function can marginally decrease and increase, respectively, by changing the 𝓁 th individual's data. Note that for 𝓁 = 1 these quantities correspond to the local sensitivity. We then say that the sensitivities are perfectly symmetric if Δ 𝓁 𝐿 (𝑓 ; 𝒙) = Δ 𝓁 𝑈 (𝑓 ; 𝒙) for all 𝓁 > 0, which held by construction for our examples in the previous section.Informally, we will say that the sensitivities are asymmetric if Δ 𝓁 𝐿 (𝑓 ; 𝒙) << Δ 𝓁 𝑈 (𝑓 ; 𝒙) (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 remove the labels for 𝐿 1 𝑓 (𝒙), 𝐿 2 𝑓 (𝒙), and 𝐿 3 𝑓 (𝒙) as they become too condensed around 𝑓 (𝒙) but we keep their tick marks on the x-axis. We again slightly alter our mechanism M.3 to uniformly draw an output in [𝑡 𝑘-1 , 𝑡 𝑘 ] for easier visualization, which implies our PDF will be a step function between the potential outputs.For a 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 Δ 1 𝑈 (𝑓 ; 𝒙) here. The inverse sensitivity mechanism weakens the unbiased definition to better take advantage of the asymmetry from Δ 𝓁 𝐿 (𝑓 ; 𝒙) << Δ 𝓁 𝑈 (𝑓 ; 𝒙) and we see in Figure 7 that the probability mass of outputs less than 𝑓 (𝒙) becomes much more closely concentrated around 𝑓 (𝒙). 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 & Durfee (2020) could be applied here and potentially be both unbiased and have low variance if the a priori sensitivity parameter closely matches the Δ 𝓁 𝐿 (𝑓 ; 𝒙) 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 Figure 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 significantly reduce the variance. More specifically, if we map Figure 5 to these lower output bounds, then the reflective inverse sensitivity will be much steeper right below 𝑓 (𝒙), 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 to naturally consider unbounded data for a 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-independent stream of potential outputs {𝑡 𝑖 }, we provide a simple and general strategy for this selection in Appendix B that robustly maintains accuracy across different invocations and datasets. As a 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.We previously defined asymmetric sensitivity to informally be a consistent mismatch between Δ 𝓁 𝐿 (𝑓 ; 𝒙) and Δ 𝓁 𝑈 (𝑓 ; 𝒙) for most 𝓁. 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 Δ 𝓁 𝐿 (𝑓 ; 𝒙) and Δ 𝓁 𝑈 (𝑓 ; 𝒙) have a higher impact upon symmetry for larger 𝓁. Therefore, to obtain a formal measurement of asymmetry, we should consider an averaging of Δ 𝓁 𝐿 (𝑓 ; 𝒙) vs Δ 𝓁 𝑈 (𝑓 ; 𝒙) over all 𝓁 but with higher weight given to smaller 𝓁 and this weighting should be further scaled by the privacy parameter. We observe that the inverse sensitivity mechanism uniformly draws from [𝐿 𝓁 𝑓 , 𝐿 𝓁-1 𝑓 ] and [𝑈 𝓁-1 𝑓 , 𝑈 𝓁 𝑓 ] with probability proportional to Δ 𝓁 𝐿 (𝑓 ; 𝒙) ⋅ exp(-𝓁 ⋅ 𝜀/2) and Δ 𝓁 (𝑓 ; 𝒙) ⋅ exp(-𝓁 ⋅ 𝜀/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 Proof. In order to terminate at query 𝑗 + 𝑚 or later we need that the noisy threshold is above all previous noisy queries. Let is an upper bound on the probability of still continuing at step 𝑗 + 𝑚. This implies our desired claim.Proof of Lemma 4.1. We first show Pr [ 𝑀(𝒙) < 𝐿 ln 𝑘 (𝒙) ] < 𝐶/𝑘𝑒 𝜀/6 for a constant 𝐶. By Definition 3.1 and Lemma 3.5 we know that for any 𝑡 𝑖 < 𝐿 ln 𝑘+1 (𝒙) we have s 𝑓 (𝒙; 𝑡 𝑖 ) < 𝑇 -ln 𝑘. Furthermore, we assumed that 𝑓 (𝒙) ≤ 𝛽 𝐶 for a constant 𝐶 and 𝑡 𝑖 = 𝛽 𝑖 -1 so 𝑡 𝐶 > 𝑓 (𝒙) ≥ 𝐿 ln 𝑘+1 (𝒙). We then apply Lemma C.2 with 𝛼 = ln 𝑘 and 𝑚 = 𝐶, which implies Pr [ 𝑀(𝒙) < 𝐿 ln 𝑘 (𝒙) ] < 𝐶/𝑘𝑒 𝜀/6 for a constant 𝐶 as desired. when 𝑓 (𝒙) ≤ 𝛽 𝑂(1) .Proof. The proof follows identically but instead of applying Lemma 3.5 we can directly use Definition A.2 and note that setting 𝐿 𝓁 𝑓 ≡ L𝓁 𝑓 satisfies Definition A.1In 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 as it is such a well-studied statistical property, but we duplicate some of these properties for completeness. We first provide a known alternative definition of variance.Definition D.1. Let  = ℝ and for 𝒙 ∈  𝑛 , we can equivalently define variance asVar [𝒙] def = 1 𝑛 2 𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 1 2 (𝑥 𝑖 -𝑥 𝑗 ) 2We will also add some helpful notation where for any We can then apply our Definition 5.1 to get our desired result.With this helper lemma we can then provide the proof of our lower output bounds through a proof by contradiction. and gives our desired contradiction.D.2 Analysis for Lemma 5.3In 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. (𝒙 𝑖 -𝒙 𝑗 ) 2 ≤ 1 𝑛 2 ∑ 𝑗≠𝑖 (𝒙 ′ 𝑖 -𝒙 𝑗 ) 2 + (𝑏 -𝑎) 2 𝑛We assumed that all datasets were restricted to [𝑎, 𝑏] 𝑛 so we must then have ∑ 𝑗≠𝑖 (𝒙 𝑖 -𝒙 𝑗 ) 2 ≤ 𝑛(𝑏-𝑎) 2 , which then implies our desired inequality by the non-negativity of squared error.Next we show that 𝑈 𝓁 Var (𝒙) ≤ 𝑈 𝓁 Var (𝒙). It suffices to show that for an arbitrary 𝒙 ′ such that 𝑑 ham (𝒙, 𝒙 ′ ) = 𝓁 we have Var [𝒙 ′ ] ≤ Var [𝒙]+ 𝓁(𝑏-𝑎) 2 𝑛 . We previously showed that Var [𝒙] ≥ Var [𝒙 ′ ]+ (𝑏 -𝑎) 2 /𝑛 for any 𝒙, 𝒙 ′ such that 𝑑 ham (𝒙, 𝒙 ′ ) = 1, so our claim then follows inductively. Therefore, our construction of 𝑈 𝓁 Var satisfies Definition A.1 as desired.In this section, we 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.We now define our datasets as (𝒙, 𝑦) ∈  𝑛 × ℝ 𝑛 and we set 𝑑 ham ((𝒙, 𝑦), (𝒙 ′ , 𝑦 ′ )) = |{𝑖 ∶ 𝒙 𝑖 ≠ 𝒙 ′ 𝑖 or 𝑦 𝑖 ≠ 𝑦 ′ 𝑖 }| to be the Hamming distance between datasets. We will be considering binary classification and multi-class classification, so we define cross-entropy loss for both.Definition E.1. Given machine learning model for binary-classification 𝜔 ∶  → ℝ and assume all 𝑦 𝑖 ∈ {0, 1}, letBCE 𝜔 (𝒙, 𝑦) = 𝑛 ∑ 𝑖=1 -𝑦 𝑖 log ( 1 1 + 𝑒 -𝜔(𝒙 𝑖 ) ) -(1 -𝑦 𝑖 ) log ( 𝑒 -𝜔(𝒙 𝑖 ) 1 + 𝑒 -𝜔(𝒙 𝑖 ) )Similarly, given machine learning model for multi-classification 𝜔 ∶  → ℝ 𝑐 with 𝑐 classes and assume all 𝑦 𝑖 ∈ [𝑐], letCE 𝜔 (𝒙, 𝑦) = - 𝑛 ∑ 𝑖=1 log ( 𝑒 𝜔(𝒙 𝑖 ) 𝑦 𝑖 ∑ 𝑐 𝑗=1 𝑒 𝜔(𝒙 𝑖 ) 𝑗 )We also define the mean squared error and mean absolute error. where  ∶  → ℝ. We could also extend our results here to  that are specific to the index, but for simplicity we will restrict our consideration. Without loss of generality assume the indices are ordered such that (𝒙 𝑖 ) ≤ (𝒙 𝑖+1 ). We first provide lower output bounds for these functions. We then provide approximate relaxations of these bounds that will allow for easier application. We further show that our approximate bounds allow for monotonic reflective inverse sensitivities which implies improved privacy guarantees. where 𝑎 ≤ inf 𝒙 𝑘 ∈ {(𝒙 𝑘 )} and 𝑏 ≥ sup 𝒙 𝑘 ∈ {(𝒙 𝑘 )}. For any neighboring datasets 𝒙, 𝒙 ′ we have that either s 𝑓 (𝒙; 𝑡) ≤ s 𝑓 (𝒙 ′ ; 𝑡) for all 𝑡 ∈ ℝ or s 𝑓 (𝒙; 𝑡) ≥ s 𝑓 (𝒙 ′ ; 𝑡) for all 𝑡 ∈ ℝ Proof. Without loss of generality, assume 𝑓 (𝒙) ≤ 𝑓 (𝒙 ′ ) and we will show s 𝑓 (𝒙; 𝑡) ≥ s 𝑓 (𝒙 ′ ; 𝑡) for all 𝑡 ∈ 𝑅.We first consider 𝑡 ∈ [𝑓 (𝒙), 𝑓 (𝒙 ′ )]. Given that the datasets are neighboring, we must have 𝐿 1 𝑓 (𝒙) ≤ 𝑡 ≤ 𝑈 1 𝑓 (𝒙) and 𝐿 1 𝑓 (𝒙 ′ ) ≤ 𝑡 ≤ 𝑈 1 𝑓 (𝒙 ′ ). By Definition A.1 and Definition A.2, we have that len 𝑓 (𝒙; 𝑡) ≤ 1 and len 𝑓 (𝒙 ′ ; 𝑡) ≤ 1. Given that 𝑡 ∈ [𝑓 (𝒙), 𝑓 (𝒙 ′ )] this then implies s 𝑓 (𝒙; 𝑡) ∈ {1/2, 0} and s 𝑓 (𝒙 ′ ; 𝑡) ∈ {-1/2, 0}. Therefore s 𝑓 (𝒙; 𝑡) ≥ s 𝑓 (𝒙 ′ ; 𝑡).Next consider the case when 𝑡 < 𝑓 (𝒙). This implies sgn(𝑡 -𝑓 (𝒙)) = sgn(𝑡 -𝑓 (𝒙 ′ )) = -1 and also that len 𝑓 (𝒙; 𝑡) ≥ 1 and len 𝑓 (𝒙 ′ ; 𝑡) ≥ 1. By Lemma E.7 we have that 𝐿 𝓁 𝑓 (𝒙) ≤ 𝐿 𝓁 𝑓 (𝒙 ′ ) for all 𝓁 ≥ 0, which implies len 𝑓 (𝒙; 𝑡) ≤ len 𝑓 (𝒙 ′ ; 𝑡) and therefore s 𝑓 (𝒙; 𝑡) ≥ s 𝑓 (𝒙 ′ ; 𝑡).Finally consider 𝑡 > 𝑓 (𝒙 ′ ). This implies sgn(𝑡 -𝑓 (𝒙)) = sgn(𝑡 -𝑓 (𝒙 ′ )) = 1 and also that len 𝑓 (𝒙; 𝑡) ≥ 1 and len 𝑓 (𝒙 ′ ; 𝑡) ≥ 1. By Lemma E.7 we have that 𝑈 𝓁 𝑓 (𝒙) ≤ 𝑈 𝓁 𝑓 (𝒙 ′ ) for all 𝓁 ≥ 0, which implies len 𝑓 (𝒙; 𝑡) ≥ len 𝑓 (𝒙 ′ ; 𝑡) and therefore s 𝑓 (𝒙; 𝑡) ≥ s 𝑓 (𝒙 ′ ; 𝑡).We will also require the following helper lemma in order prove Lemma E.6. The proof for 𝑈 𝓁 𝑓 (𝒙) ≤ 𝑈 𝓁 𝑓 (𝒙 ′ ) follows equivalently.We will provide the efficient instantiation for multi-class cross entropy loss as this can easily be extended to binary cross entropy loss. Without loss of generality, assume the indices are ordered such that -log ( 𝑒 𝜔(𝒙 𝑖 ) 𝑦 𝑖 ∑ 𝑐 𝑗=1 𝑒 𝜔(𝒙 𝑖 ) 𝑗 ) ≤ -log ( 𝑒 𝜔(𝒙 𝑖+1 ) 𝑦 𝑖+1 ∑ 𝑐 𝑗=1 𝑒 𝜔(𝒙 𝑖+1 ) 𝑗 )We can then provide the lower output bounds for cross entropy loss As seen with variance in Section 5, we have that 𝑈 1 CE 𝜔 (𝒙, 𝑦) = ∞ which implies that cross-entropy loss 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. We provide a proof for these upper output bounds in Appendix E.The corresponding algorithm for instantiating MSE with our method is identical to Algorithm 2. The privacy guarantees from Theorem 5.5 also follow equivalently, but we can additionally improve the privacy to be (𝜀 1 + 𝜀 2 )-DP by applying Lemma E.6 to achieve monotonicity. We can also achieve 𝑂(𝑛 log(𝑛) + 𝑞) 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 𝓁 > 𝑐 where we set 𝑐 = 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).See Karwa & Vadhan (2018); Du et al. (2020); Biswas et al. (2020); Kamath et al. (2019); Bun et al. (2019); Aden-Ali et al. (2021); Ashtiani & Liaw (2022); Kothari et al. (2022); Tsfadia et al. (2022); Liu et al. (2022); Kamathet al. (2022) 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: The greatest weakness of this paper is perhaps the lack of justifications of why the proposed mechanism should work better; especially the asymmetric part. What it does is skip the t's smaller than f(x) and only look at bigger ones, hence we are moving the mass probability from one side of the distribution and put it on the other. The paper provides some intuition but I still fail to see why it should help. I am inclined to believe that in the private variance computation it helps because we know variances cannot be negative.

By and large I think it is pointing out a phenomenon noticeable in practice, and I don't doubt that it could be applicable to more cases than have already been observed. Still there is the missing piece of puzzle of why we are observing this and how to extend this knowledge to other related problems. The community could benefit greatly from that missing theoretical analysis and it will complete the story.
questions: 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: limitations: The authors have adequately addressed them.
paper_summary: paper_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.
strength_weakness: strength_weakness: The theoretical guarantee can be vacuous in some reasonable settings. For example, the upper bound in lemma 4.1 can be loose when $f(x)\ll 1$ for all $x$.
questions: 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: limitations: See weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: As the author noted in the paper (lines 178-179), the proposed method may not yield significant improvements when applied to vector-valued queries due to the structure of high-dimensional space.

typo: L^{\log k}} instead of L_f^{\log k}} in Lemma 4.1 and its proof.
questions: 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: limitations: The authors provide this part in the checklist
paper_summary: paper_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.
strength_weakness: strength_weakness: (1) The paper is not well-written and is very hard to follow. The abstract and introduction mentions the notion of asymmetric sensitivity without any intuitive explanation. Due to the lack of this important intuition, it is very difficult to understand well the contributions of this paper although the authors list their works in Section 1.3.
(2)The important definition of asymmetric sensitivity mechanism (Line 187) is very unclear. The benefit of asymmetrcity compared with the (symmetric) inverse sensitivity mechanisms in (Asi and Duchi 2020. 
(3)The paper fails to provide the motivations and explanations for theoretical results in a clear and convincing way. The authors consider many concepts and notions but don’t provide their clear logical connection to the main topic of the paper. 
(4)The citations usually appear in the main text not in the footnote (like in Page 7).
questions: questions: (1)Line 208: Why the computation time is O(log n?
(2)In Definition 3.1,  why 1/2? Can we replace it with 0 or 1?
(3)Could you please rewrite the definition of asymmetric sensitivity mechanisms in the form of sparse vector technique or in the form of DP mechanisms? What is the benefit of asymmeticity? Could you provide a concrete example where the sensitivity is asymmetric and explain how your techniques can be applied to it?
(5)Use the above example to illustrate the variance-bias tradeoff. 
(6)What is the advantage of asymmetric sensitivity mechanisms in this paper over inverse sensitivity mechanisms in the literature?
limitations: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: In general the paper reads well, but it took me a while to parse the main story together. I would suggest authors to simplify some parts of the introduction to make the paper easier to approach. For example, I was rather confused by the use of "inverse of a function" in the introduction, since I don't think it is clear at this point what kind of functions the paper talks about. Therefore it was unclear to me what would be the argument of the function to take the inverse from. This becomes very clear later in the paper, but perhaps some motivating example. to introduce reader to the topic of inverse sensitivity, would be beneficial.

I also think the utility result, Lemma 4.1, could be better discussed. There is some further discussion about the result in the appendix, but I would suggest moving some of that to the main paper. It would be very important to at least discuss, what is the key take-away of the utility guarantee. Otherwise it is somewhat hard to appreciate it.
questions: questions: - Can you clarify what is the motivation for subsampling 1000 samples from each data set in your variance experiments? Is the full data variance task too easy to show any difference between the methods? Or does the O(n) runtime become a bottleneck for running the experiments on the full data?

- typos
    * "... in it’s full generality ..."
    * in the end of page 6.: "even if $U_1^k(x) = \infty$", I guess it should be $U_f^1(x)$?
limitations: limitations: I believe the limitations are properly discussed.

Comments: title: I will rasie my evaluation
Official comment by reviewer J6Z2
comment: Thank you for your rebuttal.   I am satisfied with the answers. I will raise my evaluation to 6.
Thank you for answering my question! I will keep my score.
Thank you for your response! I'm happy to keep my score as is.