Privately Publishable Per-instance Privacy
Authors: Rachel Emily Redberg
Yu-Xiang Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: differential privacy
private ERM
per-instance privacy
objective perturbation

Abstract: We consider how to privately share the personalized privacy losses incurred by objective perturbation, using per-instance differential privacy (pDP). Standard differential privacy (DP) gives us a worst-case bound that might be orders of magnitude larger than the privacy loss to a particular individual relative to a fixed dataset. The pDP framework provides a more fine-grained analysis of the privacy guarantee to a target individual, but the per-instance privacy loss itself might be a function of sensitive data. In this paper, we analyze the per-instance privacy loss of releasing a private empirical risk minimizer learned via objective perturbation, and propose a group of methods to privately and accurately publish the pDP losses at little to no additional privacy cost.  

Privately Publishable Per-instance Privacy
Rachel Redberg
Yu-Xiang Wang Department Computer Science
Department of Computer Science
UC Santa Barbara Santa Barbara, CA 93106 rredbergduss. edu
UC Santa Barbara Santa Barbara, CA 93106 yuxiangwecs ucsb. edu
Abstract
We consider how to privately share the personalized privacy losses incurred by objective perturbation, using per-instance differential privacy (pDP). Standard differential privacy (DP) gives worst-case bound that might be orders of magnitude larger than the privacy loss to a particular individual relative to a fixed dataset. The pDP framework provides more fine-graines analysis of the privacy guarantee to target individual, but the per-instance privacy loss itself might be a function of sensitive data. In this paper, analyze the per-instance privacy loss of releasing a private empirical risk minimizer learned via objective perturbation, and propose group of methods privately and accurately publish the pDP losses little to no additional privacy cost.
Introduction
An explosion of data has fueled innovation in machine learning applications and demanded, in equal turn, privacy protection for the sensitive data with which machine learning practitioners train and evaluate models.
Differential privacy (DP) (Dwork et al., 2006, 2014a) has become a mainstay of privacy-preserving data analysis, replacing less robust privacy definitions such k-anonymity which fail to protect against sufficiently powerful de-anonymization attacks (Narayanan & Shmatikov, 2008). In contrast, DP offers provable privacy guarantees that are robust against an arbitrarily strong adversary.
The data curator could trivially protect against privacy loss by reporting a constant function, or by releasing only data-independent noise. The key challenge of DP is to release privatized output that retains utility to the data analyst.
A desired level of utility in a machine learning application might necessitate a high value of e, but the privacy guarantees degrade quickly past (Triastcyn & Faltings, 2020) construct an example whereby differentially private algorithm with allows an attacker to use estimate to conclude with up 88% accuracy that an individual is in dataset. For c 5, the theoretical upper bound on the accuracy of an optimal attack is 99.3%.
Moreover, practical applications of differential privacy commonly use large values of A study of Apple's deployment of differential privacy revealed that the overall daily privacy loss permitted by the system as high as for Mac OS 10.12.3 and 14 for iOS 10.1.1 (Tang al., 2017) offering only scant privacy protection!
Recent work (Yu et al., 2021) has empirically justified large privacy parameters by conducting membership inference attacks to demonstrate that these seemingly tenuous privacy guarantees are actually much stronger in practice. These results unsurprising from the perspective that DP gives a inta-inndeenndent bound on the worst-case privacy loss which is likely to be a conservative estimate of the risk particular individual when DP algorithm is applied particular input dataset.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Per-instance differential privacy provides a theoretically sound alternative to the empirical approach for revealing the gap between the worst-case DP bound and the actual privacy loss in practice. The privacy loss to particular individual relative to fixed dataset might be orders of magnitude smaller than the worst-case bound guaranteed by standard DP. In this case, an algorithm meeting desired level of utility but providing weak DP guarantees may, for the same level of utility, achieve drastically more favorable per-instance DP guarantees.
The remaining challenge is that the per-instance privacy loss is a function of the entire dataset; publishing directly would negate the purpose of privately training a model in the first place! this paper, we propose a methodology to privately release the per-instane, privacy losses associated with private empirical risk minimization. Our contributions are as follows:
We introduce ex-post per-instance differential privacy to provide sharp characterization of the privacy loss a particular individual that adapts to both the input dataset and the algorithm's 's output.
We present a novel analysis of the ex-post per-instance privacy losses incurred by the objective perturbation mechanism, demonstrating that these ex-post pDP losses are orders of magnitude smaller than the worst-case guarantee of differential privacy.
We propose a group of methods to privately and accurately release the ex-post pDP losses. In the particular case of generalized linear models, we show that we can accurately publish the private ex-post pDP losses using a dimension- and dataset-indepente
bound.
One technical result of independent interest is new DP mechanism that releases the Hessian matrix by adding a Gaussian Orthogonal Ensemble matrix, which improves the classical "AnalyzeGauss" (Dwork et al., 2014b) by roughly constant factor of
1.1 Related Work
This paper builds upon (Wang. 2019), which proposed the per-instance DP framework and left as an open question the matter of publishing the pDP losses. We extend the pDP framework to ex-post setting to provide privacy guarantees that adapt even more fluidly to data-dependent properties of our algorithms. Another fundamental ingredient in our privacy analysis is the objective perturbation algorithm (Obj-Pert) of (Chaudhuri et al., 2011), further analyzed by (Kifer et al., 2012), which privately releases the minimizer of an empirical risk by adding linear perturbation to the objective function before optimizing.
Per-instance DP and ex-post per-instance DP belong to growing family of DP definitions that provide a more fine-gre nhe-grained characterization of the privacy loss. Among these are data- data-dependent DP (Papernot et al., 2018), which conditions fixed dataset; personalized DP (Ghosh & Roth, 2011; Ebadi et al., 2015; Liu et al., 2015), which conditions on a fixed individual's datapoint; and ex-post DP (Ligett al., 2017), which conditions on the realized output of the algorithm. Per-instance DP conditions on both a fixed dataset and a fixed individual's s datapoint, and ex-post per-instance DP adapts even further to the realized output of the algorithm. A more detailed comparison of these DP variants is included in the supplementary materials.
Other data-adaptive methodologies include propose-test-relcase (Dwork & Lei, 2009) and local sensitivity (Nissim et al., 2007). In addition, Bayesian differential privacy (Triastcyn & Faltings, 2020) provides dettaddeeendent privacy guarantees that afford strong protection to "typical" data by making distributional assumptions about the sensitive data. The Rényi- Dirii-D--assee privacy filters of (Feldman & Zmic, 2020) are also closely related to our work; the authors study composition of personalized (but not per-instance) privacy losses using adaptively-chosen privacy parameters.
2 Preliminaries
2.1 Symbols and Notation
We write the output of a randomized algorithm A as A(-), and for continuous distributions we take Pr(A(D) o] to be the value of the probability density function at output o.
We will let E 2 refer to both an individual and their data; for example, individual z holds data (z. y) in supervised learning problem. We take 2 = U to be the space of datasets with

