# DP-Auditorium: a Large Scale Library for Auditing Differential Privacy

William Kong, Andrés Muñoz Medina,
Mónica Ribero, and Umar Syed Google Research, NY, {weiweikong, ammedina,
mribero<EMAIL_ADDRESS>
###### Abstract

New regulations and increased awareness of data privacy have led to the
deployment of new and more efficient differentially private mechanisms across
public institutions and industries. Ensuring the correctness of these
mechanisms is therefore crucial to ensure the proper protection of data.
However, since differential privacy is a property of the mechanism itself, and
not of an individual output, testing whether a mechanism is differentially
private is not a trivial task. While ad hoc testing techniques exist under
specific assumptions, no concerted effort has been made by the research
community to develop a flexible and extendable tool for testing differentially
private mechanisms. This paper introduces DP-Auditorium as a step advancing
research in this direction. DP-Auditorium abstracts the problem of testing
differential privacy into two steps: (1) measuring the distance between
distributions, and (2) finding neighboring datasets where a mechanism
generates output distributions maximizing such distance. From a technical
point of view, we propose three new algorithms for evaluating the distance
between distributions. While these algorithms are well-established in the
statistics community, we provide new estimation guarantees that exploit the
fact that we are only interested in verifying whether a mechanism is
differentially private, and not in obtaining an exact estimate of the distance
between two distributions. DP-Auditorium is easily extensible, as demonstrated
in this paper by implementing a well-known approximate differential privacy
testing algorithm into our library. We provide an extensive comparison to date
of multiple testers across varying sample sizes and differential privacy
parameters, demonstrating that there is no single tester that dominates all
others, and that a combination of different techniques is required to ensure
proper testing of mechanisms.

##  1 Introduction

The protection of data contributors’ privacy is a growing concern as data-
driven algorithms become increasingly ubiquitous. Differential privacy (DP)
addresses this concern by developing mechanisms, which are private
counterparts for traditional algorithms that consume user data and that
guarantee with high probability that the output of the mechanism does not
reveal any information about a user that could not have been known without the
user being part of the input data. Specifically, a mechanism is differentially
private if, for neighboring datasets (i.e., datasets that differ in only one
record), an adversary is unable to determine from the output of the mechanism
which of the neighboring datasets the output came from. Differential privacy
is widely used by industry and governments as it meets strict user rights and
data protective regulations such as the General Data Protection Regulation
(GDPR) and the Digital Markets Act (DMA).

As DP becomes more prevalent, so too do the risks of incorrect
implementations, which can potentially jeopardize user privacy. Accordingly,
auditing differentially private mechanisms is a critical step for increasing
confidence in the correctness of DP pipelines and ensuring that user rights
are met. However, the variety of mechanisms, tasks, and generalized
definitions for differential privacy make it difficult to inspect the
correctness of this vast amount of algorithms. This suggests that automated
and generalizable end-to-end tests for the implementation of such mechanisms
are desirable for expanding the confidence of their correctness.

In this paper, we take a step forward in standardizing the way in which
differential privacy is audited. We introduce DP-Auditorium , a DP auditing
library implemented in Python that allows practitioners to test DP guarantees
from only black-box access to a mechanism and allows for continuous
improvements from the research community. DP-Auditorium also introduces a new
family of function-based tests for Rényi, pure, and approximate differential
privacy. This family allows for black-box detection of a variety of bugs
without knowledge or assumptions about the source of randomness (e.g., noise
decay, or variance).

DP-Auditorium implements two main components: testers and dataset finders.
Testers take a mechanism and a pair of datasets as input and aim to find
violations of a privacy guarantee on the provided datasets. Dataset finders
suggest the neighboring datasets. DP-Auditorium combines these components
allowing for flexible testing of diverse mechanisms and privacy definitions in
an automated way and is able to catch bugs reported in the literature as well
as implementation bugs in our own experiments for this paper (see Section
6.7).

###  1.1 Contributions.

  * •

We introduce a family of function-based testers for Rényi, pure, and
approximate differential privacy. These testers use variational
representations of divergence measures between distributions well known to the
statistical community to lower bound the true privacy parameters of a
mechanism on a given pair of datasets. The specific application to privacy
allows us to derive new finite complexity bounds for estimating the Hockey
Stick divergence, the Rényi divergence, and the maximum mean discrepancy
(MMD). While the complexity of previous histogram-based testers depends on the
discretization of the output space [1, 2], our testers optimize over a family
of functions that parametrize the complexity of the test. We also provide an
industry ready implementation that consistently outperforms histogram based
divergence estimators. This new function based approach is also more flexible
and is amenable to testing high-dimensional and continuous output spaces,
without an explicit discretization of the output space.

  * •

We implement dataset finders that suggest neighboring datasets. We implement
known approaches for finding neighboring datasets, namely grid search and
randomized search. We expand this suite by incorporating Bayesian optimization
techniques that generate datasets maximizing the divergences we wish to
estimate. While grid search is advantageous when side-information about
potential bugs is available, optimization-based finders accelerate and in some
cases are even the determinant in finding certain bugs.

  * •

We conclude our paper with an extensive comparison of testers and dataset
finders. We show that they are able to detect a variety of bugs. While
experiments show that no tester is globally better, we provide insight into
what testers are more suitable for detecting certain bugs under different
privacy definitions.

  * •

DP-Auditorium introduces a tester wrapper that can integrate most if not all
of the previous black-box testing work. The library will be open sourced and
open to researchers and practitioners to experiment and test DP mechanisms.

The remainder of the paper is structured as follows. In section section 2, we
provide preliminary notions and notation. In section 4, we formalize privacy
tests and dataset finding algorithms. We conclude our paper in section 6 by
evaluating and discussing different testers.

###  1.2 Related work.

There are generally two approaches used in differential privacy testing that
we review below.

Property testing literature. The first approach, which includes our proposed
methodology, aims to directly estimate the effective privacy parameters from
black-box access to the tested mechanism and compare these effective privacy
parameters with the ones stated by the privacy guarantee. This approach
focuses on estimating the distance between the distributions induced by the
mechanism on neighboring datasets. The problem thus consists of two key
challenges: 1) estimating the distance between distributions given two fixed
neighboring datasets, and 2) finding the pair of neighboring datasets that
maximize the distance between these distributions.

The problem of estimating distances between distributions has been extensively
studied in the statistics and hypothesis testing community. While providing a
comprehensive overview of this literature is beyond the scope of this work, we
briefly highlight [3, 4, 5], which consider estimating probability distances
through optimization methods over function spaces. Their work provides
asymptotic guarantees, while we provide strict finite sample complexities to
obtain a lower bound on divergences between two distributions.

For the specific task of estimating Rényi divergence, our estimator is
inspired by the work of [6], which considers using neural networks to estimate
Rényi divergence. The finite sample complexity bounds provided in that work,
however, depend on the structure of the neural network and can rapidly become
vacuous for the purpose of testing differential privacy. In contrast, our
complexity bounds are independent of the network structure, as we are
primarily concerned with lower bounds on the Rényi divergence.

Several related approaches lower bound privacy parameters but make assumptions
on the type of mechanisms to provide finite sample complexity guarantees. For
example, [7] proposes to estimate the regularized kernel Rényi divergence, a
lower bound on the Rényi divergence between distributions of a randomized
mechanism. However, this approach requires knowledge about the covariance
matrix of the underlying distributions, which is impractical for most
mechanisms other than the Gaussian and Laplace mechanisms, and inaccessible in
the black-box setting. Similarly, [8] provides techniques for lower-bounding
$\epsilon$. Unfortunately, the previous method needs access to the cumulative
distribution function of the distribution of the privacy loss random variable,
which is unknown under our assumption of black box mechanism evaluation. None
of the aforementioned techniques considers the second problem of finding
datasets where the privacy guarantee can break.

A large body of literature exists regarding the testing of a mechanism’s
privacy for specific settings or under assumptions on the mechanism. [9]
proposes a differential privacy tester for mechanisms with discrete and finite
output spaces that requires access to the distribution over datasets and the
probability measure over outputs induced by the tested mechanism. For the
dataset search, instead of testing privacy in the worst case setting, they
test if the mechanism satisfies the guarantee over fixed datasets with high
probability. More importantly, the tester does not work for continuous output
spaces. [1] presents a test for discrete $(\epsilon,\delta)$-DP mechanisms but
omits the problem of finding the worst case pair of neighboring datasets.
StatDP [10] proposes a system for detecting differential privacy violations by
post-processing the output of the mechanisms through different statistics. The
tester requires semi-black box access to the mechanisms (as one of the post
processing techniques requires running the mechanism without privacy), which
is infeasible for auditing certain mechanisms.

DP-Sniper [11] provides an $\epsilon$-DP black-box mechanism tester that
explicitly attempts to find a set in the output space that maximizes the
difference in probability for the output of the mechanism. Their framework is
specific to detecting $\epsilon$-DP, and the high sample complexity (millions
of samples) makes this approach impractical for some mechanisms. On the
dataset search problem, DPSniper uses predetermined rules that may hinder its
ability to detect violations on new tasks, and it runs under non-classic
neighboring relations such as the $\ell_{\infty}$ relation instead of the
classic swap or add/remove definition of neighboring.

ML focused testing literature. The second approach focuses on machine learning
predictive models learning algorithms rather than arbitrary statistical tasks
[12].

On a different vein, some work uses adversarial attacks that try to break the
privacy definition. Examples of these approaches are the celebrated membership
inference attacks [13, 14, 15] and data reconstruction attacks [16, 17] of
deep learning models trained with DP-SGD. Hence, the validation of whether a
mechanism satisfies privacy is linked to the ability of the attack to succeed.
The tests generated by these approaches are very valuable when trying to
understand potential privacy risks on a single data set, by manually designing
canaries that are expected to have highest sensitivity. For example, [18]
extends the work of [11] by developing data poisoning attacks to explore the
space of datasets focusing on machine learning predictive models learning
algorithms rather than arbitrary statistical tasks.

Running these tests generally requires white box access to the trained model
and, more importantly, requires access to large portions of the training data,
making auditing of a privately trained model impossible for someone who is not
the data curator. Consequently, the resulting lower bounds from these
approaches tend to be loose [19, 20]. Moreover, the budget $\epsilon$
predicted by these experiments is generally much smaller than the theoretical
budget. For example, some authors [21] assert that their proposed models were
private with an $\epsilon=10^{-3}$ when these models were trained without
privacy.

Dataset search in this space typically relies on pre-determined datasets, or
canaries, which do not attempt to understand the worst-case (unknown) scenario
that differential privacy aims to protect. However, recent work has introduced
a randomized approach to crafting canaries that, with high probability, finds
datasets that break the privacy guarantee for the Gaussian mechanism in high
dimensions [22].

##  2 Preliminaries

Notation. For $n$ a natural number, $[n]=\\{1,...,n\\}$ denotes the set the
set of positive numbers up to $n$. We reserve $\epsilon,\alpha,\delta$ for
privacy parameters, $\gamma$ will represent the error tolerance, $\beta$ will
represent the probability of failure of a given test.

We start by formally defining the tested privacy properties and notions.

######  Definition 2.1.

