# Auditing Privacy Mechanisms via Label Inference Attacks

Róbert István Busa-Fekete
Google Research NY
<EMAIL_ADDRESS>
Travis Dick
Google Research NY
<EMAIL_ADDRESS>
Claudio Gentile
Google Research NY
<EMAIL_ADDRESS>
Andrés Muñoz Medina
Google Research NY
<EMAIL_ADDRESS>
Adam Smith
Boston University
& Google DeepMind
<EMAIL_ADDRESS>Marika Swanberg
Boston University
& Google Research NY
<EMAIL_ADDRESS>

###### 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 one multiplicative. These
incorporate previous approaches taken in the literature on empirical auditing
and differential privacy. The 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 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.

##  1 Introduction

Data sharing and processing provides an undeniable utility to individuals and
the society at large. The modern data ecosystem has played a 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 a number of empirical measures of disclosure risks
against several types of attacks, including: inference attacks [28],
reconstruction attacks [5], re-identification attacks [14] and label inference
attacks [13, 30].

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 of privacy that take adversarial uncertainty
into account. At a fundamental level, whether one is studying reconstruction
or membership inference, nearly every privacy disclosure metric comes down to
quantifying the relationship between an adversary’s prior and posterior
knowledge before and after a data release.

In this work, we consider a number of ways to summarize this prior-posterior
relationship, and we apply our proposed metrics to a few Privacy Enhancing
Technologies (PETs). We consider two families of metrics: As a 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 a 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-
based and differential privacy-based PETs, and hence compare their privacy-
accuracy trade-off curves: _What accuracy does one get for a given level of
privacy protection?_ Together, these metrics paint a more balanced and nuanced
picture of the disclosure risks and accuracy trade-offs posed by aggregation
and differentially private mechanisms.

We will focus on the simplest possible scenario for information sharing: the
case where a user wishes to disclose a single bit of information (for instance
a binary label in a classification problem). While this problem is simple to
present, it already highlights a lot of the difficulties in providing measures
of privacy that are meaningful for both noise-based and aggregate-based tools.
Most notably, it already requires handling the correlations—known to an
attacker, but unknown to the mechanism—between the visible features and the
hidden, sensitive labels. Similar to [30], we incorporate adversarial
knowledge by a prior, and measure the difference between the prior and the
adversary’s posterior distribution conditional on observed aggregates.

Understanding binary labels already has practical implications. For instance,
with Chrome’s proposed conversion reporting API [1], the event of a user
converting after clicking on an online ad — buying a product, signing up for a
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
advantage 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 [30]. (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,
10]), 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 a 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.

##  2 Preliminaries

For a natural number $n$, let $[n]=\\{i\in\mathbb{N}\colon i\leq n\\}$. Let
$\mathcal{X}$ denote a feature (or instance) space and $\mathcal{Y}$ be a
binary ($\mathcal{Y}=\\{0,1\\}$) or multiclass ($\mathcal{Y}=[c]$) label
space. We assume the existence of a joint distribution $\mathcal{D}$ on
$\mathcal{X}\times\mathcal{Y}$, encoding the correlation between the input
features and the labels. The marginal distribution over $\mathcal{X}$ will be
denoted by $\mathcal{D}_{\mathcal{X}}$, and the conditional distribution of
$y$ given $x$ will be denoted by $\mathcal{D}_{\mathcal{Y}|x}$. For
distributions over binary labels, we denote by
$\eta(x)=\operatorname*{\mathbb{P}}_{y\sim\mathcal{D}_{\mathcal{Y}|x}}(y=1|x)$
the probability of drawing label 1 conditioned on feature vector $x$. In the
multiclass case, we will use
$\eta(x,a)=\operatorname*{\mathbb{P}}_{y\sim\mathcal{D}_{\mathcal{Y}|x}}(y=a|x)$,
for $a\in\mathcal{Y}=[c]$. We define a dataset
$S=\langle(x_{1},y_{1}),\ldots,(x_{m},y_{m})\rangle$ as a sequence of pairs
$(x_{i},y_{i})$, each one drawn i.i.d. from $\mathcal{D}$. We use
$\mathbf{x}=(x_{1},\ldots,x_{m})$ to denote the features in $S$ and
$\mathbf{y}=(y_{1},\ldots,y_{m})$ to denote the corresponding labels.

In order to unify the study of privacy enhancing technologies, for the rest of
the paper we model PETs as (possibly randomized) functions
$\mathcal{M}:(\mathcal{X}\times\mathcal{Y})^{m}\to\mathcal{Z}$. These
functions map a collection of $m$ labeled examples to a privacy protected
representation in the domain $\mathcal{Z}$. The domain $\mathcal{Z}$ depends
on the PET but, throughout the paper, it will be clear from the context.

In our setting, we consider PETs that protect labels and release features in
the clear (so, strictly speaking, the output of a PET should also include
$\mathbf{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
metrics APIs: one which satisfies label differential privacy, and one which
relies on random aggregation. These are the two PETs on which we will also be
able to give theoretical guarantees. We formulate them for binary
classification.

######  Definition 2.1.

Given $\varepsilon\geq 0$, we say that a (randomized) algorithm $A$ that takes
as input $S$ is $\varepsilon$-Label Differentially Private
($\varepsilon$-Label DP) if for any two datasets $S$ and $S^{\prime}$ that
differ in the label of a single sample we have
$\operatorname*{\mathbb{P}}(A(S)\in B)\leq
e^{\epsilon}\,\operatorname*{\mathbb{P}}(A(S^{\prime})\in B),$ where $B$ is
any subset of the output space of $A$.

Randomized Response (RR) is a classical [29] way of achieving $\epsilon$-Label
DP. In the binary classification case, RR with privacy parameter
$\pi=1/(1+e^{\epsilon})$ simply works by randomly flipping each label $y_{j}$
in the dataset with independent probability $\pi$ before revealing it to the
learning algorithm. For a fixed $\epsilon>0$, RR corresponds to the function
$\mathcal{M}_{\text{RR}}(\mathbf{x},\mathbf{y})=\tilde{}\mathbf{y}=(\tilde{y}_{1},\ldots,\tilde{y}_{m})\in\\{0,1\\}^{m}$,
where $\tilde{}y_{i}=1-y_{i}$ with probability $\pi=1/(1+e^{\epsilon})$ and
equal to $y_{i}$ with probability $1-\pi$, independently for each $i\in[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 a given size
$k$,
$S=\langle(x_{11},y_{11}),\ldots,(x_{1k},y_{1k}),\ldots,(x_{n1},y_{n1}),\ldots,(x_{nk},y_{nk})\rangle,$
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 $\\{(\mathcal{B}_{i},\alpha_{i}),\,i\in[n]\\}$
of $n$ labeled bags of size $k$, with $m=nk$, where
$\mathcal{B}_{i}=\\{x_{ij}\colon j\in[k]\\}$,
$\alpha_{i}=\frac{1}{k}\sum_{j=1}^{k}y_{ij}$ is the label proportion (fraction
of labels “1") in the $i$-th bag, and all the involved samples
$(x_{ij},y_{ij})$ are drawn i.i.d. from $\mathcal{D}$. Thus, the attacker
receives information about the $m$ labels $y_{ij}$ of the $m$ instances
$x_{ij}$ from dataset $S$ only in the aggregate form determined by the $n$
label proportions $\alpha_{i}$. Note, however, that the feature vectors
$x_{ij}$ are individually observed. From an attacker viewpoint, this setting
is sometimes called Learning from Label Proportions (LLP). Hence, LLP
corresponds to the function
$\mathcal{M}_{\text{LLP}}(\mathbf{x},\mathbf{y})=(\alpha_{1},\ldots,\alpha_{n})\in[0,1]^{n}$.

#### Learning from privatized labels.

Randomized response is especially appealing from a 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 hyper-parameters. Often
the theoretical guarantees of these learners in terms of sample complexity are
only deteriorated by some constant that depends on the label noise level, see,
for example [26]. To improve accuracy, we debias the gradients in a post-
processing step similar to Equation (7) in [19]; we discuss the debiasing
details in Appendix C.

On the other hand, a simple and very well-known method for learning from
aggregate labels is the one that of [31] call Empirical Proportion Risk
Minimization. In fact, different versions of this algorithm are discussed in
the literature without a 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 a loss function
$\ell\,:\,\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}^{+}$, a hypothesis
set of functions $\mathcal{H}\subset\mathbb{R}^{\mathcal{X}}$, mapping
$\mathcal{X}$ to a (convex) prediction space
$\widehat{}\mathcal{Y}\subseteq\mathbb{R}$, and a collection
$\\{(\mathcal{B}_{i},\alpha_{i}),\,i\in[n]\\}$ of $n$ labeled bags of size
$k$, PropMatch minimizes the empirical _proportion matching loss_ , i.e., it
solves the following optimization problem:

$\min_{h\in\mathcal{H}}\sum_{i=1}^{n}\ell\left(\frac{1}{k}\sum_{j=1}^{k}h(x_{ij}),\alpha_{i}\right)~{}.$

It is known that the above method is consistent (see for instance [12]). That
is, training a model this way – under some mild conditions on $\ell$ and
$\mathcal{H}$ and for a large enough sample – results in learning a model $h$
that minimizes the expected _event level_ loss
${\operatorname*{\mathbb{E}}}_{(x,y)\sim\mathcal{D}}[\ell(h(x),y)]$.

Finally, for our baselines, it will be helpful to consider a PET that reveals
no label information at all: $\mathcal{M}_{\bot}(\mathbf{x},\mathbf{y})=\bot$.

##  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 [30] 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
$\mathcal{D}$. On the other, they will pave the way for our experimental
findings in Section 4.

A reconstruction advantage metric is grounded in the following natural privacy
question: _How much does releasing the output of a PET increase the risk of
label inference compared to not releasing anything?_ This corresponds
naturally to measuring an attacker’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
$\mathcal{A}:\mathcal{X}^{m}\times\mathcal{Z}\to\mathcal{Y}^{m}$ that maps the
features $\mathbf{x}$ and the output of a PET
$\mathcal{M}(\mathbf{x},\mathbf{y})$ to a vector of predicted labels, one for
each example. We compare this attacker’s success to the the _uninformed_ or
_prior_ attacker that gets $\mathbf{x}$ and the PET that reveals no label
information $\mathcal{M}_{\bot}(\mathbf{x},\mathbf{y})=\bot$. To measure the
efficacy of an attacker compared to its prior, we define a number of _attack
utility_ variants.

The _E xpected Attack Utility_ of adversary $\mathcal{A}$ using information
from PET $\mathcal{M}$ on a collection of $m$ examples drawn i.i.d. from a
distribution $\mathcal{D}$ is defined as:

$\operatorname{EAU}(\mathcal{A},\mathcal{M},\mathcal{D})=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}(\mathbf{x},\mathbf{y})\sim\mathcal{D}^{m},\,i\sim\text{Uniform}([m]),\,\text{coins
of
}\mathcal{M}\end{subarray}}\bigl{(}\mathcal{A}(\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y}))_{i}=y_{i}\bigr{)}~{}.$

In words, the expected attack utility of adversary $\mathcal{A}$ is the
probability that $\mathcal{A}$ correctly guesses the label of a randomly
chosen example when provided the features and the output of $\mathcal{M}$.
Equivalently, this is the expected fraction of the $m$ examples that the
adversary predicts the correct label for. The adversary’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 $\mathcal{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 $\mathcal{D}$ over
$\mathcal{X}\times\mathcal{Y}$, either completely (e.g., Definition 3.1) or
approximately through learning on disjoint data (as in our experiments in
Section 4).

Further, we define the _I ndividual Expected Attack Utility_ on input data
$x_{i}$ as

$\operatorname{IEAU}_{i}(\mathcal{A},\mathcal{M},\mathcal{D},x_{i})=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}y_{i}\sim\mathcal{D}_{\mathcal{Y}|x_{i}}(\mathbf{x}^{(-i)},\mathbf{y}^{(-i)})\sim\mathcal{D}^{m-1}\text{,
coins of
}\mathcal{M}\end{subarray}}\left(\mathcal{A}(\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y}))_{i}=y_{i}\,\Big{|}\,x_{i}\right)\,,$

where $\mathbf{x}^{(-i)}$ is $\mathbf{x}$ with the $i$-th item $x_{i}$
dropped, and likewise for $\mathbf{y}^{(-i)}$. The quantity
$\operatorname{IEAU}_{i}(\mathcal{A},\mathcal{M},\mathcal{D},x_{i})$
emphasizes the (expected) attack utility on a specific piece of data $x_{i}$
when the associated label $y_{i}$ is drawn from the conditional distribution
$\mathcal{D}_{\mathcal{Y}|x_{i}}$. For instance,
$\operatorname{IEAU}_{i}(\mathcal{A},\mathcal{M}_{\text{LLP}},\mathcal{D},x_{i})$
measures, for a given $x_{i}$, the chance that an attacker is able to
reconstruct the associated label $y_{i}$, if $y_{i}$ generated from
$\mathcal{D}_{\mathcal{Y}|x_{i}}$ and, by virtue of mechanism
$\mathcal{M}_{\text{LLP}}$, $y_{i}$ becomes part of a bag (of some size $k$),
only the bag label proportion $\alpha$ 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, $\mathbf{x}$,
together with the output of the PET, $\mathcal{M}(\mathbf{x},\mathbf{y})$, and
an alternate setting where the adversary gets only the features (which is
equivalent to using $\mathcal{M}_{\bot}$). 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 to the PET rather than to correlations between the
features $\mathbf{x}$ and labels $\mathbf{y}$ which are inherent in the
distribution $\mathcal{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) we will
also consider a multiplicative version, based on utility ratios.

######  Definition 3.1.

Given a PET $\mathcal{M}$ for a set of $m$ examples drawn from a data
distribution $\mathcal{D}$, the (additive) _E xpected attack Advantage_ is
defined as

$\displaystyle\operatorname{EAdv}(\mathcal{M},\mathcal{D})$
$\displaystyle=\sup_{\mathcal{A}_{\text{informed}}}\operatorname{EAU}(\mathcal{A}_{\text{informed}},\mathcal{M},\mathcal{D})$
$\displaystyle-\sup_{\mathcal{A}_{\text{uninformed}}}\operatorname{EAU}(\mathcal{A}_{\text{uninformed}},\mathcal{M}_{\bot},\mathcal{D})~{}.$

Similarly, when the $i$-th item $x_{i}$ is kept frozen, the _I ndividual
Expected attack Advantage_ is defined as

$\displaystyle\operatorname{IEAdv}(\mathcal{M},\mathcal{D},x_{i})=\sup_{\mathcal{A}_{\text{informed}}}\operatorname{IEAU}(\mathcal{A}_{\text{informed}},\mathcal{M},\mathcal{D},x_{i})-\sup_{\mathcal{A}_{\text{uninformed}}}\operatorname{IEAU}(\mathcal{A}_{\text{uninformed}},\mathcal{M}_{\bot},\mathcal{D},x_{i}).$

Note that RR is generally described in terms of its behavior on a single
example $(x,y)$, rather than a collection of $m$ i.i.d. samples. Likewise,
label aggregation operates on each bag of size $k<<m$ independently. However,
since the data is i.i.d., it is easy to see 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 A.5 contains further variants of attack advantage, like one that
accounts for the tail of the attack advantage distribution, as well as
associated bounds. These can be stretched to the point where the feature
vector $\mathbf{x}=(x_{1},\ldots,x_{m})$ is arbitrary, and only the properties
of the condition distribution $\mathcal{D}_{\mathcal{Y}|x}$ is factored in.

###  3.1 Bounding the Additive Attack Advantage

