#  ExpM+NF: Differentially Private Machine Learning that Surpasses DPSGD
††thanks:  1Both authors contributed equally.  ††thanks:  Research sponsored
by the Laboratory Directed Research and Development Program of Oak Ridge
National Laboratory, managed by UT-Battelle, LLC, for the U. S. Department of
Energy. This manuscript has been co-authored by UT-Battelle, LLC under
Contract No. DE-AC05-00OR22725 with the US DOE. The United States Government
retains and the publisher, by accepting the article for publication,
acknowledges that the United States Government retains a non-exclusive, paid-
up, irrevocable, world-wide license to publish or reproduce the published form
of this manuscript, or allow others to do so, for United States Government
purposes. The DOE will provide public access to these results of federally
sponsored research in accordance with the DOE Public Access Plan
(http://energy.gov/downloads/doe-public-access-plan). ††thanks: Code
containing experiments presented available at Redacted URL. ††thanks: Special
thanks to Adam Spanhaus and Vishakh Gopu for their wisdom in debugging PyTorch
implementation issues, and to Cory Watson for making sure the big computers
“just work”.

Robert A. Bridges1, Vandy J. Tombs1, Christopher B. Stanley  Oak Ridge
National Laboratory, Oak Ridge, TN
{bridgesra, tombsvj, stanleycb} @ornl.gov

###### Abstract

In this pioneering work we formulate ExpM+NF, a method for training machine
learning (ML) on private data with pre-specified differentially privacy
guarantee $\varepsilon>0,\delta=0$, by using the Exponential Mechanism (ExpM)
and an auxiliary Normalizing Flow (NF). We articulate theoretical benefits of
ExpM+NF over Differentially Private Stochastic Gradient Descent (DPSGD), the
state-of-the-art (SOTA) and de facto method for differentially private ML, and
we empirically test ExpM+NF against DPSGD using the SOTA implementation
(Opacus [1] with PRV accounting) in multiple classification tasks on the Adult
Dataset (census data) and MIMIC-III Dataset (electronic healthcare records)
using Logistic Regression and GRU-D, a deep learning recurrent neural network
with $\scriptstyle\mathtt{\sim}$20K-100K parameters. In all experiments,
ExpM+NF achieves greater than 93% of the non-private training accuracy (AUC)
for $\varepsilon\in[1\mathrm{e}{-3},1]$, exhibiting greater accuracy (higher
AUC) and privacy (lower $\varepsilon$ with $\delta=0$) than DPSGD.
Differentially private ML generally considers $\varepsilon\in[1,10]$ to
maintain reasonable accuracy; hence, ExpM+NF’s ability to provide strong
accuracy for orders of magnitude better privacy (smaller $\varepsilon$)
substantially pushes what is currently possible in differentially private ML.
Training time results are presented showing ExpM+NF is comparable to (slightly
faster) than DPSGD. Code for these experiments will be provided after review.
Limitations and future directions are provided.

###### Index Terms:

differential privacy, machine learning, exponential mechanism, normalizing
flows, optimization

Figure 1: Figure depicts private data enclave on which outside entities would
like to train a machine learning model. New technique, ExpM+NF, depicted at
right, trains an auxiliary Normalizing Flow (NF) model to sample near optimal
parameters from the otherwise intractable Exponential Mechanism (ExpM)
density. Privacy parameters $(\varepsilon>0,\delta=0)$ are prespecified by the
private data center.

##  1 Introduction

As collection and storage of data on individuals and entities becomes more
frequent and detailed, rigorous methods for ensuring privacy of machine
learning (ML) models trained on sensitive data is a pressing need. Examples
from diverse domains are easy to find including predictive models for:
advanced diagnosis and treatment using healthcare records and images [2, 3],
increased security of IOT devices [4], and enabling smart meters to help
transition to a carbon-free energy grid [5], to name a few.

Winning the 2017 Gödel prize, differential privacy (DP) is a widely accepted
standard for privacy preserving analytics that has been adopted by the 2020 US
Census [6], Apple [7], Google [8], Microsoft [9] and a myriad of research
applications [10]. DP masks private data by injecting randomness into an
algorithm, often at the expense of accuracy. In particular, DP admits provable
quantifiable limits–in terms of a privacy budget $(\varepsilon,\delta)$–on the
possible inferences an outsider can make about the private data when viewing
the results of the analytics.

In this paper, we present ExpM+NF, a fundamentally different approach for
achieving differentially private ML, by which we mean training an ML algorithm
on a single (private) dataset with a DP guarantee. Our method leverages the
Exponential Mechanism (ExpM) [11], a well-established DP technique for
optimizing a utility (inverse loss) function. The process is to sample from
the ExpM distribution, a probability distribution over the model’s parameter
space (the domain of the utility/loss function) so that near-optimal (resp.,
far-from-optimal) parameters have high (resp., low) likelihood. By design,
sampling from this distribution produces, with high likelihood, near-optimal
parameters that are furnished with a strong privacy guarantee—the privacy
budget $\varepsilon>0$ is pre-specified and $\delta=0$.

While ExpM is well known, two obstructions prevented its prior use in ML
applications. First, sampling from the requisite distribution is intractable
except for finite or otherwise very simple sample domains, where ExpM reduces
to sampling from a multinomial. Examples of using ExpM for differentially
private ML in the finite setting exist, e.g.: [12] (private decision tree with
only categorical features), [13] (private PCA), and [14] (private feature
selection with only categorical variables). Notwithstanding these examples,
ExpM is historically intractable in most ML applications as the optimization
is of a loss function over continuous parameter space [15, 16, 17, 18].
Secondly, an a priori bound on sensitivity must be proven for the given
utility (equiv., loss) function, which is difficult in general, e.g., see
[17].

To address the first barrier, we leverage an auxiliary Normalizing Flow (NF)
model—a deep learning model—that permits sampling from the otherwise
intractable ExpM density [19]. For the second hurdle, by constraining our
training to $\ell(2)$ (equiv. MSE) loss, we are able to bound sensitivity for
supervised learning tasks with bounded targets (accommodating classification
tasks via binary/one-hot encoding). The combined technique, ExpM+NF (see
Figure 1), promises near optimal parameters and a strong privacy guarantee
($\varepsilon>0,\delta=0$) that is specified in advance by the user. Our
hypothesis is that ExpM+NF attains better accuracy and privacy,
simultaneously, than the current SOTA for differentially private ML.

Differentially private ML is currently achieved almost exclusively by a
single, preeminent technique—Differentially Private Stochastic Gradient
Descent (DPSGD) [20, 21]. DPSGD achieves a privacy guarantee by clipping and
adding Gaussian noise to each gradient during SGD training. The many privacy
guarantees (one per step) are collected into a single, overarching guarantee
via composition theorems [22, 23, 24, 20, 25, 26]. In the conventional
scenario of training ML on a single private dataset, one can see that DPSGD is
wasteful by design—privacy is expended so that all gradients may be
publicized, yet all that is required is the trained model. This leads to the
overall privacy guarantee worsening with each step during training, of which
hundreds to tens of thousands are usually needed. Once the privacy budget is
expended, training must cease, perhaps prematurely. This has led to an
unusable accuracy-privacy tradeoff in practice; e.g., accuracy results of
Resnet-18 (model) on ImageNet (data) fall from 70% without privacy to under
20% with privacy ($\varepsilon=2$) [27], and to quote Suriyakumar et al. [28]
“DP learning algorithms are not well suited for off-the-shelf use in health
care. First, DP models have significantly more severe privacy-utility
tradeoffs in the MIMIC-III [electronic health records] setting, …” Secondly,
by expending privacy at each gradient step, DPSGD can only provide approximate
DP, i.e., $\delta>0$ (see Definition 1), a consequence of relying on
composition theorems and, independently, of using Gaussian noise.

In contrast, our proposed method accommodates a single pre-specified strong
(i.e., not approximate) differential privacy guarantee
($\varepsilon>0,\delta=0$) that is achieved via a sample from the ExpM
distribution. This avoids the step-wise decline in overall privacy as well as
the use of the Gaussian Mechanism, and the application of advanced composition
theorems, which necessitate $\delta>0$ (see Definition 1). By circumventing
these drawbacks we hypothesize, and our results empirically confirm, that
ExpM+NF admits stronger privacy and accuracy than is possible with DPSGD.

We present experiments using the Adult Dataset (US Census data) [29] and
MIMIC-III data [30] (the preeminent electronic healthcare records dataset). We
train a Logistic Regression (LR) model ($\scriptstyle\mathtt{\sim}$100 to 2.5K
parameters) for both and for MIMIC, a modern deep learning recurrent neural
network model called the Gated Recurrent Unit with Decay (GRU-D) [31]
($\scriptstyle\mathtt{\sim}$20K to 100K parameters) to compare ExpM+NF against
the state-of-the-art implementation of DPSGD and their non-private baselines.
Our experiments target high-priority domains for privacy.

Our results show that ExpM+NF achieves similar accuracy with orders of
magnitude better privacy (lower $\varepsilon$ with $\delta=0$) than DPSGD in
every experiment. More specifically, ExpM+NF achieves Area Under the ROC curve
(AUC) of greater than 93% of the non-private baselines for $\varepsilon$ as
small as $1\mathrm{e}{-3}$ in every experiment—three to four orders of
magnitude smaller than is considered in any similar previous work, and
advancing the current standard that $\varepsilon\in[1,10]$ is expected for ML
[21]. This pushes what is possible in differentially private ML as the vast
increase in the privacy budget may be used to address other hardships. For
example, using basic composition one can afford to train hundreds, possibly
thousands of ExpM+NF models, say with $\varepsilon_{i}\approxeq
1\mathrm{e}{-3}$ for hyperparameter tuning and still achieve a strong overall
privacy guarantee, say $\varepsilon\approxeq 1$, today; or, to prevent
anomalous training runs (e.g., bad randomized starting conditions) that can
occasionally happen with a single model, one may release ten ExpM+NF models,
each trained with $\varepsilon/10$ to be used in a voting scheme.

We note that our MIMIC-III non-private models reproduce previous works of Wang
et al. [32], and our DPSGD implementations reproduce previous work of
Suriyakumar et al. [28]. Although not an identical comparison (we cannot fully
replicate these works without identical data and code), our non-private and
DPSGD implementations exhibit greater or comparable accuracy and privacy than
the previous works on these same datasets and learning tasks. By making our
code public, we seek to set a reproducible benchmark for these learning tasks
both in the private and non-private setting.

Limitations and future directions for advancing this promising method are
discussed in Section 5. There are two primary limitations to ExpM+NF in this
work. First, ExpM+NF requires a sensitivity bound for each loss function, and
thus far we have only provided such a proof for $\ell(2)$ (equiv. mean squared
error) loss. While this does not prove limiting in our experiments, future
research is required for application to other loss functions. By comparison,
DPSGD is readily applicable to theoretically any loss function. Secondly,
ExpM+NF requires a completely different training regime (training an auxiliary
NF model whose loss function depends the desired model and its loss function);
hence, custom software engineering is currently required for use on each model
architecture (e.g., on LR, GRU-D, …). DPSGD comes professionally packaged in a
PyTorch plugin, Opacus [1].

###  1.1 Background

Previous works on benchmark datasets and experiments with differentially
private ML that lead to our work are discussed in our Experimental Methodology
Section 3. Throughout, we denote the real numbers as $\mathbb{R}$. We will
denote the universe from which datasets $X,X^{\prime}$ are drawn as $D$ (so
$X,X^{\prime}\in D$) and use $X,X^{\prime}$ to denote neighboring datasets,
meaning they are identical except for at most one data point (one row). The
function $u:\Theta\times D\to\mathbb{R}$ will be a utility or scoring function
we wish to maximize privately over $\Theta$, the space of possible parameters
for $u$. In the setting of machine learning, $\Theta$ is the space of
parameters for the model; and we will use $X,Y$ for the features and targets
in lieu of simply $X$. Given loss function $L(X,Y,\theta)$, the utility is
defined as $u:=\phi\circ L$, with $\phi$ strictly decreasing, and usually
$\phi(t)=-t$. The term “mechanism” simply means random function.

####  1.1.1 Differential Privacy

We begin by introducing when a mechanism is considered differentially private.

######  Definition 1 (Differential Privacy).

A mechanism $f:\Theta\times D\to\mathbb{R}$ satisfies
$(\varepsilon,\delta)$-Differential Privacy or is $(\varepsilon,\delta)$-DP if
and only if

$P(f(\theta,X)\in A)\leq P(f(\theta,X^{\prime})\in A)e^{\varepsilon}+\delta$

for all neighboring $X,X^{\prime}\in D,\theta\in\Theta,\varepsilon\geq 0$ and
for all measurable sets $A$. When $\delta=0$, we say $f$ is $\varepsilon$-DP.

The $\varepsilon$ term is an upper bound on the privacy loss. Intuitively,
differential privacy measures how much an individual data point changes the
output distribution of the mechanism $f$. If the mechanism’s output is nearly
identical in both cases (when any data point is or isn’t included), meaning
that $\varepsilon$ is very small, then this is a privacy guarantee for any
individual data point. This quantifies the intuitive notion that it is
essentially indistinguishable if any one data point is included or not.

Approximate DP, or $(\varepsilon,\delta)$-DP, provides a relaxed
definition—$\delta$ is the probability that the mechanism $f$ is not
guaranteed to be $\varepsilon$-DP. This “probability of failure”
interpretation has let many to suggest that $\delta$ should be no larger that
$1/N$ where $N$ is the number of data points in the dataset [33].

Differential privacy has many useful properties. First, post-processing is
“free”, meaning if $f(\theta,X)$ is $(\varepsilon,\delta)$-DP, the same
guarantee holds after composition with any function $h$; i.e., $h\circ f$ is
also $(\varepsilon,\delta)$-DP [33]. Secondly, it satisfies composition
theorems; the most basic of which says that if $f_{1}$ and $f_{2}$ satisfy
$(\varepsilon_{1},\delta_{1})$-DP and $(\varepsilon_{2},\delta_{2})$-DP,
respectively, then $f_{1}\circ f_{2}$ satisfies
$(\varepsilon_{1}+\varepsilon_{2},\delta_{1}+\delta_{2})$-DP [33]. The general
problem of estimating the overall privacy bound (a single
$\varepsilon,\delta)$) for a sequence of mechanisms
$f_{i}(\theta_{i},X),i=1,...,m$ each furnished with a privacy guarantee
$(\varepsilon_{i},\delta_{i})$-DP, is important for use. As the basic
composition theorem above holds, it is not a tight bound (better estimates may
exist), and hence, a large body of work [22, 23, 24, 20, 25, 26] provide
advanced composition theorems (tradeoffs of $\varepsilon$ and $\delta$ that
depend on the $\varepsilon_{i},\delta_{i}$) that estimate this overall bound.
Intuitively, as more information is released (as $m$ grows), the overall
privacy guarantee gets worse ($\varepsilon$ and $\delta$ increase), and all
advanced composition theorems entail an increase of $\delta$ for the better
estimate of $\varepsilon$.

