Auditing Privacy Mechanisms via Label Inference Attacks
Authors: Robert Istvan Busa-Fekete
Travis Dick
Claudio Gentile
Andres Munoz medina
Adam Smith
Marika Swanberg
Venue: NeurIPS 2024 spotlight (2024)
Keywords: label inference
label reconstruction
differential privacy
learning from label proportions
Primary area: privacy
TL;DR: We propose auditing tools for privacy mechanisms via label reconstruction advantage measures, allowing to place a variety of proposed label privatization schemes—some differentially private, some not—on the same footing.

Abstract: We propose reconstruction advantage measures to audit label privatization mechanisms. A reconstruction advantage measure quantifies the increase in an attacker's ability to infer the true label of an unlabeled example when provided with a private version of the labels in a dataset (e.g., aggregate of labels from different users or noisy labels output by randomized response), compared to an attacker that only observes the feature vectors, but may have prior knowledge of the correlation between features and labels. We consider two such auditing measures: one additive, and on multiplicative. These cover previous approaches taken in the literature on empirical auditing and differential privacy. These measures allow us to place a variety of proposed privatization schemes---some differentially private, some not---on the same footing. We analyze these measures theoretically under a distributional model which, we claim, encapsulates reasonable adversarial settings. We also quantify their behavior empirically on real and simulated  prediction tasks. Across a range of experimental settings, we find that differentially private schemes dominate or match the privacy-utility tradeoff of more heuristic approaches.

Auditing Privacy Mechanisms via Label Inference Attacks
Róbert István Busa-Fekete Google Research NY busarobi@google. com
Travis Dick Google Research NY tdi cdikkooogge..o com
Claudio Gentile Google Research NY cgentile@google. com
Andrés Muñoz Medina Google Research NY ammedina@google.. com
Adam Smith Boston University Google DeepMind ads22@bu. edu
Marika Swanberg
Boston University
Google Research NY marikas@bu. edu
Abstract
We propose reconstruction advantage measures to audit label privatization mecha- nisms. A reconstruction advantage measure quantifies the increase in attacker's s ability to infer the true label an unlabeled example when provided with private version of the labels in dataset (e.g., aggregate of labels from different users noisy labels output by randomized response), compared to an attacker that only observes the feature vectors, but may have prior knowledge of the correlation between features and labels. We consider two such auditing measures: one addi- tive, and multiplicative. These incorporate previous approaches taken in the literature on empirical auditing and differential privacy. The measures allow us to place variety of proposed privatization schemes-ae some differentially private, some not-on the same footing. We analyze these measures theoretically under a distributional model which encapsulates reasonable adversarial settings, We also quantify their behavior empirically on real and simulated prediction tasks. Across a range of experimental settings, we find that differentially private schemes dominate or match the privacy-utility tradeoff of more heuristic approaches.
Introduction
Data sharing and processing provides an undeniable utility to individuals and the society large. The modern data ecosystem has played significant role in scientific advancement, economic growth, and technologies that benefit individuals in their daily lives. Yet, the collection, processing, and sharing of sensitive information can lead to real privacy harms. Understanding the theoretical and empirical risks associated with different types of data disclosure is a rich area of research and topic of discussion. The privacy community has studied number of empirical measures of disclosure risks against several types of attacks, including: inference attacks 229 reconstruction attacks [5].
re-identification attacks [14] and label inference attacks [13 31].
While differential privacy gives rigorous guarantees against these attacks by worst-case adversaries, it is natural to wonder whether non-DP (deterministic) mechanisms give any empirical privacy protections. This line of inquiry necessitates empirical measures privacy that take adversarial un- certainty into account. At fundamental level, whether one is studying reconstruction membership inference, nearly every privacy disclosure metric comes down to quantifying the relationship between an adversary's 's prior and posterior knowledge before and after data release.
In this work, we consider a number of ways summarize this proor-posterior relationship. and apply our proposed metrics to few Privacy Enhancing Technologies (PETs). We consider two
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

families of metrics: As coarse measure, we consider the expected additive difference between the prior and posterior success rates; while this does not capture unlikely high-disclosure events, it gives sense for the risk posed to an average individual. To better capture such events, we then consider the finer-grained multiplicative difference between the adversary's prior and posterior: These empirical measures of privacy risk allow us to relate and compare the risks of both aggregation-base and differential privacy-basee PETs, and hence compare their privacy-accuracy trade-off curves: What accuracy does one get for given level of privacy protection? ? Together, these metrics paint a more balanced and nuanced picture of the disclosure risks and accuracy trade-off's posed by aggregation and differentially private mechanisms.
We will focus on the simplest possible scenario for information sharing: the case where user wishes to disclose single bit of information (for instance binary label in a classification problem). While this problem is simple to present, it already highlights lot of the difficulties in providing measures of privacy that are meaningful for both noise-based and aggregate- -ased tools. Most notably, it already cachannsmmbetweeen
requires handling the correlations- the visible features and the hidden, sensitive labels, Similar to [31. we incorporate adversarial knowledge by a prior, and measure the difference between the prior and the adversary's 's posterior distribution conditional on observed aggregates.
to an attacker, but unknown to the
Understanding binary labels already has practical implications. For instance, with Chrome's proposed conversion reporting API [I, the event of user converting after clicking on an online ad - buying a product, signing up for newsletter, installing an app, etc. - or not is considered sensitive. and therefore is reported only with some noise. However, once reported, ad tech providers can use features associated with an ad click (impression information, publisher information, etc.) to train models that can predict future conversions.
Our contribution. We make several contributions: (i) We introduce additive reconstruction advan- tage measures as ways to quantify the amount of leakage associated with a generic (not necessarily differentially private) privacy mechanism. These are variants and extensions of the Expected Attack Utility (EAU) and advantage contained in [3 (ii) We quantify such measures for randomized response and random label aggregation under different correlation assumptions with public data. (iii) We consider a more demanding multiplicative reconstruction advantage measure (in the spirit of predecessors of differential privacy [17 IO)), and again quantify this advantage for randomized response and random label aggregation. (iv) We conduct a series of experiments on benchmark and synthetic datasets measuring the privacy-utility tradeoff of a number of basic mechanisms, including randomized response, label aggregation and label aggregation plus Laplace or geometric noise. Remarkably, these experiments show that learning with aggregate labels tends to be strictly harder in practice than learning with randomly perturbed labels. That is, differentially private schemes dominate or match the privacy-utility tradeoff of label aggregate schemes for all or most privacy levels and for both types of advantage measure, a conclusion we have not seen clearly spelled out in prior work on privacy. Even measured "on their own turf", deterministic aggregation which lack provable guarantees like differential privacy-do not provide significant advantage.
Prior Work. Our measures of privacy risk relate closely to previous work on membership inference and auditing, as well as to variants of differential privacy that assume adversarial uncertainty. We discuss these in Section 3.3] after defining our measures.
Reproducibility. For the sake of full reproducibility of our experimental setting and results, our code is available at the link httptt:tt/gthihiii http://ggichuuu.cooooooooeo// reoogglerrssarrchoooogee..
tree/ bree/master/ www.tiig...iiviic......o
2 Preliminaries
For a natural number n. let [n] = N: n3.
Let X' denote a feature (or instance) space and
) be binary ( = {00 1}) or multiclass ( = [c)) label space. We assume the existence of a joint distribution D on X' x V, encoding the correlation between the input features and the labels. The marginal distribution over X' will be denoted by Dx. and the conditional distribution of y given x will be denoted by Dy For distributions over binary labels, we denote by 7)x)) = P PorDyyi (v = 1 1|x) the probability of drawing label 1 conditioned on feature vector x. In the multiclass case, we will use 712 a) = Py-Dyi= (y- = a|z), for a E y = [c]. We define a dataset S = ((x), v1), ..... (#m. vn)) as sequence of pairs (xt, y:), each one drawn i.i.d. from D. We use x = (aI Lnn) to denote the features in S and y (y1,.... . fm) to denote the corresponding labels. We will sometimes abuse the

---

notation in the math, and write for brevity (x.y) instead of (x1, v1)...., (Im, Vmm). Consistent with this notation abuse, we will often use x x y and (X x )) interchangeably no ambiguity will arise.
In order to unify the study of privacy enhancing technologies, for the rest of the paper model PETs as (possibly randomized) functions M (X x y)m - Z. These functions map a collection of m labeled examples a privacy protected representation in the domain Z. The domain Z depends on the PET but, throughout the paper, it will be clear from the context.
In setting, we consider PETs that protect labels and release features in the clear (so, strictly speaking, the output of a PET should also include x itself; we leave implicit in our notation). Despite this, our reconstruction advantage measures can be applied to any PET, we recall below two standard (and very basic) PETs that have been proposed for various Ads metries APIs: one which satisfies label differential privacy, and one which relies on random aggregation. These are the two PET's on which we will also be able to give theoretical guarantees. We formulate them for binary classification.
Definition 2.1. Given 2 O, we say that (randomized) algorithm A that takes as impul S is e-Label Differentially Private (e-Label DP) for any two datasets S and S' that differ in the label of a single sample we have P(A(()) E B) S P(A((S) E B), where B is any subset of the output space of A.
Randomized Response (RR) is classical 30 way of achieving c-Label DP. In the binary classifica- tion case, RR with privacy parameter π = 1/(1 + +e)) simply works by randomly flipping each label Y; in the dataset with independent probability before revealing it to the learning algorithm. For a fixed e > 0, RR corresponds to the function .MRR (x, y) = y = (yi...., Dm) E {0, 11mh. where 5 1 Y/ with probability x= 1/(1 + e²) and equal to y, with probability 1 π, independently for each E [m].
A completely different label privacy mechanism. still very utilized in practice (see, e.g., the Privacy Sandbox API in Google 1 and the Apple SKAN initiative (2) is one based on (random) label aggregation, whereby the dataset S gets partitioned uniformly at random into bags of given size k, S = ((=11- Mi....... (I1R= v1x);.... (I Yo1). (a Bnk)), and only feature vectors and the fraction of positive labels in each bag are revealed to the attacker/learning algorithm. In other words, the attacker has access to S via a collection {(B,, a;), i E [n]} of n labeled bags of size k. with m nk, where B, = { j E [K]], a, = Σ Vig is the label proportion (fraction of labels "I") in the i-th bag, and all the involved samples (zij, Wey) are drawn i.i.d. from D. Thus, the attacker receives information about the m labels yıj of the m instances Tay from dataset S only in the aggregate form determined by the n label proportions og Note, however, that the feature vectors Tıy are individually observed. From an attacker viewpoint, this setting is sometimes called Learning from Label Proportions (LLP). Hence, LLP corresponds to the function MLLP(X, y)= = (at...., ax,) E [0,
Learning from privatized labels. Randomized response is especially appealing from practical point of view, since privatized data with label flipping can be handled by many prominent learning algorithms as is, with some tuning of their these learners in terms of sample complexity are only deteriorated by some constant that depends on the label noise level, see, for example (27). To improve accuracy, we debias the gradients in post-processing step similar to Equation (7) in 119 we discuss the debiasing details in Appendix C
Often the theoretical guarantees of
On the other hand, simple and very well-known method for learning from aggregate labels is the one that of [33 call Empirical Proportion Risk Minimization. In fact, different versions of this algorithm are discussed in the literature without clear reference to its origin. In [12], the authors simply call this algorithm the Proportion Matching algorithm (PROPMATCH), and we shall adopt their terminology here. Given loss function & R x IR + R+, a hypothesis set of functions H R mapping X' (convex) prediction space D0 C R. and collection {(B,, ass, E [m]) of n. labeled bags of size k; PROPMATCH minimizes the empirical proportion matching loss, i.e., it
solves the following optimization problem: minge Σm= ( E 1 (ss) It known that
the above method is consistent (see for instance (2] That is, training model this way - under some mild conditions on l and H and for a large enough sample- - results in learning a model h that minimizes the expected event level loss ((z.))-(((((())) v)]. Finally, for our baselines, it will be helpful to consider a PET that reveals no label information at all: MM y) = L.
3

---

3 Auditing Large-Scale Label Inference
In this section, we propose a number of auditing metrics to measure the risk of large-scale label reconstruction. Unlike DP auditing techniques which focus on worst-case guarantees, we will focus here on distributional guarantees. In doing so, we extend the (additive) reconstruction advantage definition introduced in 31 to the LLP setting and propose meaningful variants of it.
Our reconstruction advantage measures can be applied to virtually any PET for auditing purposes. For concreteness, we will also provide analytical bounds on such measures when applied to PETs like RR and label aggregation. On one hand, these bounds help illustrate the precise dependence on the data distribution D. On the other, they will pave the way for our experimental findings in Section
A reconstruction advantage metric is grounded in the following natural privacy question: How much does releasing the ouiput of a PET increase the risk of label inference compared to not releasing anything? This corresponds naturally to measuring an attacker's 's prior over a target person's ' label compared to the attacker's posterior after viewing the mechanism output.
We model the attacker (often called "adversary" later on) as a function A x x Z + ym that maps the features x and the output of PET M(x, y) to vector of predicted labels, one for each example. We compare this attacker's 's success to the the uninformed or prior attacker that gets x and the PET that reveals no label information M (x, y) I. To measure the efficacy of an attacker compared to its prior, we define a number of attack utility variants.
The Expected Attuck Utility of adversary A using information from PET M on collection of m examples drawn i.i.d. from a distribution D is defined as:
P EAU(A.M,D) (x.))>"" Un- (m]), coins of M
=y))
where A(::,) is the i-th component of vector A(;, .). In words, the expected attack utility of adversary A is the probability that A correctly guesses the label of a randomly chosen example when provided the features and the output of M. Equivalently, this is the expected fraction of the examples that the adversary predicts the correct label for. The adversary's 's success rate may depend on the distribution over features and labels. For example, if labels are entirely determined by features, then our metric should reflect that privatized labels (for any mechanism .M) reveal no additional information about the true labels. To control for the information that features inherently reveal about labels, we assume that the adversary has knowledge of the data distribution D over X' x V, either completely (c.g.. Definition 3.1) or approximately through learning on disjoint data (as in our experiments in Section
Further, we define the Individual Expected Attack Utility input data 2;
(A,,;(,,M,D,z))
PP (x "/""- coins of M
1/1 xi
where x(- is x with the i-th item I, dropped, and likewise for y(i), The quantity (EA M, D, .²)) emphasizes the (expected) attack utility on a specific piece of data I; when the associated label yi is drawn from the conditional distribution Dylz.- For instance, (A, D, x.) measures, for a given 24, the chance that an attacker is able to recon- struct the associated label ye, if y generated from Dylz, and, by virtue of mechanism MILPP, y/ becomes part of a bag (of some size k), only the bag label proportion being revealed to the attacker.
In order to measure the increase in risk incurred by releasing the output of a PET, we consider the attack utility of an optimal adversary in two scenarios: one in which the adversary gets the features, x, together with the output of the PET, MMxx,, y), and an alternate setting where the adversary gets only the features (which is equivalent using M.). We call the difference in attack utility between the informed and uninformed adversary the attack advantage. Intuitively, the attack advantage measures the label reidentification risk that can be attributed the PET rather than to correlations between the features x and labels y which are inherent in the distribution D. Since we have given two notions of attack utility above, we have two corresponding notions of attack advantage. Below is an additive version, based on utility differences, later on (Section 3.2 version, based on utility ratios.
we will also consider a multiplicative

---

Definition 3.1. Given PET M for set of m examples drawn from a data distribution D. the (additive) Expected attack Advantage is defined as
EAdv(M, D) sup EAU (informed M, D)
sup Ausudimmnd
GAUninninfoommel M.. D)
Autoraund
Similarly, when the i-th item xy is kept frozen, the Individual Expected attack Advantage is defined as IEAdv(M, M,D))) sup TRAU(Aigormaat M, D,,;))
sup
TEAU (uninffrooed M D,
Autiowadd
Ausisforonn
Note that RR is generally described in terms of its behavior on a single example (xz, y). rather than collection of m i.i.d. samples. Likewise, label aggregation operates on each bag of size k << m independently. However, since the data i.i.d., easy that the attack advantage for RR is independent of the number of examples m, while the attack advantage for (random) label aggregation will only depend on k, rather than m.
Appendix [..5 contains further variants of attack advantage, like one that accounts for the tail of the attack advantage distribution, well associated bounds. These be stretched to the point where the feature vector x = (Z1,...,,fi Tm)) ) is arbitrary, and only the properties of the condition distribution Dyle is factored in.
3.1 Bounding the Additive Attack Advantage
As warm up, we begin by studying the additive expected attack advantage for LLP when the labels independent of the features. Note that, since the features do not play any role in this simplified setting, the notions of advantage coincide. We recall again that all results involving MLLP (Theorems 3.2 3.3 and 3.4 below) deal with single bag when computing advantage measures (hence we will write a instead of a;)). This is because distribution D is known to the adversary, and the bags the adversary observes are independent of one another, hence there is no extra advantage from operating on an entire dataset of bags at once. All proofs are given in the appendix.
Theorem 3.2. Fix data distribution D. let p (( 1), and fix an arbitrary threshold J0. 1/2]. If labels are independent of features (i.e., D is product of distributions over X and y), then for all bag sizes k 2 1 we have:
p(1-p) R
ifp E [0,
EAdv D) min(p,
Eaiimmia, a}l
ifp 1/2 2 8
where 21-)) hides constants independent of B and k.
A couple of remarks are in order. First, observe that, as expected. the advantage EAdv(Mup, D) always non negaaiiae This can be easily derived by noting that [[[a] = p and then applying Jensen's 's inequality to the concave function æ + min(xx 1- for x E [0, 1]. Second, despite being non-negative, Theorem 3.2 also proves the desirable property that EAdv D) goes zero as the bag size increases. The convergence rate is in general of the form 1/Vk, but it becomes negative exponential in k when p is bounded away from 1/2.
We now investigate general distributions over features and labels and consider in turn EAdv and IEAdv.
Theorem 3.3. Let 'D be arbitrary distribution on X x/ p E[(((x)), and μ Bln(=)(1-n(a2) Then, for all bag sizes 2 2 we have:
EAdv(Mur. D) ō - (1/1/A((111 - -p))
+ 11/4
Vi.
where Ö hides logarithmic factors in k.
Hence, also in this more general case of LLP, the advantage converges to zero the bag size k grows large. Compared to the rate in Theorem 3.2 are only losing the log k factors implicit in the Ô notation. This is because, when applied to the scenario where labels and features are independent,
(xx) = is constant with x, so that μ = p(1 p). and the first term becomes / /p(l_p) while the k
second one reads (p(1-p))'/4 which is lower order when is large. We strongly believe that the tighter gap-dependent analysis carried out for Theorem extends to the more general scenario of Theorem 3.3 but we leave this as an open question.
The corresponding bound for the individual expected attack advantage is given next.
5

---

Theorem 3.4. Under the same assumptions and notation as in Theorem k log(1/p).
3.3 we have, for μ > 0, and
H IBAdv(Mur: (, N2O -00((00-)))) (1)11
V
p
122
pal22k
where 14 n)(x)) (7xx)),, and Ô hides logarithmic factors in k.
In the bounds of Theorems 3.2 3.3 and 3.4 the dependence on the data distribution D is encoded in p(1 pp and μu; as p(1 p) and/or μ gets smaller we should naturally expect a smaller advantage, as the adversary is facing an easier label prediction problem. Appendix c.nnaans further distribution- dependent results, like bound on the advantage that, conditioned on x (Z1...., Fm), is of the form 1: Σ ===1
14
where f4; = r)(x:)(1 -=))))
We now provide the corresponding expression for the additive attack advantage for RR (at a given level 2 0). We recall that the results of (31 imply that every c-label-DP PET M has advantage bounded as [Adv(M, D) < Ite-. However, one drawback of this bound is that it is distribution independent (or, rather, worst case over distribution D). Yet, the attack advantage depends heavily on D. For extreme example, if we have P ((x,)))((( PET, which is not directly captured by only relying on the properties of c-DP.
2_
1) 1, the attack ad advantage is zero for every
Recall that, since RR operates on each example independently. the advantage is independent of the number of examples m (a formal proof given in Appendix (A.6). Hence we derive a bound for IEAdv(MRR. D, a. ) and expression for the optimal adversary under RR (see Appendix A.7).
Theorem 3.5. For any data distribution D, the individual expected attack advantage IEAdv(Mee D, for randomized response with privacy parameter =Tter (min(n(21), n((11)] - -T) E 1-
-Tte is equal to
We use the above expression our experiments (Section 4) estimate the attack advantage of RR for various values of e. Being distribution dependent, this expression leads to much tighter bounds on 2 0.46, while for one the attack advantage. For example e 1, the bound from K1 T+e
dataset used in our experiments we that the attack advantage for RR at e 1 is only 0.00095.
3.2 Multiplicative Attack Advantage
The definitions of attack advantage given so far measure the absolute change in successful reconstruc- tion, not the relative change. Moreover, they do not fully capture the different levels of confidence in the reconstruction, since they involve an expectation over either (x, or y given x. Next, we give an additional set of definitions that capture these important nuances. For the sake of brevity, in this section we directly instantiate the adversaries Antoreed and Aunintormed to Bayes optimal predictors.
Definition 3.6. Given data distribution D. mechanism M. index i, and pair of labels a, b Y, the multiplicative advantage is the difference of log odds ratios:
Tx 2, - log 772,, a) T, Tx, 2, b)
Ia Ta, D, 2, = log
n(x;, b)
where T((,,a)) = P(y = a x1)x;)= and TT x, a) = PywDy, (y. = a x, M(x, y) = 2) is the probability of y, after observing the output of M. We denote the binary case by I10(-) I(-) and shorten 77(2;) == r)(,,, 1) and (x, := (x, 1).
This particular formulation has the advantage that (a,, D, x, 2, i) is large in absolute value when- ever there is a large relative change in either label probability. This also entails that a multiplicative- style advantage metric is generally stronger than an additive one.
When v7xz)) and n. (x, 2) are both less than 1/2 (in the binary setting), we have (M, D, x, 2, =
(log (xx2)) ). with symmetric expression for the case that both are close to 1. Because we assume ((M((x)) = y; a, x) i.i.d. sampling, one can easily see that (M, D, i) log P(M(x, = =21y; = b, x)
which makes it clear that for e-label DP mechanisms like MRR (at level e) the above log ratio is at most

---

in absolute value for all x and On the other hand, for MLLP. there is always a small chance that all the examples in the bag will have the same label making the above log ratio infinite. However, for large k and distributions 'D in which the 17 a) values are not too close to O or 1, the leakage (a,((M, D, x, 2, i) might be small in most cases.
What values of multiplicative advantage should be considered acceptable? We argue that this probability should be viewed as probability of system failure and set appropriately small. (For example, when running with MLLP on modern-scale data sets, we might create billions of bags; even a tiny probability of failure can lead to many bags whose individuals have their labels revealed exactly). The next theorem gives high probability bounds for MLLP in the simple case when the distribution D a product distribution.
Theorem 3.7. Fix data distribution D over features and binary labels, let ((aa))) Dy = 1), and assume the labels are independent of features (i.e,, D is a product of distributions over X' and y).
Then there are universal constants C1, C2 > O such that for p E (0, 1), all bag sizes k 2 e lm(1/6) and all i [k] we have
p(-p))
(HoLMMer Mur(xx y).0)/ e
In(1/5) p(1 - (11-
S
Then, when &s is sufficiently large and the conditional label probabilities nf(;;) are all equal some constant p E (0, ). the probability of failure drops off exponentially as l increases. When working with a data set of size m, we can substitute 5 8' k to get a bound on the probability that any bag in the dataset exhibits extreme values of leakage Pa, For the setting covered by Theorem [3.7 one gets that the bags must be of size k ~ log(n) [p(11 - p)) for the probability of extreme bags to converge towards O. In the experiments in Section we report results on both the additive and the multiplicative reconstruction advantage criteria.
3.3 Connection to prior work on auditing and membership inference, and distributional DP
Our approach on quantifying attack advantage can be viewed as fitting into recent line of work on auditing learning algorithms via membership inference attacks. This class of attacks was introduced by [21] and subsequently studied in theory [T] [8] and practice 29]. Whether used as attacks or empirical lower bounds on differential privacy parameters 22 these approaches set up hypothesis test for the presence or absence of a particular target record in the training data [15. They diverge in whether they consider an adversary with access to all the rest of the training data ('fully informed"), or with only distributional knowledge of the rest of the training data (usually made available to the attacker as an independent sample drawn from the same distribution).
In our setting, testing for the presence of an individual makes no sense, since individual records' features are known. In the binary case, our measures are success metries for testing the hypothesis that a particular individual's 's label is 1 as opposed to O: Multiplicative advantage bounds the ratio of true- to false-positive rates of the Bayes' optimal test, while additive advantage measures the difference of true- and false-positive rates. This perspective was also taken in previous work: for example, [26] use such a test to bound the differential privacy parameters of label-DP algorithms. However, their modeling assumes a fully informed adversary (that knows all labels). In contrast, we posit a reasonable model of adversarial uncertainty in order to look at the risks of mechanisms such as label aggregation. In this respect, our approach follows more in the line of membership inference attacks that use only distributional knowledge, or to variants of differential privacy that assume adversarial uncertainty such as [9 7 16].
Further relevant references include 225 32). which have been developed more in the Cryptography literature. Like here, those papers propose to measure prediction advantage by comparing the information status of an agent before and after seen the obfuscated data. Yet, they do not consider the public features/private label mixed setting we study here, which is clearly necessary when investigating. for instance, the LLP mechanism. As a result, the measures proposed in 25 32) generally fail to distinguish between the information gained as result of: (1) correlation to the public features, and (2) the mechanism output. Hence, they overestimate the revelation of the mechanism, at times to the extreme. Consider, for clarity, the case where 7)(x)) is either 0 or 1 for all xT. In this case the adversary's 's inference advantage zero for any reasonable measure of advantage, since the adversary has perfect knowledge of the labels without the mechanism output.
7

