# PAC Privacy: Automatic Privacy Measurement and Control of Data Processing

Hanshen Xiao
<EMAIL_ADDRESS>Srinivas Devadas
<EMAIL_ADDRESS>
###### Abstract

We propose and study a new privacy definition, termed Probably Approximately
Correct (PAC) Privacy. PAC Privacy characterizes the information-theoretic
hardness to recover sensitive data given arbitrary information
disclosure/leakage during/after any processing. Unlike the classic
cryptographic definition and Differential Privacy (DP), which consider the
adversarial $($input-independent$)$ worst case, PAC Privacy is a simulatable
metric that quantifies the instance-based impossibility of inference. A fully
automatic analysis and proof generation framework is proposed: security
parameters can be produced with arbitrarily high confidence via Monte-Carlo
simulation for any black-box data processing oracle. This appealing automation
property enables analysis of complicated data processing, where the worst-case
proof in the classic privacy regime could be loose or even intractable.
Moreover, we show that the produced PAC Privacy guarantees enjoy simple
composition bounds and the automatic analysis framework can be implemented in
an online fashion to analyze the composite PAC Privacy loss even under
correlated randomness. On the utility side, the magnitude of (necessary)
perturbation required in PAC Privacy is not lower bounded by
${\Theta}(\sqrt{d})$ for a $d$-dimensional release but could be $O(1)$ for
many practical data processing tasks, which is in contrast to the input-
independent worst-case information-theoretic lower bound. Example applications
of PAC Privacy are included with comparisons to existing works.

Keywords: PAC Privacy; Automatic Security Proof; $f$-Divergence; Mutual
Information; Instance-based Posterior Advantage; Reconstruction Hardness;
Inference Hardness; Membership Attack.

##  1 Introduction

Privacy concerns with information leakage from data processing are receiving
increasing attention. Obtaining usable security which provides high utility,
low implementation overhead and meaningful interpretation, is challenging.
Theoretically, the underlying problem can be described by the following
generic model. Assume some sensitive data $X$ is processed by some mechanism
$\mathcal{M}$ and the output $\mathcal{M}(X)$ is published. We want to
characterize, given $\mathcal{M}(X)$, how much information an adversary can
infer about $X$. In the applications of data analysis and machine learning,
$\mathcal{M}(X)$ could be any statistics or model learned from $X$ [1]; in
encryption, $\mathcal{M}(X)$ could be ciphertexts of $X$ [37]; in side channel
attacks, $\mathcal{M}(X)$ could be any physical signal observed by the
adversary, such as memory access pattern [59] or network traffic [20] when
accessing or sending $X$.

To formalize and quantify the information leakage, a large number of security
metrics have been proposed varying from the perfect secrecy [56] of Shannon,
to computational indistinguishability [38], which forms the foundation of
modern cryptography, to Differential Privacy (DP) [29] and its variants based
on various statistical divergence metrics [49], and many other definitions
based on information-theoretic quantities, such as Fisher-information privacy
[32].

Most existing privacy or security definitions (including all above-mentioned
examples) are rooted in indistinguishability likelihoods. They set out to
quantify the difference between the likelihoods
$\mathbb{P}(\mathcal{M}(X)=o|X=X_{0})$ and
$\mathbb{P}(\mathcal{M}(X)=o|X=X^{\prime}_{0})$ for different input selections
from various perspectives. For instance, perfect secrecy requires that for
arbitrary input data $X$, the distribution of $\mathcal{M}(X)$ must be
identical. Cryptographic security relaxes the statistical indistinguishability
to that any polynomial-time adversary cannot distinguish the distributions of
$\mathcal{M}(X_{0})$ and $\mathcal{M}(X^{\prime}_{0})$ for any input
candidates $X_{0}$ and $X^{\prime}_{0}$. Similarly, DP and its variants
quantify the difference between $\mathcal{M}(X_{0})$ and
$\mathcal{M}(X^{\prime}_{0})$ for any two adjacent datasets 111Here, we say
$X_{0}$ and $X^{\prime}_{0}$ are adjacent if they only differ in one
datapoint, i.e., their Hamming distance is $1$.  by some divergence function
$\mathcal{D}\big{(}\mathsf{P}_{\mathcal{M}(X_{0})}\|\mathsf{P}_{\mathcal{M}(X^{\prime}_{0})}\big{)}$.
For example, classic $\epsilon$-DP [29] is based on maximal divergence
$\mathcal{D}_{\infty}(\mathsf{P}_{\mathcal{M}(X_{0})}\|\mathsf{P}_{\mathcal{M}(X^{\prime}_{0})})=\sup_{o}\log\big{(}{\mathbb{P}(\mathcal{M}(X_{0})=o)}/{\mathbb{P}(\mathcal{M}(X^{\prime}_{0})=o)}\big{)}$.

The interested reader may wonder if there is an intuitive privacy
interpretation of the limited likelihood difference? In particular, can
likelihood indistinguishability tell us given $\mathcal{M}(X)$, how much of
the sensitive data $X$ an adversary can recover? Unfortunately, none of above-
mentioned definitions can directly answer this question. This is not because
those metrics are incomplete but because additional assumptions must be made.
In general, to quantify reconstruction hardness, we have to specify the
adversary’s prior knowledge and the (conditional) entropy of objective $X$. In
the extreme case where the adversary already has the full knowledge of $X$, or
where $X$ is simply a public constant, then no matter what kind of mechanism
$\mathcal{M}$ is applied to encode $X$, the adversary can perfectly recover
it, regardless of $\mathcal{M}(X)$. Thus, the likelihood difference only
partially captures the changes to the adversary’s belief or the additional
information regarding $X$ after observing $\mathcal{M}(X)$.

Compared to the extensive studies along the line of (in)distinguishability,
formal characterization of reconstruction hardness is a long-standing,
challenging problem. The estimation of the priors regarding sensitive data $X$
and resultant output distribution of $\mathcal{M}(X)$ could already be
intractable – this is especially likely in the high-dimensional scenario.
Thus, as mentioned before, most security/privacy definitions only focus on the
likelihood divergence and avoid complicated, such as Bayesian, analysis to
properly quantify the posterior inference hardness. As a consequence, to make
a meaningful guarantee, most classic definitions treat the sensitive input
deterministically and consider the adversarial worst-case, i.e., the maximal
distribution divergence between $\mathcal{M}(X_{0})$ and
$\mathcal{M}(X^{\prime}_{0})$ for two arbitrary input candidates $X_{0}$ and
$X^{\prime}_{0}$. Such worst-case indistinguishability is a very strong
guarantee since it is independent of any particular input distribution, but is
also expensive, especially for statistical data processing. At a high level,
there are two key obstacles in the application of such indistinguishability
measurement:

  1. (a)

Adversarial Worst-case Proof is Hard: It is, in general, non-trivial to
tightly or analytically characterize the worst case and privatize an
(adaptively-iterative) algorithm to ensure satisfied output divergence. For
example, in DP, calculation of the sensitivity, the maximal possible change on
the output by replacing a single datapoint, is, in general, NP-hard [66]. Even
in common applications such as to differentially privately train a neural
network, the tight sensitivity bound of Stochastic Gradient Descent (SGD)
remains open. The only known generic privatization approach, DP-SGD, restricts
the sensitivity using clipped/normalized per-sample gradient, and adds noise
step by step to derive an upper bound in a compositional fashion [1]. However,
the tight composition bound calculation is also known to be #P hard [51].
Though many efforts have been devoted to obtaining efficient and tighter
composition [49], the applications of DP-SGD in modern deep learning, and
large-scale private database queries still encounter severe utility
compromise. Therefore, an automatic and usable privacy analysis framework for
arbitrary data processing is desirable.

  2. (b)

Data Entropy Matters in Reconstruction: Reconstruction (or inference) of data
is, in general, a harder problem for an adversary than simply distinguishing
[39]. However, worst-case indistinguishability cannot capture the data
entropy. We give a simple example. A dataset
$X=\\{x_{1},x_{2},\ldots,x_{n}\\}$ is generated as i.i.d. samples from some
Gaussian distribution and we simply publish its empirical average, i.e.,
$\mathcal{M}(X)=1/n\cdot(\sum_{i=1}^{n}x_{i})$. Even without any further
obfuscation on $\mathcal{M}(X)$ like perturbation, intuitively, we see some
potential hardness to reconstruct $X$ from its average $\mathcal{M}(X)$. For
an adversary who only knows the data distribution, it is impossible to
perfectly reconstruct $X$ deterministically due to ambiguity. But the data
leakage of this trivial aggregation cannot be properly analyzed from a
distinguishability angle, since one can always determine the true input from
two datasets whose means are different. However, in practical processing even
for a given data pool, many kinds of randomness can enforce data to be
processed to enjoy entropy, for example, subsampling or data augmentation
[58], where the participants are randomized. Therefore, a more generic
security/privacy definition, which enables instance-based analysis in terms of
both data priors and specific inference objective, is attractive.

In this paper, we tackle the fundamental problem of quantifying the
relationship among data entropy, disclosure, and reconstruction hardness.
Besides a more meaningful interpretation via inference impossibility, to
address the above two mentioned challenges in classic security/privacy
regimes, we want a more generic definition, which enables (a) automatic
security proof, and (b) instance-based worst-case analysis. To this end, a new
privacy definition, termed Probably Approximately Correct (PAC) Privacy, is
proposed, which enables a user to keep track of the data leakage of an
arbitrary (black-box) processing mechanism with confidence, via simulation. At
a high level, $(\delta,\rho,\mathsf{D})$ PAC Privacy characterizes the
following reconstruction hardness:

For some sensitive data $X$ distributed in $\mathsf{D}$ and a mechanism
$\mathcal{M}$, given $\mathcal{M}(X)$, there does not exist an adversary
$($possibly computationally-unbounded$)$ who can successfully return
$\tilde{X}$ such that $\rho(\tilde{X},X)=1$ under measure function $\rho$ with
probability at least $(1-\delta)$.

We use the notion “PAC” as we borrow the idea of well-known PAC learning
theory [63] and describe the adversary’s reconstruction/inference task as a
generic learning problem. The difference compared to classic learning theory
is that we study impossibility results. The $\rho(\cdot,\cdot)$ captures an
arbitrary inference task of interest and $\rho(\tilde{X},X)=1$ if and only if
adversary’s inference $\tilde{X}$ satisfies the reconstruction criterion. For
example, if we set out to prevent the adversary from recovering a single
digital bit of data $X$, then we may select $\rho$ such that
$\rho(\tilde{X},X)$ returns $1$ only when $\tilde{X}$ and $X$ collide in at
least one coordinate. More discussions can be found below Definition 1.

Our presented PAC Privacy framework has the following appealing properties and
important implications:

  1. 1.

Wide Applicability: The PAC Privacy framework presented can theoretically be
used to analyze any data processing. Via $f$-divergence, we present a simple
quantification of the posterior advantage that the adversary gains by
observing the disclosure $\mathcal{M}(X)$ for arbitrary inference problems.
Thus, PAC Privacy can characterize very generic reconstruction/inference
hardness under any selection of the measure function $\rho$, which captures
classic attacks such as membership inference and identification. Through
instance-based (Gaussian) perturbation, we show how to efficiently control PAC
Privacy parameters. In contrast to the adversarial worst-case, the noise
magnitude in PAC Privacy does not necessarily scale with dimensionality but
can be $O(1)$ in high-dimensional release.

  2. 2.

Automatic Privacy Analysis: To our knowledge, PAC Privacy is the first non-
trivial automatic security definition. Theoretically, no worst-case proof is
needed but one can determine a perturbation mechanism (if necessary) fully
automatically in polynomial time to ensure desired security parameters with
arbitrarily high confidence. More importantly, this universal framework only
requires sufficient Monte-Carlo simulations while the underlying data
processing mechanism could be a black-box oracle – no algorithmic analysis is
required. This is very different from classic definitions such as cryptography
and DP, where the key challenge is to derive the algorithmic worst-case proof.

  3. 3.

Connections to the Input-Independent Worst Case and Generalization Error: We
also connect PAC Privacy, DP and generalization error. Given assumptions on
priors, we show DP can produce PAC Privacy, and PAC Privacy can then provide a
generalization error guarantee, while the reverse direction, in general, does
not hold. However, in practical data applications, PAC Privacy could bring
significant (empirical) perturbation improvement, and can characterize the
optimal instance-based perturbation required. We show concrete examples in
private release of local samples, mean estimation and deep learning models.
Though the tools we apply to develop the foundation of PAC Privacy include
$f$-divergence and mutual information, we stress that PAC Privacy is not
defined using any existing information-theoretical metric or statistical
divergence, but by the impossibility of inference described above. Therefore,
PAC Privacy enjoys a very straightforward interpretation. More discussion can
be found in Section 7.

Paper Organization: At a high level, the paper has two parts, i.e., the
definition of PAC Privacy and the control of security parameters via automatic
analysis. In Section 2, we formally present the definitions and
interpretations of PAC Privacy. In Section 3, we show generic bounds of PAC
Privacy parameters using $f$-divergence and mutual information in various
setups. With these bounds, we move on to present automatic algorithms to
determine proper perturbation (if necessary) to produce desired PAC Privacy.
In Section 4.1, we present the methods for deterministic data processing, and
in Section 4.2, we study the case of randomized mechanisms. In Section 4.3, we
discuss how to approximate the optimal perturbation in general. In Section 5,
we study the composition of PAC Privacy in various setups. In Section 6, we
proceed to study and compare the adversarial and instance-based worst case.
Practical applications of PAC Privacy are included. We summarize related works
in Section 7, where we also discuss the relationship between PAC Privacy,
Differential Privacy and generalization error. Finally, we conclude in Section
8. The generalization to local PAC Privacy via secure implementation of
automatic privacy analysis in a decentralized setup can be found in the full
version.

##  2 PAC Privacy

We assume each private datapoint $x$ is defined over some domain
$\mathcal{X}$, and the dataset $X\in\mathcal{X}^{*}$. Our goal is to formalize
the privacy leakage from a data processing mechanism $\mathcal{M}$, where
$\mathcal{M}:\mathcal{X}^{*}\to\mathcal{Y}\subset\mathbb{R}^{d}$. Both
$\mathcal{X}$ and $\mathcal{Y}$ are measurable spaces. The data distribution
$\mathsf{D}$ is defined over $\mathcal{X}^{*}$. $\mathcal{M}$ can be either
deterministic or randomized. Different analyses will be provided later for
these two cases. The formal definition of PAC Privacy is as follows.

######  Definition 1 ($(\delta,\rho,\mathsf{D})$ PAC Privacy).

For a data processing mechanism $\mathcal{M}$, given some data distribution
$\mathsf{D}$, and a measure function $\rho(\cdot,\cdot)$, we say $\mathcal{M}$
satisfies $(\delta,\rho,\mathsf{D})$-PAC Privacy if the following experiment
is impossible:

A user generates data $X$ from distribution $\mathsf{D}$ and sends
$\mathcal{M}(X)$ to an adversary. The adversary who knows $\mathsf{D}$ and
$\mathcal{M}$ is asked to return an estimation $\tilde{X}\in\mathcal{X}^{*}$
on $X$ such that with probability at least $(1-\delta)$,
$\rho(\tilde{X},X)=1$.

In Definition 1, we adopt a way to describe the reconstruction hardness as a
game between the user and the adversary. The adversary sets out to learn
something from the disclosure $\mathcal{M}(X)$. The measure function (on the
adversary’s learning performance) $\rho(\cdot,\cdot)$ can be arbitrarily
selected according to the adversarial inference task of interest. For example,
$\mathcal{X}\subset\mathbb{R}^{d^{\prime}}$ for some dimension $d^{\prime}$
and a safe reconstruction error is set to be $\epsilon$ in the $l_{2}$ norm.
Then, we can define $\rho(\tilde{X},X)=1$ if and only if
$\|\tilde{X}-X\|_{2}\leq\epsilon$ and Definition 1 suggests it is impossible
for an adversary to recover private data $X$ within $\epsilon$ error with
probability at least $(1-\delta)$. Another example, $\mathcal{X}^{*}$ is some
finite set and $X\in\mathcal{X}^{*}$ contains $n$ elements. Similarly, we
define $\rho(\tilde{X},X)=1$ iff $\\#(\tilde{X}\cap X)>(n-\epsilon)$. Then,
Definition 1 implies that there does not exist an adversary who can identify
more than $(n-\epsilon)$ elements/participants of $X$ from $\mathcal{X}^{*}$
with probability at least $(1-\delta)$. As a remark, a neat expression of
$\rho$ is not important or even necessary in PAC Privacy and we simply use
$\rho$ to indicate whether the adversary’s reconstruction satisfies a certain
criterion.

It is worthwhile to mention that in Definition 1 and results presented later,
we do not put any specific restrictions on $\mathsf{D}$ or the adversary’s
strategy. $\mathsf{D}$ could be a generic joint distribution of datapoints
generated, though with additional assumptions we may obtain tighter bounds
(such as Theorem 2). Before proceeding, we augment the definition of PAC
Privacy to incorporate (instance-based) additional posterior advantage,
commonly adopted in classic privacy definitions. That is, for any specific
priors given, we set out to quantify how much the disclosure of
$\mathcal{M}(X)$ can help the adversary to implement successful inference. To
measure such advantage, we first formally introduce the definition of
$f$-divergence.

######  Definition 2 ($f$-Divergence).

Let $f:(0,+\infty)\to\mathbb{R}$ be a convex function with $f(1)=0$. Let
$\mathsf{P}$ and $\mathsf{Q}$ be two distributions on some measurable space,
and the $f$-divergence $\mathcal{D}_{f}$ between $\mathsf{P}$ and $\mathsf{Q}$
is defined as

$\mathcal{D}_{f}(\mathsf{P}\|\mathsf{Q})\coloneqq\mathbb{E}_{Q}\big{[}f(\frac{d\mathsf{P}}{d\mathsf{Q}})\big{]}.$