As a warm up, we begin by studying the additive expected attack advantage for
LLP when the labels are independent of the features. Note that, since the
features $\mathbf{x}$ do not play any role in this simplified setting, the
notions of advantage coincide. All proofs are given in the appendix.

######  Theorem 3.2.

Fix a data distribution $\mathcal{D}$, let
$p=\operatorname*{\mathbb{P}}_{(x,y)\sim\mathcal{D}}(y=1)$, and fix an
arbitrary threshold $\beta\in[0,1/2]$. If labels are independent of features
(i.e., $\mathcal{D}$ is a product of distributions over $\mathcal{X}$ and
$\mathcal{Y}$), then for all bag sizes $k\geq 1$ we have:

$\displaystyle\operatorname{EAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D})$
$\displaystyle=\min\\{p,1-p\\}-{\operatorname*{\mathbb{E}}}_{\alpha}[\min\\{\alpha,1-\alpha\\}]\leq\begin{cases}\sqrt{\frac{p(1-p)}{k}}&\text{if
$p\in[0,1]$}\\\ e^{-\Omega(\beta^{2}k)}&\text{if
$|p-1/2|\geq\beta$},\end{cases}$

where $\Omega(\cdot)$ hides constants independent of $\beta$ and $k$.

A couple of remarks are in order. First, observe that, as expected, the
advantage $\operatorname{EAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D})$ is
always non-negative. This can be easily derived by noting that
$\operatorname*{\mathbb{E}}[\alpha]=p$ and then applying Jensen’s inequality
to the concave function $x\mapsto\min\\{x,1-x\\}$, for $x\in[0,1]$. Second,
despite being non-negative, Theorem 3.2 also proves the desirable property
that $\operatorname{EAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D})$ goes to zero
as the bag size $k$ increases. The convergence rate is in general of the form
$1/\sqrt{k}$, 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 $\operatorname{EAdv}$ and $\operatorname{IEAdv}$.

######  Theorem 3.3.

Let $\mathcal{D}$ be an arbitrary distribution on
$\mathcal{X}\times\mathcal{Y}$, $p=\operatorname*{\mathbb{E}}[\eta(x)]$, and
$\mu=\operatorname*{\mathbb{E}}[\eta(x)(1-\eta(x))]$. Then, for all bag sizes
$k\geq 2$ we have:

$\displaystyle\operatorname{EAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D})=\widetilde{O}\biggl{(}$
$\displaystyle\frac{\mu^{1/4}(p(1-p))^{1/4}}{\sqrt{k}}+\frac{\mu^{1/4}}{k}\biggr{)}~{},$

where $\widetilde{O}$ hides logarithmic factors in $k$.

Hence, also in this more general case of LLP, the advantage converges to zero
as the bag size $k$ grows large. Compared to the rate in Theorem 3.2, we are
only losing the $\log k$ factors implicit in the $\widetilde{O}$ notation.
This is because, when applied to the scenario where labels and features are
independent, $\eta(x)=p$ is constant with $x$, so that $\mu=p(1-p)$, and the
first term becomes $\sqrt{\frac{p(1-p)}{k}}$, while the second one reads
$\frac{(p(1-p))^{1/4}}{k}$, which is lower order when $k$ is large. We
strongly believe that the tighter gap-dependent analysis we carried out for
Theorem 3.2 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.

######  Theorem 3.4.

Under the same assumptions and notation as in Theorem 3.3, we have, for
$\mu>0$, and $k\geq\frac{2}{\mu}\log(1/\mu)$,

$\displaystyle\operatorname{IEAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D},x_{i})=\mu_{i}\,\widetilde{O}\left((p(1-p))^{1/4}\sqrt{\frac{\mu}{k}+\frac{1}{\mu^{3/2}k}}+\sqrt{\frac{\mu}{k^{2}}+\frac{1}{\mu^{3/2}k^{2}}}\,\right),$

where $\mu_{i}=\eta(x_{i})(1-\eta(x_{i}))$, and $\widetilde{O}$ hides
logarithmic factors in $k$.

In the bounds of Theorems 3.2, 3.3 and 3.3 the dependence on the data
distribution $\mathcal{D}$ is encoded in $p$ and $\mu$ (as $p$ and/or $\mu$
gets smaller we should naturally expect a smaller advantage, as the adversary
is facing an easier label prediction problem). Appendix A.5 contains further
distribution-dependent results, like a bound on the advantage that,
conditioned on $\mathbf{x}=(x_{1},\ldots,x_{m})$, is of the form
$\frac{1}{k}\sum_{i=1}^{k}\frac{\mu_{i}}{\sqrt{\sum_{j:j\neq i}\mu_{j}}},$
where $\mu_{i}=\eta(x_{i})(1-\eta(x_{i}))$.

We now provide the corresponding expression for the additive attack advantage
for RR (at a given level $\epsilon\geq 0$). We recall that the results of [30]
imply that every $\epsilon$-label-DP PET $\mathcal{M}$ has advantage bounded
as $\operatorname{EAdv}(\mathcal{M},\mathcal{D})\leq
1-\frac{2}{1+e^{\epsilon}}$. However, one drawback of this bound is that it is
distribution independent (or, rather, worst case over distribution
$\mathcal{D}$). Yet, the attack advantage depends heavily on $\mathcal{D}$.
For an extreme example, if we have
$\operatorname*{\mathbb{P}}_{(x,y)\sim\mathcal{D}}(y=1)=1$, the attack
advantage is zero for every PET, which is not directly captured by only
relying on the properties of $\epsilon$-DP.

Recall that, since RR operates on each example independently, the advantage is
independent of the number of examples $m$ (a formal proof is given in Appendix
A.6). Hence we derive a bound for
$\operatorname{IEAdv}(\mathcal{M}_{\text{RR}},\mathcal{D},x_{1})$, and an
expression for the optimal adversary under RR (see Appendix A.7).

######  Theorem 3.5.

For any data distribution $\mathcal{D}$, the individual expected attack
advantage $\operatorname{IEAdv}(\mathcal{M}_{\text{RR}},\mathcal{D},x_{1})$
for randomized response with privacy parameter
$\pi=\frac{1}{1+e^{\varepsilon}}$ satisfies

$\operatorname{IEAdv}(\mathcal{M}_{\text{RR}},\mathcal{D},x_{1})=\bigl{(}\min\\{\eta(x_{1}),1-\eta(x_{1})\\}-\pi\bigl{)}\cdot\mathbb{I}\\{\eta(x_{1})\in[\pi,1-\pi]\\}~{}.$

We use the above expression in our experiments (Section 4) to estimate the
attack advantage of RR for various values of $\epsilon$. Being distribution
dependent, this expression leads to much tighter bounds on the attack
advantage. For example at $\epsilon=1$, the bound from [30] is
$1-\frac{2}{1+\epsilon}\approx 0.46$, while for one dataset used in our
experiments we see that the attack advantage for RR at $\epsilon=1$ is only
$0.00095$.

###  3.2 Multiplicative Attack Advantage

The definitions of attack advantage given so far measure the absolute change
in successful reconstruction, 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 $(\mathbf{x},\mathbf{y})$ or
$\mathbf{y}$ given $\mathbf{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
$\mathcal{A}_{\text{informed}}$ and $\mathcal{A}_{\text{uninformed}}$ to Bayes
optimal predictors.

######  Definition 3.6.

Given data distribution $\mathcal{D}$, mechanism $\mathcal{M}$, index $i$, and
pair of labels $a,b\in\mathcal{Y}$, the _multiplicative advantage_ is the
difference of log odds ratios:

$I_{a,b}(\mathcal{M},\mathcal{D},\mathbf{x},z,i)=\log\frac{\pi_{i}(\mathbf{x},z,a)}{\pi_{i}(\mathbf{x},z,b)}-\log\frac{\eta(x_{i},a)}{\eta(x_{i},b)}\,$

where $\eta(x_{i},a)=\operatorname*{\mathbb{P}}(y_{i}=a\,|\,x_{i})$ and
$\pi_{i}(\mathbf{x},z,a)={\operatorname*{\mathbb{P}}}_{\mathbf{y}\sim\mathcal{D}_{\mathcal{Y}|\mathbf{x}}^{m}}\left(y_{i}=a\mid\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y})=z\right)$
is the probability of $y_{i}=a$ after observing the output $z$ of
$\mathcal{M}$. We denote the binary case by $I_{1,0}(\cdot)=I(\cdot)$ and
shorten $\eta(x_{i}):=\eta(x_{i},1)$ and
$\pi_{i}(\mathbf{x},z):=\pi_{i}(\mathbf{x},z,1)$.

This particular formulation has the advantage that
$I_{a,b}(\mathcal{M},\mathcal{D},\mathbf{x},z,i)$ is large in absolute value
whenever there is a large relative change in either label probability.

When $\eta(x_{i})$ and $\pi_{i}(\mathbf{x},z)$ are both less than 1/2 (in the
binary setting), we have
$I(\mathcal{M},\mathcal{D},\mathbf{x},z,i)=\Theta(\log\frac{\pi_{i}(\mathbf{x},z)}{\eta(x_{i})})$,
with a symmetric expression for the case that both are close to 1. Because we
assume i.i.d. sampling, one can easily see that

$I_{a,b}(\mathcal{M},\mathcal{D},\mathbf{x},z,x_{i})=\log\frac{\operatorname*{\mathbb{P}}(\mathcal{M}(\mathbf{x},\mathbf{y})=z\,|\,y_{i}=a,\mathbf{x})}{\operatorname*{\mathbb{P}}(\mathcal{M}(\mathbf{x},\mathbf{y})=z\,|\,y_{i}=b,\mathbf{x})}~{},$

which makes it clear that for $\varepsilon$-label DP mechanisms like
$\mathcal{M}_{\text{RR}}$ (at level $\epsilon$) the above log ratio is at most
$\varepsilon$ in absolute value for all $\mathbf{x}$ and $\mathbf{y}$. On the
other hand, for $\mathcal{M}_{\text{LLP}}$, 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 $\mathcal{D}$ in
which the $\eta(x,a)$ values are not too close to 0 or 1, the leakage
$I_{a,b}(\mathcal{M},\mathcal{D},\mathbf{x},z,x_{i})$ might be small in most
cases.

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. (For example, when running with
$\mathcal{M}_{\text{LLP}}$ 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 $\mathcal{M}_{\text{LLP}}$ in the simple case when the
distribution $\mathcal{D}$ is a product distribution.

######  Theorem 3.7.

Fix a data distribution $\mathcal{D}$ over features and binary labels, let
$p=\operatorname*{\mathbb{P}}_{(x,y)\sim\mathcal{D}}(y=1)$, and assume the
labels are independent of features (i.e., $\mathcal{D}$ is a product of
distributions over $\mathcal{X}$ and $\mathcal{Y}$). Then there are universal
constants $c_{1},c_{2}>0$ such that for $p\in(0,1)$, all bag sizes
$k\geq\frac{c_{1}\ln(1/\delta)}{p(1-p)}$, and all $i\in[k]$ we have

$\operatorname*{\mathbb{P}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}_{\mathcal{Y}|x_{i}}^{m}}\left(\Bigl{|}I_{1,0}(\mathcal{M}_{\text{LLP}},\mathcal{D},\mathbf{x},\mathcal{M}_{\text{LLP}}(\mathbf{x},\mathbf{y}),x_{i})\Bigl{|}>c_{2}\sqrt{\frac{\ln(1/\delta)}{p(1-p)k}}\right)\leq\delta~{}.$

Then, when $k$ is sufficiently large and the conditional label probabilities
$\eta(x_{i})$ are all equal to some constant $p\in(0,1)$, the probability of
failure drops off exponentially as $k$ increases. When working with a data set
of size $m$, we can substitute $\delta=\delta^{\prime}\cdot\frac{k}{m}$ to get
a bound on the probability that any bag in the dataset exhibits extreme values
of leakage $I_{a,b}$. For the setting covered by Theorem 3.7, one gets that
the bags must be of size $k\approx\log(n)/(p(1-p))$ for the probability of
extreme bags to converge towards 0. In the experiments in Section 4, 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 a
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 [11, 18] and practice [28]. Whether used as attacks or empirical
lower bounds on differential privacy parameters [22], these approaches set up
a 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 metrics for testing the hypothesis that a particular individual’s
label is 1 as opposed to 0: 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, [25] use such a test to lower-
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
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].

##  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 a range of privacy parameters. See Appendix C for full
details on our PETs, experimental setup, and additional results.

#### Mechanisms.

We empirically evaluate a number of proposed mechanisms for label privacy:
randomized 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,1]$. The noise scale for both LLP+Lap and
LLP+Geom is chosen so that the PETs satisfy $\epsilon$ 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
postprocessing is to correct for the bias introduced by clipping. We
empirically study these advantage measures on a variety of synthetic and
benchmark datasets, reporting either the AUC vs. advantage trade-off or the
prior-vs-posterior 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
$\eta(x)=\operatorname*{\mathbb{P}}(y=1|x)$. In our synthetic datasets we
compute the advantage measures for different distributions on $\eta(x)$;
however, for non-synthetic data sets, the value of $\eta(x)$ is not explicitly
known. Instead, we estimate $\eta(x)$ for each $x$ by training a classifier
$h$ (without any PETs) and use the prediction probability $h(x)$ as a proxy
for $\eta(x)$. We compute the figure of merit (additive or multiplicative
advantage) for the optimal informed and uninformed attackers using these
estimates.

Figure 1: Prior-posterior scatter plots for LLP, RR, and LLP+Geom from two
synthetic datasets (where the prior $\eta(x)$ is drawn) and the two real-world
datasets (where $\eta(x)$ is approximated). The colors of the dots correspond
to different parameter values for the PETs. For each bag size $k$ and
distribution, we did 1000 independent runs. The further a point is from the
$y=x$ dotted line, the more is revealed about its label as a result of the
PET.

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 a 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$.

#### Results.

Our results are reported in Figures 1, 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 is a relatively balanced dataset, while KDD12 is a quite
imbalanced one.

Figure 1 give scatter plots of prior
$\operatorname*{\mathbb{P}}(y=1\,|\,\mathbf{x})$ vs. posterior
$\operatorname*{\mathbb{P}}(y=1\,|\,\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y})=z)$
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 $\epsilon$
(for RR and LLP+Geom). The behavior of LLP+Lap is reported in Appendix C 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 on 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 a posterior of 0 or 1 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 to
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,1]^{2}$, which correspond to 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 0 labels or 1 labels) become much more likely.