To achieve differential privacy in practice, randomness is leveraged.
Determining how much randomness to inject requires understanding how sensitive
the output of the mechanism is to different datasets.

######  Definition 2 (Sensitivity).

The sensitivity of a mechanism $f:\Theta\times D\to\mathbb{R}$ is
$\max|f(\theta,X)-f(\theta,X^{\prime})|$ where the max is over neighboring
$X,X^{\prime}\in D,\theta\in\Theta$. We use $s$ to denote an upper bound on
sensitivity.

Once the sensitivity is determined, there are several DP mechanisms that have
been shown to satisfy differential privacy. In this work, we utilize the
exponential mechanism.

######  Definition 3 (Exponential Mechanism).

For data $X\in D$ and a utility function $u:\Theta\times D\to\mathbb{R}$ with
sensitivity $s$, the Exponential Mechanism (ExpM) returns $\theta\in\Theta$
with likelihood $p_{ExpM}(\theta;X)\propto\exp(\varepsilon u(\theta,X)/(2s))$.

A needed theorem shows ExpM satisfies differential privacy.

######  Theorem 1 ([11, 33]).

The Exponential Mechanism (ExpM) i.e., sampling $\theta\sim
p_{ExpM}(\theta,X)\propto\exp(\varepsilon u(\theta,X)/(2s))$ where utility
function $u$ has sensitivity $s$, provides $\varepsilon$-DP.

The original treatment of ExpM [11] furnishes utility theorems—rigorous
guarantees that bound how far ExpM samples can be from the optima.

####  1.1.2 Differentially Private Machine Learning

Differentially Private Stochastic Gradient Descent (DPSGD) is the predominant
method for achieving differential privacy in machine learning models [21].
Algorithm 1 in [20] describes how the gradient for each data point (not batch)
is clipped and Gaussian noise is added according a predefined noise scale.
Clipping the gradient is necessary to ensure a bound on the sensitivity of the
learning algorithm. The original DPSGD work also introduces the Moments
Accountant as a method for approximating the privacy bound $\varepsilon$ given
some $\delta$. The Moments Accountant relies on advanced composition theorems
and noticing that the privacy bound is improved due to training in batches
(i.e., subsampling the data) to tighten the upper bound on the privacy budget
$\varepsilon$.

Following their work, there have been several privacy accounting methods
proposed for DPSGD. One worth highlighting is the RDP Accounting method that
computes the Renyi-DP, a relaxed definition of $(\varepsilon,\delta)$-DP from
which an $(\varepsilon,\delta)$-DP bound can be computed. The RDP Accountant
produces a tighter bound on the privacy budget than the Moments Accountant.

Gopi et al. in [26] later noted that for each iteration of training, there is
a privacy curve $\delta_{i}$ over $\varepsilon$ and that it is non-trivial to
determine how to compose these to produce a single privacy curve for the
entire training procedure. Based on prior work, they propose the PRV
Accountant method that utilizes the privacy random variable (PRV) and Fast
Fourier Transform to compose the privacy curves to arbitrary accuracy. This
method introduces an error term for both $\varepsilon$ and $\delta$. They also
show that the RDP Accounting method significantly overestimates the true value
of $\varepsilon$. It’s worthwhile to note that since the PRV Accounting method
was only recently developed, the prior state-of-the-art results on MIMIC III
used DPSDG with the RDP accounting method.

We note that objective perturbation, whereby one adds noise to the objective
(loss) function, has been proposed for differentially private ML [16, 34], yet
previous works on which we build, namely Suriyakumar et al. [28], report DPSGD
is superior to objective perturbation. For a survey of differentially private
ML, see Ji et al. [16] and Ponomareva et al. [21]

####  1.1.3 Normalizing Flows

We reference readers to the survey of Normalizing Flow (NF) research by
Papamakarios et al. [19]. An NF model is a neural network,
$g=g_{k}\circ...\circ g_{1}:\mathbb{R}_{z}^{n}\to\mathbb{R}_{\theta}^{n}$,
with each layer $g_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n}$, called a flow, that
is invertible and differentiable. We let $\theta_{NF}$ denote the parameters
of $g$ to be learned, and suppress this notation for simplicity unless needed.
Notably, $g$ (and by symmetry, $g^{-1}$) preserves probability densities: if
$p_{z}$ is a probability density, then $\theta\mapsto
p_{z}(g^{-1}(\theta))|\det J_{g^{-1}}(\theta)|$ is also, which is proven by
the change of variables induced by $\theta=g(z)$.

Let $p^{*}_{\theta}$ be an intractable target density over $\mathbb{R}^{n}$
(meaning $p^{*}_{\theta}$ can be computed up to a constant factor, but we
cannot sample from $p^{*}_{\theta}$), in our case $p^{*}=p_{ExpM}$. Let
$p_{z}$ be a tractable density also over $\mathbb{R}^{n}$, especially, $p_{z}$
is Gaussian. Then $g$ can be trained to transform $p_{z}$ into $p_{\theta}$ so
that $p_{\theta}\thickapprox p^{*}_{\theta}$ as follows: iteratively sample a
batch $z_{i}\sim p_{z},i=1,...,N$ and minimize the empirical KL divergence of
the base density $p_{z}$ with the pull-back of the target density, namely
$p^{*}_{\theta}(g(z))|\det J_{g}(z)|$; that is, minimize “Reverse KL” (RKL)
loss,

$\displaystyle KL($ $\displaystyle p_{z}(z),p^{*}_{\theta}(g(z))|\det
J_{g}(z)|)\approxeq$ (1)
$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\log\frac{p_{z}(z_{i})}{p^{*}_{\theta}(g(z_{i}))|\det
J_{g}(z_{i})|}\ .$

Once trained, $\theta=g(z)$ with $z\sim p_{z}$ gives approximate samples from
previously intractable $p_{\theta}$!

What is needed to compute this loss function is efficient computation of,
first, the target density $p^{*}_{\theta}(\theta)$, and second, the log
determinant Jacobian term $\log|\det J_{g}|$. Generally, NFs are designed to
make computing this log determinant computationally feasible (e.g., using
flows $g_{i}$ so that $J_{g}$ is triangular or that satisfy Therorem 2) while
balancing the expressiveness.

In this work, we leverage the Planar Flows of Rezende & Mohamed [35] and their
more expressive generalization, Sylvester Flows [36]. Let
$z\in\mathbb{R}^{d},\ A(d\times m),\ B(m\times d),\ c\in\mathbb{R}^{m}$, and
$h:\mathbb{R}\to\mathbb{R}$ an activation function that we ambiguously apply
to vectors componentwise ($h(\vec{v})=[h(v_{1}),...,h(v_{d})]^{t}$).

######  Definition 4 (Sylvester Flow).

A Sylvester flow is defined as $g(z)=z+Ah(Bz+c)$, and note that
$J_{g}(z)=I_{d}+A_{d\times m}\text{diag}(h^{\prime}(Bz+c))_{m\times
m}B_{m\times d}.$

######  Theorem 2 (Sylvester a.k.a. Weinstein–Aronszajn Theorem).

$\det(I_{d}+A_{d\times m}B_{m\times d})=\det(I_{m}+B_{m\times d}A_{d\times
m})$.