Here, we use $d\mathsf{P}$ $(d\mathsf{Q})$ to represent the probability
density $($or mass$)$ function of the continuous $($or discrete$)$ probability
distribution $\mathsf{P}$ $(\mathsf{Q})$.

In Definition 2, when we select $f(x)=x\log(x)$, it becomes the Kullback-
Leibler (KL) divergence; when we select $f(x)=\frac{1}{2}|x-1|$, it becomes
the total variation, where
$\mathcal{D}_{TV}(\mathsf{P}\|\mathsf{Q})=\frac{1}{2}\cdot\int|d\mathsf{P}-d\mathsf{Q}|$.
In the following, we define $(1-\delta^{\rho}_{o})$ as the optimal a priori
chance that an adversary who only knows the data distribution $\mathsf{D}$ can
complete the objective reconstruction task before observing the release
$\mathcal{M}(X)$.

######  Definition 3 (Optimal Prior Success Rate).

For given measure $\rho$ and data distribution $\mathcal{D}$, we define
$(1-\delta^{\rho}_{o})$ as

$1-\delta^{\rho}_{o}\coloneqq\sup_{\tilde{X}\in\mathcal{X}^{*}}\Pr_{X\sim\mathsf{D}}\big{(}\rho(\tilde{X},X)=1\big{)},$

which represents the optimal a priori success rate only based on adversary’s
prior knowledge on $\mathsf{D}$ to recover $X$ such that the reconstruction
satisfies the criterion defined by $\rho$.

######  Definition 4 ($(\Delta_{f}\delta,\rho,\mathsf{D})$ PAC Advantage
Privacy).

A mechanism $\mathcal{M}$ is termed $(\Delta_{f}\delta,\rho,\mathsf{D})$ PAC-
advantage private if it is $(\delta,\rho,\mathsf{D})$ PAC private and

$\Delta_{f}\delta\coloneqq\mathcal{D}_{f}(\bm{1}_{\delta}\|\bm{1}_{\delta^{\rho}_{o}})=\delta^{\rho}_{o}f(\frac{\delta}{\delta^{\rho}_{o}})+(1-\delta^{\rho}_{o})f(\frac{1-\delta}{1-\delta^{\rho}_{o}}).$

Here, $\bm{1}_{\delta}$ and $\bm{1}_{\delta^{\rho}_{o}}$ represent two
Bernoulli distributions of parameters $\delta$ and $\delta^{\rho}_{o}$,
respectively.

In Definition 4, $\Delta_{f}\delta$ captures the additional (posterior)
advantage gained by the adversary after observing $\mathcal{M}(X)$. When we
select $\mathcal{D}_{f}$ to be total variation, $\Delta_{TV}\delta$ simply
becomes the difference $\delta^{\rho}_{o}-\delta$, as commonly used in classic
cryptographic analysis. Accordingly, once we have an upper bound on
$\delta^{\rho}_{o}-\delta$, plugging in $\delta^{\rho}_{o}$ provides a lower
bound on the posterior failure rate $\delta$.

The seemingly artificial aspect of Definition 4 in using $f$-divergence as the
measure is motivated by Theorem 1, where we give generic upper bounds on
$\Delta_{f}\delta$. In particular, when $\mathcal{D}_{f}$ is selected to be
KL-divergence, we can simply bound $\Delta_{KL}\delta$ via mutual information.
In addition, it is not hard to see that when $\mathcal{M}$ satisfies perfect
secrecy, $\Delta_{f}\delta$ is $0$ for any $f$. Before the end of this
section, we have the following important remarks on PAC Privacy.

Reconstruction Metric Selection: Definitions 1 and 4 provide a unified
framework to capture generic inference hardness. Membership and identification
attacks are now special cases by selecting a specific data generation and a
specific measure $\rho$.

######  Definition 5 ($(\delta,\rho,\mathsf{U},\mathsf{D})$ PAC Membership
Privacy).

For a data processing mechanism $\mathcal{M}$, given some measure $\rho$ and a
data set $\mathsf{U}=(u_{1},u_{2},\ldots,u_{N})$, we say $\mathcal{M}$
satisfies $(\delta,\rho,\mathsf{U},\mathsf{D})$-PAC Membership Privacy if the
following experiment is impossible:

A user applies certain sampling $($described by $\mathsf{D})$ on $\mathsf{U}$
to generate a dataset $X\sim\mathsf{D}$, and sends $\mathcal{M}(X)$ to an
adversary. The adversary who knows $\mathsf{U},\mathsf{D}$ and $\mathcal{M}$
is asked to return an $N$-dimensional binary vector
$\tilde{\bm{1}}_{\mathsf{U}}=\big{(}\tilde{\bm{1}}_{u_{1}},\ldots,\tilde{\bm{1}}_{u_{N}}\big{)}$
to predict the participation of each $u_{i}$, denote by
${\bm{1}}_{\mathsf{U}}=\big{(}\bm{1}_{u_{1}},\ldots,\bm{1}_{u_{N}}\big{)}$,
where $\bm{1}_{u_{i}}$ is an indicator to represent the participation of
$u_{i}$, such that with probability at least $(1-\delta)$,
$\rho(\tilde{\bm{1}}_{\mathsf{U}},\bm{1}_{\mathsf{U}})=1$.

One can imagine the distribution $\mathsf{D}$ could be Poisson (i.i.d.)
sampling or random sampling with(out) replacement from $\mathsf{U}$. From a DP
angle, such privacy amplification from sampling has been studied in [4], [65].
PAC Membership Privacy is a very important variant of PAC Privacy in practical
applications, which can give a formal security proof against the well-known
and fundamental membership inference attack problem [57].

We may consider the classic statistical query model, where there is some
sensitive data set $\mathsf{U}$, for example, medical records of $N$ patients,
held by a server. The server is asked to answer some query, expressed as
disclosing the results of $\mathcal{M}$. The server randomly samples a subset
$X$ of elements from $\mathsf{U}$; for example, each datapoint in $\mathsf{U}$
will be independently selected with probability ${1}/{2}$, to participate in
the computation of $\mathcal{M}(X)$. If we select
$\rho(\tilde{\bm{1}}_{\mathsf{U}},\bm{1}_{\mathsf{U}})=1$ only when
$\tilde{\bm{1}}_{\mathsf{U}}$ and $\bm{1}_{\mathsf{U}}$ collide in at least
one entry, then $(\delta,\rho,\mathsf{U},\mathsf{D})$-PAC Membership Privacy
suggests that even if the adversary already knows the whole data pool
$\mathsf{U}$, he still cannot successfully infer any participants in the
processing mechanism $\mathcal{M}$. In other words, PAC Membership Privacy
quantifies the risk incurred by any group of persons who allow their data to
be processed through $\mathcal{M}$.

If, on the other hand, our privacy concern pertains to individuals, we simply
consider the reconstruction hardness of each single datapoint in the set $X$,
and similarly define PAC Individual Privacy as follows.

######  Definition 6 ($(\delta,\rho,n,\mathsf{D})$ PAC Individual Privacy).

For a data processing mechanism $\mathcal{M}$, given some data distribution
$\mathsf{D}$, the total number $n$ of datapoints, a measure
$\rho(\cdot,\cdot)$, we say $\mathcal{M}$ satisfies
$(\delta,\rho,n,\mathsf{D})$-PAC Individual Privacy if for any $i\in[1:n]$ the
following experiment is impossible:

A user generates data $X=(x_{1},x_{2},\ldots,x_{n})$ from distribution
$\mathsf{D}$ and sends $\mathcal{M}(X)$ to an adversary. The adversary who
knows $\mathsf{D}$ and $\mathcal{M}$ is asked to return an estimation
$\tilde{x}_{i}$ on $x_{i}$ such that with probability at least $(1-\delta)$,
$\rho(\tilde{x}_{i},x_{i})=1$.

If the input domain $\mathcal{X}$ is some finite set and we want to measure
how hard it is for an adversary to identify the true selection of $x_{i}$, we
may set $\rho$ to be $\rho(\tilde{x}_{i},x_{i})=1$ iff $\tilde{x}_{i}=x_{i}$.
Then, the reconstruction becomes the identification problem. We have to stress
that a proper selection of measure $\rho$ is important to make PAC Privacy
meaningful in different scenarios. Different error metrics will capture
different perspectives of data privacy. For biological or financial data, such
as ages and incomes, $l_{p}$ norm, such as $l_{1}$ and $l_{2}$, is usually
meaningful. But for sensitive image or natural language data, $l_{p}$ norm may
not be able to fully characterize the leakage of contextual information, and
membership and identification hardness are better options. PAC Privacy
provides a unified framework for arbitrary inference tasks and privacy
concerns.

Lack of Knowledge: In all the above definitions, we assume the adversary has
full knowledge of the a priori data generation distribution $\mathsf{D}$, or
$\mathsf{D}$ is public. However, our current PAC Privacy framework cannot
properly quantify the inference hardness due to the lack/absence of prior
knowledge. For example, suppose the data $X$ is generated from some
distribution $\mathsf{D}$, say a random picture selected from a pool of cat
images. For an adversary who does not have full knowledge but only knows that
the users’ pictures could be selected from an image pool of cats or dogs, the
inference would be harder compared to the full knowledge setup. Unfortunately,
our techniques used in PAC Privacy rely on the entropy of data, which does not
change conditional on such lack of knowledge. However, in the other direction,
PAC Privacy does quantify the inference hardness in a more generic scenario
when the adversary has more knowledge rather than simply knowing $\mathsf{D}$.
We refer the reader to Remark 1 in Section 3.

Although our current framework cannot exactly quantify the inference hardness
amplification from the lack of knowledge, PAC Privacy enjoys strong and
realistic privacy interpretation from this perspective. If a certain inference
problem is already difficult for an adversary who has full knowledge, then it
is even more difficult for an adversary who lacks knowledge. Suppose a user
holds a set $\mathsf{U}$ of cat images and randomly samples, say, 1000 samples
from them, to produce $X$ and discloses $\mathcal{M}(X)$. If $\mathcal{M}(X)$
satisfies PAC Privacy such that even an adversary who knows $\mathsf{U}$ and
the data generation $\mathsf{D}$ cannot identify or recover the 1000
participants, then it is even more difficult for an adversary to identify or
recover the 1000 selected samples from the universe of cat images.

##  3 Foundation of PAC Privacy

In this section, we present our generic results to enable concrete PAC Privacy
analysis. Before we state the theorems, we need the following additional
notations to express the results.

######  Definition 7 (Entropy).

For a random variable $x$ defined on a discrete set $\mathcal{X}$, the
(Shannon) entropy $\mathcal{H}(x)$ of $x$ is defined as
$\mathcal{H}(x)=\sum_{x_{0}\in\mathcal{X}}-\Pr(x=x_{0})\log\Pr(x=x_{0}).$ If
$x$ is in a continuous distribution on some domain $\mathcal{X}$, then the
(differential) entropy $h(x)$ of $x$ is defined as
$h(x)=\int_{x_{0}\in\mathcal{X}}-\mathbb{P}(x=x_{0})\log\mathbb{P}(x=x_{0})dx_{0},$
where $\mathbb{P}$ represents the probability density function.

With a slight abuse of notation, we simply apply $\mathcal{H}(x)$ to denote
the (Shannon/differential) entropy of $x$ depending on its distribution for
simplicity. Accordingly, we can define the conditional entropy
$\mathcal{H}(x|w)$ for two random variables $x$ and $w$ in some joint
distribution, where
$\mathcal{H}(x|w)=\sum_{w_{0}\in\mathcal{W}}\mathcal{H}(x|w=w_{0})\Pr(w=w_{0}).$
When $w$ is in some continuous distribution, we can similarly define the
conditional entropy in an integral form as differential entropy. In the
following, we will use $\mathsf{P}_{x}$ to denote the distribution of a random
variable $x$.

######  Definition 8 (Mutual Information).

For two random variables $x$ and $w$ in some joint distribution, the mutual
information $\mathsf{MI}(x;w)$ is defined as

$\mathsf{MI}(x;w)\coloneqq\mathcal{H}(x)-\mathcal{H}(x|w)=\mathcal{D}_{KL}(\mathsf{P}_{x,w}\|\mathsf{P}_{x}\otimes\mathsf{P}_{w}),$

i.e., the KL-divergence between the joint distribution of $(x,w)$ and the
product of the marginal distributions of $x$ and $w$, respectively.

Mutual information measures the dependence between $x$ and $w$.
$\mathsf{MI}(x;w)=\mathsf{MI}(w;x)$ is always non-negative and equals $0$ if
$x$ is independent of $w$.

######  Theorem 1.

For any selected $f$-divergence $\mathcal{D}_{f}$, a mechanism
$\mathcal{M}:\mathcal{X}^{*}\to\mathcal{Y}$ satisfies
$(\Delta_{f}\delta,\rho,\mathsf{D})$ PAC Advantage Privacy if

$\displaystyle\Delta_{f}\delta=\mathcal{D}_{f}\big{(}\bm{1}_{\delta}\|\bm{1}_{\delta^{\rho}_{o}}\big{)}\leq\inf_{\mathsf{P}_{W}}\mathcal{D}_{f}\big{(}\mathsf{P}_{X,\mathcal{M}(X)}\|\mathsf{P}_{X}\otimes\mathsf{P}_{W}\big{)}.$
(1)

Here, $\bm{1}_{\delta}$ and $\bm{1}_{\delta^{\rho}_{o}}$ are two Bernoulli
distributions of parameters $\delta$ and $\delta^{\rho}_{o}$, respectively;
$\mathsf{P}_{X,\mathcal{M}(X)}$ and $\mathsf{P}_{X}$ are the joint
distribution and the marginal distribution of $(X,\mathcal{M}(X))$ and $X$,
respectively; and $\mathsf{P}_{W}$ represents the distribution of an arbitrary
random variable $W\in\mathcal{Y}$.

In particular, when we select $\mathcal{D}_{f}$ to be the KL-divergence and
$\mathcal{P}_{W}=\mathcal{P}_{\mathcal{M}(X)}$, $\mathcal{M}$ satisfies
$(\Delta_{KL}\delta,\rho,\mathsf{D})$ PAC Advantage Privacy where

$\displaystyle\Delta_{KL}\delta\coloneqq\mathcal{D}_{KL}(\bm{1}_{\delta}\|\bm{1}_{\delta^{\rho}_{o}})\leq\mathsf{MI}\big{(}X;\mathcal{M}(X)\big{)}.$
(2)

Here,
$\mathcal{D}_{KL}(\bm{1}_{\delta}\|\bm{1}_{\delta^{\rho}_{o}})=\delta\log(\frac{\delta}{\delta^{\rho}_{o}})+(1-\delta)\log(\frac{1-\delta}{1-\delta^{\rho}_{o}})$.

###### Proof.

See Appendix A. ∎

######  Remark 1.

In general, if the adversary has more prior knowledge $($besides the data
distribution $\mathsf{D})$ on $X$, denoted by a variable $Adv$, we can obtain
a corresponding PAC Privacy bound using Theorem 1, where the only difference
is that in $(\ref{generic_fano})$, $\mathsf{MI}(X;\mathcal{M}(X))$ and
$\delta^{\rho}_{o}$ are changed to the conditional
$\mathsf{MI}(X;\mathcal{M}(X)|Adv)$ and the corresponding failure probability
of optimal a priori guessing on $X$ conditional on $Adv$, respectively.

Theorem 1 is rooted in the well-known data processing inequality of
$f$-divergence. Roughly speaking, this inequality says postprocessing cannot
increase information. Given priors, the adversary’s reconstruction or decision
is determined by (a postprocessing of) his observation on $\mathcal{M}(X)$.
Therefore, to information-theoretically bound the posterior advantage, it
suffices to quantify the correlation between $X$ and $\mathcal{M}(X)$. Theorem
1 serves as the foundation of PAC Privacy analysis. From (1), we know that
$\Delta_{f}\delta=\mathcal{D}_{f}(\bm{1}_{\delta}\|\bm{1}_{\delta^{\rho}_{o}})$,
the change to the $f$-divergence between the optimal a priori and posterior
reconstruction/inference performance, is bounded by the corresponding
$f$-divergence between the distributions of $(X,\mathcal{M}(X))$ and $(X,W)$,
where $W$ is an arbitrary random variable independent of $X$. With the freedom
of the selections of both $f$ and $W$, if we apply KL-divergence and set $W$
to be distributed the same as ${\mathcal{M}(X)}$, we have
$\Delta_{KL}\delta\leq\mathsf{MI}(X;\mathcal{M}(X)),$ the mutual information
between $X$ and $\mathcal{M}(X)$.

It is noted that we are also free to select arbitrary $\rho$ as the objective
inference task and the success criterion in (1). Thus, another important
implication from Theorem 1 is that once we have an upper bound on
$\mathcal{D}_{f}\big{(}\mathsf{P}_{X,\mathcal{M}(X)}\|\mathsf{P}_{X}\otimes\mathsf{P}_{\mathcal{M}(X)}\big{)}$,
we indeed also control the posterior advantage of all possible adversaries’
inference tasks. This is also the foundation of the automatic proof of PAC
Privacy, where the entirety of data generation and processing $\mathcal{M}$
could be a black-box oracle; as shown in Section 4, we are able to control
such $f$-divergence without any algorithmic analysis of $\mathcal{M}$. We can
compute $\delta^{\rho}_{o}$ based on $\rho$ and $\mathsf{D}$ for any given
inference task. Given $\delta^{\rho}_{o}$, once we have the upper bound on
$\Delta_{f}\delta$, we can consequently lower bound the adversary’s failure
probability $\delta$ for inference since $\mathcal{D}_{f}$ is a deterministic
function.