Figure 2: Top: Prior-posterior scatter plots for RR (grey), LLP (blue), and
LLP+Geom (orange) with $\epsilon=1$ and $k=8$ on the same datasets as in
Figure 1. With these choice of parameters, the three mechanisms roughly
achieve the same AUC on Higgs. Middle: Empirical CDFs of (the absolute value
of) the multiplicative advantage for the three PETs on the four datasets.
Bottom: CDFs of the additive advantage.

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 98th-percentile of the
multiplicative measure (so as to 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 ($\epsilon$ for RR, $k$ 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 a 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.

These scatter plots are already suggestive of the expected behavior of the
utility-privacy tradeoff curves that will come next in Figure 3. Given an
allowed level of privacy (as measured by either additive or 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-privacy curve than LLP, with LLP+Geom somewhere in between. A
more detailed comparison between RR and LLP+Geom (or LLP+Lap) is in Appendix
D.

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 Beta(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 ($x=1$) while the CDF of
LLP+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 so 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 a tradeoff
between utility and privacy, since if we cared about privacy alone, the best
strategy would be to release no information at 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 ($\epsilon$ 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
$\epsilon$ for that $k$.

When measuring privacy loss via multiplicative advantage, RR has the best
privacy vs. accuracy tradeoff compared to all other PETs. This is consistent
with the observations in Fig. 2. In particular, the three mechanisms (with the
given parameters) have almost the same AUC on Higgs. Yet when looking at the
CDFs of the multiplicative measure one sees that the two DP mechanisms have
bounded MAs whereas LLP has a significant number of extreme values. This trend
is more pronounced for KDD12 than Higgs. Thus, for the same AUC, LLP has a
higher multiplicative advantage, with a more pronounced gap for KDD12 than for
Higgs. On the other hand, Fig. 2 also shows that the CDFs of the additive
advantage 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.

##  5 Discussion and Conclusions

We study ways to audit label privatization mechanisms for commonly used PETs:
randomized response, 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-
accuracy 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 label uncertainty, which
won’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 semantics might
be valuable and shed light on heuristics used in practice.

## References

  * [1] Chrome privacy sandbox.  https://developers.google.com/privacy-sandbox/relevance/attribution-reporting.
  * [2] Skadnetwork 4 release notes.  https://developer.apple.com/documentation/storekit/skadnetwork/skadnetwork_release_notes/skadnetwork_4_release_notes.
  * [3] Y. W. Aden.  Kdd cup 2012, track 2.  https://kaggle.com/competitions/kddcup2012-track2, 2012.
  * [4] P. Baldi, P. 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 J. Hayes.  Reconstructing training data with informed adversaries.  In 43rd IEEE Symposium 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–630, 2006.
  * [7] R. Bassily, A. Groce, J. 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 Cryptology–ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, 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-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 128–138, 2005.
  * [11] M. Bun, J. Ullman, and S. Vadhan.  Fingerprinting codes and the price of 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-Fekete, A. M. Medina, U. Syed, and S. Vassilvitskii.  Label differential privacy and private training data release.  In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, International Conference on 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, J. Karlin, S. Kumar, A. Muñoz Medina, V. Mirrokni, G. H. Nunes, S. Vassilvitskii, et al.  Measuring re-identification risk.  Proceedings of the ACM on Management of Data, 1(2):1–26, 2023.
  * [15] N. Carlini, S. Chien, M. Nasr, S. Song, A. Terzis, and 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] I. Dinur and K. Nissim.  Revealing information while preserving privacy.  In Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’03, pages 202–210. ACM, 2003.
  * [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. IEEE, 2015.
  * [19] B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, and C. Zhang.  Deep learning with label differential privacy.  Advances in neural information processing systems, 34:27131–27145, 2021.
  * [20] A. Ghosh, T. Roughgarden, and M. Sundararajan.  Universally utility-maximizing 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):e1000167, 2008.
  * [22] M. Jagielski, J. Ullman, and A. Oprea.  Auditing differentially private machine learning: how private is private sgd?  In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
  * [23] Y. Juan, Y. Zhuang, W.-S. Chin, and C.-J. Lin.  Field-aware factorization machines for ctr prediction.  In Proceedings of the 10th ACM conference on recommender systems, pages 43–50, 2016.
  * [24] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  In Y. 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] M. Malek, I. Mironov, K. Prasad, I. Shilov, and F. Tramer.  Antipodes of label differential privacy: Pate and alibi.  In Advances in Neural Information Processing Systems, volume 34, pages 6934–6945, 2021.
  * [26] 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.
  * [27] A. Röllin.  Translated Poisson approximation using exchangeable pair couplings.  The Annals of Applied Probability, 17(5-6):1596 – 1614, 2007.
  * [28] R. Shokri, M. Stronati, C. Song, and V. Shmatikov.  Membership inference attacks against machine learning models.  In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pages 3–18. IEEE Computer Society, 2017.
  * [29] S. L. Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  JASA, pages 63–69, 1965.
  * [30] R. Wu, 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–4347. PMLR, 2023.
  * [31] F. Yu, D. Liu, S. Kumar, T. Jebara, and S. Chang.  $\alpha$-svm for learning with label proportions.  In ICML, Proceedings of the 30th International Conference on Machine Learning, pages 504–512, 2013.

##  Appendix A Proofs for Section 3

We start off by providing a preliminary result that will be useful throughout
all proofs.

###  A.1 Preliminary results

Consider, for a specific $i\in[m]$, the random variables

$\displaystyle f_{1i}(\mathbf{x})$
$\displaystyle=\sup_{\mathcal{A}_{\text{informed}}}\operatorname*{\mathbb{P}}_{\mathbf{y}\sim\mathcal{D}_{\mathcal{Y}|\mathbf{x}}^{k}}(\mathcal{A}_{\text{informed}}(\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y}))_{i}=y_{i}\,|\,\mathbf{x})$
(1) $\displaystyle f_{2i}(\mathbf{x})$
$\displaystyle=\sup_{\mathcal{A}_{\text{unininformed}}}\operatorname*{\mathbb{P}}_{\mathbf{y}\sim\mathcal{D}_{\mathcal{Y}|\mathbf{x}}^{k}}(\mathcal{A}_{\text{uninformed}}(\mathbf{x},\mathcal{M}_{\bot}(\mathbf{x},\mathbf{y}))_{i}=y_{i}\,|\,\mathbf{x})~{}.$

The relevance of $f_{1i}$ and $f_{2i}$ stems from the fact that for the
mechanisms $\mathcal{M}$ we consider in this paper, the advantages
$\operatorname{EAdv}$, $\operatorname{IEAdv}$, and $\operatorname{HPAdv}$ will
be defined in terms of $f_{1i}$ and $f_{2i}$.

######  Lemma A.1.

For any PET $\mathcal{M}$, any $\mathbf{x}\in\mathcal{X}$, any conditional
data distribution $\mathcal{D}_{\mathcal{Y}|\mathbf{x}}$, number of examples
$k$, and $i\in[m]$, we have

$f_{1i}(\mathbf{x})-f_{2i}(\mathbf{x})=\min\\{\eta(x_{i}),1-\eta(x_{i})\\}-\operatorname*{\mathbb{E}}_{\mathbf{y}\sim\mathcal{D}_{\mathcal{Y}|\mathbf{x}}}\biggl{[}\min_{b\in\\{0,1\\}}\bigl{\\{}\operatorname*{\mathbb{P}}(y_{i}=b\mid\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y}))\bigr{\\}}\,|\,\mathbf{x}\biggr{]}~{},$

where $\eta:x\mapsto\operatorname*{\mathbb{P}}(y=1\mid x)$. Moreover, the
optimal (informed) adversary $\mathcal{A}^{*}$ is:

$\mathcal{A}^{*}(\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y}))_{i}:=\begin{cases}1&\text{if
$\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y}))\geq
1/2$}\\\ 0&\text{otherwise}~{}.\end{cases}$

###### Proof.

Set for brevity $z=\mathcal{M}_{\bot}(\mathbf{x},\mathbf{y})$. Since
$\mathcal{M}_{\bot}$ outputs null, and the $(x_{j},y_{j})$ pairs for $j\in[m]$
are independent, we have

$\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},z)=\operatorname*{\mathbb{P}}(y_{i}=1\mid
x_{i})=\eta(x_{i}),$

It immediately follows that the best attacker
$\mathcal{A}_{\text{unininformed}}$ involved in the computation of
$f_{2i}(\mathbf{x})$ is the Bayes optimal predictor

$\hat{y}_{i}=\arg\max_{b\in\\{0,1\\}}\operatorname*{\mathbb{P}}(y_{i}=b\mid
x_{i})$

so that

$f_{2i}(\mathbf{x})=1-\min\\{\eta(x_{i}),1-\eta(x_{i})\\}~{}.$

Let us now turn to $f_{1i}$ and fix any adversary
$\mathcal{A}_{\text{informed}}$. We lower bound the probability that the
adversary makes a mistake on $y_{i}$. Let
$z=\mathcal{M}(\mathbf{x},\mathbf{y})$ be the output of the PET, and
$(\hat{y}_{1},\dots,\hat{y}_{m})=\mathcal{A}_{\text{informed}}(\mathbf{x},z)$
be the output of the adversary. Since $\hat{y}_{i}$ is
$(\mathbf{x},z)$-measurable, we have

$\displaystyle\operatorname*{\mathbb{P}}(\hat{y}_{i}=y_{i}\mid\mathbf{x},z)$
$\displaystyle=\operatorname*{\mathbb{P}}(\hat{y}_{i}=1\mid
y_{i}=1,\mathbf{x},z)\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},z)$
$\displaystyle\qquad+\operatorname*{\mathbb{P}}(\hat{y}_{i}=0\mid
y_{i}=0,\mathbf{x},z)\operatorname*{\mathbb{P}}(y_{i}=0\mid\mathbf{x},z)$
$\displaystyle=\mathds{1}\\{\hat{y}_{i}=1\\}\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},z)+\mathds{1}\\{\hat{y}_{i}=0\\}\operatorname*{\mathbb{P}}(y_{i}=0\mid\mathbf{x},z)~{}.$

Hence

$\displaystyle\operatorname*{\mathbb{P}}(\hat{y}_{i}=y_{i}\,|\,\mathbf{x})$
$\displaystyle={\operatorname*{\mathbb{E}}}_{z|\mathbf{x}}\Bigl{[}\mathds{1}\\{\hat{y}_{i}=1\\}\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},z)+\mathds{1}\\{\hat{y}_{i}=0\\}\operatorname*{\mathbb{P}}(y_{i}=0\mid\mathbf{x},z)\,|\,\mathbf{x}\Bigl{]}$
$\displaystyle\leq{\operatorname*{\mathbb{E}}}_{z|\mathbf{x}}\bigl{[}\max\\{\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},z),\operatorname*{\mathbb{P}}(y_{i}=0\mid\mathbf{x},z)\\}\,|\,\mathbf{x}\bigr{]}$
$\displaystyle={\operatorname*{\mathbb{E}}}_{\mathbf{y}\sim\mathcal{D}_{\mathcal{Y}|\mathbf{x}}}\bigl{[}\max\\{\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y})),\operatorname*{\mathbb{P}}(y_{i}=0\mid\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y}))\\}\,|\,\mathbf{x}\bigr{]}$
$\displaystyle=1-{\operatorname*{\mathbb{E}}}_{\mathbf{y}\sim\mathcal{D}_{\mathcal{Y}|\mathbf{x}}}\bigl{[}\min\\{\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y})),\operatorname*{\mathbb{P}}(y_{i}=0\mid\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y}))\\}\,|\,\mathbf{x}\bigr{]}$
$\displaystyle=f_{1i}(\mathbf{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

$\operatorname{EAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D})={\operatorname*{\mathbb{E}}}_{\mathbf{x}}[f_{1i}(\mathbf{x})-f_{2i}(\mathbf{x})]$
(2)

holds for all $i\in[m]$ since the data sequence
$(x_{1},y_{1}),\ldots,(x_{k},y_{k})$ is i.i.d.

###  A.2 Proof of Theorem 3.2

See 3.2

###### Proof.

For a given $(x_{j},y_{j})$ in the dataset, we can consider without loss of
generality only the size-$k$ bag that $x_{j}$ falls into, and then refer the
indexing to this bag only.

Then set for brevity $\Sigma=k\alpha=\sum_{i=1}^{k}y_{i}$. From (2), we can
write

$\displaystyle\operatorname{EAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D})$
$\displaystyle={\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\min\\{\eta(x_{i}),1-\eta(x_{i})\\}\right]-{\operatorname*{\mathbb{E}}}_{\Sigma}\biggl{[}\min_{b\in\\{0,1\\}}\bigl{\\{}\operatorname*{\mathbb{P}}(y_{i}=b\mid\Sigma)\bigr{\\}}\biggr{]}$
$\displaystyle=\min\\{p,1-p\\}-{\operatorname*{\mathbb{E}}}_{\Sigma}\biggl{[}\min_{b\in\\{0,1\\}}\bigl{\\{}\operatorname*{\mathbb{P}}(y_{i}=b\mid\Sigma)\bigr{\\}}\biggr{]}~{}.$

Since $\operatorname*{\mathbb{P}}(y_{i}=1\,|\,\Sigma)=\alpha$ independent of
$i$ and $p$, the minimum value in the second expectation is

${\operatorname*{\mathbb{E}}}_{\alpha}[\min\\{\alpha,1-\alpha\\}]~{},$

and the claimed equality for
$\operatorname{EAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D})$ follows.

As for the inequality with general $p\in[0,1]$, note that, when $a,b\in[0,1]$,

$\min\\{a,1-a\\}-\min\\{b,1-b\\}\leq|a-b|~{}.$ (3)

If applied to the expression

$\min\\{p,1-p\\}-{\operatorname*{\mathbb{E}}}_{\alpha}[\min\\{\alpha,1-\alpha\\}]$

this gives

$\operatorname{EAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D})\leq{\operatorname*{\mathbb{E}}}_{\alpha}[|\alpha-p|]\leq\sqrt{{\operatorname*{\mathbb{E}}}_{\alpha}[(\alpha-p)^{2}]}=\sqrt{\frac{p(1-p)}{k}}~{},$

where the second inequality is Jensen’s.

Finally, in the case where $|p-1/2|\geq\beta$, for some gap $\beta>0$, we can
proceed through a more direct analysis. Assume $p\leq 1/2-\beta$. We can write

$\displaystyle\min\\{\mathcal{\alpha},1-\mathcal{\alpha}\\}$
$\displaystyle=\min\\{\mathcal{\alpha},1-\mathcal{\alpha}\\}\mathbb{I}\\{\mathcal{\alpha}\leq
1/2\\}+\min\\{\mathcal{\alpha},1-\mathcal{\alpha}\\}\mathbb{I}\\{\mathcal{\alpha}>1/2\\}$
$\displaystyle\qquad+\mathcal{\alpha}\mathbb{I}\\{\mathcal{\alpha}>1/2\\}-\mathcal{\alpha}\mathbb{I}\\{\mathcal{\alpha}>1/2\\}$
$\displaystyle=\mathcal{\alpha}\mathbb{I}\\{\mathcal{\alpha}\leq
1/2\\}+(1-\mathcal{\alpha})\mathbb{I}\\{\mathcal{\alpha}>1/2\\}+\mathcal{\alpha}\mathbb{I}\\{\mathcal{\alpha}>1/2\\}-\mathcal{\alpha}\mathbb{I}\\{\mathcal{\alpha}>1/2\\}$
$\displaystyle=\mathcal{\alpha}-(2\mathcal{\alpha}-1)\mathbb{I}\\{\mathcal{\alpha}>1/2\\}$
$\displaystyle\geq\mathcal{\alpha}-\mathbb{I}\\{\mathcal{\alpha}>1/2\\}~{}.$

Hence

${\operatorname*{\mathbb{E}}}_{\mathcal{\alpha}}[\min\\{\mathcal{\alpha},1-\mathcal{\alpha}\\}]\geq
p-\operatorname*{\mathbb{P}}(\mathcal{\alpha}>1/2)~{}.$

Now, $p<1/2$ implies $\min\\{p,1-p\\}=p$, which leads us to

$\min\\{p,1-p\\}-{\operatorname*{\mathbb{E}}}_{\mathcal{\alpha}}[\min\\{\mathcal{\alpha},1-\mathcal{\alpha}\\}]\leq\operatorname*{\mathbb{P}}(\mathcal{\alpha}>1/2)~{}.$

Finally, by the standard Bernstein inequality we have

$\operatorname*{\mathbb{P}}(\mathcal{\alpha}>1/2)\leq\exp\left(-\frac{k(1/2-p)^{2}}{2p(1-p)+(1-2p)/3}\right)=e^{-\Omega(k\beta^{2})}~{},$