Let $D_{0},D_{1}\subset\mathcal{D}$ be datasets, where $\mathcal{D}$ is a
domain of datasets that consist of records taking values in a domain
$\mathcal{Z}$. We say that $D_{0}$ and $D_{1}$ are neighbors, denoted
$D_{0}\sim D_{1}$, if $D_{0}$ is obtained by adding or removing a record
$z\in\mathcal{Z}$ from $D_{1}$.

######  Remark 2.2.

The notion of neighboring can be replaced by the swap definition where $D_{0}$
is obtained by swapping one record in $D_{1}$ by another record.

A _mechanism_ is a randomized function
$\mathcal{M}:\mathcal{D}\rightarrow\mathcal{X}$ (where appropriate, we denote
$\mathcal{M}(D)$ as either a single output of mechanism $\mathcal{M}$ on an
input $D$ or the distribution of the outputs). A mechanism is differentially
private if it generates ‘close’ distributions for neighboring datasets.
Several measures of closeness have been proposed.

######  Definition 2.3.

A randomized mechanism $\mathcal{M}:\mathcal{D}\to\mathcal{X}$ satisfies
$(\epsilon,\delta)$–approximate differential privacy ($(\epsilon,\delta)$–DP),
if for every pair of neighboring datasets $D_{0}$ and $D_{1}$ and every subset
$A\subseteq\mathcal{X}$ of the output space, it holds that

$P(\mathcal{M}(D_{0})\in A)\leq e^{\epsilon}P(\mathcal{M}(D_{1})\in
A)+\delta.$ (1)

$\mathcal{M}$ satisfies pure differential privacy, or is
$\epsilon$–differentially private ($\epsilon$–DP), when $\delta=0$.

A different and frequently used divergence in the differential privacy
literature is the Rényi divergence.

######  Definition 2.4.

Let $P$ and $Q$ be two distributions. The Rényi divergence of order $\alpha>1$
between the two distributions is given by

$R_{\alpha}(P||Q):=\frac{1}{\alpha-1}\log\mathbb{E}_{Q}\left[\left(\frac{dP}{dQ}\right)^{\alpha}\right].$

######  Definition 2.5.

A randomized mechanism $\mathcal{M}:\mathcal{D}\to\mathcal{X}$ satisfies
$(\alpha,\epsilon)$–Rényi differential privacy if for any pair of neighboring
datasets $D_{0}$ and $D_{1}$, it holds that

$R_{\alpha}(\mathcal{M}(D_{0})||\mathcal{M}(D_{1}))\leq\epsilon$ (2)

##  3 Testing Framework

This section presents the main DP testing framework of our library and
discusses some of its properties.

As seen in the previous section, asserting that a mechanism is private
requires verifying that the output distributions $\mathcal{M}(D_{0})$ and
$\mathcal{M}(D_{1})$ are close under some divergence for _all_ neighboring
datasets. If there exists a pair of neighboring datasets $D_{0}$ and $D_{1}$
for which the divergence of $\mathcal{M}(D_{0})$ and $\mathcal{M}(D_{1})$ is
large, it follows that the mechanism is not private. Since we treat mechanism
$\mathcal{M}$ as a black-box, we cannot observe the true output distributions
of the mechanism and exact calculation of the divergence between
$\mathcal{M}(D_{0})$ and $\mathcal{M}(D_{1})$ is not possible. Instead, we
introduce Algorithm 1 that suggests a general procedure for finding violations
of privacy properties of a mechanism, relying on samples from the mechanism to
estimate the divergence.

It is worth mentioning that our library focuses in completeness but not
soundness of the tests. This means that a mechanism failing the test will
reject the hypothesis of a mechanism’s privacy guarantee, but passing the test
is not enough evidence to accept the hypothesis of the mechanism’s privacy
guarantee. It has been shown [1] that sound tests for pure DP have exponential
sample complexity. Sound tests for approximate DP have been developed only for
finite output space mechanisms, and over a fixed pair of datasets. Testers for
black-box mechanisms that can deal with exponentially large output spaces, or
that can explore the space of datasets and confirm the privacy guarantee of a
mechanism is in general a hard open problem.

DP-Auditorium abstracts the two main steps of algorithm 1 and allows users to
specify any divergence estimator and neighboring generating routines. The
remainder of the paper will focus on specific implementations of the
divergence estimator $\widehat{D}(\cdot\|\cdot)$ as well as the introduction
of non-parametric Bayesian optimizers to handle the process of generating
neighboring datasets.

Algorithm 1 Generalized lower bound test method for DP

1: Inputs: mechanism $\mathcal{M}$, trial count $T$, a dataset generator
$\mathcal{G}$, divergence estimator $\widehat{D}$, privacy threshold $\tau$,
probability of failure $\beta$;

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

3: Generate datasets $\\{D_{0}^{t},D_{1}^{t}\\}$ using $\mathcal{G}$.

4: Set
${\mathcal{D}}_{1}^{t}:=\widehat{D}(\mathcal{M}(D_{0}^{t})\,\|\,\mathcal{M}(D_{1}^{t}))$.

5: Set
${\mathcal{D}}_{2}^{t}:=\widehat{D}(\mathcal{M}(D_{1}^{t})\,\|\,\mathcal{M}(D_{0}^{t}))$.

6: if $\max\\{{\mathcal{D}}_{1}^{t},{\mathcal{D}}_{2}^{t}\\}>\tau$ then

7: return w.p. $1-\beta$, $\mathcal{M}$ is not private

8: end if

9: end for

10: return Could not find privacy violation in $T$ trials.

##  4 Implementations of the Framework

This section presents implementations of the framework given in Algorithm 1.
More specifically, it considers the following two types:

  * •

Histograms. These methods estimate a particular divergence using histograms
(e.g., see [1]), which can (i) approximate distribution to arbitrary precision
and (ii) provide examples of where privacy violations may occur. However,
these methods are prohibitively expensive in high-dimensional settings and
large (mechanism) output spaces.

  * •

Dual divergences. These methods lower bound a particular divergence using its
dual formulation. Specifically, these methods solve the associated empirical
maximization problem using some well-known ML heuristics that scale well to
high-dimensional settings.

It is worth noting that the dual formulation mentioned above is well-known to
the statistics community. However, to the best of our knowledge, we provide
the first practical implementation for the purpose of testing differential
privacy. In Section 6, we also show that dual divergence-based approaches
generally outperform histogram-based methods in practice.

###  4.1 Pure and Rényi DP

This section presents a tester that checks if a mechanism satisfies a given
level of pure or Rényi DP. It primarily focuses on developing results for
Rényi DP and the tester implements the framework in Algorithm 1.

####  4.1.1 Rényi divergence lower bound

We first introduce a variational formulation of the Rényi divergence based on
the results in [3, 6].

######  Theorem 4.1 (Theorem 3.1 in [6]).

Let $P$ and $Q$ be probability measures on $(\mathcal{X},\mathcal{F})$ and
$\alpha>1$. Let $\Gamma$ be any function space such that
$M_{b}(\mathcal{X})\subseteq\Gamma\subseteq M(\mathcal{X})$ where
$M_{b}(\mathcal{X})$ and $M(\mathcal{X})$ are the sets of measurable bounded
and measurable functions on $\mathcal{X}$ respectively. Then,

$\displaystyle
R_{\alpha}(P\,\|\,Q)=\sup_{h\in\Gamma}\tfrac{\alpha}{\alpha-1}\log\left(\mathbb{E}_{X\sim
P}\left[e^{(\alpha-1)h(X)}\right]\right)$ $\displaystyle\hskip
71.13188pt-\log\left(\mathbb{E}_{X\sim Q}\left[e^{\alpha h(X)}\right]\right)$
(3)

Moreover, if $P$ and $Q$ admit densities, then the function optimizing the
above quantity is given by $h=\log P/Q.$

Since the complexity of the function space $\Gamma$ can be arbitrarily large,
computing the supremum in eq. 3 is generally intractable. Hence, instead of
estimating $R_{\alpha}(\cdot\|\cdot)$ to an arbitrary precision, we propose to
(i) replace $P$ and $Q$ with samples $\mathbf{X}_{0}$ and $\mathbf{X}_{1}$,
respectively, and (ii) replace $\Gamma$ with a (possibly) more restrictive
function space $\Phi$. Under these modifications, we then use a one-sided
confidence interval to obtain a suitable lower bound for
$R_{\alpha}(\cdot\|\cdot)$.

Let us now make these relaxations formal through the following definition.

######  Definition 4.2.

Let $h:\mathcal{X}\to\mathbb{R}$ be a function in $\Phi$ and $\alpha>1$.
Define

$\displaystyle R^{h}_{\alpha}(P\,\|\,Q)$
$\displaystyle:=\tfrac{\alpha}{\alpha-1}\log\left(\int
e^{(\alpha-1)h(x)}dP\right)$ $\displaystyle\hskip 28.45274pt-\log\left(\int
e^{\alpha h(x)}dQ\right)$ (4)

Given samples $\mathbf{X}_{0}=(X_{0,1},...,X_{0,n})\sim P^{n}$,
$\mathbf{X}_{1}=(X_{1,1},...,X_{1,n})\sim Q^{n}$, define its empirical
counterpart

$\displaystyle R^{h,n}_{\alpha}(\mathbf{X}_{0}\,\|\,\mathbf{X}_{1})$
$\displaystyle:=\tfrac{\alpha}{\alpha-1}\log\left(\frac{1}{n}\sum_{i=1}^{n}e^{(\alpha-1)h(X_{0,i})}\right)$
$\displaystyle\hskip 28.45274pt-\log\left(\frac{1}{n}\sum_{i=1}^{n}e^{\alpha
h(X_{1,i})}\right).$ (5)

Let $h\in\Phi\subseteq\Gamma$, define the (one-sided) estimation error as the
smallest non negative $\gamma(\Phi,n,\beta,\alpha)>0$ such that

$R^{h}_{\alpha}(P\,\|\,Q)>R^{h,n}_{\alpha}(\mathbf{X}_{0}\,\|\,\mathbf{X}_{1})-\gamma(\Phi,n,\beta,\alpha)$
(6)

with probability at least $1-\beta$ over the randomness of the $n$ samples
from $P$ and $Q$.

Observe that the parameter $\gamma$ can depend on the complexity of the
function class. As a concrete example, we characterize the complexity of the
function class

$\Phi_{C}:=\\{h\in\Gamma:|h(x)|<C\text{ for all }x\in\mathcal{X}\\}$ (7)

and prove a suitable relationship between $\gamma$ and $n$.

######  Theorem 4.3.

Let $P$ and $Q$ be two distributions. Let $\Gamma$ be as in Theorem 4.1,
$\Phi_{C}\subseteq\Gamma$ be as in (7), and $h\in\Phi_{C}$. Let
$\mathbf{X}_{0}=(X_{0,1},...,X_{0,n})$ and
$\mathbf{X}_{1}=(X_{1,1},...,X_{1,n})$ be $n$ realizations of $P$ and $Q$,
respectively. Then, if $\eta\in(0,1]$, and

$n\geq\max\left(\frac{3e^{2(\alpha-1)C}\log(2/\beta)}{\eta^{2}},\frac{2e^{\alpha
C}\log(2/\beta)}{\eta^{2}}\right)=:\underline{n},$