In the following, we will mainly focus on $\Delta_{KL}\delta$ to control PAC
Privacy since mutual information is a well-studied quantity in information
theory and has many nice properties to simplify our analysis. Intuitively,
$\mathsf{MI}(X;\mathcal{M}(X))$ quantifies the dependence between $X$ and
$\mathcal{M}(X)$, and shows how much such instance-based information (in
nats/bits by taking $\log_{e}$/$\log_{2}$ in KL-divergence) is provided by
$\mathcal{M}(X)$ to support the adversary’s inference. Especially, when we
select $\mathcal{D}_{f}$ to be total variation and still
$\mathsf{P}_{W}=\mathsf{P}_{\mathcal{M}(X)}$,

${\Delta}_{TV}{\delta}=\delta^{\rho}_{o}-\delta\leq\mathcal{D}_{TV}\big{(}\mathsf{P}_{X,\mathcal{M}(X)}\|\mathsf{P}_{X}\otimes\mathsf{P}_{\mathcal{M}(X)}\big{)}.$

By Pinsker’s inequality, which states that for two distributions $\mathsf{P}$
and $\mathsf{Q}$ on the same measurable space,
${\Delta}_{TV}(\mathsf{P}\|\mathsf{Q})\leq\sqrt{\frac{1}{2}\cdot{\Delta}_{KL}(\mathsf{P}\|\mathsf{Q})},$
we have the following corollary to give a quantification on the more intuitive
and classic posterior advantage.

######  Corollary 1.

With the same setup as Theorem 1, the posterior advantage
$(\delta^{\rho}_{o}-\delta)$ for arbitrary $\rho$ is upper bounded as

$\Delta_{TV}\delta=\delta^{\rho}_{o}-\delta\leq\sqrt{\frac{1}{2}\cdot\mathsf{MI}\big{(}X;\mathcal{M}(X)\big{)}}.$

On the other hand, we can also apply Theorem 1 to interpret the classic worst-
case security definitions. To derive the data-independent maximal leakage when
exposing $\mathcal{M}(X)$, we may take a supremum on the right side of (2) and
study $\sup_{\mathsf{D},X\sim\mathsf{D}}\mathsf{MI}(X;\mathcal{M}(X))$
instead. Thus, the adversarial worst-case analysis can be used to produce a
(loose) upper bound of PAC Privacy. For example, if we know $\mathcal{M}$ is
$\epsilon$-DP, then
$\sup_{\mathsf{D},X\sim\mathsf{D}}\mathsf{MI}(X;\mathcal{M}(X))\leq
0.5\epsilon^{2}n^{2}$ for an $n$-datapoint set $X$ (Theorem 1.10 and
Proposition 1.4 in [14]).

With Theorem 1, our goal for the remainder of this paper is clear, where we
set out to determine or bound $\mathsf{MI}(X;\mathcal{M}(X))$ with high
confidence. We first move on to analyze an important special case where
$x_{i}$ is i.i.d. generated and $\mathcal{M}(\cdot)$ is a symmetric mechanism.
Here, we call $\mathcal{M}(x_{1},x_{2},\ldots,x_{n})$ symmetric if for an
arbitrary perturbation $\pi$ on $[1:n]$, the distribution of
$\mathcal{M}(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})$ is identical, where
each element $x_{i}$ is treated equally. Many data processing tasks satisfy
the symmetric property, for example mean/median estimation or empirical risk
minimization (ERM) in machine learning, where the order of samples does not
change the result. The main motivation to study this special case is that we
can show tighter and simpler bounds to control the security parameter $\delta$
in many applications, especially when the mechanism $\mathcal{M}$ is
deterministic with respect to $X$. This will become clear in Section 4. For
notional clarity, we will use $X\sim\bar{\mathsf{D}}^{n}$ to denote that
$x_{i}$ is i.i.d. generated from some distribution $\bar{\mathsf{D}}$ to
differentiate from the generic joint distribution case.

######  Theorem 2.

A mechanism $\mathcal{M}$ satisfies $(\delta,\rho,n,\mathsf{D})$ PAC
Individual Privacy if there exist $\delta_{i}$ for $i=1,2,\ldots,n,$
satisfying $\delta_{i}\geq\delta$ and

$\displaystyle\mathcal{D}_{KL}(\bm{1}_{\delta_{i}}\|\bm{1}_{\delta^{\rho}_{o,i}})\leq\mathsf{MI}\big{(}x_{i};\mathcal{M}(X)\big{)}.$
(3)

Here,
$1-\delta^{\rho}_{o,i}=\sup_{\tilde{x}_{i}\in\mathcal{X}}\Pr(\rho(\tilde{x}_{i},x_{i})=1)$
represents the optimal prior success rate of recovering $x_{i}$.

In particular, when $X\sim\bar{\mathsf{D}}^{n}$ and $\mathcal{M}$ is a
symmetric mechanism, then

$\delta\geq\sum_{j=1}^{n}\frac{\tilde{\delta}^{j}}{n},$

for any selection of $\tilde{\delta}^{j}$ satisfying
$\mathcal{D}_{KL}(\bm{1}_{\tilde{\delta}^{j}}\|\bm{1}_{\tilde{\delta}^{j,\rho}_{o}})\leq\mathsf{MI}\big{(}X;\mathcal{M}(X)\big{)},$
where

$1-\tilde{\delta}^{j,\rho}_{o}=\sum_{l=j}^{n}{n\choose
l}(\bar{\delta}^{\rho}_{o})^{n-l}\cdot(1-\bar{\delta}^{\rho}_{o})^{l},$ (4)

and
$1-\bar{\delta}^{\rho}_{o}=\sup_{\tilde{x}\in\mathcal{X}}\Pr_{x\sim\bar{D}}({\rho}(\tilde{x},x)=1).$

###### Proof.

See Appendix B. ∎

In Theorem 2, we point out that if our objective is individual privacy, we may
get tighter bounds by applying $\mathsf{MI}(x_{i};\mathcal{M}(X))$ rather than
$\mathsf{MI}(X;\mathcal{M}(X))$. By the chain rule of mutual information [24],
we know that $\mathsf{MI}(X;\mathcal{M}(X))$ is an upper bound for any
$\mathsf{MI}(x_{i};\mathcal{M}(X))$ since for any $i$,

$\mathsf{MI}(X;\mathcal{M}(X))=\mathsf{MI}(x_{i};\mathcal{M}(X))+\mathsf{MI}(X\backslash\\{x_{i}\\};\mathcal{M}(X)|x_{i})\geq\mathsf{MI}(x_{i};\mathcal{M}(X)).$

However, to analyze $\mathsf{MI}(x_{i};\mathcal{M}(X))$, generally we need to
take the other elements $X\backslash\\{x_{i}\\}$ as part of randomness seeds
and enforce $\mathcal{M}$ to be randomized, which makes it more difficult to
give tight bounds. Therefore, in the second part of Theorem 2, in the case of
i.i.d. data with symmetric processing, we give a more fine-grained analysis
but stick to $\mathsf{MI}(X,\mathcal{M}(X))$. The idea behind this is that we
consider the chance, denoted by $(1-\tilde{\delta}^{j})$, that the adversary
can successfully recover at least $j$ many elements out of an $n$-sample set
$X$, and use the symmetric property to bound the success rate of each
individual $x_{i}$.

######  Example 1 (Applications of Theorems 1 and 2).

We consider a set $X$ of $n$ datapoints where each datapoint $x_{i}$ is i.i.d.
uniformly selected from a finite set of size $N$ and $\mathcal{M}$ is some
symmetric mechanism. Suppose $N=100$ and for any given $i$, we know the
optimal prior success rate $(1-\delta^{\rho}_{o})$ to identify the true
selection of $x_{i}$ is $0.01$. When $\mathsf{MI}(X;\mathcal{M}(X))=1$, via
Theorem 1, by numerically solving
$\mathcal{D}_{KL}(\bm{1}_{\delta_{i}}\|\bm{1}_{0.99})\leq 1$, we have a global
bound $(1-\delta)\leq 0.36$ for any $n$.

Applying Theorem 2, a larger $n$ will produce a tighter bound of $(1-\delta)$.
Given $\mathsf{MI}(X;\mathcal{M}(X))=1$, we numerically solve
$\mathcal{D}_{KL}(\bm{1}_{\tilde{\delta}^{j}}\|\bm{1}_{\tilde{\delta}^{j,\rho}_{o}})\leq
1$ to obtain the lower bound of $\tilde{\delta}_{j}$, the failure probability
that an adversary can recover at least $j$ elements for $j=1,2,\cdots,n$, and
consequently obtain the lower bound of individual inference failure
probability $\delta$. When $n=10$, we have $(1-\delta)\leq 0.17,$ and when
$n=50$, we have $(1-\delta)\leq 0.06$.

So far, we have presented the generic bounds of PAC Privacy, and to ensure
desired security parameters, the problem is reduced to controlling the mutual
information $\mathsf{MI}(X;\mathcal{M}(X))$ (or
$\mathsf{MI}(x_{i};\mathcal{M}(X))$) with high confidence.

##  4 Automatic Control of Mutual Information

In this section, we present our main results on automatic privacy measurement
and control. At a high level, we want an automatic protocol which takes
security parameters as input and returns a privatization scheme on
$\mathcal{M}$ to ensure required privacy guarantees with high confidence. In
particular, we want the least assumptions on mechanism $\mathcal{M}$, which
ideally could be a black-box oracle and no specific algorithmic analysis is
needed to produce the security proof.

One natural idea to achieve information leakage control is perturbation: when
$\mathsf{MI}(X;\mathcal{M}(X))$ is not small enough to produce satisfied PAC
Privacy, we may add additional noise $\bm{B}$, say Gaussian, to produce
smaller $\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})$. In PAC Privacy, the role of
noise is not simply perturbation but to also enforce the output of a black-box
oracle into a class of parameterized distributions. As shown below for either
deterministic or randomized algorithms, with Gaussian noise, the analysis is
reduced to the study of divergences of Gaussian mixture models. The key
question left is how to automatically determine the parameters of the noise
$\bm{B}$. We give solutions in this section. In Section 4.1, we focus on the
deterministic $\mathcal{M}(\cdot)$ w.r.t. $X$, while, in Section 4.2, we
analyze generic randomized $\mathcal{M}(\cdot)$ w.r.t. either $X$ or a single
datapoint $x_{i}$. Finally, in Section 4.3, we discuss how to approximate the
optimal perturbation.

###  4.1 Deterministic Mechanism

The estimation of mutual information is a long-standing open problem, though
it enjoys a very simple expression via (conditional) entropy or KL-divergence.
Practical mutual information estimations have been studied in many empirical
works using deep learning [10], [21] or kernel methods [50] with different
motivations such as information bottleneck [62] and causality [15]. However,
one key obstacle to use those heuristic estimations is that we cannot derive a
high confidence bound and design necessary perturbation for rigorous security
guarantees.

In this section, we assume that $\mathcal{M}$ is some deterministic function
w.r.t. $X$, for example, $\mathcal{M}$ returns the average/median of $X$ or
the global optimum of some loss function determined by $X$. Beyond the
deterministic assumption, the only other restriction is that the output
$\mathcal{M}(X)$ is bounded. Without loss of generality, we assume the $l_{2}$
norm $\|\mathcal{M}(x)\|_{2}\leq r$. Since the distribution of
$\mathcal{M}(X)$ could be arbitrary over $\mathbb{B}^{d}_{r}$, the
$d$-dimensional $l_{2}$ ball of radius $r$ centered at zero, in general, there
do not exist non-trivial upper bounds of $\mathsf{MI}(X;\mathcal{M}(X))$.
Indeed, possibly counter-intuitively, we cannot even say that the aggregation
of a larger sample set would incur less information leakage. For example,
imagine a finite set $\mathsf{U}$ where the empirical means of its subsets are
distinct. $X$ represents a subset of $\mathsf{U}$ randomly selected and
$\mathcal{M}(X)$ outputs the average of $X$. Since there is a bijection
between $X$ and $\mathcal{M}(X)$,
$\mathsf{MI}(X;\mathcal{M}(X))=\mathcal{H}(X)=O(\log{2^{|\mathsf{U}|}})$,
increasing with $|\mathsf{U}|$.

Fortunately, adding continuous noise, especially Gaussian noise, enables us to
derive generic control of $\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})$. Continuous
noise $\bm{B}$ enforces the distribution of output $\mathcal{M}(X)+\bm{B}$ to
be parameterized and continuous regardless of $\mathcal{M}$ and $X$. Below, we
show how to apply covariance estimation to fully automatically determine a
noise $\bm{B}$ to control $\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})$ with
confidence for any black-box oracle $\mathcal{M}$. In the following, we simply
set $\bm{B}$ to be some multivariate Gaussian in a form
$\mathcal{N}(0,\Sigma_{\bm{B}})$, whose covariance is $\Sigma_{\bm{B}}$.
Similarly, $\Sigma_{\mathcal{M}(X)}$ represents the covariance matrix of
$\mathcal{M}(X)$.

######  Theorem 3.

For an arbitrary deterministic mechanism $\mathcal{M}$ and a Gaussian noise of
the form $\bm{B}\sim\mathcal{N}(\bm{0},\Sigma_{\bm{B}})$,

$\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})\leq\frac{1}{2}\cdot\log\text{det}\big{(}\bm{I}_{d}+\Sigma_{\mathcal{M}(X)}\cdot\Sigma^{-1}_{\bm{B}}\big{)}.$
(5)

In particular, let the eigenvalues of $\Sigma_{\mathcal{M}(X)}$ be
$(\lambda_{1},\ldots,\lambda_{d})$, then there exists some $\Sigma_{\bm{B}}$
such that
$\mathbb{E}[\|\bm{B}\|^{2}_{2}]=(\sum_{j=1}^{d}\sqrt{\lambda_{j}})^{2},$ and
$\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})\leq 1/2.$

###### Proof.

See Appendix C. ∎

From Theorem 3, we have a simple upper bound on the mutual information after
perturbation which only requires the knowledge of the covariance of
$\mathcal{M}(X)$ when $\mathcal{M}$ is deterministic. Another important and
appealing property is that the noise calibrated to ensure the target mutual
information bound is not explicitly dependent on the output dimensionality $d$
but instead on the square root sum of eigenvalues of
$\Sigma_{\mathcal{M}(X)}$. When $\mathcal{M}(X)$ is largely distributed in a
$p$-rank subspace of $\mathbb{R}^{d}$, Theorem 3 suggests that a noise of
scale $O(\sqrt{p})$ is needed. This is different from DP where the expected
$l_{2}$ norm of noise is in a scale of ${\Theta}(\sqrt{d})$ given constant
$l_{2}$-norm sensitivity; we will present a comprehensive comparison in
Section 6.

Based on Theorem 3, we now proceed to present an automatic protocol Algorithm
1 to determine $\Sigma_{\bm{B}}$ and produce an upper bound such that
$\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})\leq(v+\beta)$ with high confidence,
where $v$ and $\beta$ are positive parameters selected as explained below.
After sufficiently many simulations, the following theorem ensures that we can
obtain accurate enough estimation with arbitrarily high probability. A
characterization on the relationship among security parameter $c$, simulation
complexity $m$ and confidence parameter $\gamma$ is given in (6).

Algorithm 1 $(1-\gamma)$-Confidence Noise Determination of Deterministic
Mechanism $\mathcal{M}$

1: Input: A deterministic mechanism
$\mathcal{M}:\mathcal{X}^{*}\to\mathbb{B}^{d}_{r}$, data distribution
$\mathsf{D}$, sampling complexity $m$, security parameter $c$, and mutual
information quantities $v$ and $\beta$.

2: for $k=1,2,\ldots,m$ do

3: Independently generate data $X^{(k)}$ from distribution $\mathsf{D}$.

4: Record $y^{(k)}=\mathcal{M}(X^{(k)})$.

5: end for

6: Calculate empirical mean $\hat{\mu}={\sum_{k=1}^{m}y^{(k)}}/{m}$ and the
empirical covariance estimation
$\hat{\Sigma}={\sum_{k=1}^{m}(y^{(k)}-\hat{\mu})(y^{(k)}-\hat{\mu})^{T}}/{m}.$

7: Apply singular value decomposition (SVD) on $\hat{\Sigma}$ and obtain the
decomposition as $\hat{\Sigma}=\hat{U}\hat{\Lambda}\hat{U}^{T},$ where
$\hat{\Lambda}$ is the diagonal matrix of eigenvalues
$\hat{\lambda}_{1}\geq\hat{\lambda}_{2}\geq\ldots\geq\hat{\lambda}_{d}$.

8: Determine the maximal index $j_{0}=\arg\max_{j}\hat{\lambda}_{j}$, for
those $\hat{\lambda}_{j}>c$.

9: if $\min_{1\leq j\leq j_{0},1\leq l\leq
d}|\hat{\lambda}_{j}-\hat{\lambda}_{l}|>r\sqrt{dc}+2c$ then

10: for $j=1,2,\ldots,d$ do

11: Determine the $j$-th element of a diagonal matrix $\Lambda_{B}$ as
$\lambda_{B,j}=\frac{2v}{\sqrt{\hat{\lambda}_{j}+10cv/\beta}\cdot\big{(}\sum_{j=1}^{d}\sqrt{\hat{\lambda}_{j}+10cv/\beta}\big{)}}.$

12: end for

13: Determine the Gaussian noise covariance as
$\Sigma_{\bm{B}}=\hat{U}\Lambda^{-1}_{\bm{B}}\hat{U}^{T}$.

14: else

15: Determine the Gaussian noise covariance as
$\Sigma_{\bm{B}}=(\sum_{j=1}^{d}\hat{\lambda}_{j}+dc)/(2v)\cdot\bm{I}_{d}$.

16: end if

17: Output: Gaussian covariance matrix $\Sigma_{\bm{B}}$.

######  Theorem 4.