---

an unspecified number of data points. D+ E 2" denotes the fixed dataset D = {z1,..... 2n 2 with the data point removed from if E D. or added to if & D. In our mathematical expressions, we use "4" to mean "add if & D, subtract otherwise". Similarly. "+" means "subtract if = ø D, add otherwise".
We distinguish between as fixed input to DP algorithm, and e(-) as a function parameterized according to a particular DP relaxation e.g., e(o, D, D=s) means the ex-post per-instance privacy loss conditioned on output dataset D, and data point z.
2.2 Differential Privacy
Let Z denote the data domain, and R the set of all possible outcomes of algorithm A. Fix c, 2 0. Definition 1. (Differential privacy) randomized algorithm A: : 2" - R satisfies (c, () if for all datasets D E Z" and data points E 2, and for all measurable sets S R,
Pr Pr[A(D) s) S <Pr(A((=s)) s) +
Differential privacy guarantees that the presence or absence of any particular data record has little impact on the output distribution of a randomized algorithm. In this paper we use the "add/remove" notion of DP, by which construct neighboring dataset D1= by adding removing an individual from dataset D).
DP is powerful and universal in that its guarantee applies any D, and set of output events. However, there are often situations where the privacy losses A vary drastically depending on its input data, and the privacy loss bound (protecting may not be informative of the privacy loss incurred to individuals when the input to A is typical. This motivated (Wang, 2019) to consider a per-instance version of the DP definition.
the worst-case pair of neighboring datasets)
Definition 2. (Per-instance differential privacy) A randomized algorithm A Z R satisfies (e)), 6PD if for dataset and data point 2, and for all measurable sets S C R,
Pr[A(D) E $) S (r(((()))))) E s) + (r( E s] S <<PP(((()) e s] +
The pDP definition can be viewed as using function eDD, D+2) that more precisely describes the privacy guarantee in protecting a fixed data point Z when A is applied dataset D.
As turns out, it is most convenient for us to work with an even more instance-specific description of the privacy loss that is further parameterized by the realized output of A ex-post after the random coins A are flipped and the outcome released.
Definition 3. (Ex-post per-instance differential privacy) A randomized algorithm A satisfies c(.)- ex-post per-instance differential privacy for individual and fixed dataset D at outcome o E Rango(AA) if
Pr Pr(A(()= - Pr Pr[A(D=e)=
log
< <(0,, ((O,,,DD. D22)
This definition generalizes the ex-post DP definition (Ligett et al., 2017) (introduced for a different purpose) to a per-instance version that depends on given pair of neighboring datascts. The above quantity is essentially the absolute value of the log-odds ratio, used extensively in hypothesis testing. Intuitively, the ex-post per-instance privacy loss E(O, D, D+=) describes how confidently an attacker could infer, given the output of algorithm A, whether not individual is in dataset D.
Despite (or perhaps because of) its precise accounting for privacy, ex-post pDP could reveal sensitive information about the dataset, as the following example explicitly illustrates.
Example 4 (The privacy risk of exposing ex-post pDP). Consider standard Gaussian mechanism A that adds noise to a counting query Q applied to datuset D, i.e. A(D) = Q(D) NO o²). Q has global sensitivity ÅQ = 1. We will show that an altacker, knowing only the oulput of algorithm A, her ex-post pDP loss and that her individual data is not contained in dataset D, can conclusively uncover the sensitive quantity QDD) protected by algorithm A.
3

---

Following the proof of Theorem ??, the ex ex-post pDP can be directly calculated as
c(o, D. D=.) [Q(D) Q(D==))( Q(D) ( - Q(++
20²
Enter attacker 2, who has auxiliary information: she knows that her own individual data is not contained in D. After algorithm A is applied to D, allacker receives oulpul o 1 and is informed of her ex ex-post pDP e(o, D, D+2)- Since +(==z) = Q(D) + 1 is known, altacker can solve for Q(D) and obtain QDD) 0 0.5 + e D, D+2)- With probability 1, only one of the two possibilities is an integer'. Therefore, exposing ex-post pDP in this case completely reveals Q(D).
Problem statement. The lesson of Example 4 is that we cannot directly reveal the ex-post pDP losses without potentially nullifying the algorithm's privacy benefits. How, then, can we privately and accurately publish the ex-post pDP losses?
The goal of this paper to develop an algorithm that publishes a function ē: 2 + E whose output estimates the ex-post pDP loss to an individual of releasing the output 8P from the objective perturbation mechanism. Any individual (not just those whose data is contained in the dataset) can plug her own data into this function order to receive a high-probabillity bound on her ex-post pDP loss which does not depend directly on any sensitive data except her own.
This requirement offers the same type privacy protection as joint differential privacy (Kearns et al., 2014), which relaxes the standard DP definition by allowing an algorithm's output to individual be sensitive only in her own private data. Our notion of privacy slightly more general in that holds for individuals both in and out of the dataset. The difference lies in how the algorithm's 's output space is defined; whereas a joint DP algorithm produces fixed-length tuple partitioning the output to each individual in the dataset, our algorithm outputs function whose domain includes any data point E Z. As a result, our methods are robust against collusion by arbitrary coalitions of adversaries, allowing repeated queries by any group of individuals without invalidating the privacy guarantees promised by the pDP losses.
2.3 Problem Setting
We consider general family of problems known as private empirical risk minimization (ERM), which aim approximate the solution an ERM problem while preserving privacy. That is, wish to privately solve optimization problems of the form
0 argmin L(0; D) + r(0): dc@
where r(f) is a regularizer and L(0: D) = Σn i=1 ((0; 2;) a loss function. Throughout, we assume
that E(0;2) and r() are convex and dwice-differentiable with respect to f. Dataset D is given by D {=) and 2, (.) for x; E X C Rd and y C IR, where ||0||| S 1 and lv| < 1.
We consider only unconstrained optimization over + = Rdd
2.4 Objective Perturbation
The objective perturbation algorithm solves
8 argmin L(0: + r(f) + -
1101 + +b"
(1)
oee
where b ~ NN,0 TT)) and parameters a, À are chosen according to a desired (c, 8)- guarantee.
Algorithm 1 Release 0" via Obj- (Kifer et al., 2012)
Input: Dataset D, noise parameter a, regularization parameter X, loss function L(0; D) E, ((0;z)), convex and twice-differentiable regularizer r(0), convex set e. Output: 0", the minimizer of the perturbed objective.
Draw noise vector ~ AO(0, O1).
Compute 9" according to (1).
'ake Q(D) 0 and
0.1 example, the possibilities 0 and -0.8.

---

Theorem 5 (Privacy guarantees of Algorithm 1 (Kifer et al., 2012)). Consider dataset D = {zsli=i loss function L(e; D) = E, [0;; zi); convex regularizer r()); and convex domain Q. Assume that {² z BLa and [[VE(0; 2:)1l2 I for all 2, E X x x and for all 0 E O. For x 28/e1 and = (8 + / Algorithm I satisfies (E1, -ddifferentt privacy.
The privacy guarantees stated in Theorem apply even when 0 is constrained a closed convex set, but for ease of our per-instance privacy analysis we will require θ IR from this point on.
3 Privately Publishable pDP
3.1 pDP Analysis of Objective Perturbation
Our goal in this section is to derive the personalized privacy losses (under Definition 3) associated with observing the output 0P of objective perturbation. This ex-posi perspective highly adaptive and also convenient for our analysis of Algorithm I, whose privacy parameters are a function of the data. Since are analyzing the per-instance privacy cost of releasing 0", it makes perfect sense to condition the pDP loss on the privatized output of the computation.
Our first technical result is a precise calculation of the ex-post pDP loss of objective perturbation.
Theorem (ex-post pDP loss of objective perturbation for a convex loss function). Let J(;; D) L(0; D) + r(0) + 2 1101 such that L(0; D) + r(0) = Σ, ((0;z;) + r(0) is a convex and twice- differentiable regularized loss function, and sample b ~ NN (a)) Then for every privacy target= (x.,)) v), releasing OP argmingeRs J(0; D) + b=O satisfies e (i D, exx)-oxs per-instance differential privacy with
1 V A
el c1(0,, D1z) -log II
(F11
20 VE(OP: :
5=1
where p1j Anu7 (V(OP: D) F E AEmeuTt U according to the eigendecomposition
(²)(0;2)= = E uu
Proof sketch. Following the analysis of (Chaudhuri et al., 20, we establish bijection between the mechanism output 0" and the noise vector b, and use a change-of-variable defined by the Jacobian mapping between jP and b in order rewrite the log-probability ratio in terms of the probability density function of b. First-order conditions then allow us to solve directly for the distribution of b. To calculate the first term of the above equation, we the eigendecomposition of the Hessian (= 2) and recursively apply the matrix determinant lemma. The of the proof is straightforward algebra. The full proof is given in Appendix ??
The above expression holds for any convex loss function, but is a bit unwieldy. The calculation becomes much simpler when we assume E(-) to be generalized linear loss function, with inner- product form E(O; =) ʃ(x 0; y)- For the sake of interpretability, we will defer further discussion of the ex-post pDP loss of objective perturbation until after presenting the following corollary.
Corollary 7 (ex-post pDP loss of objective perturbation for GLMs). Let J(:: D) L)
r(0) + 3 |101 [/ such that L(0; D) = Σ; {(0; 24) is a linear loss function, and sample b ~ NN La))
Then for every privacy target 2 = (x, y). releasing 0" = argmingens J(O: D) + be satisfies Ei(0", D., D.D==)-ex-oos per-instance differential privacy with
1 D) ;2) (o,,D.D2) S - log (1 f(()(())) + 202 /IEE(P:2))))) + Φ²
where u(x) xF +V( ((P:)() -r) ve(0p:=)
O' ;y) and s"(-) is shorthand for f"() = 0" The notation :(0p; D) means the realization of the noise vector b for which the output of Algorithm I will be 0p when the input dataset is D.
5

---

Note that the quantity (x()) in the first term is the generalized leverage score (Wei et al., 1998). quantifying the influence of data point on the model fit. The second and third terms are a function of the gradient of the loss function and provide complementary measure of how well the fitted model predicts individual z's data.
000000
1.34
00.0015
0.6
0.04
-028
0.0010
0.4
-08
0.0005
0.2
18 25
20
-05
188
0.9
2.5
2.0
188
1.5
1.0
1
-170
Figure 1: Visualization of ex-post pDP losses for logistic regression (n 1000, d = 2).
Since the ex-post pDP is function of 0P, we don't even need to run Algorithm to calculate ex-post pDP losses we can plug in directly to Corollary in order to calculate the pDP distribution induced by any hypothetical 0"", For Figure 1, we use a synthetic dataset sampled from the unit ball with two linearly separable classes separated by margin m 0.4. Then we solve for 0 = argmin [(; D) with À 1 to minimize the logistic loss, and directly perturb the output by rotating it by angle 2. .T.. We then denote 0" O+w to mean rotated counter-clockwise by angle w. The color scale is function of the ex-post pDP loss of data point z.
[0, 12 I a
Figure illustrates how the mechanism output هP affects the ex-post pDP distribution of objective perturbation for logistic regression problem. For
[0, 11). the data points closest to the decision boundary have the highest ex-post pDP loss. These data points have a strong effect on the learned model and would therefore have high leverage scores, making the first term dominate. As the perturbation (and model error) increases, the second and third terms dominate; the more badly model predicts a data point, the less protection this data point has.
Hidden in this analysis are the 8's of Theorem 5, which along with the choice of and À could affect which of the three terms is dominant. Fortunately, the probability of outputting something like @r 0_x astronomically low for any reasonable privacy setting!
3.2 Releasing the pDP losses
Next consider; after having released 0P and calculated the per-instance privacy losses of doing so, how do we privately release these pDP losses? Our goal is to allow any individual 2 E Z (in the dataset not) to know her privacy loss while preserving the privacy of others in the dataset.
Observe that the expression from Theorem 6 depends on the dataset D only through two quantities: the leverage score (u(a)= -- ( D)) and the inner product a result, we can find data-independent bound for these two terms, or privately release them with only small additional privacy cost, then we are done.
z). As

---

3.2.1 Data-independent bound of ex-post pDP losses
Below, we present pair of lemmas which will allow us to find nigh-probabiliig data-independen bound on the ex-post pDP loss.
Theorem 8. Suppose E(-) is function with continuous second-order partial derivatives. Then
d
log II (1#1))
Σ log(1 111 X
==1
where Hjj Xuu, (b((P:D) F Ei AR Uj according to the eigendecomposi-
tion ;2)(
- When specializing to linear loss functions such that 2(0;2) v), >3 = for all j > and the above bound be simplified to -log fz :1)==P ;))1==1//A)
Theorem 9. Let 0 be random variable such that 0P argmin (J(0; D) 1J as (1), where ~ NO, Ig) and E(0; 2) is a convex and twice-differentiable loss function. Then for E Z, the following holds with probability p.
"J(OP;DY V 5z) S <o
For linear loss functions the bound can be substantially strengthened to
"DOO" :z) f'(x" /
We make a few observations on the bounds. First, the general bound in Theorem holds simul- taneously for all and it depends only logarithmically in dimension when the features sparse. Second, the bound for linear loss function is dimension-free and somewhat surprising because we are actually bounding an inner product of two dependent random vectors (both depend on (*))
Finally, remark that the bounds in this section are cata-independent in that they do not depend on the of the dataset beyond already released information 0", It allows reveal a pDP bound of each individual when she plugs in her own data without costing any additional privacy budget!
3.3 The privacy report
For certain regimes, may wish to consider privatizing the data- dependent quantities of the ex-post pDP losses, at an additional privacy cost, as an alternative to using data-independent bounds. Of course, it only makes sense to do so if we can show that (a) these data-dependent estimates are more accurate than the data-independent bounds; (b) the overhead of releasing additional quantities (the additional privacy cost in terms of both DP and pDP) is not too large; and (c) pDP losses of the private reporting algorithm using indeededddeeneent bounds (so we do not have to recursively publish such reports).
share the
Full details are in the appendix. We show that by adding slightly more regularization than required by Obj-Pert (i.e., making À just bit larger so that the minimum eigenvalue of the Hessian H 2 above a certain threshold), we can find multiplicative bound that estimates μιrr) = x H uniformly for all x. We do so by adding noise to the Hessian using a natural variant of "Analyze Gauss" (Dwork al., 2014b), hence privately releasing ue" XX - R. See Algorithm 2 for details.
For brevity, we use the short-hands f'(-) := f'(=" (";w) and f"(-)= := f""="==""(>>"" (o="0;y) for GL.Ms. ((0,1) is the inverse CDF of the standard normal distribution, and GoDEa)) is the inverse CDF of the largest eigenvalue of the Gausian Orthogonal Ensemble (GOE) matrix, whose distribution is calculated exactly by (Chiani, 2014). Algorithm 2 specializes to GLMs for clarity of presentation, but we could adapt it to any convex loss function by replacing the GLM GLM--seccfic bounds with the more general ones.
O" 0P:y), where ((0;z)
We implicitly assume that the data analyst has already decided the privacy budgets e2 and eg for the data-dependent release of the gradient (third term of e1 (-)) and of the Hessian (first term of é (-)). Inputs d2 and d3 are then calibrated to achieve (E2, pDDD and (ea, DD-DP, respectively.
7

---

Algorithm 2 Privacy report for Obj-Pert on GLMs
Input: & E Rd from Obj-Pert, noise parameter 0, d2, 03; regularization parameter X; Hessian
H = E: v²e((p;; 2:) + Xla, Boolean B E (DATA-INDEP, DATA-DEPJ, failure probability
Require: X 2 203 F F (CoE(d)) (1 -p/2)
Output: Reporting function é (I, y) + R
if B = DATA-INNDD then
Set (-) == 0, <3(.) ==
Set (2) := (- Ni...) 1/2) and set n (x(x)) = ||
else if B DATA-DEP then
Privately release 9" by Algorithm ?? with parameter 02.
Set e2(-) according Theorem ??.
Set g (z) = min [SOD (()))"))))) x (llll"())))))l))))))))))))))))))
2/2). =1l" (1/4))
Privately release År by a variant "Analyze Gauss" with parameter dg. Set 6-)-) according Statement 2 of Theorem 10.
Set je (x) x
end
Set (2(2) == log (1 (-) [z)) 11 (s)(s) 2nd
a²
Output the function ?(z) == (2)))
Note that the pDP functions (2(-) and c3(-) which we use to report the additional pDP losses of releasing the private estimates of the gradient and the Hessian do not depend the dataset, and thus are not required to be separately released. The privately released pDP functions depend on 0"; to reduce clutter, we omit this parameter in our presentation of Algorithm 2.
Theorem 10. There is a universal constant C such that if X > C02va(1 (log(1/p))//3) then Algorithm 2 satisfies the following properties
2
8a 10z
2 2lgg(1//))
(18)),))-DP
201
20g
(0)
x1
("(dr:))* |x|""
("((";))" 20g
/ (2 8DP for all
201
403
E X and 0 S < 1.
3. For a fixed imput z and D, and all > 0, the privately released privacy report ē(-) satisfies that ei (ÔP, D, D+a) S <2((2) < 12e, (0p D, D,D+))=
/2log(2/p) with probability |f'[1 02
3p 3p where (-)) is the expression from Theorem
Accurate approximation with low privacy cost. This theorem shows that if we use slightly larger ObjPert then we get an upper bound the pDP for each individual 2 up to a multiplicative and additive factor. The multiplicative factor is coming from multiplicative approximation of log (1 + f (((x))()) and the additive error is due to the additional noise added for releasing the third term 3 V.((P, DY (e((P;2)) 2). The additional DP and pDP losses for releasing H and g comparable to the DP and pDP losses in Objective Perturbation itself if 02 X 0g X o.
Moreover, while using large À may appear to introduce additional bias, the required choice of A x do is actually exactly the choice to obtain the minimax rate in general convex private ERM (Bassily et al., 2014) (Figure 2 demonstrates the impact of increasing A).
Joint DP interpretation. Finally, we can also interpret our results from a joint-DP perspective (Kearns et al., 2014). Given any realized output 0r E Rd. the tuple of {ē(21, 0"), 0*)
IInttedd of adding "analyze-gauss" noise. sample from the Gaussian Orthogonal Ensemble (GOE) distribution to obtain a random matrix (Appendix ??). Under this model we show that 7 on the order of O(vo(1 (/3)

---

satisfies joint DP with the same parameter as in Theorem 10. This follows from the billboard lemma (Hsu al., 2016).
4
Experiments
Here we evaluate our methods to release the pDP losses using logistic regression as a case study. In Section 4.1, we demonstrate that the stronger regularization required by Algorithm 2 does affect the utility of the model. In Section 4.2 we show that by carefully allocating the privacy budget of the data-dependent release, we can achieve more accurate estimate of the ex-post pDP losses of Algorithm compared to the data-independenn release, with reasonable overhead (same overall DP budget and only slight uptick in the overall pDP losses).
Experiments with linear regression, with additional datasets and with alternative privacy budget allocation schemes included in the supplementary materials.
4.1 Stronger regularization does not worsen model utility
In this experiment we use synthetic dataset generated by sampling 2,, -N(0,, Ia) and normal- izing each z; E X so that ||2.|22 = 1. Then we rescale Y X to ensure y1 [0, 1] for each E Y.
Algorithm 2 requires larger À than sug- gested by Theorem 5 in order to achieve uniform multiplicative approximation of p()). We investigate the effect of stronger regularization on the utility of a private logistic regression model applied a synthetic dataset (n 1000, d 50), for several settings of 61. Since each value of é demands different minimum value of À in order to achieve (e,, (G..))diiferenttil privacy, we compare via "X-inflation": a measure of how many times larger we set than its mini- mum value required to achieve the worst- case DP bound objective perturbation.
0.50
0.45
6 0.1
0.40
6: 0.5
1
0.35
2
0.30
Alg 2
0.25
0.20
95
100
105
110
X-inflation
Figure Utility of Obj-Pert with larger
E.g., for logistic regression the objective perturbation mechanism requires À 2 z and in Figure X-inflation value of 10 means that we À 5. For each X-inflate value c, we run Algorithm with A cAutj-Pert- In particular, the star symbol marks the level of X-inflation enforced by Algorithm 2. The experimental results summarized Figure show that the performance of the private logistic regression model (as measured by the 0-1 loss) remains roughly constant across varying scales of X.
4.2 Comparison of data-independent and data-dependent bounds
The following experiments feature the credit card default dataset (n 30000, d = 21) (Yeh & Lien, 2009) from the UCI Machine Learning Repository. We privately train a binary classifier to predict whether not a credit card client z defaults on her payment (Algorithm 1), and calculate the pDP loss e (-) as well as the data-independent and -dependent estimates (-) for each the training set (Algorithm 2).
The failure probabilities for both Algorithms and 2 are set as 6 = p 10-6 Our choices of a and depend on E and follows the requirements stated in Theorem 5 to achieve DP. We don't use any additional regularization, i.e. r(0) O. For the data-dependent release, the noise parameters Ø d3. are each calibrated according to the analytic Gaussian mechanism of (Balle & Wang, 2018).
Using 1 as DP budget, investigate how to allocate the privacy budget among the components of the data-dependent release (e é1 + 62 + e3) to achieve a favorable comparison with the data- independent release which requires no additional privacy cost t1). The configuration described Figure 3, which skews the data-dependent privacy budget toward more accurately releasing of (-), was empirically chosen as example where the sum cf(() e2(-) ea(-) of privately released pDP

---

losses of the data-dependent approach are comparable to the privately released ex-post pDP loss (-) of the data-independent approach. Note that c2(-) and c)(+) aren't ex-post in the traditional sense; however, we feel comfortable summing of() + <2(+) + ea(-) since all three terms are a function of & and individual z's data. Note also that since the total budget is the same for both the data-independent and -dependent releases, é differs between them. Therefore Figure compares the accuracy of both approaches using the ratio between of (-) and e1(+) rather than their raw values.
DP budget +
2500
data-indep median
12000
data-indep T0
data-dep median data-indop data-drp
data- dep 200)
2000
1000
(1() x2 rg
1000
8000
1000
300
0.0
0.2
0.4
0.5
0.8
1.0
10'
10
privacy loss
TO/O))
(a) Distribution of privately released ex-post pDP losses.
(b) Distribution of ratios between the privately released ex-post pDP losses of (-) and their true values ex(-).
Figure 3: True and privately released pDP losses when the total privacy budget is 1. For the data-independent release we use the entire privacy budget releasing 0" (E1 1). For the data-dependent release we reserve some of the privacy budget for releasing yr (-) and g-()) (E1 = 0.2, 62 = 0.7, 63 = 0.1).
When including the additional privacy budget incurred by the data-dependent approach, the data- dependent approach loses its competitive edge over the data-independent approach. Note that setting c2 C3 = O would reduce the data-dependent approach to the data-independent one. The real advantage of the data-dependent approach can be best seen by allotting only a small portion of the overall privacy budget to Algorithm 1; then we can release jP and (.). with reasonable overhead while achieving tighter and more accurate upper bounds for (-) and (-). By suffering small additional ex-post pDP loss (Figure 3a), we can release the ex-post pDP losses of Algorithm much more accurately (Figure ??). The downside to this is that reducing 6j reduces the accuracy of the output åP. Deciding how allocate the privacy budget between 61, (2 and 63 thus requires weighing the importance of an accurate jP against the importance of an accurate cf (-).
5 Conclusion
We precisely calculate the privacy loss that an individual suffers after the objective perturbation algorithm is run on a specific dataset. The ex-post pDP loss function in DP-ERM can be accurately released to all individuals with little independent bound which empirically provides a reasonably accurate estimate of the ex-post pDP loss while requiring further privatization step. Reserving some of the privacy budget allows to alternatively release a tighter data-depente dependentn bound.
additional privacy cost. In particular,
present data-
An important next step is to extend the per-instance DP analysis to the setting of constrained optimization. There are many promising future directions including using publishable pDP losses for designing more data-adaptive DP algorithms.
10

---

Acknowledgments
The work was partially supported by NSF CAREER Award # 2048091, Google Research Scholar Award and gift from Evidation Health.
References
Balle, B. and Wang. Y.-.. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pp. 394 403. PMLR, 2018.
Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Symposium on Foundations of Computer Science, pp. 464-473. IEEE, 2014.
Chaudhuri. K., Monteleoni, C., and Sarwate, A. D. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Chiani, M. Distribution of the largest eigenvalue for real wishart and gaussian random matrices and simple approximation for the tracy-widom distribution. Journal of Multivariate Analysis, 129: 69-81, 2014.
Dwork, C. and Lei. J. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 371-380, 2009.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends in T'eoreeicall Computer Science, 9(3-4):21 1-707, 2014a.
Dwork, C., Talwar, K.. Thakurta, A., and Zhang. L. Analyze gauss: optimal bounds for privacy- preserving principal component analysis. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 11-20, 2014b.
Ebadi, H., Sands, D., and Schneider, G. Differential privacy: Now it's getting personal. ACM Sigplan Notices, 50(1):69) (011), 2015.
Feldman, V. and Zrnic, T. Individual privacy accounting via renyi filter. arXiv preprint arXiv:2008. // 193, 2020.
Ghosh, A. and Roth, A. Selling privacy at auction. In Proceedings of the 12th ACM conference on Electronic commerce, pp. 199-208, 2011.
Hsu, J., Huang, Z. Roth, A., Roughgarden, T. and Wu, Z. S. Private matchings and allocations. SIAM Journal on Computing, 1556)1995,, 2016.
Kearns, M., Pai, M., Roth, A., and Ullman, J. Mechanism design in large games; Incentives and privacy. In Conference on Innovations in theoretical computer science (ITCS-14), pp. 403-410, 2014.
Kifer, D., Smith, A., and Thakurta, A. Private convex empirical risk minimization and high- dimensional regression. In Conference on Learning Theory, pp. 25-1. JMLR Workshop and Conference Proceedings, 2012.
Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, Z. S. Accuracy first: Selecting differential privacy level for accuracy-constrained erm. Advances in Neural Information Processing Systems, 2017:2567-2577, 2017.
Liu, Z., Wang, Y.-.., and Smola, A. Fast differentially private matrix factorization. In Proceedings of the 9th ACM Conference Recommender Systems, pp. 171-178, 2015.
Narayanan, and Shmatikov, V. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium Security and Privacy (sp 2008), pp. 111-125. IEEE, 2008.

---

Nissim, K., Raskhodnikova, S., and Smith, A. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-nimi ninth annual ACM symposium on Theory of computing, pp- 75 84, 2007.
Papernot, N., Song. S., Mironov, I., Raghunathan, A., Talwar, K., and Ülfar Erlingsson. Scalable private learning with pate. In Interaaioonal Conference on Learning Representations (ICLR-18), 2018.
Tang, J., Korolova, A., Bai, X., Wang, X., and Wang, X. Privacy loss in apple's 's implementation of differential privacy on macos 12.12. arXiv preprint arXiv: 17X.v:1009007533 2017.
Triastcyn, A. and Faltings, B. Bayesian differential privacy for machine learning. In International Conference on Machine Learning, pp. 9583-9592. PMLR, 2020.
Wang, Y.-X. Per-instance differential privacy. Journal of Privacy and Confidentiality, 9(1, 2019.
Wei, B.-C., Hu, Y.-Q., and Fung. W.-K. Generalized leverage and its applications. Scandinaviar Journal of stattssiics, 25(1):25-37, 1998.
Yeh, I.C. and Lien, C.-h. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2):2473 2480 2009.
Yu, D., Zhang, H., Chen, W., Yin, J., and Liu, T. Large scale private learning via low-rank reparametrization. In International Conference on Machine Learning (ICML-21), volume 139, pp. 12208-1221 PMLR, 2021.
12


Reviews:
[{"review_id": "msy5UbH69sq", "reviewer": "Reviewer_fBsx", "summary": "The paper looks at how to release per-instance differentially private (pDP) privacy bounds, focusing on empirical risk minimization (ERM) with a convex loss function. The paper proposes methods for releasing either a looser data independent estimate or a tighter data-dependent one. Without properly checking the proofs, the paper seems sensible and interesting.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "** update after rebuttals & discussion\nI lower my score a bit due to concerns raised by other reviewers (see the other reviews for more specific points). However, I still think this is a nice paper and ready to be published.\n**\n\nThe paper focuses on pDP, basically a datapoint-specific measure of privacy, for ERM with convex losses using objective perturbation for privacy. With pDP the privacy guarantees depend on the sensitive data, and therefore cannot be released without some further privacy mechanism. The authors propose methods for releasing the pDP privacy values: a looser bound holds independent of the actul data, while under some additional assumptions a tighter data-dependent bound can be used. \nThe paper is mostly clear and easy to read. In short, I have some questions for the authors, but overall the introduced methods seem novel and interesting.\n\nQuestions/comments for the authors:\n1) It is unclear to me how the different epsilon values relate to each other, i.e., based on the paper I am not sure if plotting epsilons from standard DP vs pDP makes sense (are they on the same scale, are the privacy guarantees somehow comparable when the epsilons are equal, or how should I interpret the difference in epsilons). Can you elaborate a bit?\n\nMinor comments:\n* Definitions 1 & 2 using input space of fixed size n seems a bit weird considering the neighbourhood relation.\n* I especially liked the connection to existing statistical theory pointed out in the form generalized leverage score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is not much discussion on the limitations, although the limiting assumptions are stated clearly enough. I do not think this paper needs a separate discussion on societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Eldncq1kL6H", "reviewer": "Reviewer_NN5N", "summary": "The paper builds upon a recent work of Wang that introduced per-instance differential privacy, a refinement of the usual approximate differential privacy which captures the effect of a specific data point in the context of a specific dataset on a DP analysis. In particular, the paper proposes ways of reporting per-instance DP losses in a privacy-preserving manner (satisfying joint DP, essentially), focusing on convex ERM with objective perturbation.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper has two main contributions: the first one is evaluating per-instance privacy losses for objective perturbation, and the second one is designing mechanisms for reporting such losses. The motivation for making such reports lies in the fact that the overall DP parameter can be a conservative overestimate of the per-instance privacy loss. While the paper does a good job of emphasizing this gap between per-instance and overall DP, as well as explaining that per-instance parameters are sensitive, I think it could be more convincing in describing why we would want to make these reports in the first place. It’s certainly nice to be able to report these values to participants, but it felt like a bit of a niche objective without more motivation.\n\nIn terms of the results, I have various specific comments and questions. The presentation is not completely clear at times; some notation is never defined and I had trouble understanding certain statements.\n\n1. The data-independent bound on pDP is just a bound on personalized DP of Ebadi, Sands, Schneider (2015), right? You’re not really doing anything “per-instance” there? Note that personalized DP immediately satisfies joint DP.\n2. Related to the previous point, in the experiments you only plot the data-independent bound. Can you demonstrate empirically that it makes sense to go through the effort of providing a data-dependent bound? Again, for me per-instance differential privacy means that you’re data-dependent; otherwise you’re reporting personalized DP.\n3. I didn’t understand Figure 1 and its setup. In the lines starting with 213, there is a setup where I don’t see any randomization (denoted by b previously) in how the solution is computed. I don’t understand how what’s done there satisfies DP, what the purpose of the rotation is, and how the figure relates to Corollary 7. I might be missing something obvious.\n4. In statements such as Theorem 6, what do you mean by $\\pm$? You mean whichever sign would maximize the expression?\n5. In line 223, what do you mean by “hidden in this analysis are the delta’s of Algorithm 1”? I don’t see any delta in Algorithm 1.\n6. What is the function b(…) in Theorem 6 and Theorem 8? It’s never defined.\n7. What is $F^{-1}_{\\lambda(GOE(d))}$ in Algorithm 2? I don’t think it’s defined anywhere.\n8. I’m not sure the $D_{\\pm z}$ notation works. In Definition 3, for example, say D doesn’t contain z. Then, you’re only bounding one direction of the divergence, when $\\mathcal{A}(D)$ is in the numerator and $\\mathcal{A}(D_{\\pm z})$ in the denominator. You’re not bounding the other direction.\n9. In line 161, why does it say “simplified version”? I don’t see the difference between Algorithm 1 and equation (1).\n10. I don’t understand the expression “privacy target z” in Theorem 6/Corollary 7.\n11. I don’t understand the comment in line 168 that says “chooses a regularization strength to ensure that the objective function is strongly convex”. The objective in equation (1) is strongly convex for any non-zero lambda since all other functions are convex as well.\n12. In line 290, is theta $N(0, \\mathbb{I})$ (it’s not 1-d)?\n13. In line 291, what do you mean by Y being a deterministic function of X and theta such that …? I’m confused by several things here. First, how is Y deterministic if you’re defining Pr[Y=1]? Second, how is the probability equal to something + noise matrix? What are the dimensions of E, X, theta here?\n14. Could you clarify what result you’re referring to in the Bassily et al reference in line 281?\n15. In line 155, you could clarify which norm you’re considering (e.g., $\\ell_2$).\n16. In line 275, is it supposed to be $\\tilde \\epsilon$ between $\\epsilon_1$ and $12\\epsilon_1$?\n\n------------------------------------------------------------------------------------------------\n\nThank you for your response. It was indeed very helpful in clarifying various technical specifics and notation, so I'm happy to increase my score. That said, I'm still a bit confused about the motivation. I don't see why joint DP is the right requirement if we want to handle the \"accuracy first\" setup or justifying large global epsilons (in addition, as you described the accuracy first setup it sounds like there would be privacy leakage through the noise level, which your results might not handle). It's a nice feature to have the possibility of making these joint DP reports, but perhaps I still see it as a bit of a niche objective. I can see how building on these results you might be able to improve data-dependent approaches like propose-test-release, as you suggested, and I think this is a very promising direction and I'm eager to read these results. Unfortunately, the current submission does not give any indication of how this could be done, which is why I'm hesitant to increase my score further.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations are addressed in the conclusion section. The paper makes a contribution to the theory of differential privacy, which as a general research topic is of great societal relevance. I do not see potential negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "DbmgigWFyGW", "reviewer": "Reviewer_eTH4", "summary": "The paper considers the problem of publishing the per-instance privacy loss of a trained learning model to each individual while protecting the privacy of other participants. The paper focuses on training a convex, smooth model using objective perturbation. By deriving bounds on the per-instance ex-post privacy loss, the paper develops algorithms that publish the Hessian matrix privately, which can be used by each individual to evaluate their per-instance privacy loss.\n\nThe paper shows that under certain regimes, the algorithm can provide an approximation of the per-instance privacy loss up to constant factors. The paper also provides empirical experiments which show how the derived method provides an approximation of the per-instance privacy cost and how it compares to the worst-case bound.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Main comments:\n\n1. The main technical contribution of the paper is a per-instance DP analysis of the objective perturbation algorithm for empirical risk minimization. The result is OK but the analysis seems to be limited to the objective perturbation algorithm. For publishing privacy loss, the proposed algorithm (Algorithm 2) is limited to generalized linear models. How the technique can be generalized to other problems is less clear.\n\n2. The motivation for publishing the per-instance privacy cost needs some more justification. Since this privacy loss is only observed by the user, it is cannot be used for privacy budgeting or utility improvement. It would be nice if the authors can provide some more motivation or a practical scenario where the technique can be most beneficial.\n\n3. In the experimental results, is the privacy cost for sharing the per-instance DP loss considered in the plot? How would this affect the accuracy of the approximation? \n\nMinor comments:\n1. Line 285: I believe it should be z_n at the end.\n\nThe paper is nicely written overall and has some nice ideas. I am tending towards a rejection due to the above reasons. I am happy to increase my score if the comments can be addressed.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "1rW91E9aWBC", "reviewer": "Reviewer_aTij", "summary": "The paper considers the problem of bridging the gap between central DP, where overall epsilon is released, versus personalized epsilon, that is privacy of individual data points that may or may not have been part of a dataset analyzed with central DP.\nThe paper considers central DP of specific function: objective perturbation mechanism, this setting of achieving central DP is less common that others.\nThe paper makes an observation that naively computing personalized epsilon and releasing it will violate privacy of central DP (as this computation depends on private data) as anyone can use such an oracle to determine the real value that central DP is trying to hide.\nSince the paper considers a specific DP mechanism its results are applied only to private empirical risk minimization problems (ie function computed on the private dataset).\n\nThe proposed mechanism works by computing personalizes privacy loss (es-post pDP) directly (since it considers convex problems it is possible). It then adds noise to computed result because otherwise this metric cannot be released. However the paper also derives data-independent upper bounds for pDP that do not incur additional noise.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This is a very nice paper and I really enjoyed reading it.\n\nMy main concern is with it applicability to other DP settings (e.g., Laplace mechanism) and other mechanisms that rely on Gaussian noise and do not build on optimization function perturbation.\n\nExperimental section could  additional experiments, including experiments showing distinction between the data independent bound and the bound that contains additional Gaussian noise added, and real datasets.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are pointed out in one sentence in conclusion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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

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