then, with probability at least $1-\beta$, it follows that

$\displaystyle R_{\alpha}$ $\displaystyle(P||Q)\geq
R^{h,n}_{\alpha}(\mathbf{X}_{0}||\mathbf{X}_{1})-\log\left(\frac{1+\eta}{1-\eta}\right).$
(8)

We now make two remarks about the above result. First, the larger $C$ is, the
larger $\underline{n}$ and $\Phi_{C}$ are. Consequently, the tightness of the
lower bound in (8) can be improved by increasing $C$ at the cost of an
exponential increase in the sample complexity given by $\underline{n}$.
Second, in contrast to well-known exponential sample complexities [23] for
estimating $R_{\alpha}(\cdot\|\cdot)$, the sample complexity in Theorem 4.3 is
dimension-independent. This is primarily due to the fact that $\Phi_{C}$ is a
relatively much smaller space compared to $\Gamma$ in the context of (3) and
the fact that we are only interested in obtaining a lower bound on
$R_{\alpha}(P||Q)$. Finally, it is important to notice that, even though there
is an exponential dependency on $C$, since we know the optimal solution is
given by $\log(P/Q)$ we can generally set $C$ to be a small constant and still
ensure a tight lower bound on the approximation error to the Rényi divergence.

To conclude, we show how the above theorem can be used to characterize the
log-error in (8) in terms of $n$.

######  Corollary 4.4.

Let $n\geq 1$ be fixed. With probability $1-\beta$, the bound in (8) holds
with

$\eta=\sqrt{\frac{\max\left\\{3e^{2(\alpha-1)C},{2e^{\alpha
C}}\right\\}\cdot\log(2/\beta)}{n}}.$ (9)

####  4.1.2 Rényi tester

We now present how to use the previous results to implement a Rényi
divergence-based tester under the framework in Algorithm 1.

Recall that the previous section showed that we can choose an arbitrary
function $h\in\Phi$ to lower bound the Rényi divergence between the output of
a mechanism in two neighboring datasets. Since we would like the tightest
bound for (8), a natural heuristic for choosing $h$ is to first sample
${\mathbf{X}_{0}=(X_{0,1},\ldots,X_{0,n})}$ from $\mathcal{M}(D_{0})$,
${\mathbf{X}_{1}=(X_{1,1},\ldots,X_{1,n})}$ from $\mathcal{M}(D_{1})$, and
then choose $h$ to be the maximum of $R^{h,n}_{\alpha}(\cdot\|\cdot)$ over
$\Phi_{C}$ (or some subspace $\Psi_{C}\subseteq\Phi_{C}$).

Using the above choice of $h$, and appropriate choices of thresholds and
sampling errors, we now present the complete Rényi divergence-based tester in
Algorithm 2 which implements Algorithm 1.

Algorithm 2 RényiTester

1: Inputs: Parameters $\mathcal{M}$, $T$, $\mathcal{G}$, and $\beta$ as in
Algorithm 2; $\Psi_{C}\subseteq\Phi_{C}$ where $\Phi_{C}$ is as in (7); Rényi
DP parameters $(\alpha,\epsilon)$; and sample size $n$;

2: Compute $\eta$ as in (9) and  $\tau:=\begin{cases}\epsilon&\text{if testing
R\'{e}nyi DP,}\\\ \min(\epsilon,2\alpha\epsilon^{2})&\text{if testing pure
DP.}\end{cases}$

3: Define the estimator
$\widehat{D}(P\,\|\,Q):=\max_{h\in\Psi_{C}}R^{h,n}_{\alpha}(\textbf{X}_{0}\,\|\,\textbf{X}_{1})-\log\left(\frac{1+\eta}{1-\eta}\right)$
for any $(P,Q)$, where $\textbf{X}_{0}\sim P^{n}$ and $\textbf{X}_{1}\sim
Q^{n}$.

4: Run the same steps as in Algorithm 1 with inputs $\mathcal{M}$, $T$,
$\mathcal{G}$, $\widehat{D}$, $\tau$, and $\beta$.

Some remarks about Algorithm 2 are in order. First, it is an instance of
Algorithm 1 which sets specific values for $(\tau,\widehat{D})$, while keep
the other parameters in Algorithm 1 as inputs. Second it is used to evaluate
only pure DP or Rényi DP of a mechanism $\mathcal{M}$. Third, its efficiency
is generally to the efficiency of computing
$\max_{h\in\Psi_{C}}R^{h,n}_{\alpha}(\cdot\|\cdot)$.

In our numerical experiments, we make two concessions for the sake of
tractability. First, we consider two specific choices of $\Psi_{C}$, namely,
(i) the family of dense neural networks with bounded output and (ii) the
vector space of polynomials generated by the basis of Chebyshev polynomials of
degree at most $k$. Note that these particular choices of $\Psi_{C}$ make the
optimization problem $\max_{h\in\Psi_{C}}R^{h,n}_{\alpha}(\cdot\|\cdot)$
tractable when applying first-order method such as stochastic gradient descent
(SGD). Second, we estimate
$\max_{h\in\Psi_{C}}R^{h,n}_{\alpha}(\textbf{X}_{0}\|\textbf{X}_{1})$, by (i)
independently sampling $\textbf{X}_{0},\tilde{\textbf{X}}_{0}\sim P^{n}$ and
$\textbf{X}_{1},\tilde{\textbf{X}}_{1}\sim Q^{n}$, (ii) computing
$h^{*}:=\operatorname*{arg\,max}_{h\in\Psi_{C}}R^{h,n}_{\alpha}(\textbf{X}_{0}\|\textbf{X}_{1})$;
and (iii) evaluating
$R^{h^{*},n}_{\alpha}(\tilde{\textbf{X}}_{0}\|\tilde{\textbf{X}}_{1})$ as our
estimate.

####  4.1.3 Adaptation of RényiTester to pure DP

It is known that setting $\alpha=\infty$ for Rényi DP corresponds to pure-DP,
i.e., $\mathcal{M}$ is an $\epsilon$–DP mechanism if and only if for any
${D\sim D^{\prime}}$, we have
$D_{\infty}(\mathcal{M}(D)||\mathcal{M}(D^{\prime}))\leq\epsilon$. Lemma 4.5
below states the Rényi divergence is monotone in $\alpha$. This implies that
we can use our tester with any $\alpha>1$ to test for pure DP since
${D_{\infty}(\mathcal{M}(D)||\mathcal{M}(D^{\prime}))\geq
D_{\alpha}(\mathcal{M}(D)||\mathcal{M}(D^{\prime}))}$, so any lower bound for
$D_{\alpha}$ will also be a lower bound for $D_{\infty}$.

######  Lemma 4.5 (Proposition 9 in [24]).

Let $1<\alpha_{1}<\alpha_{2}$ and $P$ and $Q$ be probability measures. Then
$D_{\alpha_{1}}(P||Q)<D_{\alpha_{2}}(P||Q)$

In the specific case of testing pure DP, Lemma 4.6 gives a bound for the
divergence that can be used to obtain a tighter threshold for the test (see
line 5).

######  Lemma 4.6 (Lemma 1 in [24]).

Let $\mathcal{M}$ be an $\epsilon$–differentially private mechanism and
$\alpha>1$. Then
$D_{\alpha}(\mathcal{M}(D)||\mathcal{M}(D^{\prime}))\leq\min\\{\epsilon,2\alpha\epsilon^{2}\\}$.

###  4.2 Approximate DP

This section presents testers that check if a mechanism satisfies a given
level of approximate DP. Similar to the previous section, each tester
implements the framework in Algorithm 1.

####  4.2.1 Histogram Tester

The authors in paper [1] introduce a test for approximate differential privacy
over discrete and finite output spaces. We introduce this through Algorithm 3
and Algorithm 4. It requires knowledge of the output space. The test estimates
the parameter $\delta$ by directly computing the privacy loss over different
outputs.

Algorithm 3 Estimate histogram divergence

1: Input: Distributions $P$ and $Q$; universe $[m]$; $\epsilon>0$; $\beta>0$;
and $\eta>0$;

2: Compute
$\lambda=\max\bigl{\\{}4m(1+e^{2\epsilon})\beta^{-2},12(1+e^{2\epsilon})\eta^{-2}\bigr{\\}}$

3: Sample $r\sim\text{Poisson}(\lambda)$

4: Generate samples $X\sim P^{r}$ and $Y\sim Q^{r}$

5: for $j=1$ to $m$ do

6: $x_{j}=|\\{i:X_{i}=j,1\leq i\leq r\\}|$

7: $y_{j}=|\\{i:Y_{i}=j,1\leq i\leq r\\}|$

8: $z_{i}=(x_{i}-e^{\epsilon}y_{i})/r$

9: end for

10: return $-\eta+\sum^{r}_{i=1}\max\\{0,z_{i}\\}$

Algorithm 4 HistogramTester

1: Input: Parameters $\mathcal{M}$, $T$, $\mathcal{G}$, and $\beta$ as in
Algorithm 1; parameters $\eta$ as in Algorithm 3; approximate DP parameters
$(\epsilon,\delta)$; and sample size $m$;

2: Define the estimator $\widehat{D}(P\,\|\,Q)$ to be the output of Algorithm
3 with inputs $P$, $Q$, $[m]$, $\epsilon$, $\beta$, and $\eta$.

3: Set $\tau=\delta$.

4: Run the same steps as in Algorithm 1 with inputs $\mathcal{M}$, $T$,
$\mathcal{G}$, $\widehat{D}$, $\tau$, and $\beta$.

####  4.2.2 Hockey-stick divergence

It is well known that DP can be defined in terms of the Hockey stick
divergence (see Lemma 5 in [25]).

######  Lemma 4.7.

([26]) Consider the function $f(x)=\max\\{0,x-e^{\epsilon}\\}$. The Hockey-
Stick divergence between $P$ and $Q$ (of order $e^{\epsilon}$) is the
$f$-divergence defined as

$H_{\epsilon}(P||Q):=\mathbb{E}_{Q}\left[f\left(\frac{dP}{dQ}\right)\right].$
(10)

A mechanism is $(\epsilon,\delta)$–DP if and only if

$\sup_{D_{0}\sim
D_{1}}H_{\epsilon}(\mathcal{M}(D_{0})||\mathcal{M}(D_{1}))\leq\delta$

where the supremum is taken over neighboring datasets.

######  Lemma 4.8.

The variational representation for the Hockey stick divergence (see eq. 25 in
the supplementary material) is given by

$H_{\epsilon}(P||Q)=\sup_{g:0\leq g\leq
1}\mathbb{E}_{P}\left[g(X)\right]-\mathbb{E}_{Q}\left[e^{\epsilon}g(X))\right].$
(11)

Similar to the Rényi tester, the Hockey-stick tester is based on the dual
formulation given in (10). In this section, we further manipulate the
expression for the Hockey-stick divergence and establish a connection between
that divergence and an unbalanced binary classification problem.

######  Lemma 4.9.