Assume that $\mathcal{M}(X)\in\mathbb{R}^{d}$ and $\|\mathcal{M}(X)\|_{2}\leq
r$ for some constant $r$ uniformly for any $X$, and apply Algorithm 1 to
obtain the Gaussian noise covariance $\Sigma_{\bm{B}}$ for a specified mutual
information bound $v+\beta$. $v$ and $\beta$ can be chosen independently, and
$c$ is a security parameter. Then, there exists a fixed and universal constant
$\kappa$ such that one can ensure $\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})\leq
v+\beta$ with confidence at least $(1-\gamma)$ once the selections of $c$, $m$
and $\gamma$ satisfy,

$c\geq\kappa
r\big{(}\max\\{\sqrt{\frac{d+\log(4/\gamma)}{m}},\frac{d+\log(4/\gamma)}{m}\\}+\sqrt{\frac{d\log(4/\gamma)}{m}}\big{)}.$
(6)

###### Proof.

See Appendix D. ∎

At a high level, Algorithm 1 shows a way to estimate both the eigenvectors and
the spectrum (eigenvalues) of the covariance matrix $\Sigma_{\mathcal{M}(X)}$
(lines 6-7), which afterwards determines the noise parameter $\Sigma_{\bm{B}}$
(lines 8-16) to ensure desired mutual information upper bound $(v+\beta)$. In
the first part, we simply apply the eigenvalue and eigenvectors of the
empirical covariance obtained by the results of $m$ simulations as the
estimations of those of the true covariance matrix $\Sigma_{\mathcal{M}(X)}$.
In the second part to determine the noise $\bm{B}$, depending on the
eigenvalue gap (line 9), we present two different upper bounds of
${\Sigma}_{\bm{B}}$ as explained later.

Theorem 6 presents a generic tradeoff between noise, sampling complexity and
confidence. The role of $c$ in Algorithm 1 is a safe parameter that provides a
lower bound on noise. From (6), in general, we may use a larger noise (larger
$c$ for looser noise estimation) to produce higher confidence (smaller
$\gamma$) given limited computation power $m$ for sampling and simulation; on
the other hand, both $c$ and $\beta$ can also be arbitrarily small provided
sufficiently many simulations $m$ to produce accurate enough estimation.

The main reason for the need to estimate the eigenvectors of
$\Sigma_{\mathcal{M}(X)}$ in Algorithm 1 is because we need the instance-based
noise to fit the geometry of the eigenspace of $\Sigma_{\mathcal{M}(X)}$. This
is different from the adversarial worst-case, such as DP, which only focuses
on the magnitude of sensitivity and adds isometric noise; in PAC Privacy, we
add anisotropic noise, as much as needed in each direction. The key intuition
behind why we can ensure arbitrarily high confidence is because the output
domain of $\mathcal{M}(X)$ is bounded and thus $\mathcal{M}(X)$ is in a
certain sub-Gaussian distribution with concentration guarantees captured by
bounded $r$. Therefore, provided sufficiently many simulations, we can
approximate the true covariance matrix $\Sigma_{\mathcal{M}(X)}$ with
arbitrary precision with a mild assumption on the eigenvalue gap.

It is noted that depending on the eigenvalue gap defined in line 9 of
Algorithm 1, there are two cases of perturbation. When the significant
eigenvalues of $\Sigma_{\mathcal{M}(X)}$ are distinct, then for arbitrary high
confidence $(1-\gamma)$, the determined noise covariance $\Sigma_{\bm{B}}$
matches that described in Theorem 3 given large enough $m$, which allows
selection of small enough $c$. However, though the spectrum of
$\Sigma_{\mathcal{M}(X)}$ can be estimated with arbitrary high precision, we
cannot ensure a satisfied eigenvector space approximation in our current
analysis framework without the assumption on the eigenvalue gap. To this end,
in the special case without the eigenvalue gap guarantee, we have to switch to
a more pessimistic perturbation (described in line 15 in Algorithm 1), where
the $l_{2}$ norm of the noise is then explicitly dimension dependent,
${\Theta}(\sqrt{d})$. In practice, such a case is very rare, and we leave the
improvement of Algorithm 1 or a tighter analysis as an open question.

###  4.2 Randomized Mechanism

We proceed to consider the more complicated case where the mechanism
$\mathcal{M}$ is randomized, where to be specific we use the form
$\mathcal{M}(X,\theta)$ and $\theta$ is the randomness seed. Given selection
of $\theta$, $\mathcal{M}(\cdot,\theta)$ becomes deterministic. As mentioned
earlier, to analyze $\mathsf{MI}(x_{i};\mathcal{M}(X))$, we can simply combine
$X\backslash\\{x_{i}\\}$, the other elements in $X$ without $x_{i}$, with
$\theta$ as randomness seeds. Therefore, without loss of generality, we only
focus on the control of $\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})$. The randomness
seed $\theta$ of mechanism $\mathcal{M}$ is randomly selected from a set
$\bm{\Theta}=\\{\theta_{1},\theta_{2},\ldots,\theta_{|\bm{\Theta}|}\\}$. As a
simple generalization of Theorem 3, we have the following bound.

######  Corollary 2.

$\mathsf{MI}(X;\mathcal{M}(X,\theta)+\bm{B}(\theta))\leq\mathbb{E}_{\theta}\frac{\log\text{det}(\bm{I}_{d}+\Sigma_{\mathcal{M}(X,\theta)}\cdot\Sigma^{-1}_{\bm{B}(\theta)})}{2}.$
(7)

Here, we assume a random-seed dependent Gaussian noise $\bm{B}(\theta)$, where
when $\theta=\theta_{0}$,
$\bm{B}\sim\mathcal{N}(0,\Sigma_{\bm{B}(\theta_{0})}).$

Corollary 2 utilizes the following properties of mutual information.

$\displaystyle\mathsf{MI}(\theta,\mathcal{M}(X,\theta);X)=\mathsf{MI}(\theta;X)+\mathsf{MI}(\mathcal{M}(X,\theta);X|\theta)=\mathsf{MI}(\mathcal{M}(X,\theta);X|\theta);$
$\mathsf{MI}(\theta,\mathcal{M}(X,\theta);X)=\mathsf{MI}(\mathcal{M}(X,\theta);X)+\mathsf{MI}(\theta;X|\mathcal{M}(X;\theta))\geq\mathsf{MI}(\mathcal{M}(X,\theta);X).$

Therefore, $\mathsf{MI}(X;\mathcal{M}(X,\theta)+\bm{B}(\theta))$ is upper
bounded by $\mathsf{MI}(X;\mathcal{M}(X,\theta)+\bm{B}(\theta)|\theta)$, where
given $\theta$, $\mathcal{M}$ is deterministic. Thus, we can apply the results
of Section 4.1 to control each subcase dependent on the selection of $\theta$,
and Corollary 2 follows straightforwardly. However, there are two potential
limitations of Corollary 2. First, there could be exponentially many possible
selections of $\theta$ and estimations on all $\Sigma_{\mathcal{M}(X,\theta)}$
could be intractable. The other issue is that (7) is tight only if for given
$\theta$, $\mathcal{M}(X,\theta)$ is concentrated. However, in some
applications this may not be true. One example is non-convex optimization,
e.g., we run SGD in deep learning. If the generalization error is small, the
global distributions of $\mathcal{M}(X,\theta)$ and
$\mathcal{M}(X^{\prime},\theta)$ for any two representative datasets $X$ and
$X^{\prime}$ could be very close, but different $X$ with different randomness
may converge to very different local minima. Therefore, we propose an
alternative approach as Algorithm 2 and its security proof is shown in Theorem
5.

In Algorithm 2, we need the following definition of minimal-permutation
distance. The minimal-permutation distance between two $k$-block vectors
$\bm{a}$ and $\bm{b}$ is defined as
$\mathsf{d}_{\pi}(\bm{a},\bm{b})=\min_{\pi}\sum_{j}\|\bm{a}(j)-\bm{b}(\pi(j))\|^{2}/k,$
where $\bm{a}(j)$ and $\bm{b}(j)$ represent their $j$-th blocks, respectively,
and $\pi$ is some permutation on the block index $[1:k]$.

Algorithm 2 $(1-\gamma)$-Confidence Noise Determination of Randomized
Mechanism $\mathcal{M}(\cdot,\theta)$

1: Input: A randomized mechanism
$\mathcal{M}(\cdot,\theta):\mathcal{X}^{*}\to\mathbb{B}^{d}_{r}$,
$\theta\in\bm{\Theta}$, data distribution $\mathsf{D}$, sampling complexity
$m$, mutual information bound $v$, and security parameters $c$ and $\tau$.

2: for $k=1,2,\ldots,m$ do

3: From distribution $\mathcal{D}$, independently sample ${X}^{(k)}_{1}$ and
${X}^{(k)}_{2}.$

4: Randomly select $\tau$ seeds, denoted by
${\mathcal{C}}^{(k)}=\\{\theta^{(k)}_{1},\theta^{(k)}_{2},\ldots,\theta^{(k)}_{\tau}\\}$,
from $\bm{\Theta}$.

5: Compute and record
$\bm{y}^{(k,1)}=\big{(}\mathcal{M}(X^{(k)}_{1},\theta^{(k)}_{1}),\ldots,\mathcal{M}(X^{(k)}_{1},\theta^{(k)}_{\tau})\big{)},$
$\bm{y}^{(k,2)}=\big{(}\mathcal{M}(X^{(k)}_{2},\theta^{(k)}_{1}),\ldots,\mathcal{M}(X^{(k)}_{2},\theta^{(k)}_{\tau})\big{)}.$

6: Compute minimal-permutation distance
$\psi^{(k)}=\mathsf{d}_{\pi}(\bm{y}^{(k,1)},\bm{y}^{(k,2)}).$

7: end for

8: Calculate empirical mean $\bar{\psi}=\sum_{k=1}^{m}\psi^{(k)}_{\tau}/m$.

9: Output: Gaussian covariance
$\Sigma_{\bm{B}}=\frac{\bar{\psi}+c}{2v}\cdot\bm{I}_{d}$.

######  Theorem 5.

Assume that $\mathcal{M}(X,\theta)\in\mathbb{R}^{d}$ and
$\|\mathcal{M}(X,\theta)\|_{2}\leq r$ for some constant $r$, and we apply
Algorithm 2 to obtain the Gaussian noise covariance $\Sigma_{\bm{B}}$ for a
specified mutual information bound $v$. Then, if $\frac{|\bm{\Theta}|}{\tau}$
is an integer, where $|\bm{\Theta}|$ is the total number of the randomness
seeds of $\mathcal{M}(\cdot,\theta)$ and $\tau$ is the number of seeds
selected in Algorithm 2, and $c$ is a safe parameter in Algorithm 2, one can
ensure that $\mathsf{MI}(X;\mathcal{M}(X,\theta)+\bm{B})\leq v$ with
confidence at least $1-\gamma$ once

$m\geq\frac{8r^{4}\log(1/\gamma)}{c^{2}}.$

###### Proof.

See Appendix E. ∎

In Algorithm 2, our key idea is to do sampling on the randomness seeds across
$\bm{\Theta}$ rather than accessing all possible selections of $\theta$.
Similar to Algorithm 1, we set a safe parameter $c$, which could be
arbitrarily small, to lower bound the magnitude of noise added. Given $c>0$,
combining the assumption that $\|\mathcal{M}(X,\theta)\|\leq r$, we have a
very rough but uniform upper bound on $\mathsf{MI}(X;\mathcal{M}(X,\theta))$
for any possible distributions of $X$ and $\mathcal{M}(X,\theta)$. With this
fact, in each iteration in Algorithm 2, we independently sample two data
inputs $\bar{X}^{k}=\\{X^{(k)}_{1},X^{(k)}_{2}\\}$, and
${\mathcal{C}}^{(k)}=\\{\theta^{(k)}_{1},\ldots,\theta^{(k)}_{\tau}\\}$ as a
random $\tau$-subset selection of $\theta$. It can be proved that

$\mathsf{MI}(X;\mathcal{M}(X,\theta)+\bm{B})\leq\mathbb{E}_{\bar{X}^{(k)},{\mathcal{C}}^{(k)},\theta\in\mathcal{C}^{(k)}}\mathcal{D}_{KL}\big{(}\mathsf{P}_{\mathcal{M}(X^{(k)}_{1},\theta)+\bm{B}}\|\mathsf{P}_{\mathcal{M}(X^{(k)}_{2},\theta)+\bm{B}}\big{)},$
(8)

Thus, it suffices to consider a conditional local distribution when $\theta$
is restricted to the $\tau$-subset selected. $\tau$ does not influence the
lower bound of sampling complexity $m$ required. However, a larger $\tau$,
which also requires higher computational complexity to evaluate more
$\mathcal{M}(X,\theta)$, will produce a tighter upper bound. The reason behind
this is that the conditional sub-sampled distribution with
$\theta\in{\mathcal{C}}^{(k)}$ gets closer to the global distribution with
$\theta\in\bm{\Theta}$ as $\tau$ increases. We assume $|\bm{\Theta}|/\tau$ is
an integer, i.e., we can split $\bm{\Theta}$ into multiple $\tau$-subsets, to
enable the application of minimal-perturbation distance $\mathsf{d}_{\pi}$
(Lemma 6 in Appendix E in the full version) to give a tighter upper bound of
the objective KL-divergence to estimate.

However, for any proper selection of $\tau$, the upper bound (8) always holds.
Thus, once we have a high-confidence estimation of the expectation on the
right side of (8), we also obtain a high-confidence upper bound on the
objective $\mathsf{MI}(X;\mathcal{M}(X,\theta)+\bm{B})$. Further, recall that
KL-divergence between $\mathsf{P}_{\mathcal{M}(X^{(k)}_{1},\theta)+\bm{B}}$
and $\mathsf{P}_{\mathcal{M}(X^{(k)}_{2},\theta)+\bm{B}}$ for
$\theta\in\mathcal{C}^{(k)}$ is always bounded given $c>0$ and bounded $r$.
Therefore, through i.i.d. sampling, we can simply use the empirical mean to
approximate the expectation with a high probability bound.

Before the end of this section, we have some comments on the computation
complexity of Algorithms 1 and 2. As mentioned before, the deterministic
$\mathcal{M}$ is a special case of the randomized processing and Algorithm 2
also applies to the deterministic $\mathcal{M}$ where we may view
$\bm{\Theta}$ as only containing a single randomness seed. As a comparison,
Algorithm 1 requires $O(\frac{d+\log(1/\gamma)}{c^{2}})$ simulation trials,
while Algorithm 2 only requires $O(\frac{\log(1/\gamma)}{c^{2}})$ simulation
trials. Here, we assume the parameters $r$ and $\beta$ are all constants. The
reason behind the dependence on the dimensionality $d$ in Algorithm 1 is
because to characterize the optimal Gaussian noise, we need to estimate the
power of output distribution $\mathcal{M}(X)$ in each direction in
$\mathbb{R}^{d}$, captured by the spectrum of $\Sigma_{\mathcal{M}(X)}$.
Though the estimation on $l_{2}$-norm based (minimal-permutation) distance is
more efficient, as a tradeoff, the noise upper bound produced by Algorithm 2
is looser, $\Theta(\sqrt{d})$, with a strict dependence on $d$. We will give a
concrete example for this gap between the noise bound derived from Algorithm 1
and Algorithm 2 in Example 3. We leave a more generic tradeoff between the
simulation efficiency and noise control to future work.

###  4.3 Towards Optimal Perturbation

The algorithms presented so far all produce conservative bounds of
perturbation. Indeed, even for mean estimation, we will show (Example 5 in
Section 6) that the gap between the proposed and the optimal perturbation
could be asymptotically large. Indeed, in both Algorithms 1 and 2, the
proposal of perturbation distribution $\mathsf{P}_{\bm{B}}$ of noise $\bm{B}$
is independent of the selections of input selection $X$ and randomness seed
$\theta$, while the optimal perturbation could be dependent on both.
Theoretically, we can define the optimal perturbation problem as follows.

######  Definition 9 (Optimal Perturbation).

Given a data generation distribution $\mathsf{D}$, a mechanism
$\mathcal{M}(\cdot,\theta)$, an objective mutual information bound $v$, and a
perturbation scheme $\bm{B}$ in a form that $\bm{B}(X,\theta)\sim
Q^{*}(X,\theta)$, i.e., $\bm{B}$ is generated from distribution
$Q^{*}(X,\theta)$ given selections of $X$ and $\theta$, we call the noise
distribution $Q^{*}(X,\theta)$ optimal w.r.t.
$(\mathsf{D},\mathcal{M},\mathcal{K})$ for some loss function $\mathcal{K}$,
if

$\displaystyle Q^{*}(X,\theta)$
$\displaystyle=\arg\inf_{Q}\mathbb{E}_{X,\theta,\bm{B}\sim
Q}\mathcal{K}\big{(}\bm{B}(X,\theta)\big{)},$ (9) $\displaystyle
s.t.\quad\mathsf{MI}$
$\displaystyle\big{(}X;\mathcal{M}(X,\theta)+\bm{B}(X,\theta)\big{)}\leq v.$

Optimal perturbation characterizes the least noise (measured by loss function
$\mathcal{K}$) that we have to add to achieve the required mutual information
bound $v$. For example, in many applications, we are mainly concerned with the
expected $l_{2}$ norm of perturbation, where
$\mathcal{K}(\mathcal{B}(X,\theta))=\|\mathcal{B}(X,\theta)\|_{2}.$ Though a
generic efficient solution to find the optimal perturbation may not exist, we
present a propose-then-verify framework to approximate the optimal solution.
Without loss of generality, we consider the generic setup where
$\mathcal{M}(\cdot,\theta)$, $\theta\in\bm{\Theta}$, could be randomized and
we consider an equivalent discrete data generation procedure to randomly
select $X$ from a set $\mathcal{X}^{*}=\\{X_{1},X_{2},\ldots,X_{N}\\}$ of size
$N$, where the $X_{i}$s are not necessarily all distinct.