It follows that when $m<d$, we can compute the determinant, $J_{g}(z)$ in the
lower dimensional representation!

######  Definition 5 (Planar Flow).

A planar flow is a special case of a Sylvester flow when $m=1$, so
$A,B\in\mathbb{R}^{d}$.

Following Berg et al. [36], a Sylvester Flow can be implemented by using the
special case where $A=Q_{d\times d}R_{d\times m}$ and $B=\hat{R}_{m\times
d}Q^{t}_{d\times d}$ with $Q$ orthogonal and $R,\hat{R}$ upper triangular.
(This is a restriction in that it uses the same $Q$ for both $A$, $B$). To
instantiate an orthogonal matrix $Q$, we define unit vectors $v$ and set
$Q:=\prod_{v}I-2vv^{t}$ which is a product of Householder reflections. A well
know fact is that Householder reflections are orthogonal, and any orthogonal
matrix is as a product of Householder reflections [37]. Note this is obviated
in the Planar Flow case since $A,B$ are simply $d$–dimensional vectors.

##  2 ExpM+NF Method

Figure 1 depicts the setting that we will consider: a private data enclave
that wishes to permit optimization on their data; in particular, training and
publicly releasing an ML algorithm on that data. Fitting an ML model on
training features and targets $(X,Y)$ constitutes finding parameters $\theta$
that minimizes a loss function $L(X,Y,\theta)$, and ExpM requires specifying a
utility function $u(X,Y,\theta)$ to be maximized in $\theta$. Therefore, we
will set $u=\phi\circ L$ for strictly decreasing $\phi$. Throughout our
experiments we use $u=-L$, but provide insights into choosing $\phi$ in
Section 2.1.

The approximately optimal parameters $\theta$ are found by sampling

$\theta\sim p_{ExpM}(\theta)\propto\exp[u(X,Y,\theta)\varepsilon/2s]$

furnishing an $\varepsilon$-DP guarantee. Importantly, the privacy parameter
$\varepsilon$ is pre-specified. To define the density, we must identify the
sensitivity bound $s$ (Defn. 2). When $s$ is large, it diminishes the
influence of $u$, and reduces accuracy by increasing the variance of the
sampled $\theta$.

For application of our method we must first find an ideally tight bound $s$ on
the sensitivity of the utility function $u$. Since $u,s$ are intimately tied
to the loss function $L,$ this up-front task is generally required per loss
function and can depend on the model outputs. In this initial work, we
consider $\ell(2)$ loss functions ($\sum_{X,Y}(\hat{y}(x)-y)^{2}$) on
classification tasks with model outputs and targets bounded by 1 giving $s=1$;
for more details see Section 2.2.

The last step is to sample $\theta\sim p_{ExpM}(\theta).$ This step replaces
an SGD scheme but fills the same role—it produces approximately optimal
parameters for the ML model. Unfortunately, $p_{ExpM}$ is a historically
intractable density for non-finite domains, so sampling directly is infeasible
in most supervised learning applications. Our new approach trains an auxiliary
NF model (see Section 1.1.3) to transform a Gaussian base density $p_{z}$ into
our target density $p^{*}_{\theta}:=p_{ExpM}$. As we discussed when
introducing NFs (Section 1.1.3), the Reverse KL loss function, given by
Equation 1, only requires computing the determinant Jacobian term (made
tractable by the design of the NF) and $\log p_{ExpM}$ up to any positive
constant, which is simply $u\varepsilon/2s$, essentially computing our loss
function. In short, the NF training is computationally well suited for
approximating the ExpM density. In this work, the NF models will utilize
Planar and Sylvester Flows, introduced in Section 1.1.3. Finally, once a
sample is produced from the trained NF, it can be released with the
$\varepsilon$-DP guarantee, allowing use of the trained model.

Algorithm 1 outlines the basic method for producing a differentially private
ML model with ExpM+NF, which entails training an auxiliary NF model to allow
for approximate sampling from the ExpM and will give the ML model parameters
with an $\varepsilon$-DP guarantee. Variants of this general setup may be
pursued in use.

Algorithm 1 Differentially Private ML with Exp+NF

Input: Training set $(X,Y)$, a base distribution $p_{z}$, a loss function $L$,
decreasing $\phi$, privacy budget $\varepsilon$, sensitivity bound $s$.

Initialize $\theta_{\text{NF},0}$ randomly

for $t$ in $[T]$ do $\triangleright$ Train Auxilary NF Model

Generate $N$ samples from base distribution

for each $i\in[N]$, $z_{i}\sim p_{z}$

Produce $N$ parameter samples & Jacobian

for each $i\in[N]$,

$\theta_{i}=g_{\theta_{\text{NF},t}}(z_{i})$

$\log\ |\det J_{g}(z_{i})|$ (depends on NF)

Compute utility for each parameter sample

for each $i\in[N]$, $u(X,Y,\theta_{i})=\phi\circ L(X,Y,\theta_{i})$

Evaluate log of target probability of samples

$\log\
p^{*}_{\theta}(\\{\theta_{i}\\})=\tfrac{\varepsilon}{2s}\sum\limits_{i=1}^{N}u(X,Y,\theta_{i})$

Compute Reverse KL Loss using Eq. 1

$\mathcal{L}=KL[p_{z}(z_{i}),p_{\theta}^{*}(\theta_{i})|\det J_{g}(z_{i})|]$

Update NF Model

$\theta_{\text{NF},t+1}=\theta_{\text{NF},t}-\eta_{t}\nabla_{\theta_{\text{NF},t}}\mathcal{L}$

end for

sample from base distribution, $z\sim p_{z}$

Output ML model parameters, $\theta=g_{\theta_{\text{NF},T}}(z)$ and
$\varepsilon$ privacy guarantee

###  2.1 Choosing $u=\phi\circ L$

While any strictly decreasing $\phi$ theoretically ensures identical
optimization, in practice $\phi$ must separate the near-optimal $\theta$ from
those that are far from optimal. This means the derivative must be a
sufficiently large negative value over an appropriate range of $L(\theta)$ to
discriminate high versus low utility $\theta$. In particular, using a negative
sigmoid function, which is flat ($\phi^{\prime}\approxeq 0$) except in a
limited neighborhood, is unwise, unless we know which range of $L(\theta)$
will contain the optimal values a priori and shift $\phi$ to discriminate
these values. Lastly, we note that choice of $\phi$ effects the sensitivity,
and therefore may be designed to assist in producing the required sensitivity
bound.

###  2.2 Bounding Sensitivity

Define the utility to be the negative loss so

$u=-L=\sum_{(x,y)\in(X,Y)}l(x,y,\theta)+r(\theta)$

where $l(x,y,\theta)$ is the loss from data point $(x,y)$, and $r(\theta)$ is
a regularization function. For two neighboring datasets
$(X,Y),(X^{\prime},Y^{\prime})$, let $(x,y)\in(X,Y)$ and
$(x^{\prime},y^{\prime})\in(X^{\prime},Y^{\prime})$ denote the lone row of
values that are not equal. We obtain
$|u(X,Y,\theta)-u(X^{\prime},Y^{\prime},\theta)|=|l(x,y,\theta)-l(x^{\prime},y^{\prime},\theta)|$;
hence, bounding $s$ is achieved by Lipschitz or $\ell(\infty)$ conditions on
the per-data-point loss function $l$. Notably, regularization $r$ does not
affect sensitivity.

######  Theorem 3 (Sensitivity bound for $\ell(2)$ loss).

Suppose our targets and model outputs reside in $[0,1]$. If
$u=-L=-\sum_{(x,y)}(\hat{y}(x,\theta)-y)^{2}$, then $s\leq 1$. In particular,
$s\leq 1$ for classification tasks using binary/one-hot encoded targets and
logistic/soft-max outputs with $\ell(2)$ loss and $u=-L.$

###### Proof.

Since $\hat{y}(x,\theta),y\in[0,1]$ we see $(\hat{y}(x,\theta)-y)^{2}\in[0,1]$
and $(\hat{y}(x,\theta)-y^{\prime})^{2}\in[0,1]$ so
$|(\hat{y}(x,\theta)-y)^{2}-(\hat{y}(x^{\prime},\theta)-y^{\prime})^{2}|<1$. ∎

###  2.3 Contrasting ExpM+NF with DPSGD

Training a model with DPSDG is quite similar to non-private training but has a
few key differences. First, data is placed into batches for training according
to a defined sampling ratio so the actual batch size will vary during
training. Second, per example gradients must be clipped to have norm below
some value $C$ (the max_grad_norm variable). Finally, Gaussian noise with
variance $\sigma C$, where $\sigma$ is the specified noise scale, is added to
each gradient.

Once DPSGD has finished training, the resulting model comes with an
$(\varepsilon,\delta)$-DP guarantee that must be computed using an accounting
method (see Section 1.1). The weaker notion of differential privacy arises due
to DPSGD’s reliance on the Gaussian mechanism [20, 26] and the composition
theorems that the accountant uses to bound the privacy budget of the entire
training process. Because DPSGD clips the pre-example gradients, the
sensitivity of the training procedure is bounded. The privacy bound
$\varepsilon$ for DPSGD relies on the noise scale, the sampling ratio, the
number of training steps and $\delta$. We may choose a privacy budget prior to
training by fixing all but one of these parameters and using them to solve for
the unfixed parameter.

ExpM+NF, on the other hand, requires an entirely new training regime as we
must training an auxilary NF model to produce optimal parameters. As Algorithm
1 shows, this requires sampling $N$ samples from the base distribution,
pushing these samples through the normalizing flow model, computing the log
determinant of the Jacobian and computing $L(X,Y,\theta_{i})$ for each of the
parameter samples $\theta_{i}$.

Once the training of the NF model is complete, the desired private ML model
parameters are produced by pushing a single sample from the base distribution
through the NF model. These parameters come with the prespecified
$\varepsilon$-DP guarantee. This method completely avoids the use of
composition theorems for producing the privacy bounds and does not require the
weaker notion of differential privacy as $\delta=0$. It does, however, require
a sensitivity bound on the utility function, which for some utility functions
may be non-trivial to prove.

Computationally, both DPSGD and ExpM+NF incur overhead when compared to non-
private training and the computational requirements depend greatly on the
architecture of the models and hyperparameter choices for each. During
training, most of DPSGD’s inefficiency is due to clipping each gradient,
although some additional computation is needed for sampling and adding
Guassian noise to each gradient. ExpM+NF requires training an auxiliary NF
model where most of the inefficiency comes from needing to compute
$L(X,Y,\theta_{i})$ for each of the sampled parameters, $\theta_{i}$.
Discovering implementations that efficiently train the NF $g$ and ensure
gradients are tracked throughout the process was much of the research for this
work, and we will provide code for these experiments upon acceptance. DPSGD
also requires computing the privacy budget and different accounting methods
have different computational overhead. The PRV Accountant method [26] requires
an upper bound on the privacy budget which is usually found by using the RDP
accountant. For Exp+NF the privacy budget is pre-specified and thus does not
require computing. We present timing results comparing ExpM+NF, DPSGD, and
non-private training in Section 4.3.