Let $\epsilon>0$ Fix two distributions $P$ and $Q$ over $\mathcal{X}$. Let
$\mathbb{D}$ be a mixture distribution over $\mathcal{X}\times{0,1}$ defined
as
$\mathbb{D}=\frac{e^{\epsilon}}{1+e^{\epsilon}}Q\times\delta_{0}+\frac{1}{1+e^{\epsilon}}P\times\delta_{1}$.
That is, $(X,Y)\sim\mathbb{D}$ is a weighted, labeled sample from $Q$ (with
label $0$) and $P$ (with label $1$).

$H_{\epsilon}(P||Q)=(1+e^{\epsilon})\sup_{g\colon\mathcal{X}\to\\{0,1\\}}\mathbb{D}(g(X)=Y)-e^{\epsilon}$

The advantage of this formulation is that it allows for a simple derivation on
how well we can approximate the true divergence with a sample.

######  Definition 4.10.

Let $S_{m}$ denote a binomial random variable of parameters $m,p$. Let
$\gamma_{m},\beta>0$ We say that $\widehat{p}\colon=\widehat{p}(S_{n})$ is a
$(\gamma_{m},\beta)$ lower bound estimator for $p$ if with probability at
least $1-\beta$ over the draw of $S_{n}$ we have that
$p>\widehat{p}(S_{m})-\gamma_{m}$.

Note that there are multiple tools to derive lower bounds for $p$. Just to
mention a few we have Hoeffding’s inequality, Chernoff bounds and Clopper-
Pearson confidence intervals. The following well known proposition uses the
well known Hoeffding’s inequality to instantiate $\gamma_{m}$.

######  Proposition 4.11.

Let $\beta>0$ and $\widehat{p}(S_{m})=S_{m}/m$, then with probability at least
$1-\beta$:

$p\geq p(S_{m})-\sqrt{\frac{\log(1/\beta)}{2m}}.$

######  Proposition 4.12.

Let $g\colon\mathcal{X}\to\\{0,1\\}$ be any function and $\beta>0$. Let
$(x_{i},y_{i})_{i=1}^{m}\sim\mathbb{D}$ be an i.i.d sample. Let
$S_{m}=\sum_{i=1}^{m}\mathds{1}_{g(X_{i})=Y_{i}}$. If $\widehat{p}$ is a
$(\gamma_{m},\beta)$ lower bound estimator, then with probability at least
$1-\beta$ we have

$H_{\epsilon}(P||Q)\geq(1+e^{\epsilon})(\widehat{p}(S_{m})-\gamma_{m})-e^{\epsilon}.$

###### Proof.

The proof is trivial since $S_{m}$ is distributed as a binomial random
variable for a fixed function $g$. ∎

The above proposition shows that, given any classifier $g$, we can find a
lower bound on $H_{\epsilon}$. A natural question is how to find such a
classifier. Here we borrow from the extensive work on binary classification
and let

$L(\widehat{y},y):=-y\log\widehat{y}-(1-y)\log(1-\widehat{y})$ (12)

be the logistic loss. The way we choose $g$ is by minimizing $L$ on a training
sample. To more precise, we present the subroutine for estimating
$H_{\epsilon}(\cdot\,\|\,\cdot)$, using inputs $P=\mathcal{M}(D_{0})$ and
$Q=\mathcal{M}(D_{1})$, in Algorithm 1.

Algorithm 5 Estimate Hockey Stick divergence

1: Inputs: Distributions $P$ and $Q$; $\widehat{p}$ as in Definition 4.10;
$\gamma_{m}>0$; $\epsilon>0$; and sample size $m$;

2: Define a distribution $\mathbb{D}$ as in Lemma 4.9 with input distributions
$P$ and $Q$.

3: Generate samples
$\\{(x_{i},y_{i})\\}_{i=1}^{m},(x_{i}^{\prime},y_{i}^{\prime})_{i=1}^{m}\sim\mathbb{D}^{m}$.

4: Compute $h^{*}=\arg\min_{h\in H}\frac{1}{m}\sum L(h(x_{i}),y_{i})$ where
$L$ is as in (12).

5: Define $g(x)=\mathds{1}_{h^{*}(x)>1/2}$ for every $x$.

6: return
$(1+e^{\epsilon})[\widehat{p}\left(\sum_{i=1}^{m}\mathds{1}_{g(x^{\prime}_{i})=y_{i}^{\prime})}\right)-\gamma_{m}]-e^{\epsilon}$.

Using the above estimator, we now present how it can be used to implement
Algorithm 1 in Algorithm 6.

Algorithm 6 HockeyStickTester

1: Inputs: Parameters $\mathcal{M}$, $T$, $\mathcal{G}$, and $\beta$ as in
Algorithm 1; parameters $\widehat{p}$ and $\gamma_{m}$ as in Algorithm 5;
approximate DP parameters $(\epsilon,\delta)$; and sample size $m$;

2: Define the estimator $\widehat{D}(P\,\|\,Q)$ to be the output of Algorithm
5 with inputs $P$, $Q$, $\widehat{p}$, $\gamma_{m}$, $\epsilon$, and $m$.

3: Set $\tau=\delta$.

4: Run the same steps as in Algorithm 1 with inputs $\mathcal{M}$, $T$,
$\mathcal{G}$, $\widehat{D}$, $\tau$, and $\beta$.

####  4.2.3 MMD-tester

The definition of approximate differential privacy requires that a mechanism’s
output distributions for two neighboring datasets are not substantially
different from each another. Since the statistical literature describes many
distance metrics between distributions, another approach to auditing a
differentially private mechanism is to relate the magnitude of one of these
distances to the strength of the claimed privacy guarantee, and then apply a
statistical test for estimating the distance. An example of such a distance is
the _maximum mean discrepancy_

$\operatorname{MMD}(P,Q,H)\triangleq\sup_{f\in H:\left\lVert f\right\rVert\leq
1}\left(\int fdP-\int fdQ\right)$ (13)

which is the maximum difference between the expected values with respect to
distributions $P$ and $Q$ of any function in the unit ball of a reproducing
kernel Hilbert space $H$. Theorem 4.13 gives a relationship between maximum
mean discrepancy and approximate differential privacy, and is proved in the
Appendix.

######  Theorem 4.13.

Let $H$ be a reproducing kernel Hilbert space with domain $\mathcal{X}$ and
kernel $k$. Suppose $k(x,x)\leq 1$ for all $x\in\mathcal{X}$. If mechanism
$\mathcal{M}:\mathcal{D}\rightarrow\mathcal{X}$ satisfies
$(\epsilon,\delta)$-differential privacy then

$\operatorname{MMD}(\mathcal{M}(D_{0}),\mathcal{M}(D_{1}),H)\leq
e^{\epsilon}-1+(1+e^{-\epsilon})\delta$

for any pair of neighboring datasets $D_{0},D_{1}\in\mathcal{D}$.

Note that right-hand side in the statement of Theorem 4.13 approaches zero as
$\epsilon\rightarrow 0$ and $\delta\rightarrow 0$. Therefore a positive lower
bound on the maximum mean discrepancy between $\mathcal{M}(D_{0})$ and
$\mathcal{M}(D_{1})$ serves as a privacy audit of mechanism $M$. One way to
estimate the maximum mean discrepancy would be to draw samples from
$\mathcal{M}(D_{0})$ and $\mathcal{M}(D_{1})$ and then explicitly perform the
optimization over the function class $H$ from Eq. (13). Such an approach would
resemble the estimation of a lower bound on the hockey stick divergence
described in Section 4.2.2. However [27] showed that no such optimization is
necessary, since the maximum mean discrepancy equals the expected value of a
simple expression that depends only on the kernel of $H$. Theorem 4.14 is a
succinct statement of one of the main results of [27].

######  Theorem 4.14 ([27]).

Let $X$ and $X^{\prime}$ be independent random variables with distribution
$P$. Let $Y$ and $Y^{\prime}$ be independent random variables with
distribution $Q$. Let $H$ be a reproducing kernel Hilbert space with domain
$\mathcal{X}$ and kernel $k$. If $k(x,x)\leq 1$ for all $x\in\mathcal{X}$ then

$\operatorname{MMD}(P,Q,H)^{2}=\operatorname*{\mathbb{E}}\left[h(X,X^{\prime},Y,Y^{\prime})\right]$

where $h(x,x^{\prime},y,y^{\prime})=k(x,x^{\prime})-2k(x,y)+k(y,y^{\prime})$.

Theorem 4.14 shows that it is possible to estimate maximum mean discrepancy by
estimating the right-hand side of the theorem statement. Algorithm 7 and
Algorithm 8 describe a test of approximate differential privacy based on this
estimator, and Theorem 4.15 gives a theoretical guarantee of its performance.
A proof of Theorem 4.15 can be found in the Appendix. While we could have
directly used the estimator from [27], we modified it to take advantage of the
possibility of a low variance sample, using a data-dependent version of
Bernstein’s inequality due to [28].

Algorithm 7 Estimate MMD divergence

1: Input: Distributions $P$ and $Q$; kernel function $k$; $\beta>0$;
$\epsilon>0$; and sample size $n$;

2: Generate samples $X,X^{\prime}\sim P^{n}$ and $Y,Y^{\prime}\sim Q^{n}$.

3: Define
$h(x,x^{\prime},y,y^{\prime}):=k(x,x^{\prime})-2k(x,y)+k(y,y^{\prime})$.

4: Compute  $\displaystyle\hat{\mu}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}h(X_{i},X^{\prime}_{i},Y_{i},Y^{\prime}_{i})$
$\displaystyle\hat{s}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}h(X_{i},X^{\prime}_{i},Y_{i},Y^{\prime}_{i})^{2}$

5: Set $\hat{\sigma}^{2}=\hat{s}-\hat{\mu}^{2}$.

6: Compute  $\displaystyle\hat{m}$
$\displaystyle=\hat{\mu}-\sqrt{\frac{2\hat{\sigma}^{2}\log
2/\beta}{n}}-\frac{28\log 2/\beta}{3(n-1)}-(e^{\epsilon}-1)^{2}.$

7: return the estimate
$\frac{\sqrt{(e^{\epsilon}-e^{-\epsilon})^{2}+(1+e^{-\epsilon})\hat{m}}-(e^{\epsilon}-e^{-\epsilon})}{(1+e^{-\epsilon})}.$

Algorithm 8 MMDTester

1: Input: Parameters $\mathcal{M}$, $T$, $\mathcal{G}$, and $\beta$ as in
Algorithm 1; parameter $k$ as in Algorithm 7; approximate DP parameters
$(\epsilon,\delta)$; and sample size $n$;

2: Define the estimator $\widehat{D}(P\,\|\,Q)$ to be the output of Algorithm
7 with inputs $P$, $Q$, $k$, $\beta$, $\epsilon$ and $n$.

3: Set $\tau=\delta$.

4: Run the same steps as in Algorithm 1 with inputs $\mathcal{M}$, $T$,
$\mathcal{G}$, $\widehat{D}$, $\tau$, and $\beta$.

######  Theorem 4.15.

If mechanism $\mathcal{M}$ satisfies $(\epsilon,\delta)$-differential privacy
then Algorithm 8 does not find a privacy violation with probability at least
$1-\beta$.

##  5 Dataset Search