which gives the second inequality.

A similar argument holds if we reverse the assumption on $p$ to $p\geq
1/2+\beta$. ∎

###  A.3 Proof of Theorem 3.3

Again, as in the proof of Theorem 3.2, for a given $(x_{j},y_{j})$ in the
dataset, we can consider with no loss of generality only the size-$k$ bag that
$x_{j}$ falls into, and then refer the indexing to this bag only.

Recall that, for a general distribution $\mathcal{D}$ over
$\mathcal{X}\times\mathcal{Y}$ the distribution of random variable
$k\alpha=\sum_{j=1}^{k}y_{j}$ conditioned on $\mathbf{x}=(x_{1},\ldots,x_{k})$
is Poisson Binomial (PBin) with parameters $\\{\eta(x_{j})\\}_{j=1}^{k}$, that
is, the distribution of the sum of $k$ independent Bernoulli random variables
$y_{j}$, each with its own bias $\eta(x_{j})$, where
$\eta(x)=\operatorname*{\mathbb{P}}(y=1\,|\,x)$.

#### Notation.

For simplicity of notation we let $\eta_{i}=\eta(x_{i})$ be the conditional
positive probability of a label given feature vector $x$ and let
$p=\operatorname*{\mathbb{E}}[\eta_{i}].$ For fixed feature vectors
$\mathbf{x}=(x_{1},\ldots,x_{k},x_{k+1})$, let $A_{i}$ denote a Bernoulli
random variable with mean $\eta_{i}$, and let $Z_{k}=\sum_{j=1}^{k}A_{j}$

We recall the statement of the theorem we want to prove.

See 3.3

The above theorem is a direct consequence of the following Lemma.

######  Lemma A.2.

Let $\mathcal{B}$ denote a bag with $k+1$ elements. Let

$c_{k}=\frac{1}{\sqrt{k}}\left(\frac{1}{3}\log 8k+\frac{1}{6}\sqrt{2\log
8k+12kp(1-p)\log
8k}\right)=\widetilde{O}\left(\sqrt{p(1-p)}+\frac{1}{\sqrt{k}}\right)~{}.$

Then

$\displaystyle\operatorname{EAdv}(\mathcal{M}_{\text{LLP}},\mathcal{D})$
$\displaystyle\leq
k^{1/4}\sqrt{2c_{k}}\sqrt{\left(\frac{1}{e^{3/2}}+\frac{\pi}{4}+\frac{\pi}{e}\right)\frac{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{1/2}}{k^{3/2}}}+\frac{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]}{k}~{}.$

###### Proof.

Set for brevity $\mathcal{M}=\mathcal{M}_{\text{LLP}}(\mathbf{x},\mathbf{y})$.
From (2) we have

$\displaystyle\operatorname{EAdv}$
$\displaystyle(\mathcal{M}_{\text{LLP}},\mathcal{D})$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{k+1}}[\min\\{\eta(x_{k+1}),1-\eta(x_{k+1})\\}]-\operatorname*{\mathbb{E}}_{(\mathbf{x},\mathbf{y})}\left[\min\left\\{\operatorname*{\mathbb{P}}(y_{k+1}=1|\mathbf{x},\mathcal{M}),\operatorname*{\mathbb{P}}(y_{k+1}=0|\mathbf{x},\mathcal{M})\right\\}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{(\mathbf{x},\mathbf{y})}\left[|\eta(x_{k+1})-\operatorname*{\mathbb{P}}(y_{k+1}=1|\mathbf{x},\mathcal{M})|\right]~{},$

where we have again used (3). We now focus on calculating
$\operatorname*{\mathbb{P}}(y_{k+1}=1|\mathbf{x},\mathcal{M})$. Let
$\Sigma=\sum_{j=1}^{k+1}y_{j}$. Note that for a given realization of feature
vector $\mathbf{x}$, $y_{k+1}$ is distributed like $A_{k+1}$ and the output
$\mathcal{M}$ is distributed like $Z_{k+1}$. Therefore:

$\displaystyle\operatorname*{\mathbb{P}}(y_{k+1}=1\,|\,\mathbf{x},\mathcal{M})$
$\displaystyle=\operatorname*{\mathbb{P}}(A_{k+1}=1\,|\,\mathbf{x},Z_{k+1}=\Sigma)$
$\displaystyle=\frac{\operatorname*{\mathbb{P}}(A_{k+1}=1,Z_{k+1}=\Sigma\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(Z_{k+1}=\Sigma\,|\,\mathbf{x})}$
$\displaystyle=\eta_{k+1}\frac{\operatorname*{\mathbb{P}}(Z_{k}=\Sigma-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(Z_{k+1}=\Sigma\,|\,\mathbf{x})}~{}.$

Using this expression in the original expectation we see that we can bound the
advantage as

${\operatorname*{\mathbb{E}}}_{(\mathbf{x},\mathbf{y})}\left[\eta_{k+1}\left|1-\frac{\operatorname*{\mathbb{P}}(Z_{k}=\Sigma-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(Z_{k+1}=\Sigma\,|\,\mathbf{x})}\right|\right]$

Again, note that for a fixed $\mathbf{x}$, the variable $\Sigma$ is
distributed like $Z_{k+1}$. Therefore. taking expectation over $\mathbf{y}$
the above expression can be rewritten as

$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}\Biggl{[}\eta_{k+1}\sum_{s=0}^{k+1}\operatorname*{\mathbb{P}}(Z_{k+1}=s\,|\,\mathbf{x})\times$
$\displaystyle\left|1-\frac{\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(Z_{k+1}=s|\mathbf{x})}\right|\Biggr{]}=$
$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\eta_{k+1}\sum_{s=0}^{k+1}\Bigl{|}\operatorname*{\mathbb{P}}(Z_{k+1}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})\Bigl{|}\right]$

Finally, note that since $Z_{k+1}=Z_{k}+A_{k+1}$ we also have

$\displaystyle\operatorname*{\mathbb{P}}(Z_{k+1}=s\,|\,\mathbf{x})$
$\displaystyle=\operatorname*{\mathbb{P}}(A_{k+1}=1\,|\,\mathbf{x})\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})+\operatorname*{\mathbb{P}}(A_{k+1}=0\,|\,\mathbf{x})\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})$
$\displaystyle=\eta_{k+1}\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})+(1-\eta_{k+1})\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})~{}.$

Therefore, we conclude that the advantage can be bounded by

$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}$
$\displaystyle\left[\eta_{k+1}(1-\eta_{k+1})\sum_{s=0}^{k+1}\Bigl{|}\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})\Bigl{|}\right]=$
$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\eta_{k+1}(1-\eta_{k+1})\right]\,\operatorname*{\mathbb{E}}\left[\sum_{s=0}^{k+1}\Bigl{|}\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})\Bigl{|}\right]~{},$
(4)

where we have used the fact that the random variables $\eta_{i}$ are
independent from each other. Using also the fact that $\eta_{k+1}$ has the
same distribution as $\eta_{1}$ combined with Lemma A.3 below, we have that
the above quantity is bounded by:

$\displaystyle
k^{1/4}\sqrt{2c_{k}}\sqrt{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]^{k}+\frac{\pi\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{1/2}}{4k^{3/2}}+\frac{\pi\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]}{ek^{2}}}$
$\displaystyle+\frac{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]}{k}~{}.$
(5)

Moreover, notice that
$\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]+2\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]=1$.
Therefore
$\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]=1-2\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]$,
and using the fact that $\eta_{1}(1-\eta_{1})\leq\frac{1}{4}$ we have

$\displaystyle\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]^{k}$
$\displaystyle=\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}(1-2\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})])^{k}$
$\displaystyle\leq\max_{\frac{1}{4}\geq x\geq 0}x^{2}(1-2x)^{k}~{}.$

But a simple calculation shows that the above function is maximized at
$x^{\star}_{k}=\min\\{\frac{1}{k+2},1/4\\}$, thus we must have

$\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]^{k}\leq(x^{\star}_{k})^{2}(1-2x^{\star}_{k})^{k}\leq\frac{1}{(ek)^{2}}~{}$

the last inequality holding for all $k\geq 1$. In addition, we have the
trivial bound
$\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]\leq\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}$,
so that

$\displaystyle\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]^{k}$
$\displaystyle\leq\min\left\\{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2},\frac{1}{e^{2}k^{2}}\right\\}$
$\displaystyle\leq\frac{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}}{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}\,e^{2}\,k^{2}+1}$
(using $\min\\{a,b\\}\leq\frac{ab}{a+b}$, with
$a=\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{2}$ and
$b=\frac{1}{e^{2}k^{2}}$)
$\displaystyle\leq\frac{\sqrt{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]}}{e^{3/2}k^{3/2}}$
(using $x^{2}-x^{3/2}+1\geq 0$, with
$x=ek\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]$) .

Replacing this bound in (5) we obtain the following upper bound on the
advantage:

$\displaystyle k^{1/4}\sqrt{2c_{k}}$
$\displaystyle\sqrt{\left(\frac{1}{e^{3/2}}+\frac{\pi}{4}\right)\frac{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{1/2}}{k^{3/2}}+\frac{\pi\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]}{ek^{2}}}+\frac{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]}{k}$
$\displaystyle\leq
k^{1/4}\sqrt{2c_{k}}\sqrt{\left(\frac{1}{e^{3/2}}+\frac{\pi}{4}+\frac{\pi}{e}\right)\frac{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]^{1/2}}{k^{3/2}}}+\frac{\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]}{k}~{},$

as claimed. ∎

######  Lemma A.3.

Let $c_{k}$ be as in Lemma A.2. Then the following bound holds:

$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}$
$\displaystyle\left[\sum_{s=0}^{k+1}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|\right]\leq$
$\displaystyle\frac{1}{k}+k^{1/4}\sqrt{2c_{k}}\sqrt{\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]^{k}+\frac{\pi}{(4\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta)_{1})k)^{3/2}}+\frac{\pi}{e\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]k^{2}}}$

###### Proof.

Let $a>0$ and $b<k$, and let $[a,b]=\\{j\in\mathbb{N}|a\leq j\leq b\\}$. For
any $\mathbf{x}$ we then have

$\displaystyle\sum_{s=0}^{k+1}$
$\displaystyle|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|$
$\displaystyle=\sum_{s\in[a,b]}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|+\sum_{s\notin[a,b]}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1)|$
$\displaystyle\leq\sum_{s\in[a,b]}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|+\sum_{s\notin[a,b]}\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})+\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})$
$\displaystyle\leq\sum_{s\in[a,b]}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|+2\operatorname*{\mathbb{P}}(Z_{k}\notin[a,b]\,|\,\mathbf{x})$

Taking expectation over both sides with respect to $\mathbf{x}$ we have

$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}$
$\displaystyle\left[\sum_{s=0}^{k+1}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|\right]$
$\displaystyle\leq{\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\sum_{s\in[a,b]}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|\right]+2{\operatorname*{\mathbb{E}}}_{\mathbf{x}}[\operatorname*{\mathbb{P}}(Z_{k}\notin[a,b]\,|\,\mathbf{x})]$
(6)

Let now $Q_{k}$ denote the probability measure associated with a binomial
random variable with parameters $(k,p)$. Since $Z_{k}$ is a Poisson-Binomial
random variable with parameters $\eta_{1},\ldots,\eta_{k}$, the probability
$\operatorname*{\mathbb{P}}(Z_{k}\notin[a,b]\,|\,\mathbf{x})$ is a linear
function in each individual $\eta_{i}$, so that
${\operatorname*{\mathbb{E}}}_{\mathbf{x}}[\operatorname*{\mathbb{P}}(Z_{k}\notin[a,b]\,|\,\mathbf{x})]=Q_{k}([a,b]^{c})$.
We now proceed to bound the first expectation in (6). By Cauchy-Schwartz
inequality we have

$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}$
$\displaystyle\left[\sum_{s\in[a,b]}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|\right]$
$\displaystyle\leq{\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\sqrt{(b-a)\sum_{s\in[a,b]}(\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x}))^{2}}\right]$
$\displaystyle\leq{\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\sqrt{(b-a)\sum_{s=0}^{k+1}(\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x}))^{2}}\right]$
$\displaystyle\leq\sqrt{{\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[(b-a)\sum_{s=0}^{k+1}(\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x}))^{2}\right]}~{},$

where the last inequality holds by Jensen’s inequality. Let

$A=\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]\qquad{\mbox{and}}\qquad
B=2\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]~{}.$

By Lemma A.4 below we have that the above term is bounded by

$\sqrt{(b-a)\left(A^{k}+\frac{\pi}{(4Bk)^{3/2}}+\frac{\pi}{eBk^{2}}\right)}~{},$

so that (6) gives

${\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\sum_{s=0}^{k+1}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|\right]\leq
2Q_{k}([a,b]^{c})+\sqrt{(b-a)\left(A^{k}+\frac{\pi}{(4Bk)^{3/2}}+\frac{\pi}{eBk^{2}}\right)}~{}.$

Let $a=\max\\{kp-\sqrt{k}c_{k},0\\}$ and $b=\min\\{kp+\sqrt{k}c_{k},1\\}$. By
Bernstein’s inequality applied to binomial random variables we have that
$Q_{k}([a,b]^{c})=\frac{1}{2k}$. Hence, with this choice of $a$ and $b$ we
obtain

${\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\sum_{s=0}^{k+1}|\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})|\right]\leq\frac{1}{k}+\sqrt{2\sqrt{k}c_{k}}\sqrt{A^{k}+\frac{\pi}{(4Bk)^{3/2}}+\frac{\pi}{eBk^{2}}}~{}.$

The lemma follows by replacing the values of $A$ and $B$. ∎

######  Lemma A.4.

The following inequality holds

$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}$
$\displaystyle\left[\sum_{s=0}^{k+1}(\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x}))^{2}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]^{k}+\frac{\pi}{(8\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]k)^{3/2}}+\frac{\pi}{2e\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]k^{2}}~{}.$

###### Proof.

Let
$p_{s}(\mathbf{x})=\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})$,
for $s=0,\ldots,k+1$. Further, for $k+1\geq u\geq 0$ let
$g_{u}(\mathbf{x})=\frac{1}{\sqrt{k+2}}\sum_{s=0}^{k+1}p_{s}(\mathbf{x})e^{2\pi
i\frac{us}{k+2}}$ denote the discrete Fourier transform. Since, for any
$\mathbf{x}$, the mapping

$\mathbf{p}(\mathbf{x}):=(p_{0}(\mathbf{x}),\ldots,p_{k+1}(\mathbf{x}))\mapsto(g_{1}(\mathbf{x}),\ldots,g_{k+1}(\mathbf{x}):=\mathbf{g}(\mathbf{x})$

is a unitary linear transformation [8] we can write:

$\sum_{s=0}^{k+1}(\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x}))^{2}=\|\mathbf{p}(\mathbf{x})\|^{2}=\|\mathbf{g}(\mathbf{x})\|^{2}=\sum_{u=0}^{k+1}|g_{u}(\mathbf{x})|^{2}.$

Moreover, by Lemma A.5 below we have that

$g_{u}(\mathbf{x})=(1-e^{\frac{2\pi
iu}{k+2}})\frac{1}{\sqrt{k+2}}\prod_{j=1}^{k}(1-\eta_{j}+\eta_{j}e^{\frac{2\pi
iu}{k+2}})$

and therefore

$|g_{u}(\mathbf{x})|^{2}=g_{u}(\mathbf{x})\overline{g_{u}(\mathbf{x})}=\frac{1}{k+2}\left(1-\cos\frac{2\pi
u}{k+2}\right)\prod_{j=1}^{k}\left((1-\eta_{j})^{2}+\eta_{j}^{2}+2\eta_{j}(1-\eta_{j})\cos\frac{2\pi
u}{k+2}\right)~{}.$