Algorithm 3 $(1-\gamma)$-Confidence Verification of Perturbation Proposal

1: Input: A randomized mechanism
$\mathcal{M}(\cdot,\theta):\mathcal{X}^{*}\to\mathbb{B}^{d}_{r}$,
$\theta\in\bm{\Theta}$, $\mathcal{X}^{*}=\\{X_{1},X_{2},\ldots,X_{N}\\}$, a
perturbation proposal $\bm{B}(X,\theta)\sim Q(X,\theta)$, sampling complexity
$m$, security parameters $c$, $\tau_{1},\tau_{2}$ and $\tau_{3}$.

2: for $k=1,2,\ldots,m$ do

3: Randomly sample $\tau_{1}$ selections of $X$ from $\mathcal{X}^{*}$,
denoted by $\bar{X}^{(k,1)}=\\{X^{(k,1)}_{1},\ldots,X^{(k,1)}_{\tau_{1}}\\},$
and independently sample another $\tau_{2}$ selections of $X$, denoted by
$\bar{X}^{(k,2)}=\\{X^{(k,2)}_{1},\ldots,X^{(k,2)}_{\tau_{2}}\\}.$

4: Randomly sample $\tau_{3}$ selections of $\theta$ from $\bm{\Theta}$,
denoted by
$\mathcal{C}^{(k)}=\\{\theta^{(k)}_{1},\theta^{(k)}_{2},\ldots,\theta^{(k)}_{\tau_{3}}\\}.$

5: Define two sets of distributions for independent
$\bm{B}_{c}\sim\mathcal{N}(0,c\cdot\bm{I}_{d})$,
$\mathsf{P}^{(k,1)}_{i}=\sum_{j=1}^{\tau_{3}}\frac{1}{\tau_{3}}\cdot\big{(}\mathsf{P}_{\mathcal{M}(X^{(k,1)}_{i},\theta^{(k)}_{j})+\bm{B}(X^{(k,1)}_{i},\theta^{(k)}_{j})+\bm{B}_{c}}\big{)},i=1,2,\ldots,\tau_{1},$
$\mathsf{P}^{(k,2)}_{l}=\sum_{j=1}^{\tau_{3}}\frac{1}{\tau_{3}}\cdot\big{(}\mathsf{P}_{\mathcal{M}(X^{(k,2)}_{l},\theta^{(k)}_{j})+\bm{B}(X^{(k,2)}_{l},\theta^{(k)}_{j})+\bm{B}_{c}}\big{)},l=1,2,\ldots,\tau_{2}.$

6: Compute the average of KL-divergences,
$\psi^{(k)}=\sum_{i=1}^{\tau_{1}}\big{(}\frac{1}{\tau_{1}}\cdot\mathcal{D}_{KL}(\mathsf{P}^{(k,1)}_{i}\|\sum_{l=1}^{\tau_{2}}\frac{1}{\tau_{2}}\cdot\mathsf{P}^{(k,2)}_{l})\big{)}.$
(10)

7: end for

8: Calculate empirical mean $\bar{\psi}=\sum_{k=1}^{m}\psi^{(k)}/m$.

9: Output: $\bar{\psi}$.

######  Theorem 6.

Assume that $\mathcal{M}(X,\theta)\in\mathbb{R}^{d}$ and
$\|\mathcal{M}(X,\theta)\|_{2}\leq r$ for some constant $r$, and for any
perturbation proposal $Q(X,\theta)$, $\bm{B}(X,\theta)\sim Q(X,\theta)$, we
apply Algorithm 3 to obtain $\bar{\psi}$. Then, if $\frac{N}{\tau_{2}}$ and
$\frac{|\bm{\Theta}|}{\tau_{3}}$ are integers, one can ensure that
$\mathsf{MI}\big{(}X;\mathcal{M}(X,\theta)+\bm{B}(X,\theta)+\bm{B}_{c})\leq\bar{\psi}+\beta$
for an independent Gaussian noise of the form
$\bm{B}_{c}\sim\mathcal{N}(0,c\cdot\bm{I}_{d})$ with confidence at least
$1-\gamma$ when

$m\geq\frac{2\log(1/\gamma)}{\beta^{2}}\cdot\big{(}(2r^{2}/c)^{2}/\tau_{1}+\beta/3\cdot(2r^{2}/c)\big{)}.$

###### Proof.

See Appendix F. ∎

In Algorithm 3, we can give a high-confidence claim on the security parameters
produced by any perturbation proposal $Q(X,\theta)$. In practice, when input
set $X$ is large and representative enough, and the mechanism $\mathcal{M}$
can stably learn populational information from $X$, the distributions of
$\mathcal{M}(X)$ would be close to each other for most selections of $X$.
Therefore, an empirical approximation framework of optimal perturbation can be
described as follows.

  1. 1.

We follow Steps 3-5 in Algorithm 2 to sample and evaluate on some large enough
sets with respect to the selections of $X$ and $\theta$, respectively, and
optimize the noise distribution to minimize its $\mathcal{K}$ loss in (9) such
that the estimated divergence defined in (10) is smaller than $(1/O(1))\cdot
v$. Here, $v$ is the desired mutual information bound.

  2. 2.

Provided the locally-optimized noise proposal $\hat{Q}$, we can apply
Algorithm 3 to test $\hat{Q}$. If $\bm{B}\sim\hat{Q}$ does not produce the
desired mutual information bound $v$, we adjust $\bm{B}\sim\hat{Q}$ in a form
$\bm{B}+\bm{B}_{\alpha}$, where $\bm{B}_{\alpha}$ is an independent Gaussian
noise of the form $\mathcal{N}(0,\alpha\cdot\bm{I}_{d})$. We then perform
binary search on $\alpha$ via Algorithm 3 until we find a proper value.

##  5 Composition

In this section, we study the composition of PAC Privacy. Composition is an
important requirement of a practical security definition. Since the privacy
loss of any release cannot be revoked, it is necessary to keep track of the
accumulated leakage. Ideally, the respective privacy loss of multiple releases
is expected to be analytically aggregated to produce an upper bound on the
accumulated loss incurred. For example, it is well known that for two
mechanisms $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, which each satisfy
$(\epsilon_{0},\delta_{0})$-DP and use independent randomness, the composite
mechanism
$\bar{\mathcal{M}}(X)=\big{(}\mathcal{M}_{1}(X),\mathcal{M}_{2}(X)\big{)}$
then satisfies $(2\epsilon_{0},2\delta_{0})$-DP. With advanced composition,
one may obtain a sharpened bound
$\tilde{O}(\sqrt{T\log\delta^{\prime}}\epsilon_{0},T\delta_{0}+\delta^{\prime})$-DP
for a free parameter $\delta^{\prime}>0$ after a $T$-fold composition of
mechanisms each satisfying $(\epsilon_{0},\delta_{0})$-DP.

Composition also plays an important role in a classic privacy regime,
especially for DP, to analyze complicated algorithms. As mentioned before,
since the worst-case sensitivity is hard to compute, in general, to enable
non-trivial privacy analysis, a complex algorithm usually needs to be
artificially decomposed into multiple, relatively simpler operations.
Composition then provides a way to upper bound the entire leakage by
aggregating per-operation privacy loss. DP-SGD, one of the most widely-applied
DP optimization methods, is an example. The DP analysis is developed in a
compositional fashion where it is pessimistically assumed that intermediate
gradients across each iteration are released. The entire iterative
optimization is thus decomposed into multiple per-sample gradient aggregations
[1]. Accordingly, the DP composition result also shows a simple way to
determine the scale of noise required, which increases as
$\tilde{O}(\sqrt{T})$ to produce a fixed privacy guarantee.

However, we have to stress that in DP, the above described results only hold
when the randomness in different mechanisms is independent. This limitation
makes tight Differential Privacy in many applications intractable. For
example, if $\mathcal{M}_{[1:T]}$ represent $T$ sequential processings on
subsampled data from the sensitive $X$ set but the subsampling schemes in
different $\mathcal{M}_{[1:T]}$ are correlated, then more involved
compositional analysis is needed. In comparison, our PAC Privacy analysis
framework can indeed handle composition of arbitrary (possibly correlated)
mechanisms. Besides, PAC Privacy allows us to measure the end-to-end privacy
leakage of the output from an arbitrary (black-box) $\mathcal{M}$. Therefore,
there is no need to artificially decompose an algorithm and control leakage
step-by-step. This is one key difference compared to DP: we use composition in
PAC Privacy only when multiple releases are necessary.

We first consider the simplest case for $T$ mechanisms $\mathcal{M}_{[1:T]}$
where the data generation and randomness are both independent. By the chain
rule of mutual information, we then have the following equation,

$\mathsf{MI}(X_{[1:T]};\mathcal{M}_{1}(X_{1},\theta_{1}),\ldots,\mathcal{M}_{T}(X_{T},\theta_{T}))=\sum_{t=1}^{T}\mathsf{MI}(X_{t};\mathcal{M}_{t}(X_{t},\theta_{t})),$
(11)

which states that mutual information can be simply summed. Therefore, by
plugging $\sum_{k=1}^{T}\mathsf{MI}(X_{k};\mathcal{M}_{k}(X_{k}))$ into (2) in
Theorem 1, we can obtain an upper bound on the posterior advantage
$\Delta_{KL}\delta$, and accordingly a lower bound of $\delta$.

Now, we turn to consider the more generic scenario where $\mathcal{M}_{[1:T]}$
apply independent randomnesses but share the same input $X$ generated from
$\mathsf{D}$. Unfortunately, (11) does not hold anymore in this setup and
mutual information does not enjoy a triangle inequality:
$\mathsf{MI}(X;\mathcal{M}_{1}(X),\mathcal{M}_{2}(X))$ is not upper bounded by
$\mathsf{MI}(X;\mathcal{M}_{1}(X))+\mathsf{MI}(X;\mathcal{M}_{2}(X))$ in
general. This is also true for most other selections of $f$-divergence and
thus PAC Privacy, in general, cannot be simply summed up to produce an upper
bound. Fortunately, we will show below that the upper bound on mutual
information studied in Algorithm 2 and Theorem 5 can be simply summed up to
form a new bound under the composition. In other words, the PAC Privacy of
privatized algorithms using the proposed automatic analysis framework does
enjoy a simple summable composition bound.

######  Theorem 7.

For arbitrary $T$ mechanisms $\mathcal{M}_{t}(X,\theta_{t})$,
$t=1,2,\ldots,T$, whose randomness seeds $\theta_{t}$ are independently
selected, and data generation $X\sim\mathcal{D}$, if via Algorithm 2, for each
$\mathcal{M}_{t}$ a noise $\bm{B}_{t}$ is determined and independently
generated such that with confidence $(1-\gamma_{t})$,
$\mathsf{MI}(X;\mathcal{M}_{t}(X,\theta_{t}))\leq v_{t}$, then with confidence
$(1-\sum_{t=1}^{T}\gamma_{t})$,
$\mathsf{MI}(X;\mathcal{M}_{1}(X,\theta_{1}),\ldots,\mathcal{M}_{T}(X,\theta_{T}))\leq\sum_{t=1}^{T}v_{t}.$

###### Proof.

See Appendix G. ∎

From Theorem 7, when the mechanisms $M_{[1:T]}$ are identical, we need to
increase the noise by a factor at most $\sqrt{T}$ to ensure the same bound of
the $T$-composite mutual information compared to the case of a single
mechanism. Before proceeding, we have several important remarks. Even if one
does not know the mechanisms to be composed in advance, one can choose $v_{t}$
for each $\mathcal{M}_{t}$ in an online fashion and use Algorithm 2 to
determine appropriate noise for each exposure. Though the composition bound in
Theorem 7 is simple, tighter analysis exists using the proposed automatic
framework. It is noted that one can always build a new joint mechanism
$\bar{\mathcal{M}}$ which outputs
$\big{(}\mathcal{M}_{1}(X,\theta_{1}),\ldots,\mathcal{M}_{T}(X,\theta_{T})\big{)}$,
and simply apply Algorithm 2 on $\bar{\mathcal{M}}$ (or Algorithm 1 in the
deterministic case).

In the following, we move on to the even more generic case for adaptive
composition with correlated randomness. We consider $T$ mechanisms
$\mathcal{M}_{[1:T]}$ which are implemented in a sequential manner with
possibly correlated selection of randomness seeds. More formally, the output
$\mathcal{M}_{t}(X,{\theta}_{t},\mathcal{M}_{j}(X,\theta_{j}),j=1,2,\ldots,t-1)$
is defined by $X$, the randomness ${\theta}_{t}$, and the previous outputs
$\mathcal{M}_{j}(X,\theta_{j})$ for $j=1,2,\ldots,t-1$. Without loss of
generality, in the following, we use $\mathcal{M}_{t}(X,\bar{\theta}_{t})$ to
denote the $t$-th mechanism where
$\bar{\theta}_{t}=(\theta_{1},\ldots,\theta_{t})$ represents the joint
randomness seed and $\theta_{t}$ may be selected dependent on
$\bar{\theta}_{t-1}$. On the other hand, we are given a sequence of privacy
budgets $v_{0}=0<v_{1}<v_{2}<\ldots<v_{T}$ and our goal is to ensure that for
any $t=1,2,\ldots,T$, the accumulated privacy loss measured as mutual
information is upper bounded by $v_{t}$ with high confidence.

To this end, we propose an online implementation of Algorithm 2 described as
Algorithm 4. The key idea is still to incrementally aggregate existing
mechanisms to form a joint one, that we can apply similar techniques in
Algorithm 2 to analyze. Algorithm 4 has an initialization step (lines 2-6)
where $m$ input pairs $(X^{(k)}_{1},X^{(k)}_{2}),k=1,2,...,m$, are randomly
generated from $\mathsf{D}$, and for each pair we select $\tau$ randomness
seeds $\bar{\theta}^{(k)}_{1,l}$, $l=1,2,\ldots,\tau$, for $\mathcal{M}_{1}$
(lines 3-4). In the online phase, for steps $t>1$, we generate new randomness
seeds $\bar{\theta}^{(k)}_{t,l}$ conditional on $\bar{\theta}^{(k)}_{t-1,l}$
determined previously (line 9) and continue the simulations on newly-incoming
$\mathcal{M}_{t}$ over the same $m$ input pairs selected (line 11). This saves
computation, avoiding reevaluating $\mathcal{M}_{[1:t-1]}$ on fresh samples
and randomness. Given previous noise schemes $\bm{B}_{[1:(t-1)]}$ determined
by Algorithm 4 such that
$\mathsf{MI}(X;{\mathcal{M}}_{1}(X,\bar{\theta}_{1})+\bm{B}_{1},\ldots,{\mathcal{M}}_{t-1}(X,\bar{\theta}_{t-1})+\bm{B}_{t-1})\leq
v_{t-1}$, we can always determine some independent Gaussian noise $\bm{B}_{t}$
such that

$\mathsf{MI}(X;{\mathcal{M}}_{1}(X,\bar{\theta}_{1})+\bm{B}_{1},\ldots,{\mathcal{M}}_{t-1}(X,\bar{\theta}_{t-1})+\bm{B}_{t-1},{\mathcal{M}}_{t}(X,\bar{\theta}_{t})+\bm{B}_{t})\leq
v_{t},$

for any $v_{t}>v_{t-1}$ with high confidence. The following theorem describes
the tradeoff between the confidence level and sampling complexity.

######  Theorem 8.

Assume that $\mathcal{M}_{t}(X,\bar{\theta}_{t})\in\mathcal{R}^{d}$ and
$\|\mathcal{M}_{t}(X,\bar{\theta}_{t})\|_{2}\leq r$ uniformly for some
constant $r$, for $t=1,2,\ldots,T$, and we apply Algorithm 4 which returns a
sequence of Gaussian noise covariances $\Sigma_{\bm{B}_{t}}$ in an online
setup. Then, one can ensure that
$\mathsf{MI}(X;{\mathcal{M}}_{1}(X,\bar{\theta}_{1})+\bm{B}_{1},\ldots,{\mathcal{M}}_{t}(X,\bar{\theta}_{t})+\bm{B}_{t})\leq
v_{t}$ for any $t=1,2,\ldots,T,$ with confidence at least $1-\gamma$ once
$m\geq\frac{8r^{4}\log(T/\gamma)}{c^{2}}$. $c$ as before is a security
parameter.

###### Proof.

See Appendix H. ∎

As a final remark, though the deterministic algorithm is a special case of the
randomized algorithm (with a single randomness seed as discussed earlier) and
we can always use Algorithm 2 for privacy analysis, Algorithm 1 can usually
produce tighter noise bounds. However, the composition of the PAC Privacy
result derived from Algorithm 1 is more involved, which depends on the
eigenspace estimated. We leave the generalization of Theorem 7 for Algorithm 1
as an open problem. However, with simulations on incrementally aggregated
mechanisms to be composed, one can similarly build an online version of
Algorithm 1 to determine the perturbation sequentially given increasing
privacy budget for composition.

######  Example 2 (Composition).

We take the Hospital dataset from Mathworks Sample
222https://www.mathworks.com/help/stats/sample-data-sets.html as an example.
This set contains the records of 100 patients and we consider two mechanisms
$\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ which return the average of ages,
weight, and the average of blood pressure range, respectively. We consider
randomly selecting 50 individual samples to form the input $X$ and via
Algorithm 2 we need Gaussian noises $\mathbb{E}[\|\bm{B}_{1}\|_{2}]=6.85$ and
$\mathbb{E}[\|\bm{B}_{2}\|_{2}]=2.60$ to ensure that
$\mathsf{MI}(X;\mathcal{M}_{1}(X)+\bm{B}_{1})\leq 0.5$ and
$\mathsf{MI}(X;\mathcal{M}_{2}(X)+\bm{B}_{2})\leq 0.5$. With the simple
composition bound, we have that
$\mathsf{MI}(X;\mathcal{M}_{1}(X)+\bm{B}_{1},\mathcal{M}_{2}(X)+\bm{B}_{2})\leq
1$. As a comparison, by applying the automatic analysis on the joint mechanism
$\bar{M}=(\mathcal{M}_{1},\mathcal{M}_{2})$, we obtain a tighter noise bound
where there exists certain Gaussian noise $\bar{\bm{B}}$ with
$\mathbb{E}[\|\bar{\bm{B}}\|_{2}]=4.57$ to ensure
$\mathsf{MI}(X;\bar{\mathcal{M}}(X)+\bar{\bm{B}})\leq 1$. Using the simple
composition, it is noted that the noise magnitude
$\mathbb{E}[\|(\bm{B}_{1},\bm{B}_{2})\|_{2}]=7.32,$ when we handle
$\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ separately with lower-complexity
privacy analysis.