TABLE I: Information on data, prediction tasks, and models used for experiments tabularized. LR denotes logistic regression. Dataset | Prediction Task (class bias) | Models ($n_{\text{parameters}}$) | $n_{\text{rows}}$ | $n_{\text{features}}$
---|---|---|---|---
Adult [38] | Income, Binary (24.8%/75.2%) | LR (103 parameters) | 45,222 | 102
MIMIC-III [30, 32] | ICU Mortality, Binary (07.4%/92.6%) | LR (2497 parameters), GRU-D (20K-100K parameters) | 21,877 | 2,496
MIMIC-III [30, 32] | ICU Length of Stay, Binary (47.1%/52.9%) | LR (2497 parameters), GRU-D (20K-100K parameters) | 21,877 | 2,496

##  3 Experiments & Methodology

For all datasets, tasks, and models, we implement a non-private baseline,
DPSGD and ExpM+NF trained private versions. For the non-private and DPSGD
models, we provide results for both binary cross entropy loss (BCE) and
$\ell(2)$ loss, as both are common for binary classification. For privacy
methods, we vary $\varepsilon$ to see the accuracy-privacy tradeoff.
Differentially private ML research generally considers $\varepsilon\in[1,10]$
[21], hence we present plots of $0.5\leq\epsilon\leq 10$, and, investigate
results for $\varepsilon$ as low as $1\mathrm{e}{-4}$. All experiments are
coded in PyTorch.

For DPSGD the usual hyperparameters (epochs, batch size, momentum, learning
rate, and regularization parameter) function as usual. We use the PRV method
of accounting via Opacus with clipping parameter, max_grad_norm = 1 [39, 40],
$\delta=1\mathrm{e}{-5}$, roughly the inverse of the number of training data
points, as are standard, and delta_error set to $\delta/1000$ (default). We
compute the noise_multiplier parameter, which governs the variance of the
Gaussian noise added to each gradient, to achieve the target privacy
$(\varepsilon,\delta)$ based on the number of gradient steps (epochs and
batch_size parameters) and the gradient clipping parameter max_grad_norm. As
mentioned in the background section, the PRV Accounting method introduces an
error term for $\varepsilon$ that bounds the error in the estimate of the
privacy guarantee. Notably, eps_error =.01 is the default fidelity, and
computations become too expensive or intractable for eps_error <.0001. Hence,
given target epsilon $\bar{\varepsilon}$, we set eps_error to be as close as
possible to $\bar{\varepsilon}/100$ within the range $[.0001,.01]$.

Our NF models always use a Gaussian base distribution with
$N(\vec{0},\text{diag}(\sigma^{2}))$, and we treat the constant $\sigma^{2}$
appearing on the diagonal of the covariance matrix as a hyperparameter. The
number of flows and parameters of the Sylvester model (Section 1.1.3) are also
hyperparameters. Lastly, our method has hyperparmeters for training that
include: epochs, NF batch size (how many model parameters to sample from the
NF for each KL loss computation), data batch size (number of training data
points used in each KL loss computation), learning rate, momentum, and
regularization parameter.

Data is split into a train/dev/test split that is stratified, preserving class
bias in each partition. For each $\varepsilon$, we performed a randomized grid
search of hyperparemeters fitting on the train set and testing on the dev set.
The hyperparmeters were refined usually twice for a total of about 60-90
hyperparmeter train/dev runs; this same procedure is used for all training
methods (ExpM+NF, DPSGD, non-private). Only those hyperparameters producing
the best results on the dev set are used in final results–fitting on training
plus dev partitions and validating on the never-before-used test set. While in
practice, hyperparameter searching will entail a loss of privacy, we ignore
accounting for this as our goal is to compare the best achievable accuracy and
privacy of ExpM+NF, DPSGD, relative to the nonprivate baseline.

While batch normalization is commonplace in non-private deep learning, it is
not directly portable to the private setting as $z$-normalization learned in
training must be shipped with the model [40]; hence, we do not use batch
normalization for our private models, but we do provide results with vs.
without batch normalization where applicable, namely for the non-private GRU-D
model, Table IV. Details of the hyperparmeters used for each model can be
found in our code base and vary per experiment and privacy level
$\varepsilon$.

In all binary classification tasks we use AUC as our accuracy metric. Starting
conditions can lead to anomalously good/bad models for all methods (non-
private, DPSGD, ExpM+NF). We present the median across ten models, each with
different random seeds, to provide robustness to outliers. More specifically,
for both DPSGD and non-private training with BCE and $\ell(2)$ loss, once
hyperparameter searching is complete, we train ten non-private baseline
models, each with a different random seed, and present the median AUC. The
highest non-private median across the two loss functions is the considered the
baseline for each dataset, task and appears as a dotted line in result plots.
For ExpM+NF we train ten NFs using the best hyperparameters and produce 1,000
sampled parameter sets from each NF, for a total of 10,000 parameter sets. We
instantiate the 10,000 resulting models, compute their AUC results, and
compare the median to DPSGD and the non-private baseline. One may prefer to
compute the median of the 1,000 AUCs per NF model (producing 10 median AUCs),
and report the median of these medians. We have empirically verified that the
results are nearly identical in our experiments.

While we cannot visualize the NF’s output distribution, we can investigate the
distribution of AUCs attained by ExpM+NF models for each $\varepsilon$
parameters. We present box plots in which indicate the distribution’s median
(middle line), first (Q1) and third (Q3) quartiles (box), and extend 1.5 times
the inner quartile range (Q1 - 1.5 IQR, Q3+ 1.5 IQR, whiskers). To see
anomalous models arising from fortunate/unfortunate starting positions
(different random seeds), we overlay each of the ten model’s means.

###  3.1 Adult Dataset Experimental Design

The Adult Dataset [38] is a subset of 1994 census data. We drop rows that have
missing values leaving 45,222 rows. The target column is binary, indicating
whether the adjusted gross income is above/less or equal to $50K. The class
bias is approximately 24.8%/75.2%. Column fnlwgt gives the weight of each row
(this is not a feature as it provides the proportion of the population that
has the same set of features), and gives a multiple in our loss function. Six
columns are numeric columns (age, capital_loss, captial_gain, education_num,
hours_per_week, fnlwgt); two are binary (sex and the target); and the
remaining eight columns are categorical with more than two values. We have
converted all binary categorical columns to numerical binary values
$\\{0,1\\}$, and categorical columns with more than two values into one-hot
encoding. After this preparation, we have 104 columns (102 features, 1 weights
column, 1 target).

For this prediction task, we test LR with a bias term, which entails 103
parameters to be learned with privacy. We used RMSProp optimizer for all
models (non-private logistic regression, DPSGD PRV, and NF) with this dataset,
task. Our train/dev/test ratio is 64%/16%/20%.

###  3.2 MIMIC III Dataset Experimental Design

MIMIC-III [30] is a large, open, electronic health record (EHR) database
covering a diverse group of critical care patients at a medical center from
2001–2012. Our experimental design follows a progression of research on MIMIC-
III. Wang et al. [32] create benchmarks of needed healthcare predictive tasks
from the MIMIC-III dataset, downloadable (from MIMIC-III v1.4, as
all_hourly_data.h5) with the codebase [41]. We use the binary prediction task
benchmarks ICU Mortality and ICU Length of Stay ($>$ 3 days) from Wang et
al.’s pipeline. These tasks differ only in target and share the feature set
consisting of 104 measurement means per hour over a 24 hour period for 21,877
patients. Mortality is extremely imbalanced (07.4%/92.6%), while Length of
Stay is balanced (47.1%/52.9%). We employ standardization ($z-$score
normalization) for each feature, and it is applied independently per
train/dev/test partition to prevent privacy issues.

As an example use of the ICU Mortality and Length of Stay benchmarks, Wang et
al. also present results of non-private LR and GRU-D [31] models. Che et al.
[31] introduce the Gated Recurrent Unit with Decay (GRU-D) model, a deep
neural network for time series learning tasks. GRU-D interpolates between the
last seen value and the global mean so censored (missing) data does not need
to be imputed in advance. Additionally, the hidden units of the GRU are
decayed to zero with learned decay per component, which allows features that
should have short influence (e.g., heart rate) vs. long influence (e.g.,
dosage/treatment) to have learned rate of diminishing value. Wang et al.
provide non-private results for LR and GRU-D models on these two tasks as well
as implementations.

Suriyakumar et al. [28] replicate Wang et al.’s results on these two tasks for
non-private baselines, then provide DPSGD (with RDP accountant) results as
well. To the best of our knowledge, Suriyakumar et al. [28] present the state
of the art in differentially private ML on these MIMIC-III benchmarks.
Unfortunately, their code is not provided.

Using the currently available data (MIMIC-III v1.4, as all_hourly_data.h5),
and following preprocessing code and descriptions of Wang et al. we replicate
these benchmarks as closely as possible. Further, we implement the LR and
GRU-D models with non-private and DPSGD with PRV accounting training as to
compare against ExpM+NF. PRV accounting [26] provides a better privacy bound
than RDP, and we present comparative results across the two accounting
methods. There are discrepancies between our dataset and Suriyakumar et al.’s
description of the data, possibly because MIMIC-III was updated. The current
MIMIC-III ICU Mortality and Length of Stay benchmarks have 89.1% missingness
rate and 104 features per hour $\times$ 24 hours giving 2,496 columns.
Suriyakumar et al. claim to have 78% missingness and only 78 features per
hour, but they report the number of columns is reported as “24,69”, seemingly
a typo (if the correct is 2,496, would entail 104 feature per hour). The
number of rows matches exactly. The LR models entails privately learning these
2,497 parameters. Like our Adult Dataset Experiment, we use RMSProp optimizer
with a scheduler that reduces the learning rate for all LR models.

For GRU-D, we follow Suriyakurmar et al. [28] and when needed the original
GRU-D work of Che et al. [31]. Suriyakumar et al. [28] used batch
normalization (BN) even when training privately with DPSGD, but this has since
been revealed as a source of privacy leakage [40]. Hence, we do not use BN
with our DPSDG implementations, but we do train a non-private model both with
and without BN applied to the top regressor layer. We apply a dropout layer to
the top regressor layer, treating the dropout probability as a hyperparameter.
Unlike [28], we treat the hidden size as a hyperparameter for all experiments.
The main motivation for this choice was that memory constraints on the GPU
hardware used to perform ExpM+NF required that we used a hidden size no larger
than 10. For the non-private and DPSGD implementations, we allow the hidden
size to vary between 10 and 100 for our randomized grid search, so this
constraint was only limiting for our new method. For training non-privately
and with DPSGD, we use the Adam optimization method and for the NF model we
use RMSProp with a scheduler. This is our the best possible replication of
Wang et al. and Suriyakurmar et al.’s experiments save the choice to omit
batch normalization.

Notably, Che et al [31] also provide non-private GRU-D results on MIMIC-III
data for an ICU Mortality prediction task. Since Che et al. do not follow the
preprocessing of Wang et al. and specifically claim to use 48 hours of data
(while we, Wang, Suriyakurmar use 24 hours), we do not consider their results
comparable.

##  4 Experimental Results