Therefore we can write

$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}$
$\displaystyle\left[\sum_{s=0}^{k+1}(\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x}))^{2}\right]$
$\displaystyle=\frac{1}{k+2}{\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\sum_{u=0}^{k+1}\left(1-\cos\frac{2\pi
u}{k+2}\right)\prod_{j=1}^{k}\left((1-\eta_{j})^{2}+\eta_{j}^{2}+2\eta_{j}(1-\eta_{j})\cos\frac{2\pi
u}{k+2}\right)\right]$
$\displaystyle=\frac{1}{k+2}\sum_{u=0}^{k+1}\left(1-\cos\frac{2\pi
u}{k+2}\right)\prod_{j=1}^{k}{\operatorname*{\mathbb{E}}}_{\mathbf{x}}\left[\left((1-\eta_{j})^{2}+\eta_{j}^{2}+2\eta_{j}(1-\eta_{j})\cos\frac{2\pi
u}{k+2}\right)\right]~{},$ (7)

Where we have used the fact that the random variables $\eta_{j}$ are
independent. Finally by linearity of expectation and the fact that $\eta_{j}$
is distributed as $\eta_{1}$ for all $j$, we have

$\displaystyle{\operatorname*{\mathbb{E}}}_{\mathbf{x}}$
$\displaystyle\left[\sum_{s=0}^{k+1}(\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x}))^{2}\right]$
$\displaystyle\frac{1}{k+2}\sum_{u=0}^{k+1}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]+2\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]\cos\frac{2\pi
u}{k+2}\right)^{k}~{}.$ (8)

Applying Proposition A.6 below with
$a=\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]$ and
$b=2\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]$ we have that the above
expression is bounded by

$\operatorname*{\mathbb{E}}[\eta_{1}^{2}+(1-\eta_{1})^{2}]^{k}+\frac{\pi}{(8\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]k)^{3/2}}+\frac{\pi}{2e\operatorname*{\mathbb{E}}[\eta_{1}(1-\eta_{1})]k^{2}}$

which gives the claimed result. ∎

######  Lemma A.5.

Let
$p_{s}(\mathbf{x})=\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})$
and let
$g_{u}(\mathbf{x})=\frac{1}{\sqrt{k+2}}\sum_{s=0}^{k+1}p_{s}(\mathbf{x})e^{\frac{2\pi
ius}{k+2}}$ denote the discrete Fourier transform of
$\mathbf{p}(\mathbf{x})=(p_{1}(\mathbf{x}),\ldots,p_{s}(\mathbf{x}))$. Then

$g_{u}(\mathbf{x})=\frac{1}{\sqrt{k+2}}(1-e^{\frac{2\pi
iu}{k+2}})\prod_{j=1}^{k}(1-\eta_{j}+\eta_{j}e^{\frac{2\pi iu}{k+2}})$

###### Proof.

By definition of $g_{u}(\mathbf{x})$ we have:

$\displaystyle\frac{1}{\sqrt{k+2}}$
$\displaystyle\left(\sum_{s=0}^{k+1}e^{\frac{2\pi
ius}{k+2}}\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-\sum_{s=0}^{k+1}e^{\frac{2\pi
ius}{k+2}}\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})\right)$
$\displaystyle=\frac{1}{\sqrt{k+2}}\left(\sum_{s=0}^{k+1}e^{\frac{2\pi
ius}{k+2}}\operatorname*{\mathbb{P}}(Z_{k}=s\,|\,\mathbf{x})-e^{\frac{2\pi
iu}{k+2}}\sum_{s=0}^{k+1}e^{\frac{2\pi
iu(s-1)}{k+2}}\operatorname*{\mathbb{P}}(Z_{k}=s-1\,|\,\mathbf{x})\right)$
$\displaystyle=\frac{1}{\sqrt{k+2}}(1-e^{\frac{2\pi
iu}{k+2}}){\operatorname*{\mathbb{E}}}_{Z_{k}}[e^{\frac{2\pi
iu}{k+2}Z_{k}}\,|\,\mathbf{x}]$
$\displaystyle=\frac{1}{\sqrt{k+2}}(1-e^{\frac{2\pi
iu}{k+2}})\phi_{Z_{k}\,|\,\mathbf{x}}\left(\frac{2\pi u}{k+2}\right)$

where $\phi_{Z_{k}\,|\,\mathbf{x}}$ denotes the characteristic function of
$Z_{k}$ conditioned on $\mathbf{x}$. Using the fact that
$Z_{k}=\sum_{j=1}^{k}A_{j}$ and that $A_{1},\ldots,A_{k}$ are independent
given $\mathbf{x}$, we have
$\phi_{Z_{k}\,|\,\mathbf{x}}=\prod_{j=1}^{k}\phi_{A_{j}\,|\,x_{j}}$. The
result follows from the fact that $A_{j}$ is a Bernoulli random variable and
therefore $\phi_{A_{j}\,|\,x_{j}}(z)=(1-\eta_{j}+\eta_{j}e^{iz}).$ ∎

######  Proposition A.6.

For any $a,b,k>0$ such that $a+b=1$ we have

$\frac{1}{k+2}\sum_{u=0}^{k+1}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}\leq
a^{k}+\frac{\pi}{(4kb)^{3/2}}+\frac{\pi}{ebk^{2}}$

###### Proof.

Using the fact that $\cos\frac{2\pi u}{k+2}\leq 0$ for
$u\in[(k+2)/4,3(k+2)/4]$ we have that

$\displaystyle\sum_{u=0}^{k+1}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}$
$\displaystyle=\sum_{u=0}^{{k+2}/4}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}$
$\displaystyle\qquad+\sum_{u=(k+2)/4+1}^{3(k+2)/4}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}$
$\displaystyle\qquad+\sum_{u=3(k+2)/4+1}^{k+1}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}$
$\displaystyle\leq(k+2)a^{k}+\sum_{u=0}^{(k+2)/4}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}$
$\displaystyle\qquad+\sum_{u=3(k+2)/4+1}^{k+1}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}$
$\displaystyle=(k+2)a^{k}+2\sum_{u=0}^{(k+2)/4}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}~{},$

where we used the fact that $(1-\cos t)\leq 2$ 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 see that

$\displaystyle\sum_{u=0}^{(k+2)/4}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}$ $\displaystyle\leq
2\pi^{2}\sum_{u=0}^{(k+2)/4}\frac{u^{2}}{(k+2)^{2}}\left(1-4\pi
b\frac{u^{2}}{(k+2)^{2}})\right)^{k}$ $\displaystyle\leq
2\pi^{2}\sum_{u=0}^{(k+2)/4}\frac{u^{2}}{(k+2)^{2}}e^{-4\pi
kb\frac{u^{2}}{(k+2)^{2}}}$

Therefore we conclude that

$\frac{1}{k+2}\sum_{u=0}^{k+1}\left(1-\cos\frac{2\pi
u}{k+2}\right)\left(a+b\cos\frac{2\pi u}{k+2}\right)^{k}\leq
a^{k}+4\pi^{2}\sum_{u=0}^{(k+2)/4}\frac{u^{2}}{(k+2)^{2}}e^{-4\pi
kb\frac{u^{2}}{(k+2)^{2}}}\frac{1}{k+2}~{}.$

Finally, applying Proposition A.7 with $m=k+2$ and $\alpha=4\pi kb$ we can
upper bound the above quantity by:

$a^{k}+4\pi^{2}\left(\frac{\sqrt{\pi}}{4(4\pi kb)^{3/2}}+\frac{1}{4e\pi
bk(k+2)}\right)\leq a^{k}+\frac{\pi}{(4kb)^{3/2}}+\frac{\pi}{ebk^{2}}~{},$

which concludes the proof. ∎

######  Proposition A.7.

Let $m>0$ and $\alpha>0$. Then

$\sum_{u=0}^{m/4}\frac{u^{2}}{m^{2}}e^{-\alpha\frac{u^{2}}{m^{2}}}\frac{1}{m}\leq\frac{\sqrt{\pi}}{4\alpha^{3/2}}+\frac{1}{e\alpha
m}$

###### Proof.

Let $f\colon\mathbb{R}\to\mathbb{R}$ be given by $x\mapsto x^{2}e^{-\alpha
x^{2}}$. Note that the sum we are attempting to bound is then given by:

$\sum_{u=0}^{m/4}f\left(\frac{u}{m}\right)\frac{1}{m}$

Note also that $f$ has a maximum at $x_{0}=\frac{1}{\sqrt{\alpha}}$. Thus $f$
is increasing for $x<x_{0}$ and decreasing otherwise. In particular if

$\sum_{u=0}^{m/4}f\left(\frac{u}{m}\right)\frac{1}{m}=\sum_{u=0}^{\lfloor
x_{0}\rfloor}f\left(\frac{u}{m}\right)\frac{1}{m}+\sum_{u=\lceil
x_{0}\rceil}^{m/4}f\left(\frac{u}{m}\right)\frac{1}{m}:=L+U,$

then $L$ corresponds to a lower Riemman sum for $f$ and
$L\leq\int_{0}^{\frac{\lfloor x_{0}\rfloor+1}{m}}f(x)dx$. Similarly $U$ is an
upper Riemman sum for $f$ and $U\leq\int_{\frac{\lceil
x_{0}\rceil-1}{m}}^{1/4-\frac{1}{m}}f(x)dx$. Therefore we have

$\displaystyle\sum_{u=0}^{m/4}f\left(\frac{u}{m}\right)\frac{1}{m}$
$\displaystyle\leq\int_{0}^{1/4-1/m}x^{2}e^{-\alpha
x^{2}}dx+\int_{\frac{\lceil x_{0}\rceil-1}{m}}^{\frac{\lfloor
x_{0}\rfloor+1}{m}}f(x)dx$ $\displaystyle\leq\int_{0}^{\infty}x^{2}e^{-\alpha
x^{2}}+\frac{1}{m}\max_{x}f(x)$
$\displaystyle=\frac{\sqrt{\pi}}{4\alpha^{3/2}}+\frac{1}{e\alpha m}~{},$

as claimed. ∎

######  Proposition A.8.

The following inequality holds for any $t\in[0,1/4]$:

$1-2(\pi t)^{2}\leq\cos 2\pi t\leq 1-4\pi t^{2}$

###### Proof.

For the lower bound we start from the fact that for any $x\geq 0$ it is well
known that

$\sin 2\pi x\leq 2\pi x.$

Integrating this inequality from $[0,t]$ we have that $\int_{0}^{t}\sin 2\pi
x\leq\pi t^{2}$. Since $\int_{0}^{t}\sin 2\pi x=\frac{1}{2\pi}(1-\cos 2\pi t)$
the lower bound follows.

For the upper bound we proceed in a similar fashion. By the fact that $\sin
2\pi x$ is concave for $x\in[0,1/4]$ we have that

$\sin 2\pi x=\sin 2\pi((1-4x)\cdot 0+4x\cdot\frac{1}{4})\geq(1-4x)\sin
0+4x\sin\frac{\pi}{2}=4x.$

Again integrating the above inequality from $0$ to $t$ we have $\frac{1-\cos
2\pi t}{2\pi}\geq 2t^{2}$. ∎

###  A.4 Proof of Theorem 3.4

###### Proof.

The proof follows the same argument of the proof used in 3.3, where we see
that, in view of the factorization in Equation 4 we may bound the individual
expected advantage as:

$\operatorname{IEAdv}(\mathcal{M},\mathcal{D},x_{k+1})\leq\eta(x_{k+1})(1-\eta(x_{k+1})\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\left[\sum_{s=0}^{k}|P(Z_{k}=s|\mathbf{x})-P(Z_{k}=s-1|\mathbf{x})|\right]~{}.$

But from Lemma A.3 it follows that this can be bounded by

$\displaystyle\mu_{i}\,O\left((p(1-p))^{1/4}\sqrt{(1-2\mu)^{k}k^{1/2}+\frac{1}{\mu^{3/2}k}}+\sqrt{\frac{(1-2\mu)^{k}}{k^{1/2}}+\frac{1}{\mu^{3/2}k^{2}}}\right)~{}.$

Now, since $(1-2\mu)^{k}k^{1/2}<\frac{\mu}{k}$ for
$k\geq\frac{2}{\mu}\log\left(\frac{1}{\mu}\right)$, we upper bound accordingly
the two terms involving $(1-2\mu)^{k}$, 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

$f_{1}(\mathbf{x})=\sup_{\mathcal{A}_{\text{informed}}}\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\mathbf{y}\sim\mathcal{D}^{m}_{\mathcal{Y}|\mathbf{x}}\\\
i\sim\text{Uniform}([m])\\\ \text{coins of
}\mathcal{M}\end{subarray}}(\mathcal{A}_{\text{informed}}(\mathbf{x},\mathcal{M}(\mathbf{x},\mathbf{y}))_{i}=y_{i}\,|\,\mathbf{x})$

and

$f_{2}(\mathbf{x})=\sup_{\mathcal{A}_{\text{uninformed}}}\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\mathbf{y}\sim\mathcal{D}^{m}_{\mathcal{Y}|\mathbf{x}}\\\
i\sim\text{Uniform}([m])\\\ \text{coins of
}\mathcal{M}\end{subarray}}(\mathcal{A}_{\text{uninformed}}(\mathbf{x},\mathcal{M}_{\bot}(\mathbf{x},\mathbf{y}))_{i}=y_{i}\,|\,\mathbf{x})$

Specifically, we define

$\displaystyle\operatorname{HPAdv}(\mathcal{M},\mathcal{D},\theta)=\operatorname*{\mathbb{P}}_{\mathbf{x}\sim\mathcal{D}_{\mathcal{X}}^{m}}\left(f_{1}(\mathbf{x})-f_{2}(\mathbf{x}))>\theta\right)~{},$

viewed as a function of $\theta\in[0,1]$, which we call the _H igh Probability
attack Advantage_ (at level $\theta$). This is simply a high-probability
version of $\operatorname{EAdv}(\mathcal{A},\mathcal{M},\mathcal{D})$ over the
generation of $\mathbf{x}$. A similar high-probability version can be defined
for the individual version of the attack advantage.

We begin by observing that in the special case of $\mathcal{M}_{\text{RR}}$,
we have
$\operatorname{IEAdv}_{1}(\mathcal{M}_{\text{RR}},\mathcal{D},x_{1})=f_{1}(\mathbf{x})-f_{2}(\mathbf{x})$,
so that the high probability bound involved in the computation of
$\operatorname{HPAdv}(\mathcal{M}_{\text{RR}},\mathcal{D},\theta)$ is a direct
consequence of the tail properties of the function
$\eta(x_{1})=\operatorname*{\mathbb{P}}(y_{1}=1\,|\,x_{1})$ as applied to the
expression for
$\operatorname{IEAdv}_{1,1}(\mathcal{M}_{\text{RR}},\mathcal{D},x_{1})$ in
Theorem A.17. Thus, for $\mathcal{M}_{\text{RR}}$, the connection from
$\operatorname{IEAdv}$ to $\operatorname{HPAdv}$ is immediate.

We continue with studying $\operatorname{HPAdv}$ for
$\mathcal{M}_{\text{LLP}}$. We have the following bound.

######  Theorem A.9.

Under the same assumptions and notation as in Theorem 3.3 (main body) there
are universal constants $c_{1},c_{2}>0$ such that, for $k=\Omega(1/\mu)$,