As seen in section 3, algorithm 1, auditing tests with only black-box access
to a mechanism $\mathcal{M}$ consist of two stages: (1) generation of
neighboring datasets $D_{0}$ and $D_{1}$, and (2) divergence estimation over
$\mathcal{M}(D_{0})$, $\mathcal{M}(D_{1})$. Below we discuss the dataset
generation step.

The methods proposed in the literature fall in two categories:

  * •

Exploratory methods: These methods ignore any knowledge about the algorithm
and/or potential bugs. In this category falls randomized search, that
generates datasets without any side information independently at random over
trials. A second exploratory method is to divide the search space over a grid
and deterministically evaluate the test over the grid. These methods can be
useful when knowledge about the mechanism is available and randomized search
can have guarantees of finding a dataset where the guarantee will break. For
example, [22] shows that for high-dimensional gaussians, random canaries over
the unit sphere are guaranteed to sample a dataset where the privacy
parameters are maximized.

  * •

Explotation methods: For black-box testing, the literature has mostly
considered crafted datasets that assume certain datasets can be more
vulnerable, e.g. where the sensitivity of the mechanism is maximized. While
this methods can be very efficient to catch certain bugs, they may fail at
finding others that do not happen at the predicted datasets.

We propose a new heuristic that balances these two frameworks by leveraging a
gaussian process bandit [29] to tradeoff explotation and exploration and find
datasets that maximize a specific divergence in algorithm 1. Specifically,
assuming that we have access to

$R_{\alpha}^{h,n}:(D,D^{\prime})\subseteq\mathcal{X}\times\mathcal{X}\to\mathbb{R}.$

Our goal is to produce a sequence $(D_{t},D_{t}^{\prime})_{t}$ that approaches
the optimum. In our experiments we will use an open-sourced implementation of
the well known Bayesian optimization software Vizier [30].

##  6 Experiments

We evaluate the different testers and dataset finders along several
dimensions. We begin by comparing the testers’ ability to detect different
bugs in non-private randomized mechanisms. Then, we evaluate their false
positive rate for flagging private mechanisms as non-private. We then move to
evaluate different dataset search schemes described in section 4 with all
testers. Finally, we provide a complexity analysis of different testers run
time and sample complexity.

Hyperparameters. Unless stated otherwise, all testers use a probability of
failure $\beta=1/3$. RényiTester uses $\alpha=1.5$, approximate DP testers set
$\delta=0.01$ for approximate DP tests and $\delta=0$ for pure DP.
HistogramTester uses a universe size of 100. For all the experiments we report
the average over 10 runs.

DP-Sniper was run on our mechanisms, however, the tester always failed to
complete, even for small sample sizes; thus, it is omitted from our results.

###  6.1 Evaluated mechanisms

Pure DP mean mechanisms. The first three mechanisms attempt to privately
compute the mean by generating the random estimates

$\displaystyle\textsc{DPLaplace
}(X):=\frac{\sum_{i=1}^{n}X_{i}}{\tilde{n}}+\rho_{1},$
$\displaystyle\textsc{NonDPLaplace1
}(X):=\frac{\sum_{i=1}^{n}X_{i}}{n}+\rho_{2}$
$\displaystyle\textsc{NonDPLaplace2
}(X):=\frac{\sum_{i=1}^{n}X_{i}}{n}+\rho_{1}$

where $\tilde{n}=\max\\{10^{-12},n+\tau\\}$, $\tau\sim{\rm
Laplace}(0,2/\varepsilon)$, $\rho_{1}\sim{\rm
Laplace}(0,2/[\tilde{n}\varepsilon])$, and $\rho_{2}\sim{\rm
Laplace}(0,2/[n\varepsilon])$. DPLaplace satisfies $\epsilon$-DP,
NonDPLaplace1 one violates the guarantee because it has access to the private
number of points, and NonDPLaplace2 one privatizes the number of points to
estimate the scale of the noise added to the mean statistic but the mean
itself is computed using the non-private number of points. We also evaluate
JointMedian an implementation of a private median mechanism, and NoisyMax a
private noisy max mechanism for selecting an index with highest counts from a
finite set of $[n]$ indices.

Sparse vector technique mechanisms. The next six mechanisms address different
private and non-private implementations of the sparse vector technique (SVT),
a mechanism for releasing a stream of $c$ queries on a fixed dataset. SVT
mechanisms compare each query value against a threshold and the given
algorithm returns certain outputs for a maximum number of queries $c$. We
denote these by SVT1 –SVT6  and they correspond to Algorithms 1-6 in [31].
SVT1  and SVT2  satisfy $\epsilon$-DP. SVT4  satisfies $(\frac{1+6c}{4})$-DP,
and $\textsc{SVT3 },\textsc{SVT5 }$, and SVT6  do not satisfy $\epsilon$-DP
for any finite $\epsilon$.

Rényi DP mean mechanisms. To verify the ability of our tester to detect
violations of Rényi differential privacy we first instantiate NonDPGaussian1
and NonDPGaussian2 , analogs of NonDPLaplace1 and NonDPLaplace2 but that add
Gaussian noise instead of Laplace noise.

###  6.2 Bug catching rate

False positives.  Note that from an information theoretic point of view, no
tester can claim a truly private mechanism is not private. Therefore, the only
reason for a potential false positive comes from a sampling error which is
controlled by the parameter $\beta$. In our experiments we verify this is true
as none of our testers claim a private mechanism to be non-private.

True positives. Table 1 introduces the true negative rate detection for each
tester. For this table, we fixed a pair of neighboring datasets where a
violation is known to occur. We ran each tester 10 times for two different
privacy regimes, high privacy ($\epsilon=0.01$) and low privacy
($\epsilon=1.0$). Due to discretization, the HistogramTester does not apply to
mechanisms whose output has more than one-dimension and consequently does not
apply to SVT mechanisms. We observe that on the specific datasets provided,
the HistogramTester detects only NonDPLaplace2 independently of the sample
size but the fails at detecting other bugs. The RényiTester misses all the SVT
mechanisms but catches the rest for the high privacy regime. The MMD tester
catches version 1 of non-private mean but fails at catching the rest. Finally,
the HockeyStick tester catches all but SVT3 . For SVT, it benefits from the
high privacy regime while one-dimensional it varies between these two.

Table 1: Detection rate of non-private mechanisms. We report the number of times each tester detects a privacy violation on a fixed dataset where a privacy violation is known to occur. Each tester is run 10 times. We report for high privacy regime ($\epsilon=0.01$) and low privacy regime ($\epsilon=1.0$) Mechanism | $\epsilon$ | Historgram | HS | Rényi | MMD
---|---|---|---|---|---
n (In thousands) |  | $50$ | $100$ | $500$ | $50$ | $100$ | $500$ | $50$ | $100$ | $500$ | $50$ | $100$ | $500$
NonDPLaplace1 | 0.01 | 0 | 0 | 0 | 9 | 8 | 9 | 10 | 10 | 10 | 10 | 9 | 10
| 1.0 | 0 | 0 | 0 | 10 | 10 | 10 | 0 | 0 | 0 | 0 | 0 | 0
NonDPLaplace2 | 0.01 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 7 | 5 | 0 | 1 | 0
| 1.0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
NonDPGaussian1 | 0.01 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 4 | 10
. | 1.0 | 0 | 0 | 0 | 10 | 10 | 10 | 0 | 0 | 0 | 0 | 0 | 0
NonDPGaussian2 | 0.01 | 0 | 0 | 0 | 6 | 5 | 5 | 10 | 10 | 10 | 0 | 0 | 0
| 1.0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVT3 | 0.01 |  | - |  | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 1.0 |  | - |  | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
SVT4 | 0.01 |  | - |  | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 0
| 1.0 |  | - |  | 10 | 10 | 10 | 0 | 0 | 0 | 0 | 0 | 0
SVT5 | 0.01 |  | - |  | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 1.0 |  | - |  | 10 | 10 | 10 | 0 | 0 | 0 | 0 | 0 | 0
SVT6 | 0.01 |  | - |  | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
| 1.0 |  | - |  | 10 | 10 | 10 | 0 | 0 | 0 | 0 | 0 | 0

###  6.3 Dataset Finder algorithms

Table 2 compares three different approaches for finding datasets where privacy
violations occur. We observe that all approaches tend to find a dataset for a
given bug, but grid search, that pursues an exhaustive deterministic
evaluation of the dataset space tends to find datasets at a slower rate than
randomized search algorithms.

Table 2: Average number of trials to find a bug. We run each tester 10 times. For each pair of (Tester, $\mathcal{G}$) we report the average number of trials the algorithm takes to find a privacy violation, with a maximum of 50 trials. RényiTester uses $\alpha=1.5$. Histogram Tester uses a discretization parameter of $m=100$. All testers use $n=500000$ samples and $\epsilon=0.01$ Mechanism (down) | Gaussian process bandit
---|---
Dataset finder | Histogram | Renyi | MMD | HS
NonDPLaplace1 | 50 | 1.0 | 1.0 | 1.2
NonDPLaplace2 | 8.3 | 9.5 | 12.3 | 2.5
NonDPGaussian1 | 50.0 | 1.0 | 1.0 | 50.0
NonDPGaussian2 | 50.0 | 3.6 | 47.3 | 19.1
SVT 3 | - | 50.0 | 50.0 | 50.0
SVT 4 | - | 50.0 | 50.0 | 50.0
SVT 5 | - | 50.0 | 50.0 | 50.0
SVT 6 | - | 50.0 | 50.0 | 50.0
| Randomized
NonDPLaplace1 | 50.0 | 1.0 | 1.0 | 1.3
NonDPLaplace2 | 10.1 | 3.6 | 12.3 | 1.5
NonDPGaussian1 | 50.0 | 1.0 | 1.0 | 50
NonDPGaussian2 | 50.0 | 1.2 | 47.3 | 45.6
SVT 3 | - | 50.0 | 50.0 | 50
SVT 4 | - | 50.0 | 50.0 | 50
SVT 5 | - | 50.0 | 50.0 | 50
SVT 6 | - | 50.0 | 50.0 | 50
| Grid search
NonDPLaplace1 | 50.0 | 1.0 | 1.0 | 1.1
NonDPLaplace2 | 50.0 | 3.0 | 12.3 | 30.2
NonDPGaussian1 | 50.0 | 1.0 | 1.0 | 50.0
NonDPGaussian2 | 50.0 | 11.3 | 47.3 | 50.0
SVT 3 | - | 50.0 | 50.0 | 50.0
SVT 4 | - | 50.0 | 50.0 | 50.0
SVT 5 | - | 50.0 | 50.0 | 50.0
SVT 6 | - | 50.0 | 50.0 | 50.0

###  6.4 Running time

Another important element of a testing library is the running time for each
tester. While the purpose of this testing library is not to serve as a unit-
test but potentially as an integration test (allowing for a more prolonged
testing time), it remains crucial to ensure that running times are not
prohibitive to ensure adoption of this library. In Figure 1 we show the
running time as a function of the sample size of running different tests for a
single trial of testing the NonDPLaplace1 mechanism. Experiment were ran using
a Colab notebook with two different back-ends. The first back-end used only a
CPU while the second backend used a NVIDIA V100 GPU. We ran the testers
varying the number of samples across $\\{50000,100000,500000\\}$. Each tester
was ran 10 times and Figure 1 shows the average running time across the 10
iterations. As one can see, the hockey stick divergence tester running on CPUs
seems to have the longest running time yet when training the discriminator
model using GPUs, the run time reduces significantly and in fact is faster
than most other testers for sample size 500,000. Note also that,even though
both the Rényi tester and the hockey-stick divergence tester both train a
neural network, their running times are different and the benefits from the
hardware accelerators seem to be bigger for the hockey-stick divergence test.
This could be because we run the hockey-stick divergence tester for a longer
period of time (30 epochs vs 5 epochs) in order to achieve convergence.