We discuss results by experiment in the subsections below. In addition to the
accuracy vs. privacy results per experiment, we include results on our NF
model distributions, and DPSGD accounting methods.

Figure 2: Adult Dataset Results - plots compare ExpM+NF, DPSGD, and nonprivate
baseline models’ median AUC results across ten models per $\varepsilon$. Left
plot shows results for $\varepsilon\in[1\mathrm{e}-4,1]$ (extremely strong to
strong privacy) and right plot for $\varepsilon\in[1,10]$ (strong to weak
privacy). ExpM+NF achieves greater accuracy than DPGSD for all $\varepsilon$
and achieves greater than $93\%$ of the non-private training for
$\varepsilon\geq 5\mathrm{e}-4.$ Figure 3: Adult dataset results, for each
$\varepsilon$ value, ten NF models are trained and used to produce 1,000
samples each from the ExpM distribution. We present box plots of the 10,000
resulting classifiers’ AUC values. For each NF model’s 1,000 samples we
compute the mean AUC, which are overlayed as dots.

###  4.1 Adult Dataset Results

Our hyperparameter search found that DPSGD needs very few epochs (usually
under 25) and relatively small batch sizes. Given the small number of epochs
no scheduler was used with DPSGD. For NF training and the nonprivate model, a
scheduler was used with patience = 1000. We found that only 2-7 planar flows
(see Section 5), on the order of 1,000 parameters, provided the best results.

Our nonprivate logistic model achieved similar results for both BCE and
$\ell(2)$ loss, namely 91.82% and 91.93%, respectively. Figure 2 compares
DPSGD, ExpM+NF, and the nonprivate baseline’s median AUC across the ten models
trained for each method and privacy parameter. DPSGD results show only
slightly better results for BCE vs. $\ell(2)$ loss. Both experience a steady
drop from about $98\%$ of the non-private AUC at $\varepsilon=1$ to
essentially random guessing at $\varepsilon=2.5\mathrm{e}{-4}.$

Our results show that ExpM+NF provides greater privacy and accuracy than DPSGD
across the board, and ExpM+NF achieves greater than 98% of the non-private AUC
for $\varepsilon\geq 2.5\mathrm{e}{-2}$ and greater than 93% of the non-
private AUC for $\varepsilon\geq 5\mathrm{e}{-4}.$ ExpM+NF admits results for
$\varepsilon$ as low as $1\mathrm{e}{-6}$, the lowest we attempted, although
results become essentially random for $\varepsilon=1\mathrm{e}{-5}$ or less on
this dataset, task. ExpM+NF median AUC for $\varepsilon=1\mathrm{e}{-1}$ and
$1\mathrm{e}{-2}$ are anomalously low compared to results for neighboring
$\varepsilon$ values. Figure 3 visualizes the AUC distribution per
$\varepsilon$ using box plots with the ten NFs’ means overlaid. We can see in
Figure 3 that $\varepsilon=1\mathrm{e}{-1}$ had two NF models whose mean was
far lower than the others (two dots much lower than median), and
$\varepsilon=1\mathrm{e}{-2}$ experienced three such outlier NFs. All ten NFs
for each $\varepsilon$ had identical hyperparmeters, with the lone difference
being the random seed. This leads us to believe that starting conditions can
have a large effect on ExpM+NF’s accuracy, and the randomness in the ten NF
starts are seen in the results.

###  4.2 MIMIC III Results

Our work shows substantial improvement for differentially private ML on the
previous works’ health care prediction tasks [32, 28]. By using the PRV
Accounting method, we achieve state-of-the-art for DPSGD with both LR and
GRU-D models on both ICU Mortality and Length of Stay tasks. Further still, by
using ExpM+NF we are able to outperform these new state-of-the-art DPSGD
results. Table II displays experimental results for the ICU Mortality and
Length of Stay task experiments with both LR and GRU-D.

In these experiments, ExpM+NF again exhibits greater than 93% of the non-
private models’ AUC for all $\varepsilon\geq 1\mathrm{e}-3$. ExpM+NF surpasses
DPSGD in all experiments except $\varepsilon\geq 2$ with LR model on the
Length of Stay task, in which all privacy methods achieve 99% of the non-
private model. Viewed through another lens, ExpM+NF maintains a greater AUC
for $\varepsilon\geq 1\mathrm{e}-3$ than DPSGD for
$\varepsilon=1,\delta=1\mathrm{e}-5$ in all MIMIC-III experiments,
respectively. For both prediction tasks, the AUCs achieved by ExpM+NF of the
GRU-D model are, for all $\varepsilon\geq 1\mathrm{e}-3$, better than the non-
private LR or GRU-D models’ results reported by Suriyakumar [28]. These
results shows that for both the simple LR model and the deep learning model
GRU-D, Exp+NF substantially pushes the privacy-accuracy curve.

Our results show no significant difference in non-private or DPSGD trained
models when using BCE vs. $\ell(2)$ loss. We found substantial limitations to
the DPSGD RPD accountant compared to the SOTA accounting method, PRV. Our
results show GRU-D, a much more expressive model than LR, does indeed surpass
LR in AUC for non-private and each private training method in all experiments,
respectively. This trend is seen in Che et al.[31] and Wang et al. [32], but
results are the inverse (LR is more accurate) in results of Suriyakumar et al.
[28].

We provide benchmark timing results for all three training methods. Our
findings are that all private training methods are slower than non-private
(expected), and that when including the time to compute the noise_multiplier,
DPSGD is slower than ExpM+NF for both LR and GRU-D training.

Our variance of the NFs’ AUC distributions was less than in the Adult Data
experiment. We include figures and discussion in the Appendix 5.1.

TABLE II: Median AUC results on MIMIC-III Mortality and Length of Stay prediction experiments aaaaa Mortality, Logistic Regression |  |
---|---|---
aaaaaaaaaaa Mortality, GRU-D |  |
aaaa Length of Stay, Logistic Regression |  |
aaaaaaaaaa Length of Stay, GRU-D |  |
TABLE III: AUC scores for non-private LR model results for this and prior works on MIMIC-III tasks. Bold results are best per task. _Underlined_ are the best result in this work.  | [32] | [28] |  $\ell(2)$ loss | BCE loss
---|---|---|---|---
ICU Mortality | .887 | .82 | _.839_ | .83
Length of Stay | .716 | .69 | .675 | _.681_

####  4.2.1 Logistic Regression Results

Non-private LR results for both MIMIC-III prediction tasks reside in Table
III. Wang et al.’s LR used SciKit Learn while we use PyTorch.

To the best of our knowledge, the state-of-the-art for a differentially
private LR model on MIMIC-III is given in [28]. They report LR model AUC for
“low privacy” ($\varepsilon=3.5\mathrm{e}5$, $\delta=1\mathrm{e}{-5}$) and
“high privacy” ($\varepsilon=3.5$, $\delta=1\mathrm{e}{-5}$) on both ICU
Mortality and Length of Stay tasks. Privacy of $\varepsilon>10$ is widely
considered ineffective [21]; hence, the “low privacy”
$\varepsilon=3.5\mathrm{e}5$ is practically unreasonable but perhaps useful
for investigating sensitivity of this parameter. Our replication of the same
experiment produced LR models trained with DPSGD that greatly improve on this
prior state-of-the-art. On ICU Mortality, Suriyakumar et al. [28] report 60%
AUC for $(3.5,1\mathrm{e}{-5})$-DP, whereas we are able to achieve 76% AUC for
the same $(3.5,1\mathrm{e}{-5})$-DP. Our DPSGD implementations are able to
achieve $72-76\%$ AUC on this task for $0.5\leq\varepsilon\leq 10$ and
maintain AUC above 60% until $\varepsilon<1\mathrm{e}{-1}$. For the Length of
Stay task, Suriyakumar et al. [28] report 60% AUC for
$(3.5,1\mathrm{e}{-5})$-DP, yet our models have 67% AUC for the same
$\varepsilon$, which is only slightly below the non-private baseline. Again,
we do not see an AUC below 60% until $\varepsilon<1\mathrm{e}{-1}$. Much of
this improvement can be attributed to using the PRV Accounting method, which
allowed us to use much less noise to achieve the same level of privacy.

The ExpM+NF method outperforms these new state-of-the-art DPSGD results. As
seen in Table II, on the ICU Mortality task, ExpM+NF achieve 80.5% AUC (95% of
the non-private AUC) for $\varepsilon=1$, and for $\varepsilon\geq
1\mathrm{e}{-4}$ results are above 89% of the non-private AUC (above 75% AUC).
By comparison, DPSGD falls below 75% AUC, 89% of the non-private AUC, for
$\varepsilon\leq 2$.

For the Length of Stay task, DPSGD surpasses ExpM+NF for $2\leq\varepsilon\leq
7$, although all private models lie between 67.2–67.8% AUC, greater than 99%
of the non-private AUC, $\varepsilon\geq 2$. Likely randomness due to the
model initialization and noise in the hyperparameter search process may
influence which model is slightly better/worse for any given $\varepsilon\geq
2$ as the results are so tight. However, a vast difference is again seen when
the privacy is increased as ExpM+NF achieves over 97.5% of the non-private AUC
for $\varepsilon\geq 1\mathrm{e}{-4}$. As was seen in the Adult Dataset
experiment, there are times that for some smaller $\varepsilon$ the ExpM+NF
median AUC is greater than a nearby larger $\varepsilon$. Variations in the
selected hyperparameters and initial starting conditions are the suspected
cause.

####  4.2.2 GRU-D Results

Table IV compares results of the GRU-D non-private baseline for previous works
and ours, specifically including BCE vs $\ell(2)$ loss and with batch
normalization vs. without. We see nearly identical results in our results for
each prediction task across the the two loss functions and with/without batch
normalization, except for one instance, $\ell(2)$ loss with batch
normalization is worse. GRU-D non-private baseline results of our method
compared to previous works reside in Table IV. Our results are very close but
slightly below Wang et al. [32], yet better than Suriyakumar et al. [28]. The
gains in GRU-D’s performance of ours and Wang et al.’s results may be due to
differences in data or other implementation details. Specifically, our
hyperparameter search found that a hidden size of about 35-40 performed best,
which is much smaller than the 67 hidden size that [28] (and the original work
of Che et al. [31]) used.

For the Length of Stay task, Suriyakumar et al. [28] report an AUC of 61% for
GRU-D with $(3.5,1\mathrm{e}{-5})$-DP. We reach 70% AUC with DPSGD for the
same level of privacy. This is better than the AUC reported by Suriyakumar et
al. [28] for both the non-private LR and GRU-D models and we are able to
maintain an AUC greater than 65% for $\varepsilon>1\mathrm{e}{-2}$ with DPSGD.
As we discussed in the prior section, much of the gains in AUC for GRU-D with
DPSGD are likely due using the PRV Accounting method. Some of the gains could
also be attributed to the same causes that provided the large gains we made
for the non-private GRU-D model.