$\displaystyle\operatorname{HPAdv}\left(\mathcal{M}_{\text{LLP}},\mathcal{D},c_{1}\sqrt{\frac{\mu}{k}}\right)\leq(k+1)\,e^{-c_{2}\,k\mu}~{}.$

In order to prove this theorem, we first need ancillary results related to
Poisson Binomial distributions.

We denote a Poisson Binomial distribution with parameters
$\\{\eta_{1},\dots,\eta_{k}\\}$ by $\text{PBin}(\eta_{1},\dots,\eta_{k})$.

######  Lemma A.10.

Let $s,\Sigma\sim\text{PBin}(\eta_{1},\dots,\eta_{k})$,
$\Sigma^{(1)}\sim\text{PBin}(\eta_{2},\dots,\eta_{k})$, where
$\eta_{1},\ldots,\eta_{k}\in[0,1]$ are such that

$\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})\geq 1~{}.$

Then

$\displaystyle{\operatorname*{\mathbb{E}}}_{s}\Biggl{[}\Biggl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s)-\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s-1)}{\operatorname*{\mathbb{P}}(\Sigma=s)}\Biggl{|}\Biggl{]}\leq\frac{9}{\sqrt{\sum_{i=2}^{k}\eta_{i}(1-\eta_{i})}}~{}.$

###### Proof.

We will use the following distribution to approximate Poisson Binomial
distributions.

######  Definition A.11.

[27] We say that an integer random variable $Y$ is distributed according to
the translated Poisson distribution with parameters $\mu$ and $\sigma^{2}$,
denoted $\text{TP}(\mu,\sigma^{2})$, if and only if $Y$ can be written as

$Y=\lfloor\mu+\sigma^{2}\rfloor+Z,$

where $Z$ is a random variable distributed according to
$\text{Poisson}(\sigma^{2}+\\{\mu-\sigma^{2}\\})$, being
$\\{\mu-\sigma^{2}\\}$ the fractional part of $\mu-\sigma^{2}$, and
$\lfloor\mu+\sigma^{2}\rfloor$ the integer part of $\mu+\sigma^{2}$.

Let us then define two random variables $\Gamma$ and $\Gamma^{(1)}$. Variable
$\Gamma$ is $\text{TP}(\mu,\sigma^{2})$ with $\mu=\sum_{i=1}^{k}\eta_{i}$ and
$\sigma^{2}=\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})$, while $\Gamma^{(1)}$ is
$\text{TP}(\mu_{1},\sigma^{2}_{1})$, where $\mu_{1}=\sum_{i=2}^{k}\eta_{i}$
and $\sigma^{2}_{1}=\sum_{i=2}^{k}\eta_{i}(1-\eta_{i})$.

Let $d_{\text{TV}}$ denote the total variation distance. We can write

$\displaystyle{\operatorname*{\mathbb{E}}}_{s}\Biggl{[}\Biggl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s)-\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s-1)}{\operatorname*{\mathbb{P}}(\Sigma=s)}\Biggl{|}\Biggl{]}$
$\displaystyle=\sum_{s=0}^{k}\operatorname*{\mathbb{P}}(\Sigma=s)\times\Biggl{[}\Biggl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s)-\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s-1)}{\operatorname*{\mathbb{P}}(\Sigma=s)}\Biggl{|}\Biggl{]}$
$\displaystyle=\sum_{s=0}^{k}\Biggl{|}\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s)-\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s-1)\Biggl{|}$
$\displaystyle\leq\sum_{s=0}^{k}\Biggl{|}\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s)-\operatorname*{\mathbb{P}}(\Gamma=s)\Biggl{|}+\sum_{s=0}^{k}\Biggl{|}\operatorname*{\mathbb{P}}(\Gamma=s)-\operatorname*{\mathbb{P}}(\Gamma^{(1)}=s-1)\Biggl{|}$
$\displaystyle\qquad+\sum_{s=0}^{k}\Biggl{|}\operatorname*{\mathbb{P}}(\Gamma^{(1)}=s-1)-\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s-1)\Biggl{|}$
(9) $\displaystyle\leq
d_{\text{TV}}(\Sigma,\Gamma)+\sum_{s=0}^{k}\Biggl{|}\operatorname*{\mathbb{P}}(\Gamma=s)-\operatorname*{\mathbb{P}}(\Gamma^{(1)}=s-1)\Biggl{|}+d_{\text{TV}}(\Sigma^{(1)},\Gamma^{(1)})$
$\displaystyle\leq\frac{\sqrt{\sum_{i=1}^{k}\eta_{i}^{3}(1-\eta_{i})}+2}{\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})}+\frac{\sqrt{\sum_{i=2}^{k}\eta_{i}^{3}(1-\eta_{i})}+2}{\sum_{i=2}^{k}\eta_{i}(1-\eta_{i})}$
(10)
$\displaystyle\qquad+\sum_{s=0}^{k}\Biggl{|}\operatorname*{\mathbb{P}}(\Gamma=s)-\operatorname*{\mathbb{P}}(\Gamma^{(1)}=s-1)\Biggl{|}$
$\displaystyle\leq\frac{3}{\sqrt{\sigma}}+\frac{3}{\sqrt{\sigma_{1}}}+\sum_{s=0}^{k}\Biggl{|}\operatorname*{\mathbb{P}}(\Gamma=s)-\operatorname*{\mathbb{P}}(\Gamma^{(1)}=s-1)\Biggl{|}~{},$
(11)

where (9) follows from the triangle inequality, (10) follows from Lemma A.12
below, and (11) follows from the overapproximation

$\frac{\sqrt{\sum_{i=1}^{k}\eta_{i}^{3}(1-\eta_{i})}+2}{\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})}\leq\frac{\sqrt{\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})}+2}{\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})}\leq\frac{3}{\sqrt{\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})}}~{},$

the latter inequality exploiting the condition
$\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})\geq 1$.

######  Lemma A.12.

[[27], see (3.4) therein] Let $J_{1},\dots,J_{k}$ be independent random
Bernoulli with parameters $p_{1},\dots,p_{k}$. Then

$d_{\text{TV}}\left(\sum_{i=1}^{k}J_{i},\text{TP}(\mu,\sigma^{2})\right)\leq\frac{\sqrt{\sum_{i=1}^{k}p_{i}^{3}(1-p_{i})}+2}{\sum_{i=1}^{k}p_{i}(1-p_{i})}$

where $\mu=\sum_{i=1}^{k}p_{i}$ and $\sigma^{2}=\sum_{i=1}^{k}p_{i}(1-p_{i})$.

We recall a lemma which will be useful to upper bound the last term in (11).

######  Lemma A.13.

[6] For $\mu_{1},\mu_{2}\in\mathbb{R}$ and
$\sigma^{2}_{1},\sigma_{2}^{2}\in\mathbb{R}_{+}$ such that
$\lfloor\mu_{1}-\sigma_{1}^{2}\rfloor\leq\lfloor\mu_{2}-\sigma_{2}^{2}\rfloor$,
it holds that

$d_{\text{TV}}\Big{(}\text{TP}(\mu_{1},\sigma_{1}^{2}),\text{TP}(\mu_{2},\sigma_{2}^{2})\Big{)}\leq\frac{|\mu_{1}-\mu_{2}|}{\sigma_{1}}+\frac{|\sigma_{1}^{2}-\sigma_{2}^{2}|+1}{\sigma_{1}^{2}}\enspace.$

We will need the following technical lemma as well.

######  Lemma A.14.

For $\mu\in\mathbb{R}$ and $\sigma_{1}^{2},\sigma_{2}^{2}\in\mathbb{R}_{+}$,
let us define $X_{1}\sim\text{TP}(\mu,\sigma^{2}_{1})$ and
$X_{2}\sim\text{TP}(\mu+1,\sigma^{2}_{2})$. Then

$\operatorname*{\mathbb{P}}(X_{1}=\ell-1)=\operatorname*{\mathbb{P}}(X_{2}=\ell)$

for all $\ell\in\mathbb{Z}$.

###### Proof of Lemma A.14.

One has to observe that Translated Poisson distribution is equivalent to a
Poisson distribution with parameter $\delta$ where $\delta=\mu-\gamma$ and
$\gamma=\lfloor\mu-\sigma^{2}\rfloor$, but it is shifted by $\gamma$.
Moreover, note that $\gamma+1=\lfloor\mu+1-\sigma^{2}\rfloor$, thus
$\delta+1=\mu-\gamma+1$. This observation implies the claim with $\mu+1$. ∎

We continue by using both Lemma A.13 and Lemma A.14. Define
$\Gamma^{(2)}\sim\text{TP}(\mu_{1}+1,\sigma^{2}_{1})$. We can write

$\displaystyle\sum_{s=0}^{k}\Biggl{|}\operatorname*{\mathbb{P}}(\Gamma=s)-\operatorname*{\mathbb{P}}(\Gamma^{(1)}=s-1)\Biggl{|}$
$\displaystyle=\sum_{s=0}^{k}\Biggl{|}\operatorname*{\mathbb{P}}(\Gamma=s)-\operatorname*{\mathbb{P}}(\Gamma^{(2)}=s)\Biggl{|}$
$\displaystyle=d_{\text{TV}}\Big{(}\text{TP}(\mu,\sigma^{2}),\text{TP}(\mu_{1}+1,\sigma_{1}^{2})\Big{)}$
$\displaystyle\leq\frac{|\mu-\mu_{1}-1|}{\sigma}+\frac{|\sigma^{2}-\sigma_{1}^{2}|+1}{\sigma^{2}}$
(from Lemma A.13)
$\displaystyle=\frac{1-\eta_{1}}{\sigma}+\frac{\eta_{1}(1-\eta_{1})+1}{\sigma^{2}}$
$\displaystyle\leq\frac{3}{\sqrt{\sigma}}~{},$

the latter inequality using again the condition
$\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})\geq 1$.

Piecing together gives

$\displaystyle{\operatorname*{\mathbb{E}}}_{s}\Biggl{[}\Biggl{|}1-\frac{\operatorname*{\mathbb{P}}(\Sigma^{(1)}=s-1)}{\operatorname*{\mathbb{P}}(\Sigma=s)}\Biggl{|}\Biggl{]}\leq\frac{6}{\sqrt{\sigma}}+\frac{3}{\sqrt{\sigma_{1}}}\leq\frac{9}{\sqrt{\sigma_{1}}}~{}.$

This concludes the proof. ∎

With these results handy, we are ready to prove Theorem A.9. Recall the
functions $f_{1}(\mathbf{x})$ and $f_{2}(\mathbf{x})$ defined in the main
body.

###### Proof of Theorem A.9.

Let $\Sigma=\sum_{j=1}^{k}y_{j}$. From Lemma A.1, we see that

$f_{1}(\mathbf{x})=1-\frac{1}{k}\sum_{i=1}^{k}{\operatorname*{\mathbb{E}}}_{\mathbf{y}\sim\mathcal{D}_{\mathcal{Y}|\mathbf{x}}}\biggl{[}\min_{b\in\\{0,1\\}}\bigl{\\{}\operatorname*{\mathbb{P}}(y_{i}=b\mid\mathbf{x},\Sigma\bigr{\\}}\,|\,\mathbf{x}\biggr{]}$

and

$f_{2}(\mathbf{x})=1-\frac{1}{k}\sum_{i=1}^{k}\min\\{\eta(x_{i}),1-\eta(x_{i})\\}$

so that

$\displaystyle f_{1}(\mathbf{x})-f_{2}(\mathbf{x})$
$\displaystyle=\frac{1}{k}\sum_{i=1}^{k}\left(\min\\{\eta(x_{i}),1-\eta(x_{i})\\}-{\operatorname*{\mathbb{E}}}_{\mathbf{y}\sim\mathcal{D}_{\mathcal{Y}|\mathbf{x}}}\biggl{[}\min_{b\in\\{0,1\\}}\bigl{\\{}\operatorname*{\mathbb{P}}(y_{i}=b\mid\mathbf{x},\Sigma\bigr{\\}}\,|\,\mathbf{x}\biggr{]}\right)$
$\displaystyle\leq\frac{1}{k}\sum_{i=1}^{k}\left|\eta(x_{i})-{\operatorname*{\mathbb{P}}}_{\Sigma|\mathbf{x}}(y_{i}=1\mid\Sigma,\mathbf{x})\right|~{},$

where in the inequality we have again used (3).

But, for any given $s\in\\{0,1,\ldots,k\\}$,

$\displaystyle\operatorname*{\mathbb{P}}(y_{i}=1\,|\,\Sigma=s,\mathbf{x})$
$\displaystyle=\operatorname*{\mathbb{P}}(y_{i}=1\,|\,\mathbf{x})\,\frac{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,y_{i}=1,\mathbf{x})}{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,\mathbf{x})}$
$\displaystyle=\eta(x_{i})\,\frac{\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,\mathbf{x})}$
$\displaystyle=\eta(x_{i})\,\frac{\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})}{\eta(x_{i})\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})+(1-\eta(x_{i}))\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s\,|\,\mathbf{x})}$

where $\Sigma^{(-i)}=\sum_{j:j=1,j\neq i}^{k}y_{j}~{}.$

Hence

$\displaystyle
f_{1}(\mathbf{x})-f_{2}(\mathbf{x})\leq\frac{1}{k}\sum_{i=1}^{k}\eta(x_{i})(1-\eta(x_{i})){\operatorname*{\mathbb{E}}}_{s}\Bigl{[}\Bigl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,\mathbf{x})}\Bigl{|}\,|\,\mathbf{x}\Bigl{]}~{},$
(12)

where $s$ (conditioned on $\mathbf{x}$) is distributed as
$\text{PBin}(\eta(x_{1}),\ldots,\eta(x_{k}))$. Set for brevity
$\mu=\operatorname*{\mathbb{E}}[\eta(x)(1-\eta(x)]$, and introduce the short-
hand notation

$C_{\beta,i}=C_{\beta}(\mathbf{x}^{(-i)})=\mathbb{I}\Bigl{\\{}\sum_{j:j=1,j\neq
i}^{k}\eta(x_{j})(1-\eta(x_{j}))\leq(k-1)\mu-\beta\Bigl{\\}}~{},$

for some $\beta\in[0,(k-1)\mu)$ to be specified. In the above
$\mathbf{x}^{(-i)}$ denotes $\mathbf{x}$ with its $i$-th item $x_{i}$ removed.

We have

$\displaystyle\eta(x_{i})(1-\eta(x_{i}))$
$\displaystyle{\operatorname*{\mathbb{E}}}_{s}\Bigl{[}\Bigl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,\mathbf{x})}\Bigl{|}\,|\,\mathbf{x}\Bigl{]}$
$\displaystyle=C_{\beta,i}\eta(x_{i})(1-\eta(x_{i})){\operatorname*{\mathbb{E}}}_{s}\Bigl{[}\Bigl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,\mathbf{x})}\Bigl{|}\,|\,\mathbf{x}\Bigl{]}$
$\displaystyle\qquad+(1-C_{\beta,i})\eta(x_{i})(1-\eta(x_{i})){\operatorname*{\mathbb{E}}}_{s}\Bigl{[}\Bigl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,\mathbf{x})}\Bigl{|}\,|\,\mathbf{x}\Bigl{]}$
$\displaystyle\leq
C_{\beta,i}+(1-C_{\beta,i})\eta(x_{i})(1-\eta(x_{i})){\operatorname*{\mathbb{E}}}_{s}\Bigl{[}\Bigl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,\mathbf{x})}\Bigl{|}\,|\,\mathbf{x}\Bigl{]}~{},$

since

$\eta(x_{i})(1-\eta(x_{i})){\operatorname*{\mathbb{E}}}_{s}\Bigl{[}\Bigl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,\mathbf{x})}\Bigl{|}\,|\,\mathbf{x}\Bigl{]}\leq
1~{}.$