(a)

(b)

Figure 1: Run time (in seconds) for different testers (a) when ran using a
single CPU (b) when using a GPU accelerator.

###  6.5 ScaleGD

We include a flawed DP-GD’s [32] implementation. The implementation for this
mechanism corresponds to a DP-GD optimizer that receives a model $f_{\theta}$,
learning rate, noise multiplier $\sigma$, clip norm value $G$, and takes a DP-
GD with noise scaled by $\sigma G$ respect to the parameters $\theta$. The
implementation simulates a scenario where a developer assumes using a noise
multiplier $\sigma_{\text{theory}}$ but in reality uses a noise multiplier
$\sigma_{\text{effective}}$. We dub this scenario ScaledGD . To catch this
bug, a one-dimensional model $\theta$ is sufficient so we do not experiment
with larger models. Different bugs that could require experimenting with
larger models.

We highlight that $\sigma_{\text{effective}}=\frac{\sigma_{\text{theory}}}{2}$
corresponds to a true bug in the literature. It corresponds to a frequent
accounting error when using batch or micro-batch clipping instead of per-
example clipping in DP-SGD. Per-example clipping is memory and computationally
expensive when training high-dimensional models. To address these constraints
at the cost of utility, practitioners split a batches of size $n$ into $m$
microbatches of size $n/m$, compute average gradients over each micro-batch,
clip and noise the per-microbatch gradient, and finally average the resulting
noisy micro-batch gradients. It sometimes goes unnoticed but the sensitivity
of per-microbatch gradients is $2G$ instead of $G$.

We explore this bug on DP-GD using a standard Rényi differential privacy
accounting framework. The implementation adds gaussian noise with scale
$s\cdot\sigma_{\text{theory}}$ where $0<s<1$ is a factor decreasing the
assumed noise scale $\sigma_{\text{theory}}$. In fig. 2 we show the ability of
RényiTester to catch the bug for different values of $s$ given an
$(\alpha,\epsilon)-$Renyi DP guarantee. We observe that the divergence
estimates follow the true divergence values and the tester catches the bug for
$s\leq 0.6$.

Figure 2: True and estimated value of the Rényi divergence on samples of
ScaledGD .

###  6.6 Effect of sample size

Although for most of the test runs, the results of Table 1 do not seem to be
sensitive to the number of samples drawn from a mechanism. A deeper dive into
the divergence evaluation of these mechanisms show that there is in fact a
benefit obtained from using larger sample sizes. In particular, for a fixed
dataset, Figure 3(a) shows that the estimated divergence increases with sample
size. Moreover, not surprisingly, the confidence intervals do become smaller
as the sample increases. A similar effect can be found on the number of trials
required to detect a privacy violation using the Gaussian process bandit
algorithm. As one can observe in Figure 3(b), the number of trials can
drastically decrease — in view of the reduce variance of divergence estimation
— as the number of samples returned by the mechanism increases.

(a)

(b)

Figure 3: Effects of sample size on (a) the divergence estimation of the
output mechanism (b) the number of trials needed to find a privacy violation.
Privacy parameters in this experiment were $\epsilon=1$ for the SVT mechanism
and $\epsilon=1.0,\delta=0.01$ for the Gaussian mechanism

###  6.7 Testing anecdotes

It is worth mentioning that, while preparing the experimental code for this
paper, we were under the assumption that the algorithm SVT4 was private. In
effect, the mechanism is private albeit with a higher value of $\epsilon$ than
what the original introduction of the algorithm claims [31]. We were therefore
puzzled by the fact that the Hockey-stick divergence tester would find a
privacy violation. It wasn’t until further reviewing [31] that we realized
that our understanding was wrong and that the tester was indeed correctly
flagging a privacy violation on SVT4.

A similar issue happened when verifying that our tester wouldn’t flag private
mechanisms as not private. We implemented a mean estimator using a Laplace
mechanism to estimate both the numerator and the denominator of the mean. When
we ran that algorithm on our tester, the mechanism was flagged as not private.
Upon careful inspection of our implementation we realized that we didn’t
divide the privacy budget to estimate both quantities. This shows how easily
bugs can be introduced when implementing private mechanisms.

##  7 Conclusion

We have introduced a new flexible library for testing differential privacy. As
demonstrated by even simple implementation issues in our experimentation code,
failing to correctly implement a private mechanism can easily happen. These
errors have consequences that range from having wrong privacy claims in
academic publications (thus making different private algorithms for the same
task incomparable) to more serious issues of making public claims around data
protection that may not be valid. Having a unified testing framework can help
auditors and regulators ensure that private mechanisms are indeed private. It
is also a tool that can provide developers with peace of mind in implementing
complex private systems.

We also have introduced a new, powerful way of testing differential privacy
through divergence optimization over function spaces. Our results show that
this type of function-based estimation consistently outperforms histogram-
based divergence estimators. Moreover we provide a variety of these estimators
that allow for a better discovery rate of privacy bugs. We hope that by open
sourcing this efficient library, the research community can establish a
standard of doing end to end testing new differentially private algorithms.