Suriyakumar et al. [28] show a sharp decrease in AUC when training GRU-D with
DPSGD on ICU Mortality task, even in the “low privacy” case with
$\varepsilon=3\mathrm{e}5$. They report 59% AUC for this high $\varepsilon$
and 53% AUC for the “strong privacy” case, $(3.5,1\mathrm{e}{-5})$-DP, which
is not much better than random guessing. Our DPSGD PRV implementation of GRU-D
achieves median 82.7% AUC for $(3.5,1\mathrm{e}{-5})$-DP using GRU-D on the
Mortality prediction task. This is comparable to the best non-private LR model
that we achieved, and is better than the performance [28] reported for non-
private GRU-D. Our DPSGD results achieve AUC greater than 60% for each
$\varepsilon>1\mathrm{e}{-2}$ in this prediction task.

While the DPSGD results provide substantial gains on the prior state-of-the-
art, the ExpM+NF method shows even further improvement. On the ICU Mortality
task, we reach 87.1% AUC for $\varepsilon=10$, We maintain a median AUC
greater than 82.5%, i.e., greater than 94% of the non-private AUC, for every
$\varepsilon\geq 1\mathrm{e}{-3}$ we test. These results equal or surpass the
best DPSGD AUC across all $(\varepsilon,\delta)$ that we explored. For the
Length of Stay task, ExpM+NF exhibits 95.5% of the non-private AUC for all
(AUC of at least 71%) for every $\varepsilon\geq 1\mathrm{e}{-4}$. This
surpasses non-private results of Suriyakumr et al. [28]. Viewed another way,
all ExpM+NF results for $\varepsilon=1\mathrm{e}-3$ surpass DPSGD results for
any $\varepsilon$!

TABLE IV: AUC scores for non-private GRU-D model from this and prior works on MIMIC-III tasks. Bold results are best per task. _Underlined_ results are best in this work per task. BN denotes batch normalization. | [32] | [28] |  $\ell(2)$ loss | BCE loss
---|---|---|---|---
| BN | No BN | BN | No BN
ICU Mortality | 0.891 | 0.79 | 0.855 | 0.875 | 0.877 | _0.878_
Length of Stay | 0.733 | 0.67 | 0.721 | _0.724_ | 0.722 | 0.722
TABLE V: ICU Mortality Mean Benchmark Timing Results |  | Logistic Regression | GRU-D
---|---|---|---
Training | Loss | Training Time | Computing $\varepsilon$ | Total | Training Time | Computing $\varepsilon$ | Total
Non-Private | $\ell(2)$ | .87 ms | $-$ | .87 ms | .84 ms | $-$ | .84 ms
BCE | 1.67 ms | $-$ | 1.67 ms | .93 ms | $-$ | .93 ms
DPSGD | $\ell(2)$ | 1.16 ms | 1.13 ms | 2.29 ms | 1.38 ms | 1.44 ms | 2.82 ms
BCE | 1.56 ms | 1.2 ms | 2.76 ms | 1.46 ms | 1.34 ms | 2.8 ms
ExpM+NF | RKL+$\ell(2)$ | 1.65 ms | $-$ | 1.65 ms | 1.71 ms | $-$ | 1.71 ms

###  4.3 Training Times

In this section, we provide benchmark timings for training for our non-
private, DPSGD and ExpM+NF implementations, and in the case of DPSGD,
computing $\varepsilon$. We found that the best models for each of the
different methods depended highly on the hyperparameter search results, and we
only provide benchmarks for the best hyperparameters that were used for the
test set. Specifically, the number of epochs and batch size will vary between
the different implementations and in some cases the different privacy levels.
As all our models are implemented in PyTorch, we use PyTorch’s benchmark suite
over ten runs on a single NVIDIA A100 80GB GPU and 128 CPUs with 2TB of shared
RAM.

In Table V we report the mean timings for ICU Mortality Task for both LR and
GRU-D models. For DPSGD and ExpM+NF, we additionally take the mean across the
various privacy levels, noting that some $\varepsilon$ may have
hyperparameters that led it to take more or less time than this reported mean.
For the non-private GRU-D implementation, we report mean training time with
batch normalization which took less time. Timing results for Length of Stay
are similar, and reside in the Appendix, Table VIII, as well as more details
on DPSGD timing in Tables IX, X, and ExpM+NF training times in Table VII.

In nearly every case, the non-private implementation takes the least total
time, as is expected. In the case of the non-private BCE loss, the number of
epochs and batch size were larger, likely attributing to the increased
training time. LR and GRU-D models took similar amounts of time to train,
likely to due the number of epochs required (GRU-D tended to need much fewer
epochs than LR). ExpM+NF training time is more than DPSGD’s training time, but
when we add the additional time that DPSGD needs to compute $\varepsilon$,
ExpM+NF performs better. There is little computational trade-off between DPSGD
and ExpM+NF in these experiments. The innovation here is that our ExpM+NF code
computes (and tracks gradients through) the $\ell(2)$ loss for the sampled
parameters $\theta_{i}$ in parallel when computing the RKL loss for training
the NF, rather than computing this sequentially.

##  5 Conclusion, Limitations, & Future Research

The fundamental observation driving this research is that DPSGD, the de facto
method for differentially private ML, is wasteful by design in all but the
relatively rare scenario when gradients are to be made public—noise is added
to every gradient diminishing privacy with each epoch, and this entails the
need for advanced composition theorems ensuring that $\delta>0$. Our critical
insight is two-fold: first, the well-established ExpM provides a tailored
solution that bypasses these two problems, but the requisite distribution for
ML applications is intractable; second, NF models provide a promising avenue
for sampling from the ExpM distribution.

In this pioneering work, we find that ExpM+NF exhibits greater accuracy and
privacy than the current SOTA in every experiment. Further, ExpM+NF achieves
near optimal accuracy ($>93\%$ of non-private training) for $\varepsilon\geq
5\times 10^{-4}$ with $\delta=0$. As discussed by a recent survey on
differentially private learning [21], $\varepsilon$ in range $[1,10]$ is
expected with $\delta\approxeq 1/|X|$. ExpM+NF exhibits three to four orders
of magnitude better privacy for similar and in most cases, better accuracy
than DPSGD. Our overall conclusion is that ExpM+NF is superior in accuracy and
privacy than DPSGD for training differentially private classification
algorithms.

For all training methods, non-private, DPSGD, and ExpM+NF, results depended
heavily on hyperparmeters, and we found $\scriptstyle\mathtt{\sim}$100
hyperparmeter tuning runs were required to saturate our results. While we do
not report the privacy loss due to hyperparameter tuning in this work, it does
incur a privacy cost that ExpM+NF is well equipped to handle. ExpM+NF’s
ability to attain similar accuracy with orders of magnitude better privacy
provides the privacy budget to implement the needed hyperparmeter tuning and
still achieve a desirable privacy level.

Our implementations of DPSGD used the PRV accounting method, and our emperical
results confirm its superiority over RDP accounting in both accurately
estimating $\varepsilon$ and the ability to handle $\varepsilon\leq
1\mathrm{e}-1$.

Our results show that outlier NFs can produce bad results based on their
randomized initializations. The increase in accuracy and privacy by ExpM+NF
also affords a straightforward workaround, e.g., releasing ten models, each
sampled from trained NFs with different starting seeds that are then used in a
voting scheme.

We found that $\sigma$, the hyperparameter governing the variance of the NF’s
base distribution, has a large influence on results. Optimal $\sigma$ found in
hyperparameter searches tend to be larger for smaller $\varepsilon$, matching
the intuition that the NF is more accurate if the base and output
distributions’ variance vary together. In future research, we suggest testing
an NF that permits learning the base distribution’s parameters during
training.

The effect of using Sylvester flows (over planar flows) is increased
expressiveness, but it does come at the cost of many more parameters in the NF
model. For example, on the MIMIC-III ICU tasks we have dimension about
$d=2,500$. With planar flows, the number of NF parameters needed to train an
LR model is $(2d+1)\times\text{number of flows}$, which is about 50,000 for 10
flows. With Sylvester flows the number of parameters is roughly $(d\times
k+m^{2}+m+d)\times\text{the number of flows}$, where $k\leq d-1$ is how many
Householder reflections to use and $m\leq d$ (for planar flows, $m=1$). If we
use $m=k=5$ and 10 flows we have about $150,000$ NF parameters. Moving to the
GRU-D models, we increase $d$ to the $\mathcal{O}(50K)$, so the number of
parameters explodes. Future research to understand the gain to accuracy-
privacy vs the computational expense incurred by using more expressive NFs for
ExpM+NF is needed.

In this work, bounding the sensitivity of the loss function, as is required
for ExpM, was done by using $\ell(2)$ loss and the fact that our targets were
bounded (binary, or one-hot). Even constrained to only $\ell(2)$ loss, ExpM+NF
outperforms DPSGD with either BCE or $\ell(2)$ loss in nearly all experiments.
Moving to a more general setting, especially regression with $\ell(2)$ loss or
classification with other prominent loss functions, esp. log loss and KL
divergence loss, will require custom sensitivity bounds for ExpM+NF (e.g., see
[17]). Our results show that non-private and DPSGD training had similar
results for both BCE and $\ell(2)$ loss in these classification tasks; on the
other hand, the choice of loss function may prove a bigger effect on ExpM+NF’s
results since the sensitivity bounds has a direct effect on the variance of
ExpM distribution.

In practice, randomness is produced from a pseudo-random algorithm, but
differential privacy proofs follow from the assumption of true randomness.
Prior works like [42] handle the use of pseudo-randomness by introducing a
weaker computational differential privacy definition. We are unaware of
mathematical treatment that seeks to estimate the effects of using pseudo-
randomness on the privacy bound. For ExpM+NF, the psuedo-randomness comes from
the NF’s output distribution. It appears from the accuracy of our results that
the NF is indeed approximating the correct density, (near optimal parameters
are indeed found). Understanding how the privacy bound may be affected by the
the NF approximation is a next step. Notably, training of the NF furnishes
ample information on the discrepancies—each loss computation gives empirical
KL divergence of the $p_{ExpM}$ and the NF’s output density that could be used
to provide theorems that capture the difference into a quantifiable privacy
guarantee. Further, using an NF that poorly approximates the ExpM distribution
intuitively should furnish stronger privacy, as the algorithm is seemingly
ignoring the training data.

How to craft an application of ExpM+NF to the federated setting and whether it
can again push the SOTA is future research. Notably, one can theoretically
derive DPSGD from using ExpM to sample gradients [11], so the most promising
future direction of ExpM+NF in the federated setting is with federated model
aggregation methods other than gradient aggregation and is a next step.
Applications to popular federated techniques such as FedAve [43] and FedProx
[44] should be straightforward.

Our initial, custom implementations were tested for training time against
DPSGD and non-private training finding slightly faster training of ExpM+NF
then DPSGD when time to compute the noise_multiplier for DPSGD is included.
This shows that the method is computational feasible. While we provide our
research code for reproducibility, professional engineering is needed for
widespread adoption of ExpM+NF.