Algorithm 4 Online Noise Determination of Adaptively-Composed Randomized
Mechanisms $\mathcal{M}_{[1:T]}$

1: Input: A set of randomized mechanisms
$\mathcal{M}_{t}(\cdot,\bar{\theta}_{t}):\mathcal{X}^{*}\times\bm{\Theta}^{*}\to\mathbb{B}^{d}_{r}$,
$\bar{\theta}_{t}\in\bm{\Theta}_{1}\times\ldots\times\bm{\Theta}_{t}$, where
$\mathcal{M}_{t}(\cdot,\bar{\theta}_{t})$ is provided at time slot $t$ for
$t=1,2,\ldots,T$, data distribution $\mathsf{D}$, sampling complexity $m$,
security parameters $c$, $\tau$, and privacy budget
$\\{v_{0}=0,v_{1},v_{2},\ldots,v_{T}\\}$ such that
$0<v_{1}<v_{2}<\ldots<v_{T}$.

2: for $k=1,2,\ldots,m$ do

3: From distribution $\mathcal{D}$, independently sample ${X}^{(k)}_{1}$ and
${X}^{(k)}_{2}.$

4: Initially randomly select $\tau$ seeds, denoted by
$\bar{\mathcal{C}}^{(k)}_{1}=\\{\bar{\theta}^{(k)}_{1,1},\bar{\theta}^{(k)}_{1,2},\ldots,\bar{\theta}^{(k)}_{1,\tau}\\}$,
$\bar{\theta}^{(k)}_{1,l}\in\bm{\Theta}_{1}$.

5: end for

6: for $t=1,2,\ldots,T$ do

7: for $k=1,2,\ldots,m$ do

8: if $t>1$ then

9: Conditional on $\bar{\theta}^{(k)}_{t-1,l}$, randomly select
$\theta^{(k)}_{t,l}\in\bm{\Theta}_{t}$ and form a new joint seed
$\bar{\theta}^{(k)}_{t,l}=(\bar{\theta}^{(k)}_{t-1,l},\theta^{(k)}_{t,l})$,
for $l=1,2,\ldots,\tau$.

10: end if

11: Compute and record
$\bm{y}^{(k,1)}_{t}=\big{(}\mathcal{M}_{t}(X^{(k)}_{1},\bar{\theta}^{(k)}_{t,1}),\ldots,\mathcal{M}_{t}(X^{(k)}_{1},\bar{\theta}^{(k)}_{t,\tau})\big{)},$
$\bm{y}^{(k,2)}_{t}=\big{(}\mathcal{M}_{t}(X^{(k)}_{2},\bar{\theta}^{(k)}_{t,1}),\ldots,\mathcal{M}_{t}(X^{(k)}_{2},\bar{\theta}^{(k)}_{t,\tau})\big{)}.$

12: Compute averaged $l_{2}$-norm pairwise distance
$\psi^{(k)}_{t}={\|y^{(k,1)}_{t}-y^{(k,2)}_{t}\|^{2}_{2}}/{\tau}.$

13: end for

14: Calculate empirical mean $\bar{\psi}_{t}=\sum_{k=1}^{m}\psi^{(k)}_{t}/m$.

15: Output: Gaussian covariance
$\Sigma_{\bm{B}_{t}}=\frac{\bar{\psi}_{t}+c}{2(v_{t}-v_{t-1})}\cdot\bm{I}_{d}$.

16: end for

##  6 Comparison between Adversarial and Instance-based Worst Case

We start by a lower bound of the Gaussian noise if we want to ensure an input-
independent upper bound of the mutual information.

######  Theorem 9 (Lower Bound of Adversarial Gaussian Mechanism).

Given that $\|\mathcal{M}(X)\|_{2}\leq r$, for an arbitrary Gaussian
perturbation mechanism $Q(y)=\mathcal{N}(0,\Sigma(y))$, i.e., when
$\mathcal{M}(X)=y\in\mathbb{B}^{d}_{r}$, we generate $\bm{B}\sim Q(y)$ and
publish $\mathcal{M}(X)+\bm{B}$. Given $v=o(1)$, if

$\sup_{\mathcal{M},\mathsf{P}_{X}}\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})\leq v,$

then for any $y\in\mathbb{B}^{d}_{r}$ and $\bm{B}\sim Q(y)$,
$\mathbb{E}[\|\bm{B}\|_{2}]=\Omega(r\sqrt{d}/\sqrt{v}).$

###### Proof.

See Appendix I. ∎

From Theorem 9, we see that if we want a data-independent Gaussian
perturbation to ensure bounded mutual information in the adversarial worst
case, we must add a noise of magnitude of $\Omega(r\sqrt{d}/\sqrt{v})$ to any
possible output $\mathcal{M}(X)$333In Theorem 9, we restrict the noise
distribution to be Gaussian. We leave a generic lower bound for arbitrary
noise distribution as an open problem.. On the other hand, from Theorem 3, we
know this bound is also tight where a Gaussian noise of magnitude
$O(r\sqrt{d}/\sqrt{v})$ can universally ensure the mutual information is
bounded by $v$. This matches our intuition that without any other assumptions
if we want to hide arbitrary information disclosure (bounded by $r$ in $l_{2}$
norm), we need noise on each direction in $\mathbb{R}^{d}$ in a scale of
$\Omega(r)$, which finally produces the $\Omega(r\sqrt{d})$ magnitude. This,
in general, makes the perturbed release useless. Therefore, for a particular
processing mechanism $\mathcal{M}$, when the practical data is far away from
the adversarial worst case or the data-independent worst-case proof cannot be
tightly produced, there could be a huge utility compromise relative to the PAC
Privacy measurement from an instance-based angle.

######  Example 3 (Membership Inference from Mean Estimation).

We suppose $\mathsf{U}$ to be CIFAR10 [45], a canonical test dataset commonly
used in computer vision, which consists of $60,000$ $32\times 32$ color
images. We normalize each pixel to within $[0,1]$ and take each sample as a
3072-dimensional vector. We suppose each of the $60,000$ $3072$-dimensional
samples is i.i.d. randomly selected into the set $X$, where the expected
cardinality of $|X|$ equals $30,000$, to conduct the mean estimation analysis,
where $\mathcal{M}(X)$ simply returns the sum of $X$ divided by $30,000$, as
an unbiased mean estimator. Via Algorithm 1, we have that an independent
Gaussian noise whose $\mathbb{E}[\|\bm{B}\|_{2}]=0.28$ is sufficient to ensure
$\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})\leq 1$. On the other hand, in the
adversarial worst-case setup, the data of normalized pixel suggests that the
$l_{\infty}$-norm of the sensitivity is bounded by $1$. The mutual information
bound requires $\xi=1/60000$-zCDP [14], in turn requiring a noise
$\mathbb{E}[\|\bm{B}\|_{2}]=17.7$, which is 63$\times$ larger than the
instance-based analysis. As a comparison, if we apply Algorithm 2 to compute
the noise bound, it is required that $\mathbb{E}[\|\bm{B}\|_{2}]=3.94$ which
is looser compared to $0.28$ obtained from Algorithm 1, though it is more
efficient and only requires the estimation on the (pair-wise) $l_{2}$ distance
among simulation outputs.

In Example 3, we already utilize the property that each data point is
independently sampled and the individual sensitivity of the averaging operator
has a closed form $O(1/n)$ to get a tighter bound for the adversarial worst
case [14]444If each entry of $X$ is independently generated, and $\mathcal{M}$
satisfies $\xi$-Concentrated Differential Privacy (CDP), then
$\mathsf{MI}(X;\mathcal{M}(X))\leq n\xi$ [14]. . However, in general, when the
sampling is not independent or the sensitivity is intractable, one may need to
adopt the loose noise bound shown in Theorem 9, where a noise in a scale of
$2.2\times 10^{3}$ is needed. Below, we provide such an example where
producing a non-trivial adversarial worst-case proof remains open.

######  Example 4 (Private Machine Learning).

We consider measuring data leakage of deep learning on practical data. In
general, in machine learning, our goal is to optimize the weights/parameters
$w$ of some model, viewed as some function $G(\cdot,w)$, to minimize the loss
$\min_{w}\mathbb{E}_{(x,y)}\mathcal{L}\big{(}G(x,w),y\big{)}$. Here,
$\mathcal{L}$ represents some loss function, while $x$ and $y$ represent the
feature and label of a sample, respectively. Ideally, we expect the trained
out model $G(x,w)$ to predict the true label $y$ well.

In this example, we consider training a three-layer fully-connected neural
network on the MNIST dataset [47]. MNIST contains $70,000$ $28\times 28$
handwritten-digit images. We consider a data generation $X$ by randomly
sampling $35,000$ samples out of the entire data set. The neural network has
three layers, where the weights of the first layer are a $784\times 30$
matrix, those of the second layer are a $30\times 30$ matrix, and those of the
last layer are a $30\times 10$ matrix. We select the activation function
between layers to be the Relu function and use cross-entropy as the loss
function, as a common setup in deep learning [46]. The total number of
parameters in this network is $24,790$. Let the mechanism $\mathcal{M}$
correspond to running full-batch gradient descent for $1,500$ iterations with
step size $0.05$ and outputting the final weight obtained. From Algorithm 1,
we have that an independent Gaussian noise $\mathbb{E}[\|\bm{B}\|_{2}]=3.7$ is
sufficient to ensure $\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})\leq 1$. Non-
privately, the trained-out neural network achieves $94.8\%$ classification
accuracy; under the perturbation to ensure PAC Privacy, we achieve an accuracy
of $93.5\%$, i.e., a slight compromise. Unfortunately, for the adversarial
data-independent worst case, the sensitivity/stability of generic non-convex
optimization remains open 555An upper bound on individual sensitivity of
Empirical Risk Minimization is only known for strongly-convex optimization
[18] with an additional Lipschitz assumption and the loss function needs to be
a sum of individual losses on each sample..

Before the end of this section, we want to point out that there could be an
asymptotically large gap between our proposed conservative perturbation and
the optimal noise required, in particular for the individual privacy case.

######  Example 5 (Gap to Optimal Perturbation).

We return to the problem of mean estimation of Gaussian distributions
mentioned in Section 1, where we assume each
$x_{i}\in\mathbb{R}^{d}\sim\mathcal{N}(\mu,\Sigma)$ and
$\mathcal{M}(X)=1/n\cdot\sum_{i=1}^{n}x_{i}$. We focus on the individual
privacy $\mathsf{MI}(x_{i};\mathcal{M}(X))$ and set out to quantify the least
noise needed. For any independent Gaussian noise,
$\bm{B}^{\prime}\sim\mathcal{N}(0,\Sigma_{\bm{B}^{\prime}})$, we have

$\mathsf{MI}(x_{i};\mathcal{M}(X)+\bm{B}^{\prime})=\frac{1}{2}\cdot\log\big{(}det\big{(}(\frac{1}{n}\cdot\Sigma+\Sigma_{\bm{B}^{\prime}})\cdot(\frac{(n-1)}{n^{2}}\cdot\Sigma+\Sigma_{\bm{B}^{\prime}})^{-1}\big{)}\big{)}.$
(12)

On the other hand, when we apply Algorithm 1 and measure
$\mathsf{MI}(X;\mathcal{M}(X))$ as a uniform upper bound,

$\mathsf{MI}(X;\mathcal{M}(X)+\bm{B})=\frac{1}{2}\cdot\log\big{(}det\big{(}(\frac{1}{n}\cdot\Sigma+\Sigma_{\bm{B}})\cdot\Sigma^{-1}_{\bm{B}}\big{)}\big{)}.$
(13)

From $(\ref{gau_true})$ and $(\ref{gau_est})$, we can determine the
corresponding Gaussian noises to ensure a mutual information bound $v$ and
their gap shows as a lower bound of the gap between $\bm{B}$ and the optimal
perturbation $\bm{B}_{o}$, since in this example we already restrict the
noises to be Gaussian. With some calculation, we have