## References

  * [1] A. C. Gilbert and A. McMillan, “Property testing for differential privacy,” in _Allerton Conference on Communication, Control, and Computing_ , 2018.
  * [2] B. Bichsel, S. Steffen, I. Bogunovic, and M. Vechev, “Dp-sniper: Black-box discovery of differential privacy violations using classifiers,” in _Symposium on Security and Privacy (SP)_. IEEE, 2021.
  * [3] X. Nguyen, M. J. Wainwright, and M. I. Jordan, “Estimating divergence functionals and the likelihood ratio by convex risk minimization,” _IEEE Transactions on Information Theory_ , vol. 56, no. 11, 2010.
  * [4] P. Zhao and L. Lai, “Minimax optimal estimation of kl divergence for continuous distributions,” _IEEE Trans. Inf. Theor._ , vol. 66, no. 12, p. 7787–7811, dec 2020.
  * [5] B. K. Sriperumbudur, K. Fukumizu, A. Gretton, B. Schölkopf, and G. R. Lanckriet, “On the empirical estimation of integral probability metrics,” _Electronic Journal of Statistics_ , vol. 6, pp. 1550–1599, 2012.
  * [6] J. Birrell, P. Dupuis, M. A. Katsoulakis, L. Rey-Bellet, and J. Wang, “Variational representations and neural network estimation of Rényi divergences,” _SIAM Journal on Mathematics of Data Science_ , 2021.
  * [7] C. Domingo-Enrich and Y. Mroueh, “Auditing differential privacy in high dimensions with the kernel quantum Rényi divergence,” _arXiv preprint arXiv:2205.13941_ , 2022.
  * [8] V. Doroshenko, B. Ghazi, P. Kamath, R. Kumar, and P. Manurangsi, “Connect the dots: Tighter discrete approximations of privacy loss distributions,” _Proceedings on Privacy Enhancing Technologies_ , 2022.
  * [9] K. Dixit, M. Jha, S. Raskhodnikova, and A. Thakurta, “Testing the Lipschitz property over product distributions with applications to data privacy,” in _Theory of Cryptography Conference (TCC_ , 2013.
  * [10] Z. Ding, Y. Wang, G. Wang, D. Zhang, and D. Kifer, “Detecting violations of differential privacy,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_. Association for Computing Machinery, 2018, p. 475–489.
  * [11] B. Bichsel, S. Steffen, I. Bogunovic, and M. Vechev, “Dp-sniper: Black-box discovery of differential privacy violations using classifiers,” in _2021 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2021, pp. 391–409.
  * [12] M. Jagielski, J. Ullman, and A. Oprea, “Auditing differentially private machine learning: How private is private sgd?” _Advances in Neural Information Processing Systems_ , 2020.
  * [13] B. Jayaraman and D. Evans, “Evaluating differentially private machine learning in practice,” in _USENIX Security Symposium_ , 2019.
  * [14] S. Rahimian, T. Orekondy, and M. Fritz, “Differential privacy defenses and sampling attacks for membership inference,” in _ACM Workshop on Artificial Intelligence and Security_ , 2021.
  * [15] D. Chen, N. Yu, Y. Zhang, and M. Fritz, “Gan-leaks: A taxonomy of membership inference attacks against generative models,” in _ACM SIGSAC Conference on Computer and Communications Security_ , 2020.
  * [16] C. Guo, B. Karrer, K. Chaudhuri, and L. van der Maaten, “Bounding training data reconstruction in private (deep) learning,” in _International Conference on Machine Learning (ICML)_. PMLR, 2022.
  * [17] B. Balle, G. Cherubin, and J. Hayes, “Reconstructing training data with informed adversaries,” in _43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022_. IEEE, 2022, pp. 1138–1156.
  * [18] F. Lu, J. Munoz, M. Fuchs, T. LeBlond, E. V. Zaresky-Williams, E. Raff, F. Ferraro, and B. Testa, “A general framework for auditing differentially private machine learning,” in _Advances in Neural Information Processing Systems_ , 2022.
  * [19] M. Nasr, S. Songi, A. Thakurta, N. Papernot, and N. Carlin, “Adversary instantiation: Lower bounds for differentially private machine learning,” in _2021 IEEE Symposium on security and privacy (SP)_ , 2021.
  * [20] M. Nasr, J. Hayes, T. Steinke, B. Balle, F. Tramèr, M. Jagielski, N. Carlini, and A. Terzis, “Tight auditing of differentially private machine learning,” _arXiv preprint arXiv:2302.07956_ , 2023.
  * [21] M. Jagielski, J. Ullman, and A. Oprea, “Auditing differentially private machine learning: How private is private sgd?” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 22 205–22 216, 2020.
  * [22] G. Andrew, P. Kairouz, S. Oh, A. Oprea, H. B. McMahan, and V. Suriyakumar, “One-shot empirical privacy estimation for federated learning,” _arXiv preprint arXiv:2302.03098_ , 2023.
  * [23] A. Krishnamurthy, K. Kandasamy, B. Poczos, and L. Wasserman, “Nonparametric estimation of renyi divergence and friends,” in _International Conference on Machine Learning_. PMLR, 2014\.
  * [24] I. Mironov, “Rényi differential privacy,” in _IEEE computer security foundations symposium (CSF)_ , 2017.
  * [25] Y. Zhu, J. Dong, and Y.-X. Wang, “Optimal accounting of differential privacy via characteristic function,” in _International Conference on Artificial Intelligence and Statistics (AISTATS_ , 2022.
  * [26] G. Barthe and F. Olmedo, “Beyond differential privacy: Composition theorems and relational logic for f-divergences between probabilistic programs,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 2013.
  * [27] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola, “A kernel two-sample test,” _The Journal of Machine Learning Research_ , vol. 13, no. 1, pp. 723–773, 2012.
  * [28] A. Maurer and M. Pontil, “Empirical bernstein bounds and sample variance penalization,” 2009.
  * [29] T. Desautels, A. Krause, and J. W. Burdick, “Parallelizing exploration-exploitation tradeoffs in gaussian process bandit optimization,” _Journal of Machine Learning Research_ , 2014.
  * [30] D. Golovin, B. Solnik, S. Moitra, G. Kochanski, J. Karro, and D. Sculley, “Google vizier: A service for black-box optimization,” in _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_ , 2017.
  * [31] M. Lyu, D. Su, and N. Li, “Understanding the sparse vector technique for differential privacy,” _arXiv preprint arXiv:1603.01699_ , 2016.
  * [32] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _ACM SIGSAC conference on computer and communications security_ , 2016.
  * [33] Y. Polyanskiy and Y. Wu, “Information theory: From coding to learning,” _Book draft_ , 2022.
  * [34] M. Mohri, A. Rostamizadeh, and A. Talwalkar, _Foundations of machine learning_. MIT press, 2018.

##  Appendix A Additional definitions, lemmas and proofs

######  Lemma.

The variational representation for the Hockey stick divergence (see eq. 25 in
the supplementary material) is given by

$H_{\epsilon}(P||Q)=\sup_{g:0\leq g\leq
1}\mathbb{E}_{P}\left[g(X)\right]-\mathbb{E}_{Q}\left[e^{\epsilon}g(X))\right].$
(14)

###### Proof.

By definition, the conjugate function $f^{*}$ of a function $f$ is given by
${f^{*}(y)=\sup_{x\in\mathbb{R}}yx-f(x)}$. We first show that
${f^{*}(y)=e^{\epsilon}y}$ for $0<y<1$. For the Hockey stick divergence,
${f(x)=\max\\{0,x-e^{\epsilon}\\}}$, thus,

$\displaystyle f^{*}(y)$
$\displaystyle=\sup_{x\in\mathbb{R}}y^{T}x-\max\\{0,x-e^{\epsilon}\\}$

If $y<0$, $f^{*}(y)=\infty$ since $x$ can be arbitrarily negative. If $y>1$
and if $x>e^{\epsilon}$ we have that:

$\displaystyle f^{*}(y)=\sup_{x>e^{\epsilon}}yx-\max\\{0,x-e^{\epsilon}\\}$
$\displaystyle=yx-x+e^{\epsilon}$ $\displaystyle=(y-1)x+e^{\epsilon}.$

The last expression can be arbitrarily large if $x$ goes to infinity.

Finally, if $0\leq y\leq 1$, we consider two cases: $x\leq e^{\epsilon}$ and
$x>e^{\epsilon}$ and show the supremum takes the same value in both ranges.
When $x\leq e^{\epsilon}$:

$\displaystyle f^{*}(y)=\sup_{x\leq
e^{\epsilon}}yx-\max\\{0,x-e^{\epsilon}\\}$ $\displaystyle=\sup_{x\leq
e^{\epsilon}}yx=ye^{\epsilon}.$

When $x>e^{\epsilon}$,

$\displaystyle f^{*}(y)=\sup_{x>e^{\epsilon}}yx-\max\\{0,x-e^{\epsilon}\\}$
$\displaystyle=\sup_{x>e^{\epsilon}}(y-1)x+e^{\epsilon}.$

Since $y\leq 1$, $y-1\leq 0$, so $(y-1)x$ is maximized when $x$ takes the
smallest value, $x=e^{\epsilon}$. Consequently,

$\displaystyle f^{*}(y)$
$\displaystyle=\sup_{x>e^{\epsilon}}(y^{T}-1)x+e^{\epsilon}.$
$\displaystyle=(y-1)e^{\epsilon}+e^{\epsilon}=ye^{\epsilon}.$

Thus, we conclude that $f^{*}(y)=\begin{cases}ye^{\epsilon}&\text{ if }0\leq
y\leq 1,\\\ \infty&\text{ otherwise, }\end{cases}$ and $dom(f*)=[0,1]$.

The result follows by replacing $f^{*}$ in the the following variational
representation of $f-$divergences [33]:

$D_{f}(P||Q)=\sup_{g:\mathcal{X}\to
dom(f^{*})}\mathbb{E}_{P}\left[g(x)\right]-\mathbb{E}_{Q}\left[f^{*}(g(x))\right]$

∎

######  Theorem A.1 (Chernoff multiplicative bound, Theorem D.4. in [34]).

Let $X_{1},...,X_{n}$ be independent random variables drawn according to some
distribution $P$ with mean $\mu$ and support in $[0,M]$. Then for any
$\eta\in[0,\frac{M}{\mu}-1]$ the following inequalities hold:

$P\left(\frac{1}{n}\sum_{i=1}^{n}X_{i}\geq(1+\eta)\mu\right)\leq
e^{\frac{-n\mu\eta^{2}}{3M}}$ (15)

$P\left(\frac{1}{n}\sum_{i=1}^{n}X_{i}\leq(1-\eta)\mu\right)\leq
e^{\frac{-n\mu\eta^{2}}{2M}}$ (16)

######  Theorem.

(Theorem 4.3 in main body). Let $P$ and $Q$ be two distributions. Let $\Gamma$
be defined as in definition 4.2, and $h\in\Gamma$,
$h\colon\mathcal{X}\to\mathbb{R}$ be a function bounded by $C>0$, i.e.,
$\sup_{x\in\mathcal{X}}|h(x)|<C$. Let $\mathbf{X}_{0}=(X_{0,1},...,X_{0,n})$
and $\mathbf{X}_{1}=(X_{1,1},...,X_{1,n})$ be $n$ realizations of $P$ and $Q$,
respectively. Then, if $\eta\in(0,1]$, and

$n\geq\max\left(\frac{3e^{2(\alpha-1)C}\log(2/\beta)}{\eta^{2}},\frac{2e^{\alpha
C}\log(2/\beta)}{\eta^{2}}\right),$

with probability at least $1-\beta$, it follows that

$\displaystyle R_{\alpha}$ $\displaystyle(P||Q)\geq
R^{h,n}_{\alpha}(\mathbf{X}_{0}||\mathbf{X}_{1})-\log\left(\frac{1+\eta}{1-\eta}\right)$
(17)

###### Proof.

Define $\mu_{1}=\mathbb{E}_{P}\left[e^{(\alpha-1)h(x)}\right]$, and
$\mu_{2}=\mathbb{E}_{Q}\left[e^{\alpha h(x)}\right]$, and also
$M_{1}=e^{(\alpha-1)C}$ and $M_{2}=e^{\alpha C}$.

From Chernoff’s multiplicative bound ( theorem A.1, eq. 15) we know that for
$\eta_{1}\in[0,\frac{M_{1}}{\mu_{1}}-1]$, with probability less than
$e^{\frac{-n\mu_{1}\eta_{1}^{2}}{3M_{1}}}$, we have

$\frac{\frac{1}{n}\sum_{i=1}^{n}e^{(\alpha-1)h(x_{i})}}{\mathbb{E}[e^{(\alpha-1)h(X)}]}\geq(1+\eta_{1})$

This implies that

$\displaystyle\log\left[\frac{1}{n}\sum_{i=1}^{n}e^{(\alpha-1)h(x_{i})}\right]-\log\mathbb{E}_{P}\left[e^{(\alpha-1)h(X)}\right]$
$\displaystyle\geq\log(1+\eta_{1})\geq\tfrac{\alpha-1}{\alpha}\log(1+\eta_{1}),$

or equivalently,

$\displaystyle\tfrac{\alpha}{\alpha-1}\log\frac{1}{n}\sum_{i=1}^{n}e^{(\alpha-1)h(x_{i})}-\tfrac{\alpha}{\alpha-1}\log\mathbb{E}_{P}\left[e^{(\alpha-1)h(X)}\right]$
$\displaystyle\geq\log(1+\eta_{1})$ (18)

Note that by setting
$n\geq\frac{3e^{(\alpha-1)C}\log(2/\beta)}{\mu_{1}\eta_{1}^{2}}$ the above
bound holds with probability at most $\beta/2$. A similar analysis (using eq.
16) shows that for $n\geq\frac{2e^{\alpha
C}\log(2/\beta)}{\mu_{2}\eta_{2}^{2}}$ with probability at most $\beta/2$ the
following bound holds:

$\displaystyle\log\mathbb{E}_{Q}\left[e^{\alpha
h(X_{1})}\right]-\log\left[\frac{1}{n}\sum_{i=1}^{n}e^{\alpha
h(X_{1,i})}\right]$ $\displaystyle\geq\log\left(\frac{1}{1-\eta_{2}}\right).$
(19)

Finally, summing eq. 18 and appendix A, and using the union bound, with
probability $1-\beta$ we have that

$\displaystyle
R^{h,n}(\mathbf{X}_{0}||\mathbf{X}_{1})-\log\left(\frac{1}{1-\eta_{2}}\right)-\log(1+\eta_{1})\leq
R^{h}(P||Q).$

Letting $\eta=\min(\eta_{1},\eta_{2})$,

$R^{h,n}(\mathbf{X}_{0}||\mathbf{X}_{1})-\log\left(\frac{1+\eta}{1-\eta}\right)\leq
R^{h}(P||Q).$ (20)

Finally, since $h\in\Gamma$, using the variational formulation for the Rényi
divergence,

$\displaystyle R_{\alpha}(P||Q)$
$\displaystyle=\sup_{h\in\Gamma}R_{\alpha}^{h}(P||Q)$ (21) $\displaystyle\geq
R_{\alpha}^{h}(P||Q)$ (22)

and the result follows by combining eq. 20 and eq. 21. ∎

######  Definition A.2.

Given a function $f:[0,\infty)\to\mathbb{R}$ such that $f(1)=0$ and
$\lim_{t\to 0^{+}}f(t)=f(0)$. Let $P$ and $Q$ be two probability measures over
space$\mathcal{X}$ such that $P$ is absolutely continuous respect to $Q$. The
$f-$divergence between $P$ and $Q$ is defined as

$D_{f}(P||Q)=\mathbb{E}_{Q}\left[f\left(\frac{dP}{dQ}\right)\right]$ (24)

It will be useful to see $D_{f}$ through its variational representation:

$D_{f}(P||Q)=\sup_{g:\mathcal{X}\to\text{dom}(f_{ext}^{*})}\operatorname*{\mathbb{E}}_{P}\left[g(X)\right]-\operatorname*{\mathbb{E}}_{Q}\left[f^{*}(g(X))\right].$
(25)

######  Lemma A.3.

Let $\epsilon>0$ Fix two distributions $P$ and $Q$ over $\mathcal{X}$. Let
$\mathbb{D}$ be a mixture distribution over $\mathcal{X}\times\\{0,1\\}$
defined as
$\mathbb{D}=\frac{e^{\epsilon}}{1+e^{\epsilon}}Q\times\delta_{0}+\frac{1}{1+e^{\epsilon}}P\times\delta_{1}$.
That is, $(X,Y)\sim\mathbb{D}$ labels samples from $Q$ as $0$ and samples from
$P$ as $1$. Then

$H_{\epsilon}(P||Q)=(1+e^{\epsilon})\sup_{g}\mathbb{D}(g(X)=Y)-e^{\epsilon}$

###### Proof.

We begin by showing that the variational formula for the hockey-stick
divergence is maximized for functions taking values in $\\{0,1\\}$. Using
Hahn’s decomposition theorem let $A$ and $B$ be such that $\mathcal{X}=A\cup
B$, $A\cap B=\emptyset$ and $A$ is the maximal positive set of the signed
measure $\nu=P-e^{\epsilon}Q$. That is $P(A)-e^{\epsilon}Q(A)>P(A\cap
C)-e^{\epsilon}Q(A\cap C)>0$ for every $C\subset\mathcal{X}$ and
$P(B)-e^{e}pQ(B)\leq(B\cap C)-e^{\epsilon}P(B\cap C)<0$ for every $C$. Let
$g^{*}$ be defined as $g^{*}(x)=1$ if $x\in A$ and $0$ otherwise. We show that
$g^{*}$ maximizes:

$\operatorname*{\mathbb{E}}_{P}[g(x)]-\operatorname*{\mathbb{E}}_{Q}(e^{\epsilon}g(X)]$

First notice that the above expression evaluated on $g^{*}$ is given by

$P(A)-e^{\epsilon}Q(A).$

Moreover, by Proposition A.4 we also know that for any other function $g$ we
must have

$\operatorname*{\mathbb{E}}_{P}[g(X)]-e^{\epsilon}\operatorname*{\mathbb{E}}_{Q}[g(X)]=\operatorname*{\mathbb{E}}_{\nu}[g(X)]\leq\nu(A)=P(A)-e^{\epsilon}Q(A)$

Now notice that by definition of $\mathbb{D}$ we have

$\displaystyle\mathbb{D}(g(X)=Y)$
$\displaystyle=\frac{e^{\epsilon}}{1+e^{\epsilon}}Q(g(X)=0)+\frac{1}{1+e^{\epsilon}}P(g(X)=1)$
$\displaystyle=\frac{e^{\epsilon}}{1+e^{\epsilon}}(1-Q(g(X)=1))+\frac{1}{1+e^{\epsilon}}(P(g(X)=1))$
$\displaystyle=\frac{1}{1+e^{\epsilon}}\left(P(g(X)=1)-e^{\epsilon}Q(g(X)=1)\right)+\frac{e^{\epsilon}}{1+e^{\epsilon}}$
$\displaystyle=\frac{1}{1+e^{\epsilon}}\left(\operatorname*{\mathbb{E}}_{P}[g(X)]-e^{\epsilon}\operatorname*{\mathbb{E}}_{Q}[g(X)]\right)+\frac{e^{\epsilon}}{1+e^{\epsilon}}$

Taking the supremum over $g\colon\mathcal{X}\to\\{0,1\\}$ we obtain the
following:

$\sup_{g}\mathbb{D}(g(X)=Y)-\frac{e^{\epsilon}}{1+e^{\epsilon}}=\frac{1}{1+e^{\epsilon}}H_{\epsilon}(P||Q)$

∎

######  Proposition A.4.

Let $g\colon\mathcal{X}\to[0,1]$ be a measurable function. Let $\nu$ be a
signed, finite measure and let $\operatorname*{\mathbb{E}}_{\nu}[g(X)]=\int
g(x)d\nu(x)$ denote the Lebesgue integral of $g$. Let $A$ and $B$ be the
maximal positive and negative sets of $\nu$ according to Hahn’s decomposition
theorem then the following bound holds for any $g$:

$\operatorname*{\mathbb{E}}_{\nu}[g(X)]\leq\nu(A)$ (26)

###### Proof.

We begin the proof by considering the simple case where
$g(x)=\sum_{i=1}^{n}\alpha_{i}\mathds{1}_{C_{i}}(x)$ for some disjoint
measurable sets $C_{i}$ satisfying $\bigcup_{i=1}^{n}C_{i}=\mathcal{X}$ and
$\alpha_{i}\in[0,1]$. We refer to such functions as _simple_ functions. In
this case

$\displaystyle\operatorname*{\mathbb{E}}_{\nu}[g(X)]$
$\displaystyle=E_{\nu}[g(X)\mathds{1}_{A}]+[g(X)\mathds{1}_{B}]$
$\displaystyle=\sum_{i=1}^{n}\alpha_{i}\operatorname*{\mathbb{E}}_{\nu}[\mathds{1}_{A\cap
C_{i}}]+\sum_{i=1}^{n}\alpha\operatorname*{\mathbb{E}}_{\nu}[\mathds{1}_{B\cap
C_{i}}]$ $\displaystyle=\sum_{i=1}^{n}\alpha_{i}\nu(A\cap
C_{i})+\sum_{i=1}^{n}\alpha_{i}\nu(B\cap C_{i})$
$\displaystyle\leq\sum_{i=1}^{n}\alpha_{i}\nu(A\cap C_{i})$

Where we have used the the property of Hahn’s decomposition theorem:
$\nu(B\cap C_{i})\leq 0$ for all $i$ as well as the fact that $\alpha_{i}>0$.
Using the same property for the positive set $A$ we have that $\nu(A\cap
C_{i})>0$ for all $i$. Moreover since $\alpha_{i}\leq 1$ we have that the
above quantity is bounded by:

$\sum_{i=1}^{n}\nu(A\cap C_{i})=\nu(A)$

For a general measurable function $g\colon\mathcal{X}\to[0,1]$ we use the well
known property that one can approximate $g$ as a limit of simple functions
$g_{n}$. By the dominated convergence theorem we then have that

$\operatorname*{\mathbb{E}}_{\nu}[g(x)]=\operatorname*{\mathbb{E}}_{\nu}[\lim_{n\to\infty}g_{n}(x)]\leq\nu(A).$

∎

###### Proof of Theorem 4.13.

Let $k_{x}=k(x,\cdot)$ for all $x\in\mathcal{X}$. By the reproducing property
we have $k_{x}\in H$ and $f(x)=\left\langle f,k_{x}\right\rangle$ for all
$f\in H$. In particular this implies $k(x,y)=\left\langle
k_{x},k_{y}\right\rangle$. And since $k(x,x)\leq 1$ we have $\left\lVert
k_{x}\right\rVert=\sqrt{\left\langle
k_{x},k_{x}\right\rangle}=\sqrt{k(x,x)}\leq 1$ Therefore

$|f(x)|=|\left\langle f,k_{x}\right\rangle|\leq\left\lVert
f\right\rVert\left\lVert k_{x}\right\rVert\leq\left\lVert f\right\rVert.$ (27)

Let $P=\mathcal{M}(D_{0})$ and $Q=\mathcal{M}(D_{1})$. For any $f\in H$ such
that $\left\lVert f\right\rVert\leq 1$ we have

$\displaystyle\int fdP-\int fdQ$ $\displaystyle=\int f\frac{dP}{dQ}dQ-\int
fdQ$ $\displaystyle=\int\left(\frac{dP}{dQ}-1\right)fdQ$
$\displaystyle\leq\sup_{x}|f(x)|\int\left|\frac{dP}{dQ}-1\right|dQ$
$\displaystyle\leq\int\left|\frac{dP}{dQ}-1\right|dQ$

where $\frac{dP}{dQ}$ is the Radon-Nikodym derivative and the second
inequality follows from Eq. (27). Now partition $\mathcal{X}$ as follows:

$\displaystyle A$ $\displaystyle=\left\\{x\in\mathcal{X}:\frac{dP}{dQ}(x)\geq
1\right\\}$ $\displaystyle B$
$\displaystyle=\left\\{x\in\mathcal{X}:\frac{dP}{dQ}(x)<1\right\\}$

Continuing from above we have

$\int\left|\frac{dP}{dQ}-1\right|dQ=\int_{A}\left(\frac{dP}{dQ}-1\right)dQ+\int_{B}\left(1-\frac{dP}{dQ}\right)dQ$

We will bound each integral on the right-hand side. We have

$\displaystyle\int_{A}\left(\frac{dP}{dQ}-1\right)dQ$
$\displaystyle=P(A)-Q(A)$ $\displaystyle\leq e^{\epsilon}Q(A)+\delta-Q(A)$
$\displaystyle=Q(A)(e^{\epsilon}-1)+\delta$

where the inequality follows from the first part of the definition of
$(\epsilon,\delta)$-differentially privacy. We also have

$\displaystyle\int_{B}\left(1-\frac{dP}{dQ}\right)dQ$
$\displaystyle=Q(B)-P(B)$ $\displaystyle\leq
Q(B)-(e^{-\epsilon}Q(B)-e^{-\epsilon}\delta)$
$\displaystyle=Q(B)(1-e^{-\epsilon})+e^{-\epsilon}\delta$

where the inequality follows from the second part of the definition of
$(\epsilon,\delta)$-differentially privacy. Putting it all together, we have

$\displaystyle\int fdP-\int fdQ$ $\displaystyle\leq
Q(A)(e^{\epsilon}-1)+\delta+Q(B)(1-e^{-\epsilon})+e^{-\epsilon}\delta$
$\displaystyle\leq
Q(A)(e^{\epsilon}-1)+\delta+Q(B)(e^{\epsilon}-1)+e^{-\epsilon}\delta$
$\displaystyle=e^{\epsilon}-1+(1+e^{-\epsilon})\delta$

where we also used $e^{\epsilon}-1\geq 1-e^{-\epsilon}$, which can be proved
by expanding and rearranging the inequality $(e^{\epsilon}-1)^{2}\geq 0$, and
$Q(A)+Q(B)=1$. ∎

###### Proof of Theorem 4.15.

Suppose $P$ and $Q$ satisfy $(\epsilon,\delta)$-differential privacy. By
squaring both sides of Theorem 4.13 we have

$\operatorname{MMD}(P,Q,H)^{2}\leq(e^{\epsilon}-1)^{2}+2(e^{\epsilon}-e^{-\epsilon})\delta+(1+e^{-\epsilon})\delta^{2}.$

Let $X$ and $X^{\prime}$ be independent random variables with distribution
$P$. Let $Y$ and $Y^{\prime}$ be independent random variables with
distribution $Q$. By Theorem 4.14 we have

$\operatorname{MMD}(P,Q,H)^{2}=\operatorname*{\mathbb{E}}[h(X,X^{\prime},Y,Y^{\prime})].$

By the empirical Bernstein bound [28] we have with probability $1-\beta$

$\hat{\mu}-\operatorname*{\mathbb{E}}[h(X,X^{\prime},Y,Y^{\prime})]\leq\sqrt{\frac{2\hat{\sigma}^{2}\log\frac{2}{\beta}}{n}}+\frac{28\log\frac{2}{\beta}}{3(n-1)}$

where we again used $-2\leq h(X,X^{\prime},Y,Y^{\prime})\leq 2$. Putting the
above together we have

$\displaystyle 0$
$\displaystyle\leq-\hat{m}+2(e^{\epsilon}-e^{-\epsilon})\delta+(1+e^{-\epsilon})\delta^{2}.$

Minimizing the right-hand side using the quadratic formula proves the theorem.
∎