---

4 Experiments
In this section, we demonstrate how our advantage measures can be used to quantify and compare the potential privacy leakage of RR, LLP, and two additional PETs with range of privacy parameters. See Appendix for full details on our PETs, experimental setup, and additional results.
C
Mechanisms. We empirically evaluate a number of proposed mechanisms for label privacy: random- ized response (RR), Label Proportions (LLP), and two further PETs: LLP+Lap, where (zero-mean) Laplace noise is added to the label aggregate in each bag, and LLP+Geom, where geometric noise is added and then clipped so the estimated proportion lies in [0. 11. The noise scale for both LLP+Lap and LLP+Geom is chosen so that the PETs satisfy label differential privacy. Postprocessed clipped geometric noise is the mechanism for releasing a binary sum that is optimal among all differentially private mechanisms for several loss measures [20]. To minimize squared error, the optimal post- processing is to correct for the bias introduced by clipping. We empirically study these advantage measures a variety of synthetic and benchmark datasets, reporting either the AUC advantage trade-off or the sioor-vspoosterin scatter plots, that help shed light on the distribution of our advantage measures on different points in the dataset for the various PETs.
Estimating class conditionals for advantage and PET Utility. The advantage measures for all PETs we consider can all be computed as a function of the class conditional probabilities (ax) = Pyy [ In our synthetic datasets we compute the advantage measures for different distributions on r7(2); however, for non-synthetic data sets, the value of ny()) is not explicitly known. Instead, we estimate 17(x) for each by training classifier h (without any PETs) and use the prediction probability h((x) as a proxy for n)()) We compute the figure of merit (additive or multiplicative advantage) for the optimal informed and uninformed attackers using these estimates.
Rebx
Figure 1: Prior-posterior scatter plots for LLP. RR, and LLP+GGeom from two synthetic datasets (where the prior n)()) is drawn) and the two real-world datasets (where n(x) is approximated), The colors of the dots correspond to different parameter values for the PETs. For each bag size and distribution, we did 1000 independent The further a point is from the y x dotted line, the more is revealed about its label result of the PET.
45 01
18
15
10
We also measure the utility of each PET for trained models. For each dataset, PET, and privacy parameters, we apply the PET to the training labels to produce a privatized version. We then train model on the privatized data using minibatch gradient descent with the Adam optimizer (24) and a loss function designed for the PET. For RR, the loss debiases the binary crossentropy loss when evaluated on the RR labels, and for LLP, LLP+Laplace, and LLP+Geom, we minimize the Empirical Proportion Risk defined in Section 2 For each dataset, PET, and privacy parameters, we perform a grid search over the learning rate parameter and report the test AUC of the best performing learning rate. All utility results are averaged over multiple runs. The maximum standard error in the mean for the reported AUCs is 0.0076 and the vast majority are less than 0.002.
Computing posterior distributions for each PET. Given a list of priors (or estimated priors) for each data point (17(2)) R analytically compute the posterior probabilities for each of the PETs we consider.
First, we apply Bayes" theorem and use the fact that the x 's are independent:
Fly = 1|z, M(x, y) = 2) PPM((,, y) = 2|2, yi = 1). TP(n 1(x;)
(I)
P(M(x,)) = =2|x)
8

---