## References

  * [1] A. Yousefpour, I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, J. Nguyen, S. Ghosh, A. Bharadwaj, J. Zhao, G. Cormode, and I. Mironov, “Opacus: User-friendly differential privacy library in PyTorch,” _arXiv preprint arXiv:2109.12298_ , 2021.
  * [2] X. Zhang _et al._ , “Adaptive privacy preserving deep learning algorithms for medical data,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2021. [Online]. Available: https://openaccess.thecvf.com/content/WACV2021/papers/Zhang_Adaptive_Privacy_Preserving_Deep_Learning_Algorithms_for_Medical_Data_WACV_2021_paper.pdf
  * [3] S. Gao _et al._ , “Classifying cancer pathology reports with hierarchical self-attention networks,” _Artificial intelligence in medicine_ , vol. 101, p. 101726, 2019.
  * [4] M. Hassan, M. Rehmani, and J. Chen, “Differential privacy techniques for cyber-physical systems: a survey,” _IEEE Communications Surveys & Tutorials_, vol. 22, no. 1, pp. 746–789, 2019.
  * [5] M. U. Hassan _et al._ , “Differential privacy for renewable energy resources based smart metering,” _Journal of Parallel and Distributed Computing_ , vol. 131, pp. 69–80, 2019.
  * [6] A. N. Dajani _et al._ , “The modernization of statistical disclosure limitation at the u.s. census bureau,” _Presented at the September 2017 meeting of the Census Scientific Advisory Committee_ , 2017.
  * [7] Apple Differential Privacy Team. (2017) Learning with privacy at scale. Accessed: 2023-07-25. [Online]. Available: https://machinelearning.apple.com/docs/learning-with-privacy-at-scale/appledifferentialprivacysystem.pdf
  * [8] U. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in _Proceedings of the 2014 ACM Conference on Computer and Communications Security_ , 2014, pp. 1054–1067.
  * [9] B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” in _Advances in Neural Information Processing Systems 30, NIPS ’17_ , 2017, pp. 3571–3580.
  * [10] P. Xiong, T.-Q. Zhu, and X.-F. Wang, “A survey on differential privacy and applications,” _Jisuanji Xuebao/Chinese Journal of Computers_ , vol. 37, no. 1, pp. 101–122, 2014.
  * [11] F. McSherry and K. Talwar, “Mechanism design via differential privacy,” in _IEEE Symposium on Foundations of Computer Science_ , 2007, pp. 94–103.
  * [12] A. Friedman and A. Schuster, “Data mining with differential privacy,” in _Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2010, pp. 493–502.
  * [13] M. Kapralov and K. Talwar, “On differentially private low rank approximation,” in _Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms_. SIAM, 2013, pp. 1395–1414.
  * [14] S. A. Vinterbo, “Differentially private projected histograms: Construction and use for prediction,” in _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 2012, pp. 19–34.
  * [15] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?” _SIAM Journal on Computing_ , vol. 40, no. 3, pp. 793–826, 2011. [Online]. Available: https://doi.org/10.1137/090756090
  * [16] Z. Ji, Z. C. Lipton, and C. Elkan, “Differential privacy and machine learning: a survey and review,” _arXiv preprint arXiv:1412.7584_ , 2014.
  * [17] K. Minami, H. Arai, I. Sato, and H. Nakagawa, “Differential privacy without sensitivity,” in _Advances in Neural Information Processing Systems 29_ , 2016.
  * [18] J. P. Near and C. Abuah. (2022) Programming differential privacy. Accessed: 2023-09-15. [Online]. Available: https://programming-dp.com/
  * [19] G. Papamakarios _et al._ , “Normalizing flows for probabilistic modeling and inference,” _Journal of Machine Learning Research_ , vol. 22, no. 57, pp. 1–64, 2021.
  * [20] M. Abadi _et al._ , “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , 2016.
  * [21] N. Ponomareva, H. Hazimeh, A. Kurakin, Z. Xu, C. Denison, H. B. McMahan, S. Vassilvitskii, S. Chien, and A. G. Thakurta, “How to dp-fy ML: a practical guide to machine learning with differential privacy,” vol. 77, 2023, pp. 1113–1201.
  * [22] C. Dwork, “Sequential composition of differential privacy,” _Theory of Cryptography_ , pp. 222–232, 2007.
  * [23] ——, “Advanced composition of differential privacy,” in _Proceedings of the 41st Annual ACM Symposium on Theory of Computing_ , 2010, pp. 436–445.
  * [24] P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,” _IEEE Transactions on Information Theory_ , vol. 63, no. 6, pp. 4037–4049, 2017.
  * [25] J. Dong, A. Roth, and W. Su, “Gaussian differential privacy,” _Journal of the Royal Statistical Society_ , 2021. [Online]. Available: https://par.nsf.gov/biblio/10215709
  * [26] S. Gopi, Y. T. Lee, and L. Wutschitz, “Numerical composition of differential privacy,” in _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 11 631–11 642. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2021/file/6097d8f3714205740f30debe1166744e-Paper.pdf
  * [27] A. Kurakin. (2022) Applying differential privacy to large scale image classification. Accessed: 2023-07-25. [Online]. Available: https://ai.googleblog.com/2022/02/applying-differential-privacy-to-large.html
  * [28] V. M. Suriyakumar, N. Papernot, A. Goldenberg, and M. Ghassemi, “Chasing your long tails: Differentially private prediction in health care settings,” in _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , 2021, pp. 723–734.
  * [29] Adult dataset. Accessed: 2023-07-25. [Online]. Available: https://archive.ics.uci.edu/ml/datasets/adult
  * [30] A. E. W. Johnson _et al._ , “MIMIC-III, a freely accessible critical care database,” _Scientific data_ , vol. 3, 2016.
  * [31] Z. Che _et al._ , “Recurrent neural networks for multivariate time series with missing values,” _Scientific reports_ , vol. 8, no. 1, pp. 1–12, 2018\.
  * [32] S. Wang _et al._ , “Mimic-extract: A data extraction, preprocessing, and representation pipeline for mimic-iii,” in _Proceedings of the ACM conference on health, inference, and learning_ , 2020. [Online]. Available: https://github.com/MLforHealth/MIMIC_Extract
  * [33] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” _Found. Trends Theor. Comput. Sci._ , vol. 9, no. 3-4, pp. 211–407, 2014\.
  * [34] S. Neel, A. Roth, G. Vietri, and Z. S. Wu, “Differentially private objective perturbation: Beyond smoothness and convexity,” _ArXiv_ , vol. abs/1909.01783, 2019. [Online]. Available: https://api.semanticscholar.org/CorpusID:202537581
  * [35] D. Rezende and S. Mohamed, “Variational inference with normalizing flows,” in _International Conference on Machine Learning_ , 2015.
  * [36] R. Van Den Berg _et al._ , “Sylvester normalizing flows for variational inference,” in _34th Conference on Uncertainty in Artificial Intelligence_ , 2018.
  * [37] X. Sun and C. Bischof, “A basis-kernel representation of orthogonal matrices,” _SIAM journal on matrix analysis and applications_ , vol. 16, no. 4, pp. 1184–1196, 1995.
  * [38] D. Dua and C. Graff, “UCI machine learning repository,” 2017. [Online]. Available: http://archive.ics.uci.edu/ml
  * [39] “Codebase Opacus,” https://opacus.ai/, accessed: 2023-07-25.
  * [40] A. Yousefpour, I. Shilov, A. Sablayrolles _et al._ , “Opacus: User-friendly differential privacy library in PyTorch,” in _NeurIPS Workshop Privacy in Machine Learning_ , 2021.
  * [41] MIMIC-extract github repository. Accessed: 2023-05-25. [Online]. Available: https://github.com/MLforHealth/MIMIC_Extract
  * [42] I. Mironov, O. Pandey, O. Reingold, and S. Vadhan, “Computational differential privacy,” in _Annual International Cryptology Conference_. Springer, 2009, pp. 126–142.
  * [43] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [44] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” _Proceedings of Machine learning and systems_ , vol. 2, pp. 429–450, 2020.

## Appendix

###  5.1 ExpM+NF AUC Distributions for MIMIC Experiments

In this section we provide ExpM+NF box plots for the MIMIC III Experiments.
Figure 4 and Figure 5 show results for logistic regression models trained with
ExpM+NF on ICU Mortality and Length of Stay tasks, respectively. For the first
several privacy levels (decreasing at a logithmic rate), we can see that there
are very few anomalous or bad starts, likely because the hyperparameters found
were robust to these starting conditions. As the privacy level gets below
$1\mathrm{e}{-4}$, we begin to see wide variations in how well the NFs
perform. In this particular experiment, we do not begin to see median AUC
below 60% until $\varepsilon=1\mathrm{-6}$.

Figure 4: ICU Mortality Logistic Regression results, for each $\varepsilon$
value, ten NF models are trained and used to produce 1,000 samples each from
the ExpM distribution. We present box plots of the 10,000 resulting
classifiers’ AUC values. For each NF model’s 1,000 samples we compute the mean
AUC, which are overlayed as dots.  Figure 5: Length of Stay Logistic
Regression results, for each $\varepsilon$ value, ten NF models are trained
and used to produce 1,000 samples each from the ExpM distribution. We present
box plots of the 10,000 resulting classifiers’ AUC values. For each NF model’s
1,000 samples we compute the mean AUC, which are overlayed as dots.

The results for GRU-D models trained on ICU Mortality are given in Figure 6
and GRU-D models trained on Length of Stay in Figure 7. Again, we see that for
the first several privacy levels (decreasing logarithmically), there are very
few anomalous starts. As we approach $1\mathrm{e}{-4}$, we begin to see more
poor starts as the privacy level begins to affect performance.

While outlier NFs can occur, MIMIC III had far fewer than the Adult Dataset
Experiment (see Figure 3) especially for $\varepsilon>1\mathrm{e}{-4}$. This
shows that some of the bad random initialization may also be dataset
dependent. Overcoming these anomalous starts, when they do appear, can be
handled by, e.g., releasing ten sampled models that are used in a voting
scheme for slight privacy cost.

Figure 6: ICU Mortality GRU-D results, for each $\varepsilon$ value, ten NF
models are trained and used to produce 1,000 samples each from the ExpM
distribution. We present box plots of the 10,000 resulting classifiers’ AUC
values. For each NF model’s 1,000 samples we compute the mean AUC, which are
overlayed as dots.  Figure 7: Length of Stay GRU-D results, for each
$\varepsilon$ value, ten NF models are trained and used to produce 1,000
samples each from the ExpM distribution. We present box plots of the 10,000
resulting classifiers’ AUC values. For each NF model’s 1,000 samples we
compute the mean AUC, which are overlayed as dots.

Figure 8: Each quad’s subfigure provides violin plots depicting two (of ten)
densities of NF models’ AUC for four values of $\varepsilon$. Note the
changing y scale. Left quad is from Adult Data LR model, middle & right quads
are from MIMIC3 Length of Stay and Mortality prediction tasks, respectively,
both with GRU-D model.

###  5.2 Visualizing NF AUC Distributions

Our NFs produce densities in a high dimensional feature space; hence, we
cannot easily visualize them. In, Figure 8, we plot the densities of a few NF
models’ AUC values from our experiments. We can see empirically the known
trend that variance of our NF densities are increasing as privacy increases.
Most are sharply unimodal.

###  5.3 RDP Accountant vs PRV Accountant