$\small{\mathbb{E}[\|\bm{B}\|^{2}_{2}]-\mathbb{E}[\|\bm{B}_{o}\|^{2}_{2}]\geq\left\\{\begin{aligned}
&\mathbb{E}[\|\bm{B}\|^{2}_{2}]=\frac{1}{2v}\cdot(\sum_{j=1}^{d}\sqrt{\lambda_{j}})^{2},&v\geq\frac{d}{n-1}\\\
&\sum_{j=1}^{d}\min\\{\sqrt{\lambda_{j}}(\sum_{j=1}^{d}\sqrt{\lambda_{j}})/(2v),(n-1)\lambda_{j}\\},&v<\frac{d}{n-1}.\end{aligned}\right.}$
(14)

Here, $\lambda_{[1:d]}$ are the eigenvalues of $\Sigma$. From
$(\ref{noise_gap})$, when the privacy budget $v\geq d/(n-1)$, there is even no
need to add noise; in the high privacy regime, such a gap could be
$\Omega(n\operatorname{Tr}(\Sigma_{\mathcal{M}(X)})).$ Therefore, there is
still much room to improve the current analysis.

##  7 Related Works

###  7.1 Differential Privacy

DP is the most successful and practical information-theoretic privacy notion
over the last two decades. Lower bounds both in DP noise [34], [41] and
Theorem 9 suggest that, in general, there is no free lunch for input-
independent privacy guarantees – to produce meaningful security parameters,
the perturbation could be much larger than the objective disclosure and
destroy the released information. This is especially true in the high-
dimensional case, known as the curse of dimensionality. DP and our PAC Privacy
propose two different solutions to overcome this challenge.

Differential Privacy (DP) can be most naturally interpreted in a binary
hypothesis form. Consider two adjacent datasets $S_{0}$ and $S_{1}$ which only
differ in one individual datapoint and two hypotheses: $H_{0}$ where the input
set is $S_{0}$, and $H_{1}$ where the input set is $S_{1}$. A strong DP
guarantee implies that the hypothesis testing error (a combination of Type I
and II errors) is large [28]. In general, when the adversarial objective is
specified to identify the secret from a class of candidates, such inference
can be naturally characterized by a (multiple) hypothesis testing model, and
one natural privacy definition is to measure the lower bound of the
probability when the adversary outputs a wrong guess [17].

The beauty of DP in bridging meaningful privacy and tolerable utility
compromise is to focus on an individual datapoint rather than the entire
sensitive dataset. DP stays within the data-independent privacy regime.
$\epsilon$-DP for constant $\epsilon$ cannot make meaningful guarantees for
the entire data, because the security parameter grows linearly with
$n\epsilon$ for the privacy concern of $n$ datapoints (group privacy).
However, a noise of magnitude $O(\sqrt{d}/n)$ can hide any individual among
the $n$-population if one can ensure an $O(1/n)$ sensitivity. Therefore, once
the population size $n$ is large enough and we can ensure the contribution
from each individual to the output is limited enough, reasonably small
perturbation can ensure good individual privacy, interpreted as some constant
hypothesis test error [5]. However, as mentioned before, the worst-case
sensitivity proof becomes the key step in DP, which is generally not easy
beyond simple aggregation.

PAC Privacy tackles this challenge by enforcing the privacy measurement to be
instance-based to get rid of the restriction from data-independent
impossibilities. In terms of the objective to protect, PAC Privacy is stronger
and more generic, where now the privacy of the entire dataset could be
preserved once the processing mechanism $\mathcal{M}(X)$ learns or behaves
stably based on some population property of the underlying distribution
$\mathsf{D}$, from which the sensitive data $X$ is generated. Individual
Privacy is only a special case in PAC Privacy. One can imagine that if the
output of $\mathcal{M}$ is only dependent on the distribution $\mathsf{D}$,
$X$ is then independent of $\mathcal{M}(X)$ and we achieve perfect secrecy
with respect to the whole dataset. In particular, for applications in machine
learning, PAC Privacy would benefit from strong learning algorithms
$\mathcal{M}$ of good generalization. More details can be found in Section
7.2.

However, PAC Privacy also has limitations since it is not applicable when we
cannot simulate or we don’t have access to the data generation of $X$. In
contrast, data-independent privacy (if it can be proven) can always work with
meaningful interpretation regardless of any assumptions on priors. But for
most statistical data processing, where we are allowed to conduct the analysis
on subsampled data, this limitation can be overcome. Even for a given
deterministic dataset, through sub-sampling we can enforce that the selected
samples enjoy entropy and PAC Privacy provides a strong security
interpretation: even the adversary, who has full knowledge of the data pool,
cannot infer too much about selected samples in the processing mechanism
$\mathcal{M}$.

###  7.2 Other Privacy Metrics and Learning Theory Quantities

Mutual Information (MI) based Attack and Privacy Definition: MI is a well-
studied measure on the dependence between two random variables quantified in
information bits. Naturally, one may consider the MI between the secret and
the release/leakage for security purposes. A large number of existing works
apply MI to construct side-channel attacks [9, 35] or even simply adopt MI as
a privacy definition [16, 48]. For example, given known plaintexts, [35] built
a distinguisher based on empirical MI estimation where the adversary proposes
a guessing of the encryption key with the highest correlation score regarding
the side-channel leakage. [16] showed further asymptotic analysis of empirical
MI estimations under discrete randomness. Though we use $f$-divergence, where
MI based on KL-divergence is a special case, to develop impossibility results
as the foundation of PAC Privacy, our motivations and results are very
different from those prior works. On one hand, PAC Privacy is rigorously
resistant to arbitrary adversary attacks666Besides MI, there are many other
efficient side-channel attacks based on different statistical tests such as
Pearson correlation [13]., without any restrictions on the adversary’s
inference strategy or the computation power. In addition, PAC Privacy does not
use MI or other information metrics, such as Fisher information [32],
discussed below, or anonymity set [55, 60], as the leakage measurement, which,
in general, lack semantic security interpretation. Unfortunately, except DP,
most of those metrics are not semantic. For example, recent work [23] argued
that the concept of anonymity set does not resist singling-out attacks and
does not produce desirable individual privacy guarantees. In contrast, the
entire theory developed for PAC Privacy is devoted to answering the
fundamental question of how to quantify the hardness of an arbitrary
adversarial inference task.

DP under Adversary Uncertainty: With a different motivation to add less noise,
there is a line of works such as distributional DP [6] and noiseless privacy
[12], which study the relaxation of DP and take the data entropy into account.
As mentioned before, the original DP definition ensures indistinguishable
likelihoods of any two adjacent datasets in the worst case. Instead, [6, 12]
considered statistical adjacent datasets where both their common part and the
differing datapoint are generated from some distributions. The goal of such
relaxation is to exploit the data entropy to substitute (part of) the external
perturbation for the release. However, since those works are still developed
within the DP framework, [6, 12] encounter similar restrictions as those in
generic DP analysis. First, analytical distributional DP [6] and noiseless
privacy [12] bounds are only known for a limited number of applications with
very specific assumptions on the underlying data distributions. Second, the
privacy concern is still regarding the participation of an individual. In
contrast, PAC Privacy can automatically handle any black-box data generation
and processing mechanism for arbitrary adversarial inference.

Empirical Membership Inference/Data Reconstruction: As a consequence of the
loose/conservative worst-case privacy analysis such as DP [29] and maximal
leakage [42], a large number of works are devoted to empirically measuring the
actual information leakage [57, 68] or the actual privacy guarantees produced
by existing privatization methods [52, 61] especially in machine learning. For
example, [57] measured the influence of overfitting on the adversary’s
advantage of membership or attribute inference. The results in [57] suggest
that without proper privacy preservation, many popular machine learning
algorithms could have severe privacy risks. On the other hand, [52]
empirically studied the actual privacy guarantee provided by DP-SGD and showed
that there is a substantial gap between the best theoretical bound we can
claim so far and the practical distinguishing advantage of the adversary. [61]
studied DP-SGD from a different angle. [61] showed that compared to
distinguishing individual participation, DP-SGD may provide a much stronger
privacy guarantee against extraction of rare features in training data. In
other words, certain data reconstruction tasks could be much harder than
simply identifying the enrollment of an individual sample. This matches our
earlier discussion on data reconstruction and distinguishing attack in the
introduction section. Empirical works on overfitting and generalization
control are complementary, and can instruct the design of more stable
processing mechanisms with better privacy-utility tradeoff under PAC Privacy.

Fisher Privacy: A recently proposed privacy metric, which also measures the
data reconstruction error, is rooted in the Fisher information and the
Cramér–Rao bound, and is termed Fisher information leakage [32, 39, 40]. Given
an upper bound of Fisher information, one can lower bound the expected $l_{2}$
norm of reconstruction error for an adversary with given bias. However, Fisher
information leakage is still input-independent and based on likelihood
difference. There are several essential differences compared to priors-based
PAC Privacy. First, to apply the Cramér–Rao bound in data reconstruction, the
bias of the adversary’s reconstruction on each selection of $X$ must be
specified beforehand, while the optimal selection of such point-wise bias is,
in general, unknown. In contrast, PAC Privacy does not put any restrictions or
assumptions on the adversary’s strategy. Second, Fisher information only
measures the mean squared error whereas PAC Privacy handles impossibility of
arbitrary inference tasks and criteria.

Generalization Error: In learning theory, generalization error is defined as
the gap between the loss (prediction accuracy) by applying the trained model
on local data (seen) and on the data population (unseen) [67]. To be formal,
in our context, let $\mathcal{M}(X)$ represent the model learned via the
(possibly randomized) algorithm $\mathcal{M}$ from a set of samples $X$,
generated from some distribution $\mathsf{D}$. Given some loss $\mathcal{L}$,
the generalization error is defined as

$\text{Gen}(\mathsf{D},\mathcal{M})=\mathbb{E}_{\bar{X}\perp
X\sim\mathsf{D},\mathcal{M}}\big{(}\mathcal{L}(\bar{X},\mathcal{M}(X))\big{)}-\mathbb{E}_{X\sim\mathsf{D},\mathcal{M}}\big{(}\mathcal{L}(X,\mathcal{M}(X))\big{)}.$

$\bar{X}\perp X\sim\mathsf{D}$ represents that $\bar{X}$ and $X$ are i.i.d. in
$\mathsf{D}$. $\mathbb{E}_{\bar{X}\perp
X\sim\mathsf{D},\mathcal{M}}\big{(}\mathcal{L}(\bar{X},\mathcal{M}(X))\big{)}$
captures the expected accuracy from the model $\mathcal{M}(X)$ on population
data, while
$\mathbb{E}_{X\sim\mathsf{D},\mathcal{M}}\big{(}\mathcal{L}(X,\mathcal{M}(X))\big{)}$
captures the expected training accuracy. It is well known that DP can control
the generalization error [7]. Indeed, the relationship between DP, PAC Privacy
and generalization error can be described as follows. As mentioned earlier, DP
guarantees of $\mathcal{M}(X)$ can upper bound the mutual information
$\mathsf{MI}(X;\mathcal{M}(X))$ [14], and from [67],
$\mathsf{MI}(X;\mathcal{M}(X))$ can then upper bound the generalization error.
In the following, we show that PAC Privacy can also control the generalization
error. For simplicity, we assume that the distribution $\mathsf{D}$ of $X$ is
uniform over a finite set $\mathcal{X}^{*}=\\{X_{1},X_{2},\ldots,X_{N}\\}$ of
$N$ elements.

######  Theorem 10.

For any given $\mathcal{M}:\mathcal{X}^{*}\to\mathcal{Y}$, and loss function
$\mathcal{L}:(\mathcal{X}^{*},\mathcal{Y})\to(0,1)$, suppose $\mathsf{D}$ is a
uniform distribution over $\mathcal{X}^{*}$. If $\mathcal{M}$ satisfies
$\Delta_{KL}\delta\leq v$, for the criterion $\rho(\tilde{X},X)=1$ if
$\tilde{X}=X$, i.e., the identification problem, then we have
$\text{Gen}(\mathsf{D},\mathcal{M})\leq\sqrt{v/2}$.

###### Proof.

See Appendix J. ∎

However, we need to stress that the reverse direction does not hold in
general. Recall the example of mutual information in mean estimation in
Section 4.1: we can construct some discrete distribution where given
sufficiently many samples one can learn the true mean arbitrarily accurately
but the mean estimator $\mathcal{M}$ could be a bijective function, where
$\mathcal{M}(X)$ essentially leaks everything about $X$. However, small
generalization error does help PAC Privacy if the learning mechanism ensures
the trained out model is close to the population optimum. Thus, even in a case
that $\mathcal{M}(\cdot)$ is bijective, we only need small noise to satisfy a
mutual information bound.

##  8 Conclusions and Prospects

In this paper, we propose and study a new instance-based information-theoretic
privacy notion, termed PAC Privacy. PAC Privacy enjoys intuitive and
meaningful interpretations: it enables concrete measurement on the adversary’s
success rate or the posterior advantage for arbitrary data
inference/reconstruction task with the observation of disclosures. A simple
quantification via generic $f$-divergence is presented. More importantly,
based on data priors, we show an automatic privacy analysis and proof
generation framework, where theoretically no algorithmic worst-case proof is
needed. Data leakage control of black-box oracles becomes possible via PAC
Privacy. Though the instance-based and adversarial setups are, in general,
incomparable, PAC Privacy does have strong connections to cryptography and DP.
Indeed, many problems or concerns in the research or applications of DP and
cryptography have a corresponding version in PAC Privacy. The underlying
technical challenges are not necessarily the same but motivations are very
similar. We list some interesting problems here.

Gap between the Local and Central: Collaboration of semi-honest users to
amplify local DP via shuffling models has been recently proposed and studied
in [22], [30]. The key idea is to securely aggregate the local noisy response
from each user, where the underlying locally added noises also aggregate to
produce a more powerful perturbation with amplified privacy. As analyzed in
Appendix K, via MPC, PAC Privacy analysis can be implemented in a
decentralized setup and each user’s local PAC Privacy would then also benefit
from other people’s data entropy, similar to a centralized case. However,
local PAC Privacy puts more requirements on MPC, and cheap MPC implementation
is a key challenge in making it practical in large-scale systems.

Optimal Perturbation: Minimal perturbation is another fundamental problem in
both PAC Privacy and DP. In DP, the theoretical study of (asymptotically)
optimal utility loss in different data processing remains very active. Many
tight results are known for mean estimation [3], convex ERM optimization [8]
with specific solution restrictions like on $l_{1}$ norm [2], stochastic
optimization [33], and principal component analysis (PCA) [19]. All these
problems can also be systemically studied under PAC Privacy. While in PAC
Privacy, privacy at a certain level could come for free (see Example 5), our
current automatic framework needs noise to produce generic high-confidence
security parameters. Therefore, besides a theoretically tight perturbation
bound, PAC Privacy also raises its own special research problem, i.e., how to
efficiently implement privacy analysis protocols and produce perturbation
schemes matching the optimal bound? For example, with assistance of public
data, how can we properly truncate the output domain and reduce
sampling/simulation complexity?

Acknowledgements: We gratefully acknowledge the support of DSTA Singapore,
Cisco Systems, Capital One, and a MathWorks fellowship. We also thank the
anonymous reviewers for their helpful comments.

## References

  * [1] Abadi, M., Chu, A., Goodfellow, I., McMahan, H.B., Mironov, I., Talwar, K., Zhang, L.: Deep learning with differential privacy. In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. pp. 308–318 (2016)
  * [2] Asi, H., Feldman, V., Koren, T., Talwar, K.: Private stochastic convex optimization: Optimal rates in l1 geometry. In: International Conference on Machine Learning. pp. 393–403. PMLR (2021)
  * [3] Asi, H., Feldman, V., Talwar, K.: Optimal algorithms for mean estimation under local differential privacy. arXiv preprint arXiv:2205.02466 (2022)
  * [4] Balle, B., Barthe, G., Gaboardi, M.: Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems 31 (2018)
  * [5] Balle, B., Barthe, G., Gaboardi, M., Hsu, J., Sato, T.: Hypothesis testing interpretations and renyi differential privacy. In: International Conference on Artificial Intelligence and Statistics. pp. 2496–2506. PMLR (2020)
  * [6] Bassily, R., Groce, A., Katz, J., Smith, A.: Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 439–448. IEEE (2013)
  * [7] Bassily, R., Nissim, K., Smith, A., Steinke, T., Stemmer, U., Ullman, J.: Algorithmic stability for adaptive data analysis. In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. pp. 1046–1059 (2016)
  * [8] Bassily, R., Smith, A., Thakurta, A.: Private empirical risk minimization: Efficient algorithms and tight error bounds. In: 2014 IEEE 55th annual symposium on foundations of computer science. pp. 464–473. IEEE (2014)
  * [9] Batina, L., Gierlichs, B., Prouff, E., Rivain, M., Standaert, F.X., Veyrat-Charvillon, N.: Mutual information analysis: a comprehensive study. Journal of Cryptology 24(2), 269–291 (2011)
  * [10] Belghazi, M.I., Baratin, A., Rajeswar, S., Ozair, S., Bengio, Y., Courville, A., Hjelm, R.D.: Mine: mutual information neural estimation. arXiv preprint arXiv:1801.04062 (2018)
  * [11] Ben-Sasson, E., Fehr, S., Ostrovsky, R.: Near-linear unconditionally-secure multiparty computation with a dishonest minority. In: Annual Cryptology Conference. pp. 663–680. Springer (2012)
  * [12] Bhaskar, R., Bhowmick, A., Goyal, V., Laxman, S., Thakurta, A.: Noiseless database privacy. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 215–232. Springer (2011)
  * [13] Brier, E., Clavier, C., Olivier, F.: Correlation power analysis with a leakage model. In: International workshop on cryptographic hardware and embedded systems. pp. 16–29. Springer (2004)
  * [14] Bun, M., Steinke, T.: Concentrated differential privacy: Simplifications, extensions, and lower bounds. In: Theory of Cryptography Conference. pp. 635–658. Springer (2016)
  * [15] Butte, A.J., Kohane, I.S.: Mutual information relevance networks: functional genomic clustering using pairwise entropy measurements. In: Biocomputing 2000, pp. 418–429. World Scientific (1999)
  * [16] Chatzikokolakis, K., Chothia, T., Guha, A.: Statistical measurement of information leakage. In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems. pp. 390–404. Springer (2010)
  * [17] Chatzikokolakis, K., Palamidessi, C., Panangaden, P.: Probability of error in information-hiding protocols. In: 20th IEEE Computer Security Foundations Symposium (CSF’07). pp. 341–354. IEEE (2007)
  * [18] Chaudhuri, K., Monteleoni, C., Sarwate, A.D.: Differentially private empirical risk minimization. Journal of Machine Learning Research 12(3) (2011)
  * [19] Chaudhuri, K., Sarwate, A., Sinha, K.: Near-optimal differentially private principal components. Advances in neural information processing systems 25 (2012)
  * [20] Chen, S., Wang, R., Wang, X., Zhang, K.: Side-channel leaks in web applications: A reality today, a challenge tomorrow. In: 2010 IEEE Symposium on Security and Privacy. pp. 191–206. IEEE (2010)
  * [21] Cheng, P., Hao, W., Dai, S., Liu, J., Gan, Z., Carin, L.: Club: A contrastive log-ratio upper bound of mutual information. In: International conference on machine learning. pp. 1779–1788. PMLR (2020)
  * [22] Cheu, A., Smith, A., Ullman, J., Zeber, D., Zhilyaev, M.: Distributed differential privacy via shuffling. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 375–403. Springer (2019)
  * [23] Cohen, A., Nissim, K.: Towards formalizing the gdpr’s notion of singling out. Proceedings of the National Academy of Sciences 117(15), 8344–8352 (2020)
  * [24] Cover, T.M.: Elements of information theory. John Wiley & Sons (1999)
  * [25] Cramer, R., Damgård, I.B., et al.: Secure multiparty computation. Cambridge University Press (2015)
  * [26] Davies, S., Mazumdar, A., Pal, S., Rashtchian, C.: Lower bounds on the total variation distance between mixtures of two Gaussians. In: International Conference on Algorithmic Learning Theory. pp. 319–341. PMLR (2022)
  * [27] Devroye, L., Mehrabian, A., Reddad, T.: The total variation distance between high-dimensional gaussians. arXiv preprint arXiv:1810.08693 (2018)
  * [28] Dong, J., Roth, A., Su, W.J.: Gaussian differential privacy. arXiv preprint arXiv:1905.02383 (2019)
  * [29] Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Theory of cryptography conference. pp. 265–284. Springer (2006)
  * [30] Erlingsson, Ú., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., Thakurta, A.: Amplification by shuffling: From local to central differential privacy via anonymity. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2468–2479. SIAM (2019)
  * [31] Erlingsson, Ú., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., Thakurta, A.: Amplification by shuffling: From local to central differential privacy via anonymity. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2468–2479. SIAM (2019)
  * [32] Farokhi, F., Sandberg, H.: Fisher information as a measure of privacy: Preserving privacy of households with smart meters using batteries. IEEE Transactions on Smart Grid 9(5), 4726–4734 (2017)
  * [33] Feldman, V., Koren, T., Talwar, K.: Private stochastic convex optimization: optimal rates in linear time. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. pp. 439–449 (2020)
  * [34] Geng, Q., Viswanath, P.: Optimal noise adding mechanisms for approximate differential privacy. IEEE Transactions on Information Theory 62(2), 952–969 (2015)
  * [35] Gierlichs, B., Batina, L., Tuyls, P., Preneel, B.: Mutual information analysis. In: International Workshop on Cryptographic Hardware and Embedded Systems. pp. 426–442. Springer (2008)
  * [36] Goldwasser, S., Klein, S., Mossel, E., Tamuz, O.: Publicly verifiable randomness (2018)
  * [37] Goldwasser, S., Micali, S.: Probabilistic encryption & how to play mental poker keeping secret all partial information. In: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 365–377 (1982)
  * [38] Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of computer and system sciences 28(2), 270–299 (1984)
  * [39] Guo, C., Karrer, B., Chaudhuri, K., van der Maaten, L.: Bounding training data reconstruction in private (deep) learning. arXiv preprint arXiv:2201.12383 (2022)
  * [40] Hannun, A., Guo, C., van der Maaten, L.: Measuring data leakage in machine-learning models with fisher information. In: Uncertainty in Artificial Intelligence. pp. 760–770. PMLR (2021)
  * [41] Hardt, M., Talwar, K.: On the geometry of differential privacy. In: Proceedings of the forty-second ACM symposium on Theory of computing. pp. 705–714 (2010)
  * [42] Issa, I., Wagner, A.B., Kamath, S.: An operational approach to information leakage. IEEE Transactions on Information Theory 66(3), 1625–1657 (2019)
  * [43] Jin, C., Netrapalli, P., Ge, R., Kakade, S.M., Jordan, M.I.: A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03736 (2019)
  * [44] Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately? SIAM Journal on Computing 40(3), 793–826 (2011)
  * [45] Krizhevsky, A., Hinton, G., et al.: Learning multiple layers of features from tiny images (2009)
  * [46] LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. Nature 521(7553), 436–444 (2015)
  * [47] LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proceedings of the IEEE 86(11), 2278–2324 (1998)
  * [48] Makhdoumi, A., Salamatian, S., Fawaz, N., Médard, M.: From the information bottleneck to the privacy funnel. In: 2014 IEEE Information Theory Workshop (ITW 2014). pp. 501–505. IEEE (2014)
  * [49] Mironov, I.: Rényi differential privacy. In: 2017 IEEE 30th computer security foundations symposium (CSF). pp. 263–275. IEEE (2017)
  * [50] Moon, Y.I., Rajagopalan, B., Lall, U.: Estimation of mutual information using kernel density estimators. Physical Review E 52(3), 2318 (1995)
  * [51] Murtagh, J., Vadhan, S.: The complexity of computing the optimal composition of differential privacy. In: Theory of Cryptography Conference. pp. 157–175. Springer (2016)
  * [52] Nasr, M., Songi, S., Thakurta, A., Papemoti, N., Carlin, N.: Adversary instantiation: Lower bounds for differentially private machine learning. In: 2021 IEEE Symposium on Security and Privacy (SP). pp. 866–882. IEEE (2021)
  * [53] Pinsker, M.S., Prelov, V.V., Verdu, S.: Sensitivity of channel capacity. IEEE Transactions on Information Theory 41(6), 1877–1888 (1995)
  * [54] Sason, I., Verdú, S.: $f$-divergence inequalities. IEEE Transactions on Information Theory 62(11), 5973–6006 (2016)
  * [55] Serjantov, A., Danezis, G.: Towards an information theoretic metric for anonymity. In: Privacy Enhancing Technologies: Second International Workshop, PET 2002 San Francisco, CA, USA, April 14–15, 2002 Revised Papers 2. pp. 41–53. Springer (2003)
  * [56] Shannon, C.E.: Communication theory of secrecy systems. The Bell system technical journal 28(4), 656–715 (1949)
  * [57] Shokri, R., Stronati, M., Song, C., Shmatikov, V.: Membership inference attacks against machine learning models. In: 2017 IEEE symposium on security and privacy (SP). pp. 3–18. IEEE (2017)
  * [58] Shorten, C., Khoshgoftaar, T.M.: A survey on image data augmentation for deep learning. Journal of big data 6(1), 1–48 (2019)
  * [59] Stefanov, E., Dijk, M.V., Shi, E., Chan, T.H.H., Fletcher, C., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol. Journal of the ACM (JACM) 65(4), 1–26 (2018)
  * [60] Steinbrecher, S., Köpsell, S.: Modelling unlinkability. In: International workshop on privacy enhancing technologies. pp. 32–47. Springer (2003)
  * [61] Stock, P., Shilov, I., Mironov, I., Sablayrolles, A.: Defending against reconstruction attacks with r$\backslash$’enyi differential privacy. arXiv preprint arXiv:2202.07623 (2022)
  * [62] Tishby, N., Pereira, F.C., Bialek, W.: The information bottleneck method. arXiv preprint physics/0004057 (2000)
  * [63] Valiant, L.G.: A theory of the learnable. Communications of the ACM 27(11), 1134–1142 (1984)
  * [64] Vershynin, R.: High-dimensional probability: An introduction with applications in data science, vol. 47. Cambridge university press (2018)
  * [65] Wang, Y.X., Balle, B., Kasiviswanathan, S.P.: Subsampled rényi differential privacy and analytical moments accountant. In: The 22nd International Conference on Artificial Intelligence and Statistics. pp. 1226–1235. PMLR (2019)
  * [66] Xiao, X., Tao, Y.: Output perturbation with query relaxation. Proceedings of the VLDB Endowment 1(1), 857–869 (2008)
  * [67] Xu, A., Raginsky, M.: Information-theoretic analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems 30 (2017)
  * [68] Yeom, S., Giacomelli, I., Fredrikson, M., Jha, S.: Privacy risk in machine learning: Analyzing the connection to overfitting. In: 2018 IEEE 31st computer security foundations symposium (CSF). pp. 268–282. IEEE (2018)

Appendix

##  Appendix A Proof of Theorem 1 and Corollary 1

To start, we need the following lemmas.

######  Lemma 1.

Given any $f$-divergence $\mathcal{D}_{f}(\cdot\|\cdot)$, and three Bernoulli
distributions $\bm{1}_{a}$, $\bm{1}_{b}$ and $\bm{1}_{c}$ of parameters $a$,
$b$ and $c$, respectively, where $0\leq a\leq b\leq c\leq 1$. Then,
$\mathcal{D}_{f}(\bm{1}_{a}\|\bm{1}_{b})\leq\mathcal{D}_{f}(\bm{1}_{a}\|\bm{1}_{c}).$

###### Proof.

By the definition,
$g(x)=\mathcal{D}_{f}(\bm{1}_{a}\|\bm{1}_{x})=xf(\frac{a}{x})+(1-x)f(\frac{1-a}{1-x})$
and we want to show $g(x)$ is non-decreasing for $x\geq a$. With some
calculation,
$g^{\prime}(x)=\big{(}f(\frac{a}{x})-\frac{a}{x}f^{\prime}(\frac{a}{x})\big{)}-\big{(}f(\frac{1-a}{1-x})-\frac{1-a}{1-x}f^{\prime}(\frac{1-a}{1-x})\big{)}.$
It is noted that $\frac{a}{x}\leq\frac{1-a}{1-x}$ for $x\geq a$. Thus, to show
$g^{\prime}(x)\geq 0$ for $x\geq a$, it suffices to show
$t(y)=f(y)-yf^{\prime}(y)$ is non-increasing with respect to $y\in[0,1]$. On
the other hand,
$t^{\prime}(y)=f^{\prime}(y)-f^{\prime}(y)-yf^{\prime\prime}(y)\leq 0$ due to
the convex assumption of $f$. Therefore, the claim holds. ∎∎

######  Lemma 2 (Data Processing Inequality [54]).

Consider a channel that produces $Z$ given $Y$ based on the law described as a
conditional distribution $\mathsf{P}_{Z|Y}$. If $\mathsf{P}_{Z}$ is the
distribution of $Z$ when $Y$ is generated by $\mathsf{P}_{Y}$, and
$\mathsf{Q}_{Z}$ is the distribution of $Z$ when $Y$ is generated by
$\mathsf{Q}_{Y}$, then for any f-divergence $\mathcal{D}_{f}$,

$\mathcal{D}_{f}(\mathsf{P}_{Z}\|\mathsf{Q}_{Z})\leq\mathcal{D}_{f}(\mathsf{P}_{Y}\|\mathsf{Q}_{Y}).$

Now, we return to prove Theorem 1. First, we have the observation that for a
random variable $X^{\prime}\in\mathcal{X}^{*}$ in an arbitrary distribution
but independent of $X$, $\delta^{\rho}_{o}\leq\Pr_{X^{\prime}\perp
X}\big{(}\rho(X^{\prime},X)=1\big{)},$ since $\delta^{\rho}_{o}$ is the
minimum failure probability achieved by optimal a priori estimation. Here,
$a\perp b$ represents that $a$ is independent of $b$. Let the indicator be a
function that for two random variables $a$ and $b$, $\bm{1}(a,b)=1$ if
$\rho(a,b)=1$, otherwise $0$. Apply Lemma 1 and Lemma 2, where we view
$\bm{1}(\cdot,\cdot)$ as a post-processing on $(X,\tilde{X})$ and
$(X,{X}^{\prime})$, respectively, we have that

$\mathcal{D}_{f}\big{(}\bm{1}_{\delta}\|\bm{1}_{\delta^{\rho}_{o}}\big{)}\leq\mathcal{D}_{f}\big{(}\bm{1}(X,\tilde{X})\|\bm{1}(X,X^{\prime})\big{)}\leq\mathcal{D}_{f}\big{(}\mathsf{P}_{X,\tilde{X}}\|\mathsf{P}_{X,X^{\prime}}\big{)}=\mathcal{D}_{f}\big{(}\mathsf{P}_{X,\tilde{X}}\|\mathsf{P}_{X}\otimes\mathsf{P}_{X^{\prime}}\big{)}.$

On the other hand, we know $X\to\mathcal{M}(X)\to\tilde{X}$ forms a Markov
chain, where the adversary’s estimation $\tilde{X}$ is dependent on
observation $\mathcal{M}(X)$. Let the adversary’s strategy be some operator
$g_{adv}$ where $\tilde{X}=g_{adv}(\mathcal{M}(X))$. Therefore, we can apply
the data processing inequality again, where

$\mathcal{D}_{f}\big{(}\mathsf{P}_{X,\tilde{X}}\|\mathsf{P}_{X,X^{\prime}}\big{)}\leq\mathcal{D}_{f}\big{(}\mathsf{P}_{X,\mathcal{M}(X)}\|\mathsf{P}_{X,W}\big{)}=\mathcal{D}_{f}\big{(}\mathsf{P}_{X,\mathcal{M}(X)}\|\mathsf{P}_{X}\otimes\mathsf{P}_{W}\big{)}.$

Here, $X^{\prime}=g_{adv}(W)$ and $W$ is still independent of $X$. Since the
above inequalities hold for arbitrarily distributed $X^{\prime}$ once it is
independent of $X$, $W$ could also be an arbitrary random variable on the same
support domain as $\mathcal{M}(X)$ and independent of $X$. Therefore,

$\mathcal{D}_{f}\big{(}\bm{1}_{\delta}\|\bm{1}_{\delta^{\rho}_{o}}\big{)}\leq\inf_{\mathsf{P}_{W}}\mathcal{D}_{f}\big{(}\mathsf{P}_{X,\mathcal{M}(X)}\|\mathsf{P}_{X}\otimes\mathsf{P}_{W}\big{)}=\inf_{\mathsf{P}_{W}}\mathcal{D}_{f}\big{(}\mathsf{P}_{\mathcal{M}(X)|X}\|\mathsf{P}_{W}|\mathsf{P}_{X}).$

Here, we use $|\mathsf{P}_{X}$ to denote that it is conditional on $X$ in a
distribution $\mathsf{P}_{X}$. In particular, if we select $\mathsf{P}_{W}$ to
be the distribution of $\mathcal{M}(X)$, and take $\mathsf{D}_{f}$ to be KL-
divergence, we have
$\mathcal{D}_{KL}\big{(}\bm{1}_{\delta}\|\bm{1}_{\delta^{\rho}_{o}}\big{)}\leq\mathsf{MI}(X;\mathcal{M}(X)).$

##  Appendix B Proof of Theorem 2

The first part of Theorem 2 is a simple corollary of Theorem 1. When we
separately consider the adversary’s inference on each $x_{i}$, take $x_{i}$ as
the $X$ in the proof of Theorem 1 and a similar reasoning will produce the
upper bound on each posterior success rate $(1-\delta_{i})$, and the claim
follows.

Consider the second part of Theorem 2, where we assume the $x_{i}$ is i.i.d.
generated and $\mathcal{M}$ is some symmetric mechanism. We apply Theorem 1 to
upper bound the success rate that the adversary can recover at least $j$ many
$x_{i}$s out of the total $X$, as some generic inference on the whole data
$X$. Due to the i.i.d. assumption, we know the optimal a priori success rate
to recover a single $x_{i}$ equals
$1-\bar{\delta}^{\rho}_{o}=\sup_{\tilde{x}}\Pr(\rho(\tilde{x},x)=1).$
Consequently, the optimal a priori success rate to recover at least $j$ out of
$n$ samples is $\tilde{\delta}^{j,\rho}_{o}=\sum_{l=j}^{n}{n\choose
l}(\bar{\delta}^{\rho}_{o})^{n-l}\cdot(1-\bar{\delta}^{\rho}_{o})^{l}.$ Thus,
applying Theorem 1, we have that the optimal posterior success rate on
recovering at least $j$ samples $(1-\tilde{\delta}^{j})$ satisfies

$\mathcal{D}_{KL}(\bm{1}_{\tilde{\delta}^{j}}\|\bm{1}_{\tilde{\delta}^{j,\rho}_{o}})\leq\mathsf{MI}\big{(}X;\mathcal{M}(X)\big{)}.$

On the other hand, due to the i.i.d. and the symmetric assumption of
$\mathcal{M}$, we know $\mathsf{MI}(x_{i};\mathcal{M}(X))$ is identical, for
any $i\in[1:n]$. The optimal posterior success rate to recover every single
$x_{i}$ is the same as $(1-\delta)$. Therefore, let the indicator
$\bm{1}_{x_{i}}$ represent whether $x_{i}$ is successfully recovered. The
expected number of samples that an adversary can recover satisfies

$n(1-\delta)=\mathbb{E}[\sum_{i=1}^{n}\bm{1}_{x_{i}}]\leq\sum_{j=1}^{n}(1-\tilde{\delta}^{j}).$

Here, we use Fubini’s theorem on the expectation calculation, where for a
random variable $Y$ defined over $\mathbb{Z}^{+}$,

$\mathbb{E}[Y]=\sum_{j=1}^{+\infty}\Pr(Y\geq j).$

Thus, we obtain the desired lower bound of $\delta$ expressed by
$\tilde{\delta}^{j}$ for $j=1,2,\ldots,n$.

##  Appendix C Proof of Theorem 3

$\displaystyle\mathsf{MI}(X;\mathcal{M}(X)+B)$ (15)
$\displaystyle=\int\mathcal{D}_{KL}(\mathsf{P}_{\mathcal{M}(X_{0})+B}\|\mathsf{P}_{B})\mathsf{P}(X=X_{0})\leavevmode\nobreak\
dX_{0}-\mathcal{D}_{KL}(\mathsf{P}_{\mathcal{M}(X)+B}\|\mathsf{P}_{B})$
$\displaystyle=\int\mathcal{D}_{KL}(\mathsf{P}_{\mathcal{M}(X_{0})+B}\|\mathsf{P}_{B})\mathsf{P}(X=X_{0})\leavevmode\nobreak\
dX_{0}-\big{(}\mathcal{D}_{KL}(\mathsf{P}_{\mathcal{M}(X)+B}\|\mathsf{P}_{Gau(\mathcal{M}(X)+B)})+\mathcal{D}_{KL}(\mathsf{P}_{Gau(\mathcal{M}(X)+B)}\|\mathsf{P}_{B})\big{)}$
$\displaystyle\leq\int\mathcal{D}_{KL}(\mathsf{P}_{\mathcal{M}(X_{0})+B}\|\mathsf{P}_{B})\mathsf{P}(X=X_{0})\leavevmode\nobreak\
dX_{0}-\mathcal{D}_{KL}(\mathsf{P}_{Gau(\mathcal{M}(X)+B)}\|\mathsf{P}_{B}).$

Given the definition of mutual information, we first apply the results of
Gaussian approximation [53], where $Gau(A)$ represents a (multivariate)
Gaussian variable with the same mean and (co)variance as those of $A$. Then,
we drop a negative term to obtain the final inequality of (15). Next, focusing
on the integral (first) term in (15),

$\mathcal{D}_{KL}(\mathsf{P}_{\mathcal{M}(X_{0})+B}\|\mathsf{P}_{B})=\frac{1}{2}\cdot(\mathcal{M}(X_{0}))^{T}\Sigma^{-1}_{\bm{B}}(\mathcal{M}(X_{0})),$

and therefore

$\int\mathcal{D}_{KL}(\mathsf{P}_{\mathcal{M}(X_{0})+B}\|\mathsf{P}_{B})\mathsf{P}(X=X_{0})\leavevmode\nobreak\
dX_{0}=\frac{1}{2}\cdot\mathbb{E}_{X}\big{[}(\mathcal{M}(X))^{T}\Sigma^{-1}_{\bm{B}}(\mathcal{M}(X))\big{]}.$

As for the second term in the last equation of (15), we have the covariance of
$\mathcal{M}(X)$ equals
$\Sigma_{\mathcal{M}(X)}=\mathbb{E}_{X}\big{[}(\mathcal{M}(X)-\mathbb{E}[\mathcal{M}(X)])(\mathcal{M}(X)-\mathbb{E}[\mathcal{M}(X)])^{T}\big{]}$,
while the mean $\mu_{\mathcal{M}(X)}=\mathbb{E}[\mathcal{M}(X)]$. The KL
divergence between two multivariate Gaussians has a closed form, where
$\mathcal{D}_{KL}(\mathsf{P}_{Gau(\mathcal{M}(X)+B)}\|\mathsf{P}_{B})$ equals

$\displaystyle\mathcal{D}_{KL}$
$\displaystyle(\mathsf{P}_{Gau(\mathcal{M}(X)+B)}\|\mathsf{P}_{B})=\frac{1}{2}\cdot\big{(}\text{Trace}(\Sigma_{\mathcal{M}(X)}\cdot\Sigma^{-1}_{\bm{B}})$
(16)
$\displaystyle+\mathbb{E}_{X}[\mathcal{M}(X)]^{T}\Sigma^{-1}_{\bm{B}}\mathbb{E}_{X}[\mathcal{M}(X)]-\log\text{det}(\bm{I}_{d}+\Sigma_{\mathcal{M}(X)}\Sigma^{-1}_{\bm{B}})\big{)}.$

On the other hand, note that

$\displaystyle\mathbb{E}_{X}\big{[}(\mathcal{M}(X))^{T}\Sigma^{-1}_{\bm{B}}(\mathcal{M}(X))\big{]}-\mathbb{E}_{X}\big{[}\mathcal{M}(X)\big{]}^{T}\Sigma^{-1}_{\bm{B}}\mathbb{E}_{X}\big{[}\mathcal{M}(X)\big{]}-\text{Trace}(\Sigma_{\mathcal{M}(X)}\cdot{\Sigma}^{-1}_{\bm{B}})$
(17)