For RR with flipping probability p. Equation evaluates to po(a,) (1 (1-p)n(x)) if the outcome is 1.
if the outcome of pm(#)) [2.
MRR (R:) 0, and to (1-P))(a) -1
For label aggregation (LLP), the bags are independent, so we consider only single bag at a time. MLLP is deterministic, so in the numerator (T,ML((1))) = 2 2| Vi = 1)
is the probability density at of a Poisson binomial distribution with flipping probabilities (n(())...... (o((a)).....(((()))
1/ (1(x==1); ); 17((4144)) ),..,,,,....... n)(x))) Similarly, the denominator is the probability density at of a Poisson binomial distribution with flipping probabilities (1(21))-..-77(14)
For MLap-LLP and MG the terms in Equation T are convolutions of the posterior for L.P and the Laplace Geometrie distributions, respectively.
Results. Our results are reported in Figures 2 and 3 as well as in Appendix C
We used two
synthentic datasets and two real-world datasets (Higgs and KDD12). Notice that Higgs a relatively balanced dataset, while KDD12 is a quite imbalanced one.
Figure give scatter plots of prior Pyy 1 1|x) vs. posterior Ply = 1 | Mx,, y) = =) distribution on the four datasets for LLP, RR and LLP+Geom with different colors for each value of parameters k (for LLP and LLP+Geom) and (for RR and LLP+Geom). The behavior of LLP+Lap reported in Appendix for completeness, but it turned out to be similar to that of LLP+Geom.
It is instructive to observe how the points spread w.r.t. the main diagonal y x. Points that are the diagonal have no label privacy loss as a result of the PET, because the posterior is identical to the prior. On the other hand, points with posterior of 0 have complete privacy loss, since the posterior on the private label is deterministic. In general, a wider spread away from y = x indicates more privacy loss. The scatter plots tend form spindle shapes whose width is determined by the privacy parameters of the PETs. Yet, there is a substantial difference between LLP and RR. While RR generates points on the boundaries of the spindles (middle row), LLP tends to spread such points more uniformly. Moreover, some of the points for LLP lie on the edges of the square [0. 1J2, which correspond an infinite multiplicative advantage. LLP+Lap (bottom row) is somewhere in between, in that the points are also located inside the spindles, but never on the edges of the square. Note that a spindle boundary is the set of points having the same multiplicative advantage measure. Moreover. these differences become more pronounced on skewed datasets like KDD12 as the probability of homogenous bags (bags of all labels or labels) become much more likely.
Un 20:1
Figure 2: Top: Prior-posterior scatter plots for RR (grey), LLP (blue), and LLP+Geom (or- ange) with = and k 8 on the same datasets as in Fig- ure 1 With these choice of pa- rameters, the three mechanisms roughly achieve the same AUC on Higgs. Middle: Empiri- cal CDFs of (the absolute value of) the multiplicative advantage for the three PETs on the four datasets. Bottom: CDFs of the additive advantage.
hatens
34 43
P.B.
10
130
0.0
These scatter plots are already suggestive of the expected behavior of the Sillity-privacy tradeoff curves that will come next in 3 Given an allowed level of privacy (as measured by either additive multiplicative advantage) each point in the interior of the spindle associated with that privacy level will also lie in the boundary of a smaller (thus higher privacy) spindle. This will make inference harder, thereby reducing (average) utility at that level of privacy. Following this intuition, we expect RR to achieve a higher utility- -riivay-prvay curve than LLP, with LLP+Geem somewhere in between. A more detailed comparison between RR and LLP+Geeom (or LLP+Lap) is in Appendix [
Figure 2 helps further illustrate the different behavior of the considered PETs vis-à-vis the advantage measure. On the four datasets, we pick here a set of parameters that make the PETs AUC-comparable on Higgs. We then plot the empirical Cumulative Distribution Functions (CDFs) on the four datasets for both multiplicative (middle row) and additive (last row) measures. While the CDFs of additive

---

measures are roughly similar across the three PETs, this is not the case for the highly skewed 3eta(2,30) and KDD12 datasets, where one can easily spot for LLP (blue line) the presence of a significant mass of points with large multiplicative advantage. Note that in the middle row, the CDF of RR (grey line) is just a vertical line (æ = 1) while the CDF of L.P++Geom (orange line) first follows the blue line and then the grey one. These high multiplicative advantage points cannot be detected when only relying on the CDFs of the additive measure.
Utility vs. advantage tradeoff on benchmark datasets. The experiments far have compared the distribution of individual additive and multiplicative advantage induced by RR, LLP, and LLP+Geom for various parameter settings and datasets. However, the use of PETs is always tradeoff between utility and privacy, since if we cared about privacy alone, the best strategy would be to release no information all. Figure 3 plots the AUC vs advantage for each PET as we vary the PET's privacy parameters. Note that, since the x-axis is advantage, we are able to put the normally incomparable privacy parameters of the PETs on equal footing. For RR and LLP, the single privacy parameter (e and k respectively) traces out an AUC vs Advantage curve. Since LLP+Lap and LLP+Geom have two parameters, there is an area of achievable AUC vs Advantage pairs. For these mechanisms, we plot a separate curve for each bag size k showing the tradeoff when varying for that k.
When measuring privacy loss via multiplicative advantage, RR has the best privacy vs. accuracy trade- off compared to all other PETs. This is consistent with the obser- vations in Fig. 2 In particular, the three mechanisms (with the given parameters) have almost the same AUC on Higgs. Yet when looking the CDFs of the multiplicative measure one sees that the two DP mechanisms have bounded MAs whereas LLP has a significant num- ber of extreme values. This trend is more pronounced for KDD12 than Higgs. Thus, for the same AUC, LLP has a higher multiplicative ad- vantage, with more pronounced gap for KDD12 than for Higgs. On the other hand, Fig. 2 also shows that the CDFs of the additive ad- vantage are roughly the same for all three mechanisms (again, at the same AUC). Thus, in Fig. 3 the mechanisms have similar AUC vs advantage tradeoffs.
Coor
30th No Matittahe Advntagg
2et Secerti Malple aeeeeetrrrbbeee Aduerine
Geenk
k-33
Figure 3: Privacy vs utility tradeoff curves for the various PETs on the Higgs and KDD12 datasets. Utility is measured by AUC on test set, while privacy is either the additive measure (bottom row) or the 9tth-percentile of the multiplicative measure (so as to rule out the infinite multiplicative ad advantage cases that can occur for L.PP). Each point corresponds to setting of the privacy parameter for the PET (e for RR, & for LLP, and both for L.P+GGeom). The z--oordinatee is the advantage (either additive or multiplicative) value for that PET, while the y-coordinate is the test AUC of a model trained from the output of that PET. The AUC of the model trained without PET roughly corresponds to the top value achieved by these curves.
Discussion and Conclusions
We study ways to audit label privatization mechanisms for commonly used PETs: randomized re- sponse, random label aggregation, and combinations thereof. Together, the additive and multiplicative advantage measures we introduced paint a richer picture of the reconstruction risks posed by different parameter settings, and for the first time allow us to compare their privacy-accuragy trade-off curves.
The measures we propose are tailored to settings where the data are sampled i.i.d. from a distribution, and each record consists of public features together with one sensitive binary feature. Computing these measures empirically requires estimates of the adversary's 's label uncertainty, which won't 't be correct if the adversary has significant side information or, crucially, if the same data are re- used in multiple mechanisms. Handling such complex settings requires more general concepts like differential privacy. Another complexity emerges when we consider settings like click prediction, where a minority label (a click) is viewed as qualitatively more revelatory than the majority one (no click). While the measures we consider are agnostic to the label semantics, principled ways to incorporate complex semanties might be valuable and shed light heuristics used in practice.
10

---

References
Chrome privacy sandbox.
http:://wrrr..rrrr...g.ooooooooa attribution-rege reporttin
Skadnetwork 4 release notes.
[3] Y. W. Aden. Kdd cup 2012, track 2. http:///aggggaaacoccccccccotoold 2012.
[4] P. Baldi, Sadowski, and D. Whiteson, Searching for exotic particles in high-energy physics with deep learning. Nature Communications, 5(1):4308, 2014.
[5] B. Balle, G. Cherubin, and Hayes. Reconstructing training data with informed adversaries. In 43rd IEEE Symposiun on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022, pages 1138-1156. IEEE, 2022.
[6] A. D. Barbour and T. Lindvall. Translated poisson approximation for markov chains. Journal of Theoretical Probability, 19(3):609-615 630, 2006.
[7] R. Bassily, A. Groce, Katz, and A. Smith. Coupled- worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 439 448. IEEE, 2013.
[8] J. J. Benedetto. Harmonic analysis and applications. CRC Press, 2020.
[9] R. Bhaskar, A. Bhowmick, V. Goyal, S. Laxman, and A. Thakurta. Noiseless database privacy. In Advances in Crypooloy-ASIACRRPP 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Scoul, South Korea, December 4-8, 2011. Proceedings 17, pages 215-232. Springer. 2011.
[10] A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: the sulq framework. In Proceedings of the twenty-forthh ACM SIGMOD-SIGACT-SIGANN symposium on Principles of database systems, pages 128-138, 2005.
[11] M. Bun, J. Ullman, and S. Vadhan. Fingerprinting codes and the price approximate differential privacy. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 1-10, 2014.
[12] R. Busa-Fekete H. Choi, T. Dick, C. Gentile, and A. Munos Medina. Easy learning from label proportions. In Neurips 2023, 2023.
[13] R. I. Busa- Busa-Fekete, A. M. Medina, U. Syed, and S. Vassilvitskii. Label diffcrential privacy and private training data release. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, International Conference Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 3233-3251. PMLR, 2023.
[14] C. Carey, T. Dick, A. Epasto. A. Javanmard, Karlin, S. Kumar, A. Muñoz Medina, V. Mirrokni. G. H. Nunes, S. Vassilvitskii, et al. Mcasuring re-identification risk. Proceedings of the ACM Management of Data, 1(2):1226, 2023.
[15] N. Carlini, S. Chien, M. Nasr, S. Song, A. Terzis, F. Tramèr. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pages 1897-1914, 2022.
[16] D. Desfontaines and B. Pejó. Sok: Differential privacies. Proceedings on Privacy Enhancing Technologies. 2020.
[17] Dinur and K. Nissim. Revealing information while preserving privacy. In Proceedings of the Twenty- Second ACM SEGMOD-SIGACT-SIGARY Symposium on Symppso 202-210. ACM, 2003.
Principles of Database Systems, PODS '03, pages
[18] C. Dwork, A. Smith, T. Steinke, J. Ullman, and S. Vadhan. Robust traceability from trace amounts. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 650-669. IEEF, 2015.
[19] B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, and C. Zhang. Deep learning with label diffcrential privacy. Advances in neural information processing systems, 14:27131-27144 2021.
[20] A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility- miximizia privacy mechanisms. In arXiv:0811.2841, 2009.

---

[21] N. Homer, S. Szelinger, M. Redman, D. Duggan, W. Tembe. J. Muehling, J. V. Pearson, D. A. Stephan, S. F. Nelson, and D. W. Craig. Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays. PLoS genetics, 4(8)ee000116. 2008
[22] M. Jagielski, J. Ullman. and A. Oprea. Auditing differentially private machine learning: how private is private sgd? Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[23] Y. Juan, Y. Zhuang, S. Chin, and C.-J. Lin. aware factorization machines for etr prediction. In Proceedings of the 10th ACM conference on recommender systems, pages 43 50, 2016.
[24] D. Kingma and Ba. Adam: A method stochastic optimization. In Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations. ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[25] A. Makhdoumi, S. Salamatian, N. Fawaz, and M. Médard. From the information bottleneck to the privacy funnel. In 2014 IEEE Information Theory Workshop, ITW 2014, pages 501-505, IEEE, 2014.
[26] M. Malek, L. Mironov, K. Prasad, L. Shilov, and F. Tramer. Antipodes of label differential privacy: Pate and alibi. In Advances in Neural Information Processing Systems, volume 34, pages 6934-693690 6944, 2021.
[27] H. Reeve and Kabán. Classification with unknown class-conditional label noise on non-compact feature spaces. In Proceedings of the Thirty- Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2624-2651, PMLR, 25-28 Jun 2019.
[28] A. Röllin. Translated Poisson approximation using exchangeable pair couplings. The Annals of Applied Probability, (75-6))1596 1614. 2007.
[29] R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium Security and Privacy, SP 2017, San Jose, CA. USA, May 22-26. 2017, pages 18. IEEE Computer Society, 2017.
[30] S. L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. JASA, pages 63-69, 1965.
[31] R. J., P. Zhou, K. Q. Weinberger, and C. Guo. Does label differential privacy prevent label inference attacks? In International Conference on Artificial Intelligence and Statistics, pages 4336 4344. PMLR, 2023.
[32] H. Xiao and S. Devadas. Automatic privacy measurement and control of data processing. Advances in Cryptology CRYPTO 2023 43rd Annual Inter- national Cryptology Conference, CRYPTO 2023, volume 14082 of Lecture Notes in Computer Science, pages 611 16444, 2023.
[33] F. Yu, D. Liu, S. Kumar. T. Jebara, and S. Chang. a-svm for learning with label propoctions. In ICML, Proceedings of the 30th International Conference on Machine Learning, pages 504-512, 2013.
12

---

A
Proofs for Section 3
We start off by providing preliminary result that will be useful throughout all proofs.
A.1 Preliminary results
Consider, for specific E [im] the random variables
f1i(x) sup
IP Aniimes y~D
(Ainformed (x, M(x, y)); = y/s \x)
(2)
f2s(x)
sup P (Aunintormed (X, Ausinisfomnal y>D 5/x
Mi M1
xx)
The relevance of fis and far stems from the fact that for the mechanisms M we consider in this paper, the advantages EAdv, IEAdv, and HPAdv will be defined in terms of fúi and fzi-
Lemma A.1. For any PET M, any x E X, any conditional data distribution Dy number of examples k. and E [m]] we have
f11(x) f2i(x) = min n(xx))
E min (P(y: = =b x, M(x, y)) x y~Dyix bEf(0,1)
where 1) 7: x²). Moreover, the optimal (informed) adversary A" is:
((xx, :10
// M,x, 2 1/2
otherwise.
Proof. Set for brevity = = M. yx. Since Mi outputs null, and the (15, Uj) pairs for j E [m]] independent, have
P(u = 1 x, x) = P(y x;) = n7(4),
immediately follows that the best attacker Aunininfommed involved in the computation of fxx(x) the Bayes optimal predictor
Ú1 arg max P(y = xx))
ne(0.1)
so that
fxx(x) = 1 min(n(x:). 1)(x;))
Let turn to Si; and fix any adversary Ainformed- We lower bound the probability that the adversary makes a mistake on y,. Let = = M(x, y) be the output of the PET, and (S1...., (0.....,m.) = Ainonned X, 2) be the output of the adversary. Since it is (x, meaauuaaa,, we have
P( ys x2
P(ù: =
= 1, 2) P(y = 1 x,
+ P = 8/ = x, 2) Ply: = 0 x,
-1 = 13 P(y: = + 1 = 0} IP(y: = 0 x,2).
Hence
P0:: y1 xx) = E2|x 1( = 1} Pyy = + 03 P(u = 0 x, 2) x
s Ez/x [max (oax(P(( P(y (V = x, 0 [x]
EynDy Mnax(P(we =1 M11xxM(xx,))....... P(y: = x, Mx y))} |x]
EynDDyi (min(P((y
x, P(y, x, Mx y))) x]
fx.(x).
where the inequality holds because the maximum probability term is never smaller than the probability term selected by the indicator variables. Incidentally, the above also shows that the optimal informed
adversary is the one that selects the larger of the two probability terms with probability one, which makes the inequality above hold with equality.
At this point, we use the fact that
EAdv(MuP.. D) [x(sii(x) - f2i(x))
holds for all E [m]] since the data sequence (I1, v1).... .., (Øks yk) is i...d.
13

---

A.2 Proof of Theorem 3.2
Theorem 3.2. Fix data distribution let = (aay))D(y== = =), and fix an arbitrary threshold
E [0, 1/2. laabll are independent of features (i.e. D is product of distributions over X and y),
then for all bag sizes k 2 1 we have:
p(1-p) ((
ipp E [0.
EAdv(Mur, D) = mp - p} -aalminaa,
if 1/21 2 8
where D(-) hides constants independent of ß and k.
Proof. For given (Ig, My) in the dataset, can consider without loss of generality only the size-k: bag that y falls into, and then refer the indexing to this bag only.
Then set for brevity E = ka Ei= Vi. From we can write
EAdv(MIP, D) = Ex [mii[((2s), m)(1)))) Byz
min (P( = b[Σ)] bE(0,1)
min 1 p} Ey min [o
(P(() 61 |1))
Since ply: E)) a independent of and p. the minimum value in the second expectation is
[minfa, 1 - -a]].
and the claimed equality for FAAv(MMLLP, D) follows.
As for the inequality with general p E [0, 1]. note that, when a, b, E [0, 1]. min - a} min(b, 1 b} s la bl
(4)
If applied to the expression
[minfaa a]} min 1in(p11-p)) p} -p]
this gives
p(1 p)
EAdv(MuP, D) < Ealla - pll S Bal(aa p)
k
where the second inequality is Jensen's.
Finally, in the where p 1/2] 2 B, for some gap B > 0, can proceed through more direct analysis. Assume I 1/2- 3. We can write
min(a, - ar = min 1 1- < 1/2] + a 1/2]
+ +al(a> 1/2] aIIa > 1/2]
al s 1/2) (1 a) 1/2] + allaa 1/2] alfa > 1/2)
= a - (2a - 1)1l(a > 1/2]
2 a 1fa > 1/2]
Hence
E, mmi 2- 1/2).
Now, p < 1/2 implies min (p. p} = p, which leads us to min(p, 1- p} - [min a P(a > 1/2).
Finally, by the standard Bernstein inequality we have
k(1/2-10 -) p)²
P(a > 1/2) < exp
= -0(k0²
2p(1 - p) 2p)/3
which gives the second inequality.
A similar argument holds if reverse the assumption on p to p 2 1/2 + 3.
14

---