As DPSGD is so widely used, we provide the privacy estimates of using both the
PRV and RDP accounting methods for our GRU-D DPSGD experiment in Table VI. For
$\varepsilon>0.1$, the RPD Accounting method over estimates $\varepsilon$
between $0.05-2.8$. An important observation is that there appears to be a
lower limit for the RDP Accounting method, showing that $\varepsilon>0.1$ even
when the PRV Accountant is able to obtain $\varepsilon<0.1$.

TABLE VI: DPSGD PRV vs. RDP Accountant Results for GRU-D model on ICU Mortality with $\delta=1\mathrm{e}{-5}$ |  $\ell(2)$ Loss | BCE Loss
---|---|---
Target $\varepsilon$ | Steps | noise_multplier | PRV $\varepsilon$ | RDP $\varepsilon$ | Steps | noise_multplier | PRV $\varepsilon$ | RDP $\varepsilon$
0.0001 | 4764 | 10240.0 | $0.0001\pm 0.0001$ | 0.1029 | 6552 | 10240.0 | $0.0001\pm 0.0001$ | 0.1029
0.001 | 5820 | 320.0 | $0.0009\pm 0.0001$ | 0.1029 | 7820 | 380.0 | $0.0009\pm 0.0001$ | 0.1029
0.01 | 873 | 25.156 | $0.0099\pm 0.0001$ | 0.1034 | 3498 | 45.938 | $0.01\pm 0.0001$ | 0.1034
0.1 | 4368 | 6.172 | $0.0999\pm 0.001$ | 0.1354 | 9372 | 7.109 | $0.0999\pm 0.001$ | 0.1355
0.5 | 2832 | 1.074 | $0.4969\pm 0.005$ | 0.7866 | 3070 | 1.484 | $0.4986\pm 0.005$ | 0.5571
1.0 | 4370 | 0.889 | $0.9918\pm 0.01$ | 1.3874 | 8904 | 1.328 | $0.9945\pm 0.01$ | 1.0797
2.0 | 4260 | 0.709 | $1.9903\pm 0.01$ | 2.655 | 7176 | 0.854 | $1.9998\pm 0.01$ | 2.3053
3.5 | 3176 | 0.605 | $3.4961\pm 0.01$ | 4.357 | 6678 | 0.688 | $3.4931\pm 0.01$ | 4.1271
5.0 | 2808 | 0.571 | $4.9985\pm 0.01$ | 6.0285 | 3328 | 0.546 | $4.9963\pm 0.01$ | 6.0799
7.0 | 2107 | 0.511 | $6.9959\pm 0.01$ | 8.3801 | 4720 | 0.502 | $6.9973\pm 0.01$ | 8.371
10.0 | 2709 | 0.474 | $9.9969\pm 0.01$ | 11.7963 | 3834 | 0.457 | $9.9907\pm 0.01$ | 11.8117

###  5.4 Training Times

This section provides more detailed training time results. Table V reports the
mean timings for ICU Mortality Task for both logistic regression and GRU-D
models. For DPSGD and ExpM+NF, we additionally take the mean across the
various privacy levels, noting that some $\varepsilon$ may have
hyperparameters that led it to take more or less time than this reported mean.
For the non-private GRU-D implementation, we report mean training time without
batch normalization which took less time.

Table IX and Table X provide more detail on the mean time for each privacy
level for DPSGD. We report mean time to compute privacy and the
noise_multiplier but note that in practice only one of those would be needed.
Interestingly, the privacy level itself does not seem to have much influence
in the time it will take to train or compute $\varepsilon$, rather other
hyperparameters are likely more influential.

Table VII reports mean training times for ExpM+NF for each privacy level for
the MIMIC III tasks. Much like DPSGD, we can see that the privacy level
$\varepsilon$ has little influence on how long training will take.

TABLE VII: ExpM+NF Mean Training Times in milliseconds (ms) | ICU Mortality | Length of Stay
---|---|---
$\varepsilon$ | LR | GRU-D | LR | GRU-D
0.0001 | 1.92 | 2.02 | 0.87 | 2.13
0.001 | 1.90 | 2.12 | 1.83 | 1.1
0.01 | 1.82 | 1.93 | 2.22 | 1.78
0.1 | 1.87 | 1.72 | 1.88 | 2.01
0.5 | 1.84 | 2.08 | 2.16 | 1.92
1.0 | 1.69 | 1.58 | 1.87 | .93
2.0 | 1.73 | 2.05 | 1.02 | 1.92
3.5 | 1.11 | 1.29 | 1.79 | 2.54
5.0 | 1.83 | 1.90 | 1.00 | 1.48
7.0 | 1.79 | 1.20 | 2.06 | 1.96
10.0 | 1.78 | 1.97 | 1.87 | 2.1
TABLE VIII: Length of Stay Benchmark Timing Results |  | Logistic Regression | GRU-D
---|---|---|---
Task | Loss | Training Time | Computing $\varepsilon$ | Total | Training Time | Computing $\varepsilon$ | Total
Non-Private | $\ell(2)$ | 1.57 ms | $-$ | 1.57 ms | .81 ms | $-$ | .81 ms
BCE | 1.51 ms | $-$ | 1.51 ms | 1.46 ms | $-$ | 1.46 ms
DPSGD | $\ell(2)$ | 1.41 ms | 1.36 ms | 2.77 ms | 1.8 ms | 1.5 ms | 3.3 ms
BCE | 1.36 ms | 1.3 ms | 2.63 ms | 1.67 ms | 1.76 ms | 3.45 ms
ExpM+NF | RKL+$\ell(2)$ | 1.74 ms | $-$ | 1.74 ms | 1.81 ms | $-$ | 1.81 ms
TABLE IX: DPSGD Length of Stay Benchmark Timing Results in Milliseconds (ms) Model | Loss | Target $\varepsilon$ | Mean Train Time | Mean Compute Time noise_multplier | Mean Compute Time $\varepsilon$ (PRV)
---|---|---|---|---|---
LogisticRegression | $\ell(2)$ | 0.0001 | 1.66 | 0.85 | 1.86
0.001 | 1.61 | 0.96 | 1.72
0.01 | 1.0 | 1.56 | 0.9
0.1 | 1.0 | 1.61 | 1.71
0.5 | 1.06 | 1.43 | 0.89
1.0 | 1.73 | 1.52 | 1.87
2.0 | 1.56 | 1.38 | 0.9
3.5 | 1.30 | 1.82 | 0.94
5.0 | 1.29 | 1.42 | 1.74
7.0 | 1.76 | 2.09 | 0.83
10.0 | 1.57 | 1.97 | 1.64
BCE | 0.0001 | 1.83 | 2.02 | 2.02
0.001 | 1.13 | 1.31 | 1.8
0.01 | 1.44 | 0.83 | 0.87
0.1 | 1.77 | 1.87 | 1.63
0.5 | 0.97 | 1.44 | 0.88
1.0 | 0.83 | 1.37 | 0.96
2.0 | 0.87 | 1.36 | 1.01
3.5 | 1.65 | 1.96 | 1.2
5.0 | 1.77 | 1.66 | 0.96
7.0 | 1.86 | 1.79 | 1.56
10.0 | 0.89 | 0.82 | 1.47
GRU-D | $\ell(2)$ | 0.0001 | 1.82 | 1.43 | 1.45
0.001 | 1.87 | 1.87 | 1.81
0.01 | 1.90 | 1.62 | 1.59
0.1 | 1.76 | 1.06 | 2.09
0.5 | 2.01 | 1.83 | 0.87
1.0 | 1.65 | 1.93 | 0.91
2.0 | 1.77 | 1.78 | 1.31
3.5 | 1.72 | 1.62 | 1.73
5.0 | 2.09 | 1.98 | 1.99
7.0 | 1.59 | 1.40 | 0.90
10.0 | 1.65 | 1.18 | 1.92
BCE | 0.0001 | 1.47 | 1.68 | 2.20
0.001 | 1.95 | 1.92 | 1.82
0.01 | 1.61 | 1.83 | 2.02
0.1 | 1.66 | 1.42 | 2.22
0.5 | 1.36 | 1.51 | 2.03
1.0 | 1.93 | 1.64 | 1.11
2.0 | 1.55 | 1.95 | 1.81
3.5 | 1.98 | 2.01 | 1.60
5.0 | 1.23 | 1.54 | 1.73
7.0 | 1.73 | 0.96 | 0.88
10.0 | 1.95 | 2.06 | 1.99
TABLE X: DPSGD ICU Mortality Benchmark Timing Results in milliseconds (ms) model | loss | target $\varepsilon$ | Mean Train Time | Mean Compute noise_multplier | Mean Compute $\varepsilon$ (PRV)
---|---|---|---|---|---
LogisticRegression | $\ell(2)$ | 0.0001 | 2.86 | 1.74 | 0.89
0.001 | 0.81 | 1.96 | 0.85
0.01 | 1.76 | 1.89 | 0.83
0.1 | 1.63 | 1.65 | 0.86
0.5 | 1.66 | 0.97 | 1.70
1.0 | 1.01 | 1.33 | 1.76
2.0 | 0.83 | 1.36 | 0.85
3.5 | 0.82 | 1.72 | 0.87
5.0 | 1.37 | 0.80 | 0.96
7.0 | 0.87 | 1.76 | 1.91
10.0 | 1.17 | 1.72 | 0.95
BCE | 0.0001 | 1.88 | 1.79 | 1.92
0.001 | 1.63 | 0.78 | 1.69
0.01 | 1.44 | 1.11 | 1.50
0.1 | 1.42 | 0.79 | 0.87
0.5 | 1.98 | 1.61 | 0.91
1.0 | 1.91 | 1.38 | 0.89
2.0 | 1.63 | 1.43 | 1.78
3.5 | 1.18 | 1.86 | 0.93
5.0 | 1.05 | 1.32 | 0.91
7.0 | 1.29 | 0.80 | 0.95
10.0 | 1.77 | 2.79 | 0.92
GRU-D | $\ell(2)$ | 0.0001 | 1.13 | 1.85 | 1.23
0.001 | 1.37 | 0.83 | 1.69
0.01 | 1.68 | 1.64 | 1.73
0.1 | 0.97 | 1.06 | 2.02
0.5 | 0.88 | 1.77 | 1.05
1.0 | 1.85 | 1.79 | 1.50
2.0 | 1.49 | 1.56 | 0.90
3.5 | 1.60 | 1.46 | 1.28
5.0 | 0.83 | 1.84 | 0.90
7.0 | 1.74 | 0.78 | 1.64
10.0 | 1.71 | 1.01 | 1.95
BCE | 0.0001 | 1.34 | 3.02 | 1.27
0.001 | 1.89 | 1.14 | 0.87
0.01 | 1.17 | 1.23 | 0.88
0.1 | 0.83 | 1.09 | 0.92
0.5 | 1.34 | 1.73 | 1.37
1.0 | 1.06 | 0.92 | 1.97
2.0 | 1.96 | 1.86 | 1.63
3.5 | 1.01 | 1.89 | 0.88
5.0 | 1.75 | 1.47 | 2.01
7.0 | 2.44 | 1.75 | 0.89
10.0 | 1.37 | 1.94 | 2.12