for every $i$ and every realization $\mathbf{x}$.

On the other hand, a closer look at term

$(1-C_{\beta,i}){\operatorname*{\mathbb{E}}}_{s}\Bigl{[}\Bigl{|}\frac{\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s\,|\,\mathbf{x})-\operatorname*{\mathbb{P}}(\Sigma^{(-i)}=s-1\,|\,\mathbf{x})}{\operatorname*{\mathbb{P}}(\Sigma=s\,|\,\mathbf{x})}\Bigl{|}\,|\,\mathbf{x}\Bigl{]}~{}$

reveals that we are in a position to apply Lemma A.10. This allows us to
conclude that this expectation is upper bounded by111 The condition
$\sum_{i=1}^{k}\eta_{i}(1-\eta_{i})\geq 1$ therein is implied by
$C_{\beta,i}(\mathbf{x}^{(-i)})=0$, which is equivalent to $(k-1)\mu\geq
1+\beta$. This, in turn, given our choice of $\beta$, will read as
$k=\Omega(1/\mu)$.

$\frac{9(1-C_{\beta,i})}{\sqrt{\sum_{j:j\neq
i,j=1}^{k}\eta(x_{j})(1-\eta(x_{j}))}}$

for every realization of $\mathbf{x}$. Using the definition of $C_{\beta,i}$
the above can be further upper bounded by

$\frac{9}{\sqrt{(k-1)\mu-\beta}}~{}.$

Putting together, we have obtained

$\displaystyle f_{1}(\mathbf{x})-f_{2}(\mathbf{x})$
$\displaystyle\leq\frac{1}{k}\sum_{i=1}^{k}\left(C_{\beta,i}+\frac{9\eta(x_{i})(1-\eta(x_{i}))}{\sqrt{(k-1)\mu-\beta}}\right)$
$\displaystyle=\frac{1}{k}\sum_{i=1}^{k}C_{\beta,i}+\frac{9\sum_{i=1}^{k}\eta(x_{i})(1-\eta(x_{i}))}{k\sqrt{(k-1)\mu-\beta}}$

for every $\mathbf{x}$. Now, from the standard Bernstein inequality,222 Note
that we are upper bounding the second moments of the random variables
$\eta(x_{i})(1-\eta(x_{i}))$ with their first moment $\mu$, since the
variables $\eta(x_{i})(1-\eta(x_{i}))$ are in $[0,1/4]$.

${\operatorname*{\mathbb{P}}}_{\mathbf{x}\sim\mathcal{D}_{\mathcal{X}}}\left(C_{\beta,i}=0\,\,\forall\,i\right)\geq
1-k\,e^{-\frac{\beta^{2}}{2k\mu+\beta/6}}$

and

${\operatorname*{\mathbb{P}}}_{\mathbf{x}\sim\mathcal{D}_{\mathcal{X}}}\left(\sum_{i=1}^{k}\eta(x_{i})(1-\eta(x_{i}))\leq
k\mu+\beta\right)\geq 1-e^{-\frac{\beta^{2}}{2k\mu+\beta/6}}$

for every $\beta>0$. This yields

${\operatorname*{\mathbb{P}}}_{\mathbf{x}\sim\mathcal{D}_{\mathcal{X}}}\left(f_{1}(\mathbf{x})-f_{2}(\mathbf{x})>\frac{9(k\mu+\beta)}{k\sqrt{(k-1)\mu-\beta}}\right)\leq(k+1)\,e^{-\frac{\beta^{2}}{2k\mu+\beta/6}}$
(13)

holding for $0\leq\beta<(k-1)\mu$.

One can easily see that choosing $\beta=(k-1)\mu/2$ yields, when
$k=\Omega(1/\mu)$,

${\operatorname*{\mathbb{P}}}_{\mathbf{x}\sim\mathcal{D}_{\mathcal{X}}}\left(f_{1}(\mathbf{x})-f_{2}(\mathbf{x})=\Omega\left(\sqrt{\frac{\mu}{k}}\right)\right)\leq
k\,e^{-\Theta(k\mu)}~{},$

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 $\mathbf{x}=(x_{1},\ldots,x_{m})$. For
instance, combining Lemma A.10 with Eq. (12), one can easily derive a bound of
the form

$f_{1}(\mathbf{x})-f_{2}(\mathbf{x})=O\left(\frac{1}{k}\sum_{i=1}^{k}\frac{\eta(x_{i})(1-\eta(x_{i}))}{\sqrt{\sum_{j:j\neq
i}\eta(x_{j})(1-\eta(x_{j}))}}\right)~{}.$

Then, in order for this bound to be of the form $1/\sqrt{k}$, we need to make
further assumptions on the function
$x\rightarrow\operatorname*{\mathbb{P}}(y=1|x)$, the most obvious one being
$\operatorname*{\mathbb{P}}(y=1|x)\in(0,1)$ (bounded away from 0 and 1) for
all $x$.

###  A.6 The advantage of RR is independent of the number of examples

######  Lemma A.16.

For all data distributions $\mathcal{D}$, all $x_{i}$, and all datasets $S$ of
size $m$, $\operatorname{IEAdv}(\mathcal{M}_{\text{RR}},\mathcal{D},x_{i})$ is
independent of $m$, and so is
$\operatorname{EAdv}(\mathcal{M}_{\text{RR}},\mathcal{D})$.

###### Proof.

Fix any $m$, any $x_{i}$, and any data distribution $\mathcal{D}$. Then, by
Lemma A.1,

$\displaystyle\operatorname{IEAdv}(\mathcal{M}_{\text{RR}},\mathcal{D},x_{i})=\min\\{\eta(x_{i}),1-\eta(x_{i})\\}$
(14)
$\displaystyle\quad-\operatorname*{\mathbb{E}}_{y_{i}\sim\mathcal{D}_{\mathcal{Y}|x_{i}}}\biggl{[}\min\biggl{\\{}\operatorname*{\mathbb{P}}_{(\mathbf{x}^{(-i)},\mathbf{y}^{(-i)})}(y_{i}=1\mid\mathbf{x},\mathcal{M}_{\text{RR}}(\mathbf{x},\mathbf{y})),\operatorname*{\mathbb{P}}_{(\mathbf{x}^{(-i)},\mathbf{y}^{(-i)})}(y_{i}=0\mid\mathbf{x},\mathcal{M}_{\text{RR}}(\mathbf{x},\mathbf{y}))\biggr{\\}}\Bigr{|}\,x_{i}\biggr{]}~{}.$

The first term already has no dependence on $m$. We focus on the second term.

The key to this proof is that a noisy label $RR(y_{i})=\tilde{y}_{i}$ is
independent of the other true labels $y_{j},j\neq i$. Thus, we have

$\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},\mathcal{M}_{\text{RR}}(\mathbf{x},\mathbf{y}))=\operatorname*{\mathbb{P}}(y_{i}=1\mid\mathbf{x},\mathcal{M}_{\text{RR}}(\mathbf{x},\mathbf{y})_{i})=\operatorname*{\mathbb{P}}(y_{i}=1\mid
x_{i},\mathcal{M}_{\text{RR}}(x_{i},y_{i}))~{}.$

Applying this to (14), we have

$\displaystyle\operatorname*{\mathbb{E}}_{y_{i}\sim\mathcal{D}_{\mathcal{Y}|x_{i}}}\biggl{[}\min\biggl{\\{}\operatorname*{\mathbb{P}}_{(\mathbf{x}^{(-i)},\mathbf{y}^{(-i)})}(y_{i}=1\mid\mathbf{x},\mathcal{M}_{\text{RR}}(\mathbf{x},\mathbf{y})),\operatorname*{\mathbb{P}}_{(\mathbf{x}^{(-i)},\mathbf{y}^{(-i)})}(y_{i}=0\mid\mathbf{x},\mathcal{M}_{\text{RR}}(\mathbf{x},\mathbf{y}))\biggr{\\}}\mid
x_{i}\biggr{]}$
$\displaystyle=\operatorname*{\mathbb{E}}_{y_{i}\sim\mathcal{D}_{\mathcal{Y}|x_{i}}}\biggl{[}\min\bigl{\\{}\operatorname*{\mathbb{P}}(y_{i}=1\mid
x_{i},\mathcal{M}_{\text{RR}}(x_{i},y_{i})),\operatorname*{\mathbb{P}}(y_{i}=0\mid
x_{i},\mathcal{M}_{\text{RR}}(x_{i},y_{i}))\bigr{\\}}\mid x_{i}\biggr{]}.$

Plugging this back into (14) gives us
$\operatorname{EAdv}_{1}(\mathcal{M}_{\text{RR}},\mathcal{D})$ as desired.
Taking the expectation over $x_{i}\sim\mathcal{D}_{\mathcal{X}}$ completes the
proof of the second claim. ∎

###  A.7 Proof of Theorem 3.5

We prove a more verbose version of Theorem 3.5 which includes the optimal
adversary:

######  Theorem A.17.

For any data distribution $\mathcal{D}$, the individual expected attack
advantage for randomized response with privacy parameter
$\pi=\frac{1}{1+e^{\varepsilon}}$ is

$\displaystyle\operatorname{IEAdv}(\mathcal{M}_{\text{RR}},\mathcal{D},x_{1})=\bigl{(}\min\\{\eta(x_{1}),1-\eta(x_{1})\\}-\pi\bigl{)}\cdot\mathbb{I}\\{\eta(x_{1})\in[\pi,1-\pi]\\}.$

The optimal adversary maximizing
$\operatorname{IEAdv}_{1}(\mathcal{M}_{\text{RR}},\mathcal{D},x_{1})$ is

$\mathcal{A}^{*}(x_{1},\tilde{y_{1}})=\begin{cases}1,&\text{if}~{}\eta(x_{1})>1-\pi\\\
0,&\text{if}~{}\eta(x_{1})<\pi\\\
\tilde{y_{1}},&\text{otherwise}~{}.\end{cases}$

In words, upon receiving $x_{1}$, the optimal attacker $\mathcal{A}^{*}$
predicts the associated label $y_{1}$ as the noisy label $\tilde{y}_{1}$ if
the distribution $\mathcal{D}$ contains enough uncertainty about $y_{1}$ (the
condition $\eta(x_{1})\in[\pi,1-\pi]$ holds) given the extra noise level $\pi$
injected. Otherwise, it predicts deterministically (as $y_{1}$ is indeed close
to being deterministic when $\eta(x_{1})\notin[\pi,1-\pi]$).

###### Proof.

First we characterize the optimal attacker for which the individual expected
advantage is maximal. The Bayes optimal decision which minimizes the loss
$\mathbb{I}\\{A(x_{1},\tilde{y_{1}})\neq y\\}$ conditioned on $x_{1}$ and
$\tilde{y_{1}}$ is

$A^{\prime}(x_{1},\tilde{y_{1}})=\mathbb{I}\\{\operatorname*{\mathbb{P}}(y_{1}=1|x_{1},\tilde{y_{1}})>\operatorname*{\mathbb{P}}(y_{1}=0|x_{1},\tilde{y_{1}})\\}$

which can be written as

$\displaystyle
1<\frac{\operatorname*{\mathbb{P}}(y_{1}=1|x_{1},\tilde{y_{1}})}{\operatorname*{\mathbb{P}}(y_{1}=0|x_{1},\tilde{y_{1}})}=\frac{\operatorname*{\mathbb{P}}(\tilde{y_{1}}|y_{1}=1,x_{1})\operatorname*{\mathbb{P}}(y_{1}=1|x_{1})}{\operatorname*{\mathbb{P}}(\tilde{y_{1}}|y_{1}=0,x_{1})\operatorname*{\mathbb{P}}(y_{1}=0|x_{1})}$
(15)

Assume that $\tilde{y_{1}}=1$, in which case (15) becomes

$\displaystyle\frac{\pi}{1-\pi}<\frac{\eta(x_{1})}{1-\eta(x_{1})}$ (16)

which is true whenever $\eta(x_{1})>\pi$, and on the other hand, if
$\eta(x_{1})<\pi$ then (16) does not hold anymore, thus
$A^{\prime}(x_{1},\tilde{y_{1}})=0$. A similar argument holds for
$\tilde{y_{1}}=0$: The Bayes optimal decision
$A^{\prime}(x_{1},\tilde{y_{1}})=1$ if and only if $\eta(x_{1})>1-\pi$.
Putting together, and noting that $\pi\leq 1/2$, this implies that the optimal
attack is

$A^{*}(x_{1},\tilde{y_{1}})=\begin{cases}1,&\text{if}~{}\eta(x_{1})>1-\pi\\\
0,&\text{if}~{}\eta(x_{1})<\pi\\\
\tilde{y_{1}},&\text{otherwise}~{}.\end{cases}$

To compute the reconstruction advantage of optimal attacker $A^{*}$, we may
decompose the feature set into parts as

$G(\pi)=\\{x_{1}\,:\,\eta(x_{1})\in[\pi,1-\pi]\\}$

and its complement set $G^{C}(\pi)$. It is clear the advantage of the optimal
attacker $A^{*}$ restricted to $G^{C}(\pi)$ is $0$ since $\tilde{}y_{1}$ gives
no extra information on $y_{1}$ when $x_{1}\in G^{C}(\pi)$, that is, the value
of $A^{*}(x_{1},\tilde{y}_{1})$ is independent of $\tilde{y}_{1}$ when
$x_{1}\in G^{C}(\pi)$. On the other hand, the advantage of $A^{*}$ for any
$x_{1}\in G(\pi)$ is

$(1-\pi)-(1-\min\\{\eta(x_{1}),1-\eta(x_{1})\\})=\min\\{\eta(x_{1}),1-\eta(x_{1})\\}-\pi\enspace,$

since $\mathcal{M}_{\text{RR}}$ reveals the true label with probability
$1-\pi$, while the attack utility (conditioned on $x_{1}$) of the uninformed
attacker $1-\min\\{\eta(x_{1}),1-\eta(x_{1})\\}$. This concludes the proof. ∎

##  Appendix B Proofs for Section 3.2

###  B.1 Proof of Theorem 3.7

###### Proof.

Consider the difference of log-odds ratio
$I_{k,i}(\mathcal{M},\mathcal{D},\mathbf{x},z,x_{i})$, where
$z=\mathcal{M}_{\text{LLP}}(\mathbf{x},\mathbf{y})=\frac{1}{k}\sum_{i=1}^{k}y_{i}$
is the output of the aggregation PET. Since $\mathbf{y}$ is independent of
$\mathbf{x}$, we can write

$\displaystyle I_{1,0}(\mathcal{M},\mathcal{D},\mathbf{x},z,x_{i})=I(z)$
$\displaystyle=\ln\frac{\operatorname*{\mathbb{P}}(y_{1}=1\,|\,z)}{\operatorname*{\mathbb{P}}(y_{1}=0\,|\,z)}-\ln\frac{\operatorname*{\mathbb{P}}(y_{1}=1)}{\operatorname*{\mathbb{P}}(y_{1}=0)}$
$\displaystyle=\ln\frac{z}{1-z}-\ln\frac{p}{1-p}$
$\displaystyle=\ln\frac{z(1-p)}{(1-z)p}~{},$

where we used the fact that, since $kz$ is a binomial random variable,
$\operatorname*{\mathbb{P}}(y_{1}=1\,|\,z)=z$, independent of $p$. From the
standard Bernstein inequality we have, with probability $\geq 1-\delta$,

$p-B\leq z\leq p+B~{},$

where