A.3 Proof of Theorem 3.3
Again, as in the proof of Theorem 3.2 for a given (zy, Mj) in the dataset, we can consider with no loss of generality only the size-k bag that zj falls into, and then refer the indexing to this bag only.
Recall that, for general distribution D over X x the distribution of random variable ka شز= Mi conditioned on x = (#1,... .T&) is Poisson Binomial (PBin) with parameters {n( that is, the distribution of the sum of k independent Bernoulli random variables yj. each with its own bias 7223),, where 7 (z) (y ar).
Notation. For simplicity of notation we let 7Ιę - (zx) be the conditional positive probability of label given feature vector z and let p = E[m]]. For fixed feature vectors X = (#1,...., 2k41), let A; denote a Bernoulli random variable with mean 7]. and let Z =
k E}=1
prove. Theorem 3.3. Let be an arbitrary distribution on x x. = [[[(z)]], and μ (ln(z)(1- Then, for all bag sizes k 2 we have:
We recall the statement of the theorem
EAdv(Mup. D) 5
1e 1111(p((1 -p)(1)
+ 11/4
V
where Ô hides logarithmic factors k.
The above theorem is direct consequence of the following Lemma. Lemma A.2. Let B denote a bag with + 1 elements. Let
= @0VVll - -p)
1
Ck
log 8k: + 12kp(1 p) log 8K log 8k + v
Vk
Vkl
Then
EAdy D) S k2/2 / V
π
mn (1 m/)
Elm (1 - -m)
c3/2
4
k3/2
k
Proof. Set for brevity M MMLP(x, y). From have EAdy(MuLP. D)
E [min(1(((<+1)))) (
E
[min = 0|x MiH
2k+1
(x.y)
< E [l((=++1 - P(y++1 = 1|x, (x,y
where we have again used (4). We now focus on calculating P(yk+1 = 1|x M). Let E Σ5 Uy Note that for given realization of feature vector x, 3k++1 distributed like A&+1 and the output M is distributed like Z++1- Therefore:
P(
x
+ P(AA+1
Zk+1 E)
IP = =1, Exx)
P(Z x)
P(Z+ = x
TJ++1 PP(Z++1 Σ x)
Using this expression in the original expectation we see that we can bound the advantage as
P(Zx = Σ. - 1
B(xx)
M
P(Zz+1 Σ x)
Again, note that for a fixed x, the variable Σ is distributed like Ze+1. Therefore. taking expectation over y the above expression can be rewritten as
1+1
PA = 8 8 11x)
Ex
P(Zz-1=8 -|/x)x
P(Z++1 = s|x)
0
k+1 M Σ
Ex
P(Zk+1 =/xx) P(Z, = = -=11x)
==0
15

---

Finally, note that since Z Z + A we also have
P(Zk+1 = s x) P( P(Ax+1 = 1 P( = s - 1 x + P(A = x) F(z = x
7]++1 P(Z - 1 x) + mk++1 PPZx 1
= x)
Therefore, we conclude that the advantage can bounded by
P(z - = s 1|x0|
Ex
1k+1(11 71+11)
P(Zk = s x)
[++1 Σ
Ex [M++1 - mc+1)]
T = = P(Zx= =
(5)
-==0
where we have used the fact that the random variables 7/2 independent from each other. Using also the fact that 77++11 has the same distribution as combined with Lemma A.3 below, we have that the above quantity is bounded by:
π E In (1 m m))
π E m (1 - m)
1//4 2cx
Elm (1 - m))l Elni + (1 - m )1 +
4/3/2
ek2
Elm (1 m))]
(6)
k
Moreover, notice that [ny + (1 - m) ) + + 2 (1 - m1) = 1. Therefore Elns + - m))
=
1 2 Bm (1 - m)), and using the fact that m (1 - 71) - we have
Elm (1 7 ) Ebi + (1 ) Blm (1 ]] 2 (1-m)))
max 2² -2x)*
12>20
But a simple calculation shows that the above function is maximized at 2 = min 1_ 1442
1/4), thus
we must have
1
Bim (1 7/ Bini (1 m1 S (z1) 2x2)*
(ek)²
the last inequality holding for all l 2 1. In addition, we have the trivial bound E[( (1 m/1)] E(n
(1- - m ) م Elm (1 77)) ) so that
Elm (1 - m. 12 Emy EM + (1 m)) I min
Blm (1 - m))? c2
E B[m (1 - -m
I3 [m (1 m])] c.2 122 +1
(using minfa, b) <
a+b. with a = Emm m))s and b = 2x²z) )
ab
v /Em - mm]
3/2//3/2
(using x² 2- 2// +1 0, with x ck Kik m1))
Replacing this bound in (6) we obtain the following upper bound on the advantage:
1/1 20
/
1
+
E(m - m/)
v E (1 - m)]
E Elm (1 m
c3/2
4
1-/2
ek2
k
B Bim (1 m))
E mm (1 - m)]
< 22/4 12/aa/2cu /2Ck
+
e3/2
4
k3/2
h:
as claimed.
Lemma A.3. Let Ck be as in Lemma A.2
Then the following bound holds:
k+1
(P = =|/x) P(Zz s - 1 |x0 |201|
Ex
+ 1/4 ///2/ck
Enn + (1 - 71)ppp+ + (4E/m (1 - 4)33233/2
π
e EE (1 m 12
16

---

Proof. Let a > 0 and b < k, and let (a, = [j E N S s b). For any we then have
1++
PP = x1x) - P(Z 2 =
==0
Σ
IP = 8 x) - P(Zx = = 1 1|x)| + Σ
P = 8 s|x) - P(Z = ---1) 8-1)
(a
sg(a.b]
IP 8 x P(Z+ 1|x) + Σ
P(
x) + P(Z+ =8- 11x)
<E(a,b]
[a.b.
<
Σ
Pi = s x) - P = s x + 2 2 $ [a. b]
|E|o.b
Taking expectation over both sides with respect we have
k+1
Ex
P(Zz
s x|x) P(zz = s-
||x0| -
< Exx
Σ
IP 8 8 - P(Zx 8 11x/ + 2 & [a, (j]b)|())] x)]
Let now Qs denote the probability measure associated with a binomial random variable with parame- ters (k, p). Since Zu is a Poisson-Binomial random variable with parameters ..,..... -]k, the prob-
ability P(Zx $ [a, x) is a linear function in each individual Tii so that |x [IP(2 & (a, b] [x]]
Q& bl We now proceed to bound the first expectation in By Cauchy- Schhaa-S inequality
we have
Ex
Σ .E
IP
= 8/1)) P(Zz- = s - ||xx|
Ex
(b a) Σ (P = 8 (x) = -
sEla,b)
k+1
< Ex
(b
(P(Zk = =|/x) P(Z = -
1/))2
k+
Ex
(b
a) ==0
Σ
(P(Z) = s - PP(2s = 5 1|x))
where the last inequality holds by Jensen's inequality. Let
and By Lemma A.4 below we have that the above term is bounded by
= Elv (1 ?
B= 2 m))
a)
π
(4Bk)3/2
eBk
so that gives
Ex
IPZz= s|x) 12Zx =- -=1 <2Qu(l..09))
(6 (b- a) (A++ (4Bk)3/2
eBk
Let = max(kp Vieaa 0} and = min (kp + vhekk 1). By Bernstein's inequality applied to binomial random variables have that Qa, b)s) zE Hence, with this choice of a and b we
17

---

obtain
Tk+1
Ex
Σ
P( = - P(Z = - |x]]
S k + V2VBoRy
A +
(4Bk)
π
+
eBk²
The lemma follows by replacing the values of A and B.
Lemma A.4. The following inequality holds
x+1
Ex
(P =
P(Zx = s -- 1|x))]
6=0
- Einh + (1 - -m1)7² (8 (81/m (1 771 ]4)3//
π
π
2e E M1 (1 7 k2
Proof. Let ps = P(Zx = 8 x) P(Zz = 8 x), for 0, ....... A + Further, for
k ++1 1 2 u 2 0 let gu (x)
Σ ==0 Po (x)e denote the discrete Fourier transform. Since,
v
for any x, the mapping
pxx) = (po (x).. Pk+t (x)) + (x) = g(x)
is unitary linear transformation we write:
R+1
k++
Σ
(P(2) P(Zx = s 1|x)) ||g())]
gu (x)
Moreover, by Lemma A.3 below we have that
gx(x) (1 e 2+2
1
(1 nj + mE
2niu x+2
/k: +
j=1
and therefore
k
1 (1- cOS
2T
2TT
lg. (xx) Iu (x)
I1 j=1
(1-m))²
n7) 3 nz 2n, (1 m7) cos
+ 2
h +
1: + 2
Therefore we can write
x+1
Ex
Σ
(P(Z) = 8 s/x)
-P(Z = -- --
1==0
k+1
2TT
2Tu
Ex
COS
II (1-1))²+ + + 2n (1 173) cos
k k+2 2
to + 2
k + 2
w=0
3=1
1+1
2
Ex (11m)) 2 + 2n, (1 175) cos
2Tu
1 -
COS
(8)
k+2
+
+ 2
==0
j=1
Where we have used the fact that the random variables ny are independent. Finally by linearity of expectation and the fact that fi is distributed as for all j, we have
T++1
Ex
Σ
(P(Zk= = =| P(ZE= - =
k+1
2Tu
Elby + (1 m + 2 - (1-m)) cos
2Tu
COS
(9)
2
k: 2
k: + 2
==0
Applying Proposition A.6 below with E(n + ) and b 2 Bmm (1 m we have that the above expression is bounded by
Blvi + (1 m)
π
(8
(8E( (1 7 3k33/2
2e Em (1 m R
which gives the claimed result.
18

---

Lemma A.5. Let (x(x) = P(Zz = ssxx P(Z - 8 - = and let gu(x)
Eitt Ps (x(x) VFF2
denote the discrete Fourier transform of pf (xi(x),..... ...., PP(()) Then
1
Iu gu(x)
(1
112
II (1 ny + nye 2.0
vk +
j=1
Proof. By definition of Iu (x(x) have:
k+1
k+1
1
Σ
6+2
PIZk- 8 x)
Σ
R42
PiZz= -- 1|x)
V +
s=0
k+1
k-1
1
Aniua P(Zxx 8 x)
Ariy
2riu(e-1) k+3
PiZx = =s-1(x)
Vk
+
1
(1
2riu E+2
Rz, (e Fス2
Ze xx
Vk
Vk (1
1
2niu KTZ
JZZZ x + 2
2Tu
where oz, xx denotes the characteristic function of Za conditioned on x. Using the fact that Zx. Ej=1 Aj and that AI...., A are independent given x, we have oze x = I ΦA lay. The result follows from the fact that Aj is Bernoulli random variable and therefore Φ |a 12y(2) (1-1) + n))
Proposition A.6. For any a, b, k >> 0 such that a + b = 1 we have
2T
2Tu
1
COS
ke k+ 2
a bcos
1o 2
a²
(4kb)3/2
ebk-
Proof. Using the fact that cos
2 < 0 for u E [(k + 2)/,,3( + 2)/4] we have that k+2
k+1
1 - cos
2TT )
a + boos
2T )
k+2/4
Σ
-ocos
2Tu
)
b cos
2Tu
1: 2
+ 2
1s ++22
le +
x=0
3(k42)/4 Σ
k + 2 )
2Tu
2Tu
k
1 cos
a bcos
4: +
w= (k+2)/4+1
k+1
2Tu cosos
k 2 )
2x k + 2
a + bcos
== (k+2)//44
(x+2)/4
(k + 2)a +
Σ
2tu (1 11 cos
+ b cos
2TT 1:
2
k+1
k
Σ
1 cos
2 (a+ boss
2
+ 2
+ 2
w= 3=+(k+2/44+
(k+2)/4
(k: ( +2
Σ
1 (1-
cos
2Tu
2Tu ( a b cos
k + 2
+ 2
==0
where we used the fact that (1- cost) S for the first inequality and the symmetry of the cosine function for the last equality. We now apply the result of Proposition A.8 to the above expression to
19

---

see that
(A++2)/44
(k+2)/4
2Tu
2TT
w²
Σ
1 1
cos
a a bcos
2n
1 4Tb
k + 2
2
(k 2)
(hi + 2)
a=0
(k+2)/4
u²²
1mkk ..
I 2m
(#+2)²
(k: 2)2
a=0
Therefore conclude that
A++1
cos
2T
a
cos
2Tu
&
I a +4
(k+2)/1
Σ
u2
-
2):
u2
1:
2
k
+
k + 2
(k + 2)2
h: + 2
4=0
u=D
Finally, applying Proposition A.7 with k + 2 and = 4x kb we can upper bound the above quantity by:
at + 4T²
4(4kkb)3/2 + 4embk(k 2)
<a +
(4kb)3/2
ebk2
which concludes the proof.
Proposition A.7. Let m > 0 and a O. Then
Σ
m/d
2
VT
+
m
m
3/2
cam
u=D
Proof. Let f: R >> IR given by x + x e az2 then given by:
Note that the sum we are attempting to bound is
m/4
m
Note also that f has maximum To otherwise. In particular
Thus f is increasing for zo and decreasing
Va
m/4
mp
m/4 Σ
(m) m
= LL+U.
m
m
m
m
==
[
Jo Ing f(x)dx. Similarly U is an
then corresponds to lower Riemman sum for and < upper Riemman sum for f and U <
1/4-- Eilli (xx)d.. Therefore we have
m/4
1/4-1/m
Izal+1
x2 20-oxx azt de +
f(x)dx
[2gl-1 1
J0
22 e
az
+ m
max (xx)
J0
VT
+
3/2
eam
claimed.
Proposition A.8. The following inequality holds for any 1. [0. 1/4]:
1 1-2(T)) < cos 2tt 4nt
20

---

Proof. For the lower bound we start from the fact that for any 2 O it is well known that
sin 2T S 2T...
Integrating this inequality from [0, 4) we have that S0 sin 2mx S at? Since So sin 2n 25 (1 cos 2rt) the lower bound follows.
For the upper bound proceed in similar fashion. By the fact that sin 2x is concave for I E [0, 1/4] we have that
sin 2 sin ( 4x) 0 4x 2) 2 (1 4z) sin + 4x sin 4x.
Again integrating the above inequality from 0 to f. we have 1-cas 2nr 2 212.
2x
A.4 Proof of Theorem 3.4
Proof. The proof follows the same argument of the proof used in 3.3 where see that, in view of the factorization in Equation we may bound the individual expected advantage as:
(M, -
E
P((x = s|x) P(Zx 1|x)]
But from Lemma A.3 it follows that this can be bounded by
0 (p(1 (((1-)) V (11 21)22/22//22 (1-
22)*
13/2k +
k2/2
13/2222
Now, since (1 - 2212 < for k 2 log
we upper bound accordingly the two terms
involving (1 24)x and the result follows.
A.5 Tail distribution of the attack advatange
We are also interested in the tail of the distribution of the attack advantage, that is, the tail of the difference between
fi(x) sup Autames
P y-Dø Uniform([m]] coins of M
(Xxx,
and
f2(x) = sup Ausitione
P y~D Un-unifomm [m]) coins M
(Auniformod (x, (Lx,)) =3:
Specifically, we define
H.Adv(M,D.0)
TP X~Dx
(fi(x) - 52(x)) 0).
viewed as function of 0 e [0, 1]. which call the High Probability attack Advantage (at level 0). This is simply a high-probability version of (A, over the generation of x. A similar high-probability version can be defined for the individual version the attack advantage.
We begin by observing that in the special case of MRR. we have IEAdv, (MRRR. D, 21) ) fi(x) fx(x), that the high probability bound involved in the computation of HPAdv(MRR. D. is a direct consequence of the tail properties of the function (zx)) P(y = 1 x1) as applied to the expression for IEAdv1, (MRR. D, x1) in Theorem A.17 Thus, for MRR. the connection from IEAdy to HPAdy is immediate.
We continue with studying HPAdv for MLLP We have the following bound.
21

---

Theorem A.9. Under the same assumptions and notation as in Theorem 3.3 (main body) there are universal constants c₁, C2 such that, for k 12(1pp),
HPAdv MMLes D. L S (k+1)e
In order prove this theorem, we first need ancillary results related Poisson Binomial distributions. We denote Poisson Binomial distribution with parameters {?....., .T.} by PBin(?n...... nkk) Lemma A.10. Let 8, ~ P me), ( PBin(1.....,.)) Th), where m....., 1/ E [0. 1] are such that
Σ 7x 71) 2 1.
Then
P(E 8) - P(
= 1)
9
E,
=)
E 2 ni m))
Proof. We will use the following distribution to approximate Poisson Binomial distributions.
Definition A.11. (28) We say that an integer random variable Y distributed according to the translated Poisson distribution with parameters μ and o², denoted TP(u, o²)), if and only if can be written as
+u+ o² + Z,
where Z is random variable distributed according to Poisson(o + {u- o2))), being {u- o2 the fractional part of μ o², and [| + o²| the integer part of μ + o
Let us then define two random variables and ((1), Variable TP(μ4, 0²) with 1= - and σ² = = (1 77), while r() is TP( of), where μl = Σド Th and of Σド= 77(1 1,).
Let drv denote the total variation distance. We can write
((E(1) s) - P(E()) 1)
P(I()) = -P(E(1) = 1)
E,
P(E 5)
s)
PP =
k Σ
P( = s) -P(I(1) s - 1)
==0
*
Σ
P(E(4) 8) - P(T $) 8) Σ
P(T = s) -(( s-1)
==
==0
Σ P(T()) = -P((()) =8-11 -1)
(10)
drv (Ev
Σ
P(T = 8) -P((() = = - 1) +
Ei n mh) +2 V E 11 71) +2
Σ 1T(1 - m7)
( (m))
(11)
Σ
P([ = 5) - -P(((L) = --1) 1)
==0
k
3
3
+
P(T 5) P(T()) - 1)
V
V
(12)
22

---

where (TO) follows from the triangle inequality, follows from the overapproximation
follows from Lemma A.12 below, and 12
E of - - +
+2 1= ne(1 176)
3
E (7(11 17s))
17:(1 -7:))
VE. k
Dimi T7: 17:)
the latter inequality exploiting the condition Σi Till Thi) 2 1.
Lemma A.12. /128), see (3.4) therein] Let J1, , ,& be independent random Bernoulli with parameters .P.. Then
k Σ 1=
V 1 Po -ps) +2
dιv
J4, TP(P,
<
Σt Pi(1 -ps)
where μ Ex= Ps and o² E Pi(1 p.).
We recall a lemma which will be useful upper bound the last term in (22)
Lemma A.13. [6] For p1,22 E IR and of of E RR such that [ud
o
S
[u2 - o02). it holds that
drv (n((TP(m ot), TP(12, oB)) S | u2l
|o
o
+1
+
of
We will need the following technical lemma as well. Lemma A.14. For μ E R and of, of E R+, us define X1 TP(,, and X₂ TP(p+1, 1,3)) Then
PP( 1) = PPx2 ()
for all l E Z.
Proof of Lemma A. One has to observe that Translated Poisson distribution equivalent to Poisson distribution with parameter 8 where d μ 7 and [M o²J, but it is shifted by
Moreover, note that y + = 1 + o² ], thus + 1 / - + 1. This observation implies the claim with μ 1.
We continue by using both Lemma A.13 and Lemma A.14 14 write
Define (22 ~ TP(11 + 1,of). We can
P(T 5) -( 1)
Σ
P(T -P(((2) =s)
drv TP( 0²), TP(p1 + 1, of)
11 11 0² of
<
σ²
(from Lemma A.13
m
m (1
m) +1 o²
0
3
Vo
the latter inequality using again the condition Piecing together gives
Σ
11((1 - mh)) 2 1.
((E 1
6 3
< 9
E,
<
PC = 8)
Vo
Vol
V0
This concludes the proof.
23

---

With these results handy, we are ready to prove Theorem A.9 defined in the main body.
Recall the functions (x) and f2(x)
Proof of Theorem A.9
Let Σ = E/=1 Dj. From Lemma A. 1
we see that
fx() =
Dylk
min {P(ys x, xx x bE(0,1)
and
1 Σ min (n(x)), 1_)()))
fa(x)
so that
k
f1(x) f2(x) =
1
Σ
1 BynD
min be
{P( = 1 2 [x
1=1
k
1
Im(x))
(x = E, Σ,x)
k
where in the inequality we have again used 4
But, for any given E 1..1..... k}.
Ply = 1 1 = x) = Ply: = 1 x P = 8 y: 1,x)
P( 8 x)
=n(x,) P(
xx)
P(Σ s x
POE(
where ((-1) = Ex 2.ggm1..y:
Hence
P(E(-1) s|x) P(E(-() 1|x)
fi(x) - fx(x)= S k E (1a:)(1-
|x]
(13)
P(E s |
where (conditioned on x) is distributed as PBin(y(z1))..... Set for brevity μ = [[)(()) ((x)), and introduce the short-hand notation
Cg.1 (x(((xx) =
Σ Jú
(1=))(1n(3))) S (k 1)μ 8
for some 3 [0, (k: 1)1x) be specified. In the above (-i) denotes x with its i-th item x; removed.
We have
s|| -PE((- = x)
P(E(-)) s s|xx]
7(x:)(1 (E
|x
PPE s x)
(C..n(=:((1-<2))))) (P) s x) PPE( - = 1/x)
P x)
P () s x) PP i)
[x)
+1 (1 - -1- (x;)))
x
P = x
P( = =( P(E(
1
x)
$ Co, + (1 (1- Co.) -
|x
P x)
24

---

since
P x P( () = x)
71 (x:))),
x S1.
P( x)
every and every realization x. On the other hand, a closer look at term
P(E
- -P(E(-i) 1
(1 -1- (L,C
F(2 8 x)
reveals that we are a position to apply Lemma A.10 This allows us to conclude that this expectation upper bounded by
9(1 C3.i)
k E (
for every realization of x. Using the definition of C3,t the above can be further upper bounded by
V(h 118-1166 11-
Putting together, we have obtained
Cg.s 9t)(x;) - (((1))
f1(x) - f2(x)=
h 1=1
V(x: 1)11
92 n1z;) (1 - (x:3))
Ca. +
l kV (k: 1)px -
for every x. Now, from the standard Bernstein inequality
Px PXDDx (Co.s = 0 vi 2 - ke 2ka 1276
and
Σ ((.)((1-(zz)) S ky + 3
Fx~Dx
2 1 - 26x4278
for every B > 0. This yields
9(kp + +
Fx~Dx
fi(x) f2(x) >
(k: ()+ 2641270
(14)
kv (k - 1)Fx
holding for 0 < 3 < 1k-1)p
One can easily see that choosing 3 (k- 1)u/2 yields, when k 1(11u),
PxwDx (fi(x) - f2(x) = 22 = ) < ho ((K))
which concludes the proof.
Remark A.15. The analysis contained above also allows us to provide bounds on the additive advantage that are fully conditional on x (21,...,2ml) For instance, combining Lemma A.10 with Eq. 13), one can easily derive bound of the form
((x;)(1 - 17(x,))
fi(x) - f2(x) = K
Σ Djs4 ((1,)(1 m vı(x;))
Then, in order for this bound to be of the form 1/Vk, we need to make further assumptions on the function ø P 1 1|x), the most obvious one being P(y 1|z) E (0, (bounded away from
and 1) for all r.
'The condition > " 11 nx) therein is implied by (x 0. which is equivalent 1)p 2 1 + 3. This, in turn, given our choice will read as (11/p). NNote that we are upper bounding the second moments of the random variables (yxx) - n)(x)) with their first moment μ4, since the variables 17(2:)(1 n)xx)) are in 1/4].
25

---

A.6 The advantage of RR is independent of the number of examples
Lemma A.16. For all data distributions D, all 24, and all datasets S of size m, IEAdv(MRR x4) is independent of m, and so is EAdv(MRx. D).
Proof. Fix any m, any 2i, and any data distribution D. Then, by Lemma A.1
IEAR D, min(n(a;),, 1 7({x)))
(15)
E
min P (x((-0)y(00))
(yi MRR (x(-0)y(-0)
PP
(ui 0 x, MRR((,))))
The first term already has no dependence on m. We focus on the second term.
The key to this proof is that noisy label RT((y)) ij is independent of the other true labels yj. + i. Thus, we have
P(y: x, MRR( y)) P(y: Mx) = P(u 1 x,, x,, MRR
Applying this to (T)..
we have
E Vi Danra
min
P
(yi x, MRRR((x, y)),
(x (y: 0 x,, MxR
P
(x(-1) (
E MeDDyle
min
Ply:
wi, MRR (r.; wc)), Ply: y: wi, MRR (r.; vc))} di
Plugging this back into (15) gives us EAdv, (MRR. D) as desired. Taking the expectation over I2 Dx completes the proof of the second claim.
A.7 Proof of Theorem 3.5
We prove a more verbose version Theorem 3.3 which includes the optimal adversary:
Theorem A.17. For any data distribution D the individual expected attack advantage for randomized response with privacy parameter Itec is
IEAdv(MeR D,x1) 1 I))1(((=1)) E [-,1-m]}
The optimal adversary maximizing IEAdv, (MRR, D,
1, if (f1()) 1-- π
A²
if())) <
yi, otherwise.
In words, upon receiving 31, the optimal attacker A" predicts the associated label y1 as the noisy
label ú1 if the distribution 'D contains enough uncertainty about y1 (the condition 77(21) E [Ir, 1 holds) given the extra noise level æ injected. Otherwise, predicts deterministically (as y1 is indeed close to being deterministic when 17(x1) & [T, TJ).
Proof. First we characterize the optimal attacker for which the individual expected advantage is maximal. The Bayes optimal decision which minimizes the loss I[A(21. v1) y} conditioned on ø1 and y1 is
A' vi) L(1P(y1 1|21, 51) > P(y1 0/ 01)
which can be written as
Ply1 1x1, V1)
P( 91 = 1, x P(1
(16)
Ply 0 01.1,,00 21)
P(ū 91 = 0, x1) P(vi =
Assume that vi in which case (16) becomes
n((1)
(17)
π
1)(1))
26

---

which is true whenever n(21) > x, and on the other hand, if n(21) < then (T7) does not hold anymore, thus ( 91 0. similar argument holds for 1/1 0: The Bayes optimal decision A' vi) = 1 if and only if 17(11) > и. Putting together, and noting that I 1/2, this implies that the optimal attack is
1.
((1) 1 π
A (z1 01)
O, if (())) < क
Vi, otherwise
To compute the reconstruction advantage of optimal attacker A", may decompose the feature set into parts as
G( (ar (111) E 1-,1-=]]
and its complement set G GO(T). It clear the advantage of the optimal attacker A" restricted to G (*)) is 0 since Ti gives no extra information on when 21 E GO (T). that is, the value of A (211 is
independent of 5n when æ1 E GO (T)) On the other hand, the advantage of A for any x1 G( is
(1 (1-m) .) (1 - min (m(1),, - 7((1)) = min (1)21), 1 - n(<1)} - -
since MRR reveals the true label with probability - while the attack utility (conditioned on xT)
of the uninformed attacker min(m((1), 1, 7(11)) This concludes the proof.
B Proofs for Section 3.2
B.1 Proof of Theorem 3.7
Proof. Consider the difference of log-odds ratio (M, 2, where -MIP(x,y)
Ei= Vi is the output of the aggregation PET. Since y is independent x, we can write
D, In Py 1 1
In Ply 1) Plyl 0)
Plyl = 0
In P
In 1 - 1-p
In z(1 11
(1-z)p*
where we used the fact that, since k2 a binomial random variable, P(y = 1 = 2, independent of p. From the standard Bernstein inequality have, with probability 2 8,
p - B 2 B
where
2p(1 p) (n(1/))
2
B = p, p.
+ In (1/0))
k
3k
Since = + In - monotonically increasing in = E [0, 1}. this yields
(1 11-p+ B)p = In () (1))
B
(p + B) - p)
< ((2) < In
= In 1
(1 (1-p+ B)p
(1 (1-p- B)p
(1 - B)p
with the same probability. The condition A implies [1-p+Byp < $. as well as BI-
32 lm(18)
(1-2) implies 2B S p p², which in turn
B
O. We further bound the right-most side through
In(1 + x)) < x for all 0, and the left-most side via In(1 x) - x(In 2) for x E [0, 1/2]. This
gives
Bln2
B
<I( S
(1 11-pt p B)p which, after further overapproximations, allows us write
(1 (1-p-1 B)p
B In
[[()] < [1
B)p
Next, the condition 2B S p- - D2 implies (1 - - B) (1
p)/2 so that, overall,
(v In(1/8)
[(<))] < (k. p. () 2)
p
r(1 - p)k
with probability at least 1-8. 8. This concludes the proof.
27

---

C Experimental Setup for Section and Further Experimental Results
Datasets. We conduct our experiments the following datasets:
KDD2012: We use the click prediction data from the KDD Cup 2012, Track [3] with the feature processing performed in (3 The learning task for this data is to predict the click through rate for an advertisement based on a number of features related to the advertisement, the page that appears on, and the user viewing it. There are 11 categorical features that are each one-hot encoded, resulting in a sparse feature vector with 11 non-zero entries 54,686,452 dimensions. The label for the example is I if the ad was clicked, and 0 otherwise.
Higgs: We also use the Higgs dataset 44. which a binary classification dataset where the goal is to distinguish between a signal process that produces Higgs bosons, and a background process which does not. The dataset has 28 real-valued features, which are mix of kinematic properties measured by particle detectors and hand-crafted high level features designed by physicists. The dataset consists of 1 11,000,000 000 examples produced via Monte Carlo simulation. We use the first 10,000 examples as our testing data, and the remaining examples for training.
Model Architectures.
Next, describe the models we use for each dataset. We use the same model architecture regardless which PET has been used to privatize the labels.
KDD2012 Model: The model we use for KDD2012 is a deep embedding network. We reduce the dimension of each example from 54,686,452 dimensions to 500,000 dimensions by hashing feature indices. Each hashed feature index is associated with a learned embedding vector in IR.00 and the representation vector for an example is the sum of the learned embeddings for each of its non-zero hashed feature indices. This representation vector is passed through two dense layers with 100 and 50 units, respectively, and ReLU activation functions. The final output is a single unit with sigmoid activation that is interpreted the click probability for each example.
Higgs Model: For the Higgs data, we do no feature pre-processing We use a fully connected feed forward neural network with 4 hidden layers all with 300 units and ReLU activation. The final output a single unit with sigmoid activation that interpreted as the probability that the example has the positive class.
Training Setup. When training a model on the output of any PET, always use minibatch gradient descent together with the Adam optimizer (24] PET-specific training details are presented in the following paragraphs.
Training with Randomized Response. In our experiments we found that the bias in randomized response can affect prediction accuracy for the model trained on these labels, so we post-process the RR output to remove the bias introduced (see for example [19, Equation (7) therein).
Let f: + R be any function (for example the gradient) of a label, and let y E {0, 1). For plain RR,
= e¹ -1
1
E[f(RR(y))
f(()
e e++1 (f(0)+ f(1).
c- +1
Thus,
c +1 S(RR()) f(y) E
1 (1() -())
Therefore, we protessocess the output of RR to obtain an unbiased estimate of f(y) for any function f. This has no effect on the advantage, however it does help the accuracy substantially. We use this debiasing procedure to obtain unbiased estimate of the binary cross-entropy loss of the model, and perform minibatch gradient descent on the estimated loss. In all of our figures, we use "RR" to denote this debiased version of the mechanism.
Training with LLP. For LLP we use minibatch gradient descent to optimize the Empirical Pro- portion Risk defined in Section 2 We use the binary cross-entropy loss to compare the predicted label proportion against the observed label proportion. As discussed in Appendix [ since the binary cross-entropy loss is proper loss, the minimizer of the population-level proportion risk for cross-entropy loss is also minimizer of the population- cross-entropy loss, as long as the Bayes optimal classifier can be represented by the model architecture.
28

---

Training with LLP+Lap. LLP+Lap is parametrized by two parameters, k E {1, (1.2.... and >> 0. For each bag B, the mechanism discloses a, + Z. where a; is the label proportion in that bag, and Z: ~ Lap( ke), is an independent zero-mean Laplace random variable with parameter xe. that is, with variance 3ă,2 Theorem D.2 shows that for any minibatch of data, the expected gradient of the proportion matching risk is unaffected by adding mean-zero zero noise to the label proportion. Therefore, using Proportion Matching train with LLP+Lap is similar to training with LLP,, except the variance of each gradient step is increased.
Training with LLP+Geom. LLP+Geom also has parameters, At E [1,2,...] and 0, but Z, is replaced by two-sided Geometric random variable, where Z, -.- and 2, and 2, geometric distribution with probability of success 1 - e_c. The value a; + Zz is then clipped to [0. 1]. It is not hard to see that, for every given e, LLP+Geem with parameters RR with parameter c.
and e coincides with
Unlike LLP+Laplace, the clipped noisy label proportion is not an unbiased estimate of the bag's true label proportion. We post-process the output of L..P+Geom to obtain unbiased estimates of the bag's s label proportion. In particular, let o; be the true label proportion for a bag, O
(muise) a; + Z; be the
unclipped noisy proportion, and a; (clip) clip(a, (aoos [0, 1J) be the clipped noisy proportion. Then, using the memoryless property of the Geometric distribution, we have that
(moise)
(clip)
if a (elip)
E (0, 1)
E B|a
((oiis)))
(noisc)
a;
(clip))
1- -11 1 T-e 1)
if a; (elip) = 0
a (clip) =
When training with LLP+Geom, we replace the clipped label proportion by Elax aa before (noisc) is an unbiased estimate of at so is the computing the proportion matching loss. Since a: conditional expectation. After this debiasing, Theorem D.2 guarantees that the expected gradient of the proportion matching risk is the same as if the true label proportion had been used. follows that using Proportion Matching to train with LLP+Geom with proportion debiasing is similar to training with LLP except with higher variance.
(Clip)
AUC vs Advantage Experimental Setup. For all PETs, we train models to minimize the binary cross-entropy loss. For RR, we use privacy parameters in {2 22-4, 2-2 ..... .2.... J. for LLP we use bag sizes k in {2", 2 29), and for LLP+Laplace and LLP+Geom we use all combinations of E and l from the same sets. For every PET and every value of their privacy parameters, we train the model S
with each learning rate in {10-6, 5- 10 10- 10-4.0400000 5 10-4, 10 5 10 10-3,10-2 ,10-2). Finally, for each combination of privacy parameter and learning rate, we train the model 10 times (each trial corresponds to different model initialization and data shuffling, and RR noise). For each privacy parameter, we report the mean AUC of the learning rate with the highest mean AUC.
Estimating Attack Advantage. The attack advantage of the optimal attacker is estimated and reported for every PET with various parameters. The optimal attacker and its advantage have been characterized for RR as well as for LLP, in Lemma I and Theorem A.17] respectively. Crucially, notice that the advantage can be easily calculated with knowledge of the parameters of each PET (label flipping probability or the bag size), and the class conditional distribution 77(x) or at least an accurate estimate of it. We considered two estimates the class conditionals: one based on Deep Neural Networks (DNN) as described above, and one based of k-Nearest Neighbors (ANN). The ANN estimator can produce accurate estimates for class conditional distributions in the large-scale data regimes, due to its strong consistency properties that has been studied in the 70s and 80s, and that became the part of Machine Learning folklore. DNNs can also produce accurate estimates the training process and architecture is tuned carefully enough. We found that these two approaches result in very similar results on our large scale benchmark datasets, therefore we relied on the estimate provided by the DNN, and we estimated the attack advantage of the optimal attacker based on the output score of the DNN.
Remark. It is known that when trained with event-level (i.e., non-private) labels, DNNs are not guaranteed to give rise to calibrated classifiers, which is important for estimating the probabilities involved in the definition of attack advantage, while a ANN is typically calibrated. Yet, since
29

---

LUFT
koz, 055 =
L1F4
Lop
Figure 4: Prior-posterins scatter plots for LLP+Geom and LLP+Lap two synthetic datasets and the two real-world datasets. The two synthetic datasets have been generated by drawing n)() from a Beta(2,30) distribution and uniform distribution on [0, 1]. The colors of the dots correspond to different parameter values for the PETs. For each bag size and distribution, we did 1000 independent runs. The further point is from the dotted line, the more is revealed about its label as a result of the PET.
epi-0.0675
KDG12
Goom 03-00.23
Geom ops-0.125
Goom op5-0.25
Geom eps-0.25
Coom cp5-0.5
Geom 655-0.5
0.0
A0I
4.75
(eem 4.a
Gaom epv-4.0
0.70
Gaum-p--8.
Gearn spa-5.0
Ccom 16.0
Goom ess- s2.-16.00
95th fercendle cattip Acvantage
98th Percentie plicaiic Advanaage
op.-0.0525
KD012
Geom ep5-0.0625
Geam 4p:=0.125
Geom epss0.12 125
1.55
Geom ept=0.25
Geom apsn0.25
Genth 05
Goor ops-0.5
3.50
4p-100
4.79
Goom 4p5=2.0
Geom e55-2.0
Ceom 4,0-4.0
Geom ep5-4.0
Goom 8,0
Geom 635-8.0
Goom 16.016.0
Geomn 16.0
8.0
1pa-12.
LLP
830
6.55
AR
AR
Experted Additive Advantiage
Espected Addiuve Advantage
Figure 5: Privacy utility tradeoff curves for the various PETs the Higgs (left) and KDD12 (right) datasets. Utility is measured by AUC on test set, while privacy either the additive measure (bottom row) the 98th-percentile of the multiplicative measure (so as rule out the infinite multiplicative advantage cases that can occur for LLP). Each point corresponds to a setting of the privacy parameter for the PET (e for RR, for LLP, and both for LLP+Geom). The x-coordinate is the advantage (either additive or multiplicative) value for that PET, while the y-coordinate is the test AUC of model trained from the output of that PET. The AUC of the model trained without a PET roughly corresponds to the top value achieved by these curves. This plot is similar to Figure 3 except that the curves for the L.L.+Geom PET correspond to a fixed value of c, rather than a fixed value of k.
observed in our initial experiments that the two learning methods resulted in similar overall outcomes, decided go with DNNs as the underlying classifier for estimating the behavior of the optimal attacker.
Further experimental results omitted from the main text. Figure 4 contains scatter plots for LLP+Lap in addition to LLP+Geom for comparison. The two groups of scatter plots look very similar on each dataset. 5 shows the privacy-vs-utiligy plots (the data is identical to Figure B except in this case, the curves for the LLP+Geom PET correspond to a fixed value of with the bag size k varying.
Computational Resources. We conduct our experiments on cluster of virtual machines each equipped with p100 GPU, 16 core CPU, and 16GB of memory. Each training run on Higgs takes approximately 10 minutes, and each training KDD12 takes approximately 20 hours.
30

---

D PROPMATCH with Noisy Label Proportions
In this appendix we argue that the standard PROPMATCH algorithm is still an effective learning algorithm for the LLP+Lap PET (henceforth denoted MLap.LL.).. Recall that PROPMATCH generally learns by using stochastic gradient descent (SGD) to minimize the empirical proportion matching loss. Our result below shows that the expected value of the gradient of proportion matching loss is the same whether Laplace noise is added to the label proportion or not. other words, the expected trajectory of SGD for PROPMATCH when using MLap-LLP is the same for all values of e, including e <= oc, which corresponds to the special case of MMLP.. In fact, the main way that decreasing the value of (resulting in stronger differential privacy guarantees) affects utility is the increased variance of the gradients. The following result characterizes how much the variance increases compared to the case where
(or equivalently, compared PROPMATCH run with MMLP).
To analyze PROPMATCH, we require a few properties of the loss E R x - and the noise distribution. First, the loss is proper, which means that for every real-valued random variable A, the function (p) - [E((p A)) has a unique minimizer at μ = E(.A). We also assume that E(p, y) is 8p ((, y) = any + hp. where ap. bp may depend on p but not y. These conditions are satisfied by the cross entropy (or logistic) loss (p. y log(p) - (1 ---)) v) log(1 - (where p E [0, 1J) and the squared error E(p, v) (p y)².
differentiable in p. and that its derivative is affine in y. that is
Finally, we assume that the noise mechanism operates on a bag of k examples for some E N (possibly k- = 1). Given the proportion a of positive examples in the bag, it releases á = a + Za where E La || = 0 for every fixed a E 1/k, ................................ 13. This condition satisfied by LLP (since adds no noise). LLP+Lap (since Laplace noise is mean O), and the debiased versions of randomized response and L.e.+ described in Appendix C
Given a class of predictors H. of predictors h that map feature vectors to [0, 1]. we can define the problem of minimizing the population-level noisy proportion-matching loss for distribution D, defined via the choice of a bag B of k labeled examples drawn from D:
(eL
1 h(x), ã DEB
min EE NEH B,a. J:
e
This differs from the loss studied in 13 only in that we allow the label proportion to be perturbed.
The PROPMATCH algorithm essentially minimizes this loss.
Theorem D.1. Let B be random bag of size k l
be a loss function, and M
be a mechanism for releasing the label proportions with M(a)= a + Za, where |aZa|a] = 0 for all a. Suppose H. contains a predictor h- that matches the true label probabilities in D (i.e.
he (x) = Foly = 1/x). If f is proper (defined above), then he" is a minimizer of the population-level noisy proportion- satisfy P ((.))) (h' (x)) = h² (x)) 1.
loss on DD. It is essentially unique, in that any other minimizer H'' must
Theorem D.2. Let B be random bag of size k. L RXE + R U [oc) be a loss function, and M be a mechanism for releasing the label proportions with M(a) = ā = a + Zan where E[Za = 0 for all a. Suppose that a E'. y) is affine in y. Öp
For a predictor hg E H (parametrized by 0) denote by (B) = 5/ Emer (x its average prediction over B. We have
E al (B). E Vo (b)
(18)
and furthermore
E.
E (Vo((ho(B)) + E _ 1 Vol(ho( [VVol (ho()),
E (VV []] + max Var (Za))
E la Vol(ho(B),
(19)
That is, for nice loss functions like the logistic and square loss we can write the variance of the noisy I.P gradient as the sum of two terms: the variance of the L.-d- estimate of the proportion- matching loss, and a noise term that scales roughly the variance of Z. For Laplace noise, this
31

---

variance is E-zZ. For Geometric noise, the variance is upper bounded above by kI(1---1j (which is always smaller than the Laplace variance, most noticeably for large c). For small values of k; this upper bound is loose (because clipping and debiasing reduces the overall variance). For example, with randomized response (which is the same as LLP+Geom with k = 1), the variance is just E'41"
2
2e
Analyzing this formula helps us understand the performance of the noisy variants of LLP. Let us compare LLP+Geem with bag size k to averaging randomized response estimates over & separate examples. Suppose we fix с and let increase. There are three effects play: (1) the noise added for privacy is lower for LLP+Geom (variance 1 1/k² versus 1/k); (2) the bias of the gradient estimator is higher for LLP+Geom, since we are estimating the gradient of the proportion propotion-matcching loss and not necessarily the true gradient; (3) the variance due to sampling is about the same in both cases, about 1/k.
We thus get classic bias-variance tradeoff. As a thought experiment, consider what happens when e very small, and almost all the error comes from the added noise. In that case, setting & bit larger than will help, since the bias introduced will be smaller than the reduction in noise. However, there a point of diminishing returns, least when the proportion-matciin optimum is different from the true optimum (that is, when the model cannot express the Bayes-optimal predictor). Looking at the experiments with the Higgs data set, we see a muted version of this effect: for small values of c, there is no real difference in the performance of LLP+Geom for & E f1, 2, 4), but larger k introduce a real penalty. For larger values of (over 1) on Higgs, and values 6 on KDD12, the dropoff occurs already for k =
This analysis suggests that the advantages of LLP+Geom over RR will be dataset-dependent, and noticeable only for small values of e.
Proof of Theorem D.7 This proof the same as the argument in Thm 3.2]. Fix some bag B of examples, and take expectation over the sampling of their labels to get label proportion a and its noisy variant à. Because the loss is proper, the unique minimizer of the proportion matching loss is given by the predictions of h"
arg min E(p, a) = B(a) = B(a) (x).
P 0,
This is true for every bag B, and thus in expectation over the choice of B. Furthermore, this loss is unique since the indicator functions bags form a spanning set for the indicators for the support of D. If h # h" with nonzero probability, then the bag-level predictions of h will differ from those of h with nonzero probability.
Proof of Theorem D.2
1 (., Using the Let (p,,)) v) of epp. any bp. where ap
chain rule and the fact that is affine, we get:
o (ho(B), ((ha(B),a)Vahheee
(E(ho(B)) + (B) (Bho(B) Vol(ho(B)),)) + Z aho V Vgha(() = Vol(ho(B), + Za Da V
Since the noise is unbiased for every the second term above is 0 in expectation for every pair (B, a). This proves that the estimator is unbiased (Equation (18). To analyze its variance, note that the unbiasedness of â means that the two terms decorrelated, and we sum their convariances:
Covar (Vo((ho(B)) + Za Ba Vol(ha(B)..))
Covar oVol(ho (B), a:) + Covar (Za do (o)(h)(B)..))
+ E (5) da
a Vol(ho (B),
Covar (Vol(ho a:) + Covar (Za da Vol(ho
The expected squared norm of random vector is the trace of its covariance. Thus, the expres- sion above gives us the equality in Equation (88). The final inequality follows again from decor- relation: by conditioning on the pair (B, a). we pull out B|Z2] from the outer product of
32

---

Za 2 Vol(ho with itself. Taking the trace (to get the expected square norm), we can use da the fact that |/ (VoE(ho(B) a)ll is nonegative, to replace E[Ză] with an upper bound that holds for all a. This yields the final inequality in Equation (9)). as desired.
We have analyzed PROPMATCH in this section since it is the algorithm used in our experiments. Similar results hold for other LLP algorithms, like EASYLLP [12], though we do not work those out here.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main contribution of the paper clearly stated in the abstract and introduc-
tion, and reflected in the technical and experimental sections (Section 3, 4, and associated appendices).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in Section 5.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
34

---

Answer:
[Yes]
Justification:
Full proofs of all our theoretical results are given in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
All our experimental results are reproducible. Details on our experimental setting (model architecture, hyperparameter tuning, etc.) which are omitted from the main body of the paper are given in Appendix C. The datasets which we experimented with are publicly available and we have released the code we used to run experiments.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
35

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The datasets we operated are publicly available. We released the code and made available instructions on how to run our experiments at httttt::/ggtttttt com/ peg.reeeerrrcooooollrrrraaaaeeee
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. ec/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ htapss.cc/publicguudeeess
wtt.ibbmmssooooooooiy. for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Such details are partly given in Section 4 and partly in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We mention in Section and in Appendix C that all our results are averaged across 5 or 10 repetitions (depending the dataset). The associated standard errors are quite small, and still allow us to statistically tell apart the different curves when they are not overlapping. We discuss the standard errors in Section 4 paragraph "Estimating Class conditionals for advantage and PET utility".
Guidelines:
The answer NA means that the paper does not include experiments.
36

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We mention computational resources and associated wall-clock running times in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We reviewed the three main categories of concerns in the Code of Ethics (harms of the process, societal impact, and impact mitigation). We believe we have complied with the spirit and letter of the requirements
each category. In particular, no human subjects research was involved in this project, and the data sets we use are both open-source, standard ML data sets which not come with privacy or intellectual property concerns.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
37

---

Answer: [No].
Justification: This work aims to advance the science of awwar machine learning. As such, its goal is to get the benefits of training models sensitive data sets while measuring and mitigating harmful effects on individuals. Putting protections such as the ones we develop into real-world use is delicate since privacy protections can, in addition helping data contributors, have side effects such as limiting data access and model quality for sparse sub-populations. These issues, while important, are not specific our work and lie outside the scope of the paper. That is the main reason why we do not explicitly discuss in the paper the societal impact of this work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deg.lymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA].
Justification:
We don't see any such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA].
38

---

Justification:
We don't 't rely on such assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssiippssiiii thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification:
No such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
39

---

Answer: [NA]
Justification:
No such experiments.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
40


Reviews:
[{"review_id": "tgnrjYioU9", "reviewer": "Reviewer_enWp", "summary": "This paper proposes two reconstruction advantage metrics to audit label privatization mechanisms. Unlike differentially private (DP) auditing techniques, which focus on worst-case guarantees, the authors of this work focus on distributional guarantees. Concretely, the authors assume the adversary has knowledge of the data distribution $\\mathcal{D}$ over $\\mathcal{X} \\times \\mathcal{Y}$ , either completely or approximately through learning on data. This allows the adversary the leverage correlations in the data, which are unknown to the mechanism, to augment their attack. Consequently, the attack advantage metrics proposed in this work measure the label reidentification risk that can be attributed to the mechanism rather than to correlations between the features and labels inherent to the distribution $\\mathcal{D}$. Moreover, these metrics apply to both DP mechanisms and deterministic mechanisms commonly used in practice. \n\nThe first metric investigated in the paper is the additive attack advantage, which was introduced in the context of label inference attacks by Wu et al. At a high level, this metric measures the difference between the expected accuracy of two Bayes optimal adversaries: one that can see the output of the mechanism and one that cannot. Notably, the expectation is taken over both the data distribution $\\mathcal{D}$ and coin flips in the mechanism. Authors derive various analytical bounds that track how this measure changes under different correlation assumptions and mechanisms (Theorem 3.3, 3.4, 3.5), and demonstrate the privacy-utility trade-off using this metric for various DP mechanisms and a non-DP mechanism (Figure 3).\n\nSince the first metric measures average-case risk, it does not capture unlikely high-disclosure events. The second metric, the multiplicative attack advantage, is introduced to remedy this shortcoming. At a high level, this metric measures the difference of log odds ratio between the adversary's prior and posterior probability of observing two different labels. This metric can be written as $\\\\log \\\\frac{\\text{Pr}(\\mathcal{M}(\\mathbf{x}, \\mathbf{y} ) = z \\mid y_i = 1, \\mathbf{x})}{\\text{Pr}(\\mathcal{M}(\\mathbf{x}, \\mathbf{y} ) = z \\mid y_i = 0, \\mathbf{x})}$, and is therefore analogous to the ''log likelihood ratio'' that is commonly characterized in the DP literature. In contrast to the DP literature, the probability in the likelihood ratio here is taken over both the data distribution $\\mathcal{D}$ and coin flips in the mechanism. Authors provide a high probability bound for this second metric for a often utilized deterministic mechanism (Theorem 3.7), and demonstrate the privacy-utility trade-off using this metric for various DP mechanisms and a non-DP mechanism (Figure 3). Further notions of attack advantage are explored in Appendix A.5.  \n\nAn interesting result from this work is the empirical observation that learning with deterministic aggregate labels is harder than learning from randomly perturbed labels. In other words, randomized response had the best privacy-utility trade-off out of all the investigated mechanisms.", "questions": "$\\textbf{Questions:}$ \n\n1. Figure 1 plots the prior and posterior distribution for LLP, RR and LLP+Geom. While I have a guess for how these posterior probabilities were calculated (e.g. using the ''likelihood'' $\\text{Pr}(\\mathcal{M}(\\mathbf{x}, \\mathbf{y} ) = z \\mid y_i = 1, \\mathbf{x})$ and the prior $\\text{Pr}(y_i = 1 \\mid \\mathbf{x})$), the paper is not clear how the posterior probabilities were calculated, particularly for LLP+Geom and LLP+Lap. Could the authors please elaborate on how this was done? \n\n$\\textbf{Suggestions:}$\n\n1. Given how important the spindles are for the discussion in the experimental section, the remark \"Note that a spindle boundary is the set of points having the same multiplicative advantage measure\" on line 350 should be elaborated upon. I understand what the authors are trying to say, i.e. that the spindles in Figure 1 trace the contours of $\\log \\frac{y}{1-y} - \\log \\frac{x}{1-x} = \\pm C$, but this was not obvious upon a first reading. \n\n2. In Theorem 3.2, it was as initially unclear to me why the random variable $\\alpha$ appeared without a subscript denoting the ball it belongs to. I think would benefit the reader to remind them that by the iid assumption, the distribution of $\\alpha$ over each ball is the same, hence the subscript can be dropped wlog. \n\n$\\textbf{Typos and Related Nitpicks}$\n\n1. Line 224 contains what I believe is a typo. It currently reads: \"In the bounds of Theorems 3.2, 3.3 and 3.3”, whereas it should read \"In the bounds of Theorems 3.2, 3.3 and 3.4”. \n\n2. In the following line 225, the statement \"as $p$ and/or $\\mu$ gets smaller we should naturally expect a smaller advantage\" is misleading because of the previous theorems' dependence on $p$ and $1-p$. A more precise statement would be \"as $p$ gets further from 1/2\". \n\n3. There is currently an inconsistent use of $\\epsilon$ and $\\varepsilon$ in the paper. For example, in Definition 2.1 both $\\epsilon$ and $\\varepsilon$ are used in the same sentence to refer to the privacy parameter. \n\n4. In Definition 3.6, the arguments of $I\\_{a,b}$ are $I_{a,b}(\\mathcal{M}, \\mathcal{D}, \\mathbf{x}, z, i)$, but in the following paragraph the arguments $I_{a,b}(\\mathcal{M}, \\mathcal{D}, \\mathbf{x}, z, x_i)$ are used. \n\n5. Lines 266 - 267: “What values of MA hould be considered acceptable? We argue that this probability should be viewed as a probability of system failure and set appropriately small” contains a typo with \"hould\" and an acronym \"MA\" that is not defined or (as far as I can tell) mentioned again.", "limitations": "Authors adequately address the limitations of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper contains many contributions to the field of auditing DP and non-DP mechanisms via label inference attacks. It builds off of the previously proposed metric of additive attack advantage by:\n\n(1) extending it to non-DP mechanisms\n\n(2) deriving novel bounds of this metric on a non-DP mechanism often used in practice (Theorem 3.2, 3.3, 3.4) and \n\n(3) using this metric to empirically compare the privacy-utility trade-off of DP and non-DP mechanisms on equal footing. \n\nMoreover,  inspired by previous work in the DP community, this paper proposes a metric called multiplicative attack advantage, and repeats the same contributions listed above with this metric. The authors provide experimental evidence that learning with deterministic aggregate labels is harder than learning from randomly perturbed labels. This experimental result is, as far as I am aware, novel. Given these contributions, I recommend this paper for acceptance.", "weaknesses": "My main critique of this paper is that, given the prominence that the hybrid LLP+Geom mechanism plays in the experimental results, the paper spends comparatively little time explaining how either the proposed metrics or the posterior probability for this mechanism are computed. \n\nIn the Questions section, I go into more detail and ask specific questions regarding this critique, and also give some suggestions to improve organization and readability of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* Explain how to compute proposed metrics or posterior distributions.\n\nWe will include more details on how we compute the posterior distributions for each mechanism. As suggested, we do apply Bayes’ theorem to compute the posterior:  \n$$\nPr(y_i = 1 |  x, \\mathcal{M}(x,y) = z) = \\frac{Pr(\\mathcal{M}(x,y) = z | x, y_i=1) \\cdot Pr(y_i=1 | x )}{Pr(\\mathcal{M}(x,y) = z | x)} = \\frac{Pr(\\mathcal{M}(x,y) = z | x, y_i=1) \\cdot Pr(y_i=1 | x_i )}{Pr(\\mathcal{M}(x,y) = z | x)} .\n$$ \nNow, because in the above $x$ is fixed, this ratio is simply a function of the $\\eta(\\cdot)$’s, as well as any randomness in $\\mathcal{M}$.\nFor Randomized Response (RR) with flipping probability $p$ this ratio is $\\frac{p\\eta(x_i)}{p\\eta(x_i) - (1-p)(1-\\eta(x_i)}$ if the outcome of $RR(y_i)  = 0$, and $\\frac{(1-p)\\eta(x_i)}{(1-p)\\eta(x_i) - p(1-\\eta(x_i)}$ if the outcome is 1. \n\nFor label aggregation (LLP), $\\mathcal{M}$ is deterministic, so in the numerator $Pr(\\mathcal{M}(x,y) = z | x, y_i=1)$ is the probability density at $z$ of a Poisson binomial with flipping probabilities $(\\eta(x_1),\\ldots, \\eta(x_{i-1}), 1, \\eta(x_{i+1}), \\ldots, \\eta(x_k))$. Similarly, in the denominator $Pr(\\mathcal{M}(x,y) = z | x)$ is the probability density at $z$ of a Poisson binomial with flipping probabilities $(\\eta(x_1), \\ldots, \\eta(x_k))$. \n\nFor LLP + Geom and LLP + Lap, the terms in the ratio are *convolutions* of the posterior for LLP and the Geometric or Laplace distribution, respectively. \n\nSome of these posterior calculations can be found in the appendix, for example, in Line 561 for bags, and in Line 720, Eq (15) and (16), for Randomized Response. \n\n- Other suggestions/typos.\n\nWe will implement the suggestions and fix the typos – thanks !", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NO7rCsadmz", "reviewer": "Reviewer_zE7q", "summary": "The paper introduces new metrics to quantify the amount of label leakage associated with a generic privacy mechanism. It then analyzes two common label privacy mechanisms and quantifies the measures for these two mechanisms. Especially for the mechanism that also has the guarantee of differential privacy, the paper shows that the upper bound of the measures coming from differential privacy can be loose by comparing it to the results analyzed in the paper. In the experiment, the paper empirically evaluates the algorithms with both utility and the proposed privacy measurement.", "questions": "Please see the weaknesses.", "limitations": "The paper has well discussed the limitations", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is very well-written.\n2. The theoretical results of analyzing two label-privacy mechanisms are novel and useful. \n    - For the DP mechanism, the paper shows a tighter analysis in terms of the proposed measure.\n    - Unlike the results in the literature that work only for the differential privacy mechanism, the paper also shows the theoretical results for the non-DP mechanism.", "weaknesses": "As the measure is defined as the maximum advantage of all label inference attack $\\mathcal{A}$ and the paper shows how to calculate the measure exactly for two mechanisms, it would be great to see how the existing label inference attack is bounded. This is because the measure is generally hard to compute, e.g. for the mechanisms that are not analyzed in the paper. If an existing label inference attack is shown to be tight to the exact upper bound, this attack can be used as an empirical indicator of the measure too.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* As the measure is defined as the maximum advantage of all label inference attack and the paper shows how to calculate the measure exactly for two mechanisms, it would be great to see how the existing label inference attack is bounded. This is because the measure is generally hard to compute, e.g. for the mechanisms that are not analyzed in the paper. If an existing label inference attack is shown to be tight to the exact upper bound, this attack can be used as an empirical indicator of the measure too.\n\nIndeed, if there was an attack that achieved the theoretical optimum, then it could potentially be used to empirically compute the label inference measures on PETs for which this is harder to compute analytically. In practice, this is complicated by the fact that the optimal attack depends on both the data distribution and the PET itself, so an attack that is optimal in one setting may not generalize to other PETs and distributions. It’s unclear how to reconcile this, but at the very least the attack could provide a lower bound on label inference success. In our experiments (for both the informed and uninformed adversary) we either analytically computed the Bayes optimal attack (on the synthetic datasets) or an approximation to the Bayes optimal attack (on the real-world datasets) by training an ML model on non-private data. This approximation to the Bayes optimal attack may turn out to be reasonably tight if we have enough training data.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CVYExA8PAw", "reviewer": "Reviewer_kz5F", "summary": "The authors present new auditing tools for privacy mechanisms (differentially private or otherwise) with respect to the threat of label inference. They define measures to measure how much an adversary's posterior belief differs from their prior belief after viewing a dataset processed by a PET method, provide bounds on these measures for different methods theoretically, and provide an empirical assessment of privacy risks over multiple datasets. All of this is accompanied by an in-depth discussion about each definition, bound, and result, along with reflections on what this metric means for privacy and related considerations.", "questions": "* Could the authors please provide the code for reproducing the empirical results?", "limitations": "Yes, the authors do discuss that and speculate on future directions of work to address them.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* Very well-motivated work, and the motivation of why label inference is a good and more realistic threat to look at vis-a-vis membership inference, etc.\n* Very well done literature review that is at once deep and nearly exhaustive and friendly towards newcomers to this area of work.\n* Very rigorously defined quantities and notions of interest along with high-level discussions about what those quantities mean.\n* The ability to measure privacy guarantees for DP and non-DP methods alike is very welcome and is a significant step in a line of similar work (such as [1] and [2]; please note that I am *not* asking the authors to cite this, but I seek to add further evidence about why this paper is of interest to the community and to argue for its acceptance).\n* Well-designed empirical experiments with relevant quantities and plots that capture privacy leakage well. The empirical results are discussed in detail and very carefully.\n* Exhaustive theoretical discussion with bounds with respect to the two auditing measures, additive and multiplicative, for different methods (DP and otherwise).\n\n[1] Das, S., Zhu, K., Task, C., Van Hentenryck, P., & Fioretto, F. (2024). Finding ε and δ of Traditional Disclosure Control Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 38(20), 22013-22020. https://doi.org/10.1609/aaai.v38i20.30204\n[2] M. Christ, S. Radway and S. M. Bellovin, \"Differential Privacy and Swapping: Examining De-Identification’s Impact on Minority Representation and Privacy Preservation in the U.S. Census,\" 2022 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 2022, pp. 457-472, doi: 10.1109/SP46214.2022.9833668. keywords: {Couplings;Privacy;Differential privacy;Sociology;Security;Stress;Differential-privacy;census;data-swapping},", "weaknesses": "No clear weaknesses. The theory and experiments are solid, every proof is provided, the motivation is well done, and the discussion has great depth and clarity. This is among those rare papers that I cannot point to something to criticise (at least not right away).\n\nThe only weakness, to be pedantic, is the lack of code to reproduce the experiments, which I would appreciate the provision of by the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* Can you publish/provide the code?\n\nWe will publish the code, subject to internal organizational approval.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SGM540WAww", "reviewer": "Reviewer_Us4Y", "summary": "This paper proposes a number of measures of information gained by an adversary from a mechanism.  It presents some theorems and performs a number of experiments.", "questions": "--", "limitations": "The paper doesn't discuss limitations.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Research on understanding better how much can be inferred when privacy mechanisms are in place is useful.\nThe text uses mostly correct and understandable English", "weaknesses": "The formalization is insufficiently rigorous and often unclear.\nThe claimed results don't seem to be always sound.\nWhile it is to some extent interesting to define new measures, it is important to understand what we can learn from these measures.  The paper doesn't motivate why the proposed measures are preferable over existing measures.  The experiments are illustrative but don't really answer the question of the value of the measures, and also don't compare to existing alternatives.\nSeveral other measures exist, e.g., there is quite some work using entropy-based measures to quantify how much an adversary can learn, i.e., the information gained by the adversary is the difference between the prior entropy and the posterio entropy.  \n\n\nSome details:\n\n* Often $\\mathcal{M}$ is called a mechanism rather than a PET.  Usually, one uses PET to refer to a strategy to enhance privacy, not to a learning algorithm.\n* In line 154, a $(\\mathbf{x},\\mathbf{y})$ is drawn from $\\mathcal{D}^m$.  However, $\\mathcal{D}^m$ is a product of $m$ datasets, each of the form $\\mathcal{X}\\times\\mathcal{Y}$.  In contrast, $(\\mathcal{x},\\mathcal{y})$ is a pair of an element from $\\mathcal{X}^m$ and an element from $\\mathcal{Y}^m$.  These don't match syntactically.  Similar conversions of object seem to happen at several other places in the paper.\n* In line 154, I also assume that $\\mathcal{A)(\\ldots)_i$ means the $i$-th component of the output of $\\mathcal{A}$ (rather than for example $\\mathcal{A}$ applied to the $i$-th component of $(\\mathbf{x},\\mathbf{y})$.\n* In line 198, Theorem 3.2:\n  - it is unclear what is the distribution of $\\alpha$ (In fact, $\\alpha$ has been used in various contexts before and it seems hard to unambiguously decide the meaning of $\\alpha$ here).\n  - it is unclear what is the role of the threshold $\\beta$\n  - $p$ is a probability, therefore the domain of $p$ is $[0,1]$.  The first alternative in the righthandside of the equation gives $p\\in[0,1]$, so this first option will always apply.  It is unclear why then there is a second alternative $|p-1/2|\\ge \\beta$.  Depending on the constants hidden in $\\Omega$ this second alternative may not be relevant, or it may is some cases provide a stronger bound.\n  - Earlier text suggests that $\\alpha_i=\\frac{1}{k}\\sum_{j=1}^k y_{i,j}.  In the proof, line 528, it seems now that $\\alpha=\\alpha_i$, but it is unclear what is the value of $i$ for which this holds.  Maybe you mean $\\alpha$ is a random variable taking values $\\alpha_i$ where $i$ is drawn uniformly from $[k]$ but even that doesn't solve all questions around here.\n  - line 528 sets $\\Sigma=k\\alpha$ ($\\Sigma$ is a real value), but doesn't explain what $\\Sigma$ means in the conditional probability $P(\\ldots | \\Sigma)$ in the next line ($\\Sigma$ would be an event or boolean condition).  The proof gets hard to understand at that point.\n* in Line 208, when describing the behavior when $k$ increases I assume you are considering a scenario in which $n$ is kept constant.\n* Theorem 3.3 suggests that if $\\eta(x) \\in \\{0,1\\}$, then $EAdv=0$.  This is unexpected:\n  - around line 154, there is the definition of $EAU$.  The prior/uninformed attacker doesn't get any information about the distribution $\\mathcal{D}$ as $\\mathcal{M}_\\bot(x,y)=\\bot$, so he can only guess classes with probability proportionally to the frequency of these class labels.  In contrast, the informed attacker gets information from a mechanism $\\mathcal{M}$.   One would hope the attacker can learn something from $\\mathcal{M}$, especially as learning a deterministic function if easier than learning a probabilistic function.  Still, Theorem 3.3 seems to say that the EAdv will be zero.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The reviewer’s main criticisms focus on: (a) comparison to related work, and (b) clarity of the mathematical setup and notation. \n\n**Comparison to related work**\n\n* “it is important to understand what we can learn from these measures. [...] Other measures exist, like entropy based. The paper doesn't motivate why [...] preferable over existing measures.”\n\nWe do discuss related work extensively in Section 3.3. Indeed, our paper explicitly builds on several other works that aim to measure advantage. We are not aware of entropy-based measures being applied in the specific context of label aggregation, or label privacy more generally. Yet, we would be very interested to add comparisons to such works if the reviewer could suggest some specific starting points. \n\nOne possibly relevant point is that multiplicative measures such as the one we consider here generally upper bound entropy-based quantities like mutual information (which corresponds to the reviewer’s suggestion of entropy drop from prior to posterior). We can add a general discussion of that point to Section 3.2.\n\n* The paper doesn’t discuss limitations.\n\nThis is not accurate, please see Section 5.\n\n**Mathematical setup and notation**\n\n* On our measures and the associated theoretical results. \n\nThere seem to be two general misunderstandings regarding our theoretical setting. First, in our definitions of attack utility and attack advantage we are assuming the adversaries (both the informed and the uninformed ones) have full knowledge of the distribution $D$ generating the data. Second, for the PETs we actually analyze, since the data is i.i.d. the attack advantage is either depending on a single example $(x_1,y_1)$ (for Randomized Response) or a single bag of examples (for label aggregation). This is why, for instance, the bounds for label aggregation in Thm 3.2, 3.3 and 3.4 are referring to a single random bag of size $k$ instead of a set of $n$ bags of size $k$, and thus we dropped the bag index $i$ from the notation. Please recall LL. 185-189. \n \n* L. 154, syntactic mismatch. \n\nYes, this is a minor abuse of notation (and the specific sampling that we use is described in lines 82-84). In general we identify elements of $X^m \\times Y^m$ and $(X \\times Y)^m$ if they describe the same sequence of labeled examples. We will fix it throughout so as to avoid this notational inconsistency. \n\n* L. 154, is $\\mathcal{A}(...)_i$ the i-th component of the output of $\\mathcal{A}$ ?\n\nYes, your interpretation is correct. As described on L. 148, the attacker receives the feature vectors for each example, the output of the PET, and they output a prediction for the label of each example. We will add a clarification to that effect, thanks.\n\n* In line 198, Thm 3.2, ambiguity in the distribution and meaning of $\\alpha$.\n\nThank you for identifying this ambiguity. Theorem 3.2 deals with a single bag containing $k$ examples, and the relevant distributions are: the $k$ pairs $(x_j,y_j)$ are drawn i.i.d. from $D$, and $\\alpha$ is set to be the average over the $k$ labels. The theorem focuses on the case of a *single* bag since when using the $M_{LLP}$ mechanism, the bags observed by the attacker are independent and, since $D$ is known, the attacker gains no extra advantage from operating on an entire dataset of bags at once. It is thus sufficient to measure their success on a single bag. We will add some clarifying text to the paper.\n\n* Thm 3.2: role of $\\beta$ and two bounds.\n\nThm 3.2 provides two guarantees. As you point out, one of the guarantees holds without any condition on $p$, while the other requires that $p$ is sufficiently far from $1/2$. In particular, as long as $p$ is bounded away from $1/2$, the expected advantage decreases *exponentially* with $k$, rather than at the much slower rate of $k^{-1/2}$. The parameter $\\beta$ in the exponent quantifies how far from $1/2$ that $p$ is. Thus, $\\beta$ is a property of distribution $D$. The two bounds we give are generally incomparable, but when $k$ is large and there is a big enough gap $\\beta$, the second bound is clearly better.\n\n* L 528-529 meaning of conditioning on $\\Sigma$.\n\nGiven that $\\alpha$ is the proportion of the $k$ examples that had positive labels, $\\Sigma = k\\alpha$ is the number of positive labels in the bag, so $\\Sigma$ is a random variable supported on $\\{0, …, k}$. It is valid to condition probabilities on random variables. The notation $P(...| \\Sigma)$ is nothing else than a conditional expectation, which is itself a random variable since it is a function of the random variable $\\Sigma$. \n\n* L 208, when $k$ increases, is $n$ kept constant?\n\nAs said above, because the bags are independent, we only need to consider a single bag when computing advantage. So $n$ is irrelevant to the advantage result in Theorem 3.3 (and subsequent results as well) since the attacker’s ability to predict the labels in one bag does not depend on the number of bags they have.\n\n* Theorem 3.3 unexpectedly suggests that if $\\eta(x) \\in \\{0,1\\}$ then EAdv = 0.\n\nAs stated on LL. 160-163, both the uninformed and the informed attackers know the data distribution $D$ (one can also infer this from the definitions, since for a fixed $D$, we take the sup over adversaries–including ones that know $D$). Thus, when $\\eta(x) = 0$ or $\\eta(x) = 1$, both attackers have perfect knowledge of the label regardless of what the mechanism releases, since the label is unambiguously determined by the features (which are assumed to be public). So the inference advantage (conferred by the mechanism) is 0. \n\n* Often $M$ is called a mechanism rather than a PET. Usually, one uses PET to refer to a strategy [...] not to a learning algorithm.\n\nIt is true that we use both PET and Mechanism to refer to privacy enhancing technologies. However, we would like to emphasize in all cases, the PETs/Mechanisms we discuss are strategies for enhancing privacy and not learning algorithms. We will make this clearer in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "chkdHYIj1v", "reviewer": "Reviewer_mygV", "summary": "This paper develops measures for auditing privacy-preserving mechanisms that consume datasets with public features and private labels. The auditing measures compare two attackers whose goal is to infer a private label: a weaker attacker who has access to the dataset’s features and prior knowledge of the correlation between features and labels, and a stronger attacker who additionally has access to the privatized labels output by the mechanism. The advantage of the stronger attacker over the weaker attacker can be measured in two ways: additively or multiplicatively. Upper bounds on the additive and multiplicative measures are obtained for two privacy-preserving mechanisms: randomized response (RR) and learning from label proportions (LLP). These mechanisms are otherwise difficult to compare as RR satisfies label differential privacy, but LLP does not. Experiments on synthetic and real datasets, demonstrate that privacy-utility trade-offs can be evaluated using the proposed measures, and that RR dominates LLP.", "questions": "- How would you envisage these measures being applied? Would they be used to tune privacy parameters? Compare privacy-preserving mechanisms?\n- Why is the model of the adversary’s uncertainty reasonable? Could you expand on this?\n- Why does the definition of expected attack utility differ from Wu et al. (2022)?", "limitations": "Section 5 discusses limitations including the assumption of iid data, the need to estimate the adversary’s label uncertainty and label semantics. Another limitation of the work is that the measures are only instantiated for binary labels.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "**Originality:**\nWhile variations of the additive and multiplicative measures have appeared in prior work (as acknowledged by the authors), this paper appears to be the first to apply the multiplicative measure to auditing generally, and the first to apply the additive measure to auditing of non-differentially private mechanisms.\n\n**Significance:**\nThe proposed measures allow for auditing of non-differentially private mechanisms for label privacy, filling an apparent gap in the literature. The empirical finding about the dominance of randomized response (a differentially private mechanism) over learning from label proportions (a more heuristic mechanism) in terms of privacy and utility is interesting, and may encourage adoption of differential privacy in the field.\n\n**Quality:**\nThe experiments are thorough, covering a range of datasets and parameter settings for the mechanisms under audit. In addition to computing the proposed audit measures, plots visualizing the prior/posterior update for individual data points are provided, which adds another dimension to the results. \n\n**Clarity:**\nThe paper is generally clear (see comments below).", "weaknesses": "The narrative could be strengthened, perhaps by leaning more on the application to online advertising. At times, I found myself questioning the path taken in the paper. For example, why are the additive and multiplicative measures both needed? It seems the multiplicative measure is superior as it is data-dependent, and a relative comparison is arguably more natural for probabilities. I also wondered why the definitions of expected attack utility and expected attack advantage differ from Wu et al. (2022), who condition on the features $\\mathbf{x}$. It would be helpful to explain why conditioning on the features doesn’t make sense here.\n\nSome of the bounds make strong assumptions about the data distribution. For instance, Theorems 3.2 and 3.7 assume the labels and features are uncorrelated, which doesn’t seem to be an interesting case to consider. There are analogues of Theorem 3.2 for general data distributions, but not Theorem 3.7.\n\nThe proposed measures are claimed to provide “a more balanced and nuanced picture” (line 40) of privacy/accuracy trade-offs. And the model of the adversary’s uncertainty is claimed to be “reasonable” (line 298). It would be helpful to elaborate on these claims a little more, so that practitioners can better understand any caveats. I understand that the measures are more optimistic because they depend on the adversary’s uncertainty (rather than assuming the worst-case). However the validity of the measures then depends on having a good model of the adversary’s uncertainty. The model adopted in the paper seems to assume the adversary has no side information. It would be great to discuss this assumption in the context of online advertising.\n\n\n**Minor:**\n- Figure 1: It is difficult to distinguish between different coloured points for LLP and LLP+Geom.\n- line 224: Incorrect reference to Theorem 3.3.\n- line 322: Is the classifier calibrated?\n- line 252 and 260: There is an inconsistency in the last argument of the measure: $i$ vs $x_i$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* Why are additive and multiplicative measures both needed?\n\nThe multiplicative measure is generally stronger, in that a small multiplicative advantage implies a small additive one, but not vice versa. We studied both additive and multiplicative measures for a few reasons. While the multiplicative measure is closer to the standard DP interpretation of privacy, the additive measure may be more naturally interpretable in terms of X% increase in inference risk. Besides, the additive measure is more generous to LLP, so the fact that DP mechanisms in practice outperform LLP even when we use the additive measure becomes even more surprising. \n\n* Is the classifier calibrated? (See 823 in appendix)\n\nAs explained in LL. 823-836 in the appendix, we had initial experiments with both Deep Neural Network (DNN) architectures and k-Nearest Neighbor (kNN) classifiers. When trained with event-level (that is, non-private) labels, DNNs are not guaranteed to give rise to calibrated classifiers, while a kNN classifier is typically calibrated. Since we observed in our initial experiments that the two resulted in similar overall outcomes, we decided to go with DNNs as the underlying classifier throughout.\n\n* How would you envisage these measures being applied? Would they be used to tune privacy parameters? Compare privacy-preserving mechanisms?\n\nAn organization that is considering multiple otherwise incomparable PETs could use our measures to 1) establish which one has the best privacy/accuracy tradeoff for the types of data and downstream tasks they’re concerned with, and 2) set privacy parameters according to their risk tolerance. For example, in our case, Figure 3 shows that RR achieves the best tradeoff for our setting. In addition, the curves can help with choosing epsilon in an informed manner, though of course the decision should consider other contextual factors, and more than one measure of advantage. \n\n* Why is the model of the adversary’s uncertainty reasonable? Side information.\n\nWe emphasize that we do model a particular kind of side information. However, we make the assumption that, conditioned on the adversary’s side information and the public features, the labels within a batch are independent of each other. Our model aims to strike a balance between minimizing assumptions (as conservative approaches like DP do) and expressiveness. Alas, very conservative approaches will immediately disqualify deterministic mechanisms. Our goal is a reasonable framework that allows one to put deterministic mechanisms and randomized ones on the same footing.\n\nWe use a nonprivately trained predictor to capture adversarial uncertainty. This felt like the right way to get a “population-level” knowledge. \n\nGiven that bagging is done randomly, such population-level modeling seems like a good fit for the mechanisms we consider. If bags were not generated uniformly (e.g., in the extreme, if records from users in the same household were bagged together), then distributional assumptions would seem like the wrong approach, and the conservativeness of DP would make more sense. \n\nIn the context of online advertising: we imagine that existing predictive models could be used as the source of baseline probabilities. The experiments with the kdd12 data set (which comes from online advertising) provide a simple illustration.\n\n* Why does the definition of expected attack utility differ from Wu et al. (2022)? \n\nUnlike label DP mechanisms analyzed by Wu et al., LLP does not easily admit bounds that hold for all data distributions and are conditioned on arbitrary feature vectors $x$. In particular, in order to obtain a bound that has a clear dependence on the bag size $k$, the conditional distribution $\\eta(x)$ must be bounded away from 0 and 1–see Remark A.15 in the appendix. Hence, since we wanted to measure advantage for both label DP and label aggregation, so as to put the two on the same footing, we had to consider a wider spectrum of measures. Specifically, we considered three guarantees in terms of $x$ (from weaker to stronger): (i) *expected* advantage, where the guarantee is only in expectation over the distribution of $x$;. (ii) advantage in high probability over $x$; and (iii) “for all $x$” advantage (that is, conditioning on $x$, as in Wu et al.). In all three cases, though, the guarantees are in expectation over the conditional distribution of $y$ given $x$. For label aggregation (LLP), the latter two guarantees are basically only contained in the appendix (Section A.5 there in -- see, e.g., Thm A.9 and Remark A.15).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The submission introduces two auditing metrics (additive and multiplicative attack advantages) to assess the vulnerability of label privatization mechanisms. The authors effectively demonstrate the application of these metrics to (empirically) auditing both differentially private and non-differentially private privacy mechanisms. Most reviewers praised the work, noting its potential for impact in the growing field of privacy auditing. In particular, during the discussion, Reviewer mygV highlighted the paper’s practical contributions and pragmatic approach, as well as its analysis of privacy-utility trade-offs across various mechanisms. Reviewer kz5F also appreciated the rigorous theoretical analysis and empirical validation. Reviewer enWp also strongly supported acceptance, emphasizing the paper's substantial methodological contributions to auditing privacy mechanisms and noting the novelty of the experimental results.

Given the reviewers' comments and my own read of the paper, this submission is a clear acceptance. While Reviewer Us4Y raised concerns regarding the paper's rigor and its placement relative to the broader privacy literature -- engaging in an extensive back-and-forth with the authors -- these concerns were not shared by other reviewers and the AC. I encourage the authors to incorporate the suggestions provided by the reviewers and promised in their rebuttal to the final paper, including releasing their code, providing more details on how to compute posterior distributions (Reviewer enWp), fixing typos, and clarifying ambiguities in some of the mathematical results (Reviewer Us4Y).
Decision: Accept (spotlight)