$B=B(k,p,\delta)=\sqrt{\frac{2p(1-p)\ln(1/\delta)}{k}}+\frac{2}{3k}\ln(1/\delta)~{}.$

Since $z\rightarrow\ln\frac{z}{1-z}$ is monotonically increasing in
$z\in[0,1]$, this yields

$\ln\left(1-\frac{B}{(1-p+B)p}\right)=\ln\frac{(p-B)(1-p)}{(1-p+B)p}\leq
I(z)\leq\ln\frac{(p+B)(1-p)}{(1-p-B)p}=\ln\left(1+\frac{B}{(1-p-B)p}\right)$

with the same probability. The condition $k\geq\frac{32\ln(1/\delta)}{p(1-p)}$
implies $2B\leq p-p^{2}$, which in turn implies
$\frac{B}{(1-p+B)p}\leq\frac{1}{2}$, as well as $\frac{B}{(1-p-B)p}>0$. We
further bound the right-most side through $\ln(1+x)\leq x$ for all $x\geq 0$,
and the left-most side via $\ln(1-x)\geq-x(\ln 2)$ for $x\in[0,1/2]$. This
gives

$-\frac{B\ln 2}{(1-p+B)p}\leq I(z)\leq\frac{B}{(1-p-B)p}~{},$

which, after further overapproximations, allows us to write

$|I(z)|\leq\frac{B\ln 2}{(1-p-B)p}~{}.$

Next, the condition $2B\leq p-p^{2}$ implies $(1-p-B)\geq(1-p)/2$ so that,
overall,

$|I(z)|\leq\frac{2B(k,p,\delta)(\ln
2)}{p(1-p)}=O\left(\sqrt{\frac{\ln(1/\delta)}{p(1-p)k}}\right)$

with probability at least $1-\delta$. This concludes the proof. ∎

##  Appendix C Experimental Setup for Section 4 and Further Experimental
Results

#### Datasets.

We conduct our experiments on the following datasets:

KDD2012: We use the click prediction data from the KDD Cup 2012, Track 2 [3]
with the feature processing performed in [23]. 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 it 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 in
54,686,452 dimensions. The label for the example is 1 if the ad was clicked,
and 0 otherwise.

Higgs: We also use the Higgs dataset [4], which is 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 a mix of kinematic properties measured
by particle detectors and hand-crafted high level features designed by
physicists. The dataset consists of 11,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, we describe the models we use for each dataset. We use the same model
architecture regardless of 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 $\mathbb{R}^{50}$, 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 as 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 is a single unit with sigmoid
activation that is interpreted as the probability that the example has the
positive class.

#### Training Setup.

When training a model on the output of any PET, we 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:\mathcal{Y}\to\mathbb{R}$ be any function (for example the gradient) of
a label, and let $y\in\\{0,1\\}$. For plain RR,

$\operatorname*{\mathbb{E}}[f(RR(y))]=\frac{e^{\varepsilon}-1}{e^{\varepsilon}+1}\cdot
f(y)+\frac{1}{e^{\varepsilon}+1}\cdot(f(0)+f(1)).$

Thus,

$f(y)=\operatorname*{\mathbb{E}}\left[\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\cdot
f(RR(y))-\frac{1}{e^{\varepsilon}-1}\cdot(f(0)+f(1))\right].$

Therefore, we can post-process 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 an 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 Proportion
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 D, since the binary cross-entropy loss is a proper loss, the
minimizer of the population-level proportion risk for cross-entropy loss is
also a minimizer of the population-level cross-entropy loss, as long as the
Bayes optimal classifier can be represented by the model architecture.

#### Training with LLP+Lap.

LLP+Lap is parametrized by two parameters, $k\in\\{1,2,\ldots\\}$ and
$\epsilon>0$. For each bag $\mathcal{B}_{i}$ the mechanism discloses
$\alpha_{i}+Z_{i}$, where $\alpha_{i}$ is the label proportion in that bag,
and $Z_{i}\sim\text{Lap}(\frac{1}{k\epsilon})$, is an independent zero-mean
Laplace random variable with parameter $\frac{1}{k\epsilon}$, that is, with
variance $\frac{2}{k^{2}\epsilon^{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 noise to the label proportion. Therefore, using
Proportion Matching to 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, $k\in\\{1,2,\ldots\\}$ and $\epsilon>0$, but
$Z_{i}$ is replaced by a two-sided Geometric random variable, where
$Z_{i}=\frac{Z^{+}_{i}-Z^{-}_{i}}{k}$, and $Z^{+}_{i}$ and $Z^{-}_{i}$ are
geometric distribution with probability of success $1-e^{-\epsilon}$. The
value $\alpha_{i}+Z_{i}$ is then clipped to $[0,1]$. It is not hard to see
that, for every given $\epsilon$, LLP+Geom with parameters $k=1$ and
$\epsilon$ coincides with RR with parameter $\epsilon$.

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
LLP+Geom to obtain unbiased estimates of the bag’s label proportion. In
particular, let $\alpha_{i}$ be the true label proportion for a bag,
$\alpha^{\text{(noise)}}_{i}=\alpha_{i}+Z_{i}$ be the unclipped noisy
proportion, and
$\alpha^{\text{(clip)}}_{i}=\operatorname{clip}(\alpha^{\text{(noise)}}_{i},[0,1])$
be the clipped noisy proportion. Then, using the memoryless property of the
Geometric distribution, we have that

$\operatorname*{\mathbb{E}}[\alpha^{\text{(noise)}}_{i}\mid\alpha^{\text{(clip)}}_{i}]=\begin{cases}\alpha^{\text{(clip)}}_{i}&\text{if
$\alpha^{\text{(clip)}}_{i}\in(0,1)$}\\\ -\frac{1}{e^{\epsilon}-1}&\text{if
$\alpha^{\text{(clip)}}_{i}=0$}\\\ 1+\frac{1}{e^{\epsilon}-1}&\text{if
$\alpha^{\text{(clip)}}_{i}=1$}.\end{cases}$

When training with LLP+Geom, we replace the clipped label proportion by
$\operatorname*{\mathbb{E}}[\alpha^{\text{(noise)}}_{i}\mid\alpha^{\text{(clip)}}_{i}]$
before computing the proportion matching loss. Since
$\alpha^{\text{(noise)}}_{i}$ is an unbiased estimate of $\alpha_{i}$, so is
the 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. It follows that using Proportion Matching
to train with LLP+Geom with proportion debiasing is similar to training with
LLP except with higher variance.

#### AUC vs Advantage Experimental Setup.

For all PETs, we train models to minimize the binary cross-entropy loss. For
RR, we use privacy parameters $\epsilon$ in $\\{2^{-4},2^{-3},\dots,2^{5}\\}$,
for LLP we use bag sizes $k$ in $\\{2^{0},2^{1},\dots,2^{9}\\}$, and for
LLP+Laplace and LLP+Geom we use all combinations of $\epsilon$ and $k$ from
the same sets. For every PET and every value of their privacy parameters, we
train the model with each learning rate in $\\{10^{-6},5\cdot
10^{-6},10^{-5},10^{-4},5\cdot 10^{-4},10^{-3},5\cdot 10^{-3},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 A.1 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 $\eta(x)$ — or at least
an accurate estimate of it. We considered two estimates of the class
conditionals: one based on Deep Neural Networks (DNN) as described above, and
one based of $k$-Nearest Neighbors ($k$NN). The $k$NN 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 if 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.

Figure 4: Prior-posterior scatter plots for LLP+Geom and LLP+Lap on two
synthetic datasets and the two real-world datasets. The two synthetic datasets
have been generated by drawing $\eta(x)$ from a Beta(2,30) distribution and a
uniform distribution on $[0,1]$. The colors of the dots correspond to
different parameter values for the PETs. For each bag size $k$ and
distribution, we did 1000 independent runs. The further a point is from the
$y=x$ dotted line, the more is revealed about its label as a result of the
PET.

Figure 5: Privacy vs utility tradeoff curves for the various PETs on the Higgs
(left) and KDD12 (right) datasets. Utility is measured by AUC on test set,
while privacy is either the additive measure (bottom row) or the 98th-
percentile of the multiplicative measure (so as to 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 ($\epsilon$ for RR, $k$ 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 a 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
LLP+Geom PET correspond to a fixed value of $\epsilon$, rather than a fixed
value of $k$.

#### 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.
Figure 5 shows the privacy-vs-utility plots (the data is identical to Figure
3) except in this case, the curves for the LLP+Geom PET correspond to a fixed
value of $\epsilon$ with the bag size $k$ varying.

#### Computational Resources.

We conduct our experiments on a cluster of virtual machines each equipped with
a p100 GPU, 16 core CPU, and 16GB of memory. Each training run on Higgs takes
approximately 10 minutes, and each training run on KDD12 takes approximately
20 hours.

##  Appendix 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
$\mathcal{M}_{\text{Lap-LLP}}$). 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. In other words, the expected trajectory of SGD for
PropMatch when using $\mathcal{M}_{\text{Lap-LLP}}$ is the same for all values
of $\epsilon$, including $\epsilon=\infty$, which corresponds to the special
case of $\mathcal{M}_{\text{LLP}}$. In fact, the main way that decreasing the
value of $\epsilon$ (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 $\epsilon=\infty$ (or equivalently, compared to PropMatch run with
$\mathcal{M}_{\text{LLP}}$).

To analyze PropMatch, we require a few properties of the loss
$\ell:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$ and the noise distribution.
First, the loss is _proper_ , which means that for every real-valued random
variable $A$, the function $f(p)=\operatorname*{\mathbb{E}}(\ell(p,A))$ has a
unique minimizer at $\mu=\operatorname*{\mathbb{E}}(A)$. We also assume that
$\ell(p,y)$ is differentiable in $p$, and that its derivative is affine in
$y$, that is $\frac{\partial}{\partial p}\ell(p,y)=a_{p}y+b_{p}$, where
$a_{p},b_{p}$ may depend on $p$ but not $y$. These conditions are satisfied by
the cross entropy (or logistic) loss $\ell(p,y)=-y\log(p)-(1-y)\log(1-p)$
(where $p\in[0,1]$) and the squared error $\ell(p,y)=(p-y)^{2}$.

Finally, we assume that the noise mechanism operates on a bag of $k$ examples
for some $k\in\mathbb{N}$ (possibly $k=1$). Given the proportion
$\mathcal{\alpha}$ of positive examples in the bag, it releases
$\tilde{\mathcal{\alpha}}=\mathcal{\alpha}+Z_{\mathcal{\alpha}}$, where
$\operatorname*{\mathbb{E}}[Z_{\mathcal{\alpha}}|\mathcal{\alpha}]=0$ for
every fixed $\mathcal{\alpha}\in\\{0,1/k,\ldots,1\\}$. This condition is
satisfied by LLP (since it adds no noise), LLP+Lap (since Laplace noise is
mean 0), and the debiased versions of randomized response and LLP+Geom,
described in Appendix C.

Given a class of predictors $\mathcal{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 a distribution $\mathcal{D}$, defined
via the choice of a bag $\mathcal{B}$ of $k$ labeled examples drawn from
$\mathcal{D}$:

$\min_{h\in\mathcal{H}}\operatorname*{\mathbb{E}}_{\mathcal{B},\mathcal{\alpha},\tilde{\mathcal{\alpha}}}\left[\ell\left(\frac{1}{k}\sum_{x\in\mathcal{B}}h(x),\tilde{\mathcal{\alpha}}\right)\right]$

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 $\mathcal{B}$ be a random bag of size $k$,
$\ell\,:\,\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}^{+}\cup\\{\infty\\}$
be a loss function, and $\mathcal{M}$ be a mechanism for releasing the label
proportions with
$\mathcal{M}(\alpha)=\tilde{\mathcal{\alpha}}=\mathcal{\alpha}+Z_{\mathcal{\alpha}}$,
where $\operatorname*{\mathbb{E}}[Z_{\mathcal{\alpha}}|\mathcal{\alpha}]=0$
for all $\alpha$. Suppose $\mathcal{H}$ contains a predictor $h^{*}$ that
matches the true label probabilities in $\mathcal{D}$ (i.e.
$h^{*}(x)=\operatorname*{\mathbb{P}}_{\mathcal{D}}(y=1|x)$. If $\ell$ is
proper (defined above), then $h^{*}$ is a minimizer of the population-level
noisy proportion-matching loss on $\mathcal{D}$. It is essentially unique, in
that any other minimizer $h^{\prime}$ must satisfy
$\operatorname*{\mathbb{P}}_{(x,y)\sim\mathcal{D}}(h^{\prime}(x)=h^{*}(x))=1$.

######  Theorem D.2.

Let $\mathcal{B}$ be a random bag of size $k$,
$\ell\,:\,\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}^{+}\cup\\{\infty\\}$
be a loss function, and $\mathcal{M}$ be a mechanism for releasing the label
proportions with
$\mathcal{M}(\alpha)=\tilde{\mathcal{\alpha}}=\mathcal{\alpha}+Z_{\mathcal{\alpha}}$,
where $\operatorname*{\mathbb{E}}[Z_{\mathcal{\alpha}}|\mathcal{\alpha}]=0$
for all $\alpha$. Suppose that $\frac{\partial}{\partial p}\ell(p,y)$ is
affine in $y$.

For a predictor $h_{\theta}\in\mathcal{H}$ (parametrized by $\theta$) denote
by $h_{\theta}(\mathcal{B})=\frac{1}{k}\sum_{x\in\mathcal{B}}h_{\theta}(x)$
its average prediction over $\mathcal{B}$. We have

$\operatorname*{\mathbb{E}}\left[\nabla_{\theta}\ell\left(h_{\theta}(\mathcal{B}),\tilde{\mathcal{\alpha}}\right)\right]=\operatorname*{\mathbb{E}}\left[\nabla_{\theta}\ell\left(h_{\theta}(\mathcal{B}),\mathcal{\alpha}\right)\right]~{},$
(17)

and furthermore

$\displaystyle\operatorname*{\mathbb{E}}\left[\left\|\nabla_{\theta}\ell\left(h_{\theta}(\mathcal{B}),\tilde{\mathcal{\alpha}}\right)\right|_{2}^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}\left[\|\nabla_{\theta}\ell(h_{\theta}(\mathcal{B}),\mathcal{\alpha})\|^{2}\right]+\operatorname*{\mathbb{E}}\left({Z_{\mathcal{\alpha}}^{2}\cdot\left\|\tfrac{\partial}{\partial\alpha}\nabla_{\theta}\ell(h_{\theta}(\mathcal{B}),\mathcal{\alpha})\right\|^{2}}\right)$
$\displaystyle\leq\operatorname*{\mathbb{E}}\left[\|\nabla_{\theta}\ell(h_{\theta}(\mathcal{B}),\mathcal{\alpha})\|^{2}\right]+\left({\max_{\alpha}\operatorname{Var}(Z_{\mathcal{\alpha}})}\right)\cdot\operatorname*{\mathbb{E}}\left[\left\|\tfrac{\partial}{\partial\alpha}\nabla_{\theta}\ell(h_{\theta}(\mathcal{B}),\mathcal{\alpha})\right\|^{2}\right]\,.$
(18)

That is, for nice loss functions like the logistic and square loss, we can
write the variance of the noisy LLP gradient as the sum of two terms: the
variance of the LLP-based estimate of the proportion-matching loss, and a
noise term that scales roughly as the variance of $Z$. For Laplace noise, this
variance is $\frac{2}{k^{2}\varepsilon^{2}}$. For unclipped Geometric noise,
the variance is $\frac{2e^{-\varepsilon}}{k^{2}(1-e^{-\varepsilon})^{2}}$
(which is always smaller than the Laplace variance, most noticeably for large