Deep Learning with Gaussian Differential Privacy

Introduction

In many applications of machine learning, the datasets contain sensitive information about individuals such as location, personal contacts, media consumption, and medical records. Exploiting the output of the machine learning algorithm, an adversary may be able to identify some individuals in the dataset, thus presenting serious privacy concerns. This reality gave rise to a broad and pressing call for developing privacy-preserving data analysis methodologies. Accordingly, there have been numerous investigations in the scholarly literature of many fields—statistics, cryptography, machine learning, and law—for the protection of privacy in data analysis.

Along this line, research efforts have repeatedly suggested the necessity of a rigorous and versatile definition of privacy. Among other things, researchers have questioned whether the use of a privacy definition gives interpretable privacy guarantees, and if so, whether this privacy definition allows for high accuracy of the private model among alternative definitions. In particular, anonymization as a syntactic and ad-hoc privacy concept has been shown to generally fail to guarantee privacy. Examples include the identification of a homophobic individual in the anonymized Netflix Challenge dataset and the identification of the health records of the then Massachusetts governor in public anonymized medical datasets .

In this context, $(\varepsilon,\delta)$-differential privacy (DP) arose as a mathematically rigorous definition of privacy . Today, this definition has developed into a firm foundation of private data analysis, with its applications deployed by Google , Apple , Microsoft , and the US Census Bureau . Despite its impressive popularity in both the scholarly literature and the industry, $(\varepsilon,\delta)$-DP is not versatile enough to handle composition, which is perhaps the most fundamental primitive in statistical privacy. For example, the training process of deep neural networks is in effect the composition of many primitive building blocks known as stochastic gradient descent (SGD). Under a modest privacy budget in the $(\varepsilon,\delta)$-DP sense, however, it was not clear how to maintain a high prediction accuracy of deep learning. This requires a tight privacy analysis of composition in the $(\varepsilon,\delta)$-DP framework. Indeed, the analysis of the privacy costs in deep learning was refined only recently using a sophisticated technique called the moments accountant .

Ideally, we hope to have a privacy definition that allows for refined privacy analyses of various algorithms in a principled manner, without resorting to sophisticated techniques. Having a refined privacy analysis not only enhances the trustworthiness of the models but can also be leveraged to improve the prediction accuracy by trading off privacy for utility. One possible candidate is $f$-differential privacy, a relaxation of $(\varepsilon,\delta)$-DP that was recently proposed by Dong, Roth, and Su . This new privacy definition faithfully retains the hypothesis testing interpretation of differential privacy and can losslessly reason about common primitives associated with differential privacy, including composition, privacy amplification by subsampling, and group privacy. In addition, $f$-DP includes a canonical single-parameter family that is referred to as Gaussian differential privacy (GDP). Notably, GDP is the focal privacy definition due to a central limit theorem that states that the privacy guarantees of the composition of private algorithms are approximately equivalent to telling apart two shifted normal distributions.

The main results of this paper show that $f$-DP offers a rigorous and versatile framework for developing private deep learning methodologiesIt is noteworthy that training deep learning models has served as an important benchmark in testing a privacy definition since the tightness of its privacy analysis crucially depends on whether the definition can tightly account for composition and subsampling.. Our guarantee provides protection against an attacker with knowledge of the network architecture as well as the model parameters, which is in the same spirit as . In short, this paper delivers the following messages concerning $f$-DP:

Closed-form privacy bounds. In the $f$-DP framework, the overall privacy loss incurred in training neural networks admits an amenable closed-form expression. In contrast, the privacy analysis via the moments accountant must be done by numerical computation , and the implicit nature of this earlier approach can hinder our understanding of how the tuning parameters affect the privacy bound. This is discussed in Section 3.1.

Stronger privacy guarantees. The $f$-DP approach gives stronger privacy guarantees than the earlier approach , even in terms of $(\varepsilon,\delta)$-DP. This improvement is due to the use of the central limit theorem for $f$-DP, which accurately captures the privacy loss incurred at each iteration in training the deep learning models. This is presented in Section 3.2 and illustrated with numerical experiments in Section 4.1.

Improved prediction accuracy. Leveraging the stronger privacy guarantees provided by $f$-DP, we can trade a certain amount of privacy for an improvement in prediction performance. This can be realized, for example, by appropriately reducing the amount of noise added during the training process of neural networks so as to match the target privacy level in terms of $(\varepsilon,\delta)$-DP. See Section 3.2 and Section 4.2 for the development of this utility improvement.

The remainder of the paper is structured as follows. In Section 1.1 we provide a brief review of related literature. Section 2 introduces $f$-DP and its basic properties at a minimal level. Next, in Section 3 we analyze the privacy cost of training deep neural networks in terms of $f$-DP and compare it to the privacy analysis using the moments accountant. In Section 4, we present numerical experiments to showcase the superiority of the $f$-DP approach to private deep learning in terms of test accuracy and privacy guarantees. The paper concludes with a discussion in Section 5.

There are continued efforts to understand how privacy degrades under composition. Developments along this line include the basic composition theorem and the advanced composition theorem . In a pioneering work, obtained an optimal composition theorem for $(\varepsilon,\delta)$-DP, which in fact served as one of the motivations for the $f$-DP work . However, it is #P hard to compute the privacy bounds from their composition theorem . More recently, derived sharp composition bounds on the overall privacy loss for exponential mechanisms.

From a different angle, a substantial recent effort has been devoted to relaxing differential privacy using divergences of probability distributions to overcome the weakness of $(\varepsilon,\delta)$-DP in handling composition . Unfortunately, these relaxations either lack a privacy amplification by subsampling argument or present a quite complex argument that is difficult to use . As subsampling is inherently used in training neural networks, therefore, it is difficult to directly apply these relaxations to the privacy analysis of deep learning.

To circumvent these technical difficulties associated with $(\varepsilon,\delta)$-DP and its divergence-based relaxations, Abadi et al. invented a technique termed the moments accountant to track detailed information of the privacy loss in the training process of deep neural networks. Using the moments accountant, their analysis significantly improves on earlier privacy analysis of SGD and allows for meaningful privacy guarantees for deep learning trained on realistically sized datasets. This technique has been extended to a variety of situations by follow-up work . In contrast, our approach to private deep learning in the $f$-DP framework leverages some powerful tools of this new privacy definition, nevertheless providing a sharper privacy analysis, as seen both theoretically and empirically in Sections 3 and 4.

For completeness, we remark that different approaches have been put forward to incorporate privacy considerations into deep learning, without leveraging the iterative and subsampling natures of training deep learning models. This line of work includes training a private model by an ensemble of “teacher” models , the development of noised federated averaging algorithms , and analyzing privacy costs through the lens of the optimization landscape of neural networks .

Preliminaries

In the differential privacy framework, we envision an adversary that is well-informed about the dataset except for a single individual, and the adversary seeks to determine whether this individual is in the dataset on the basis of the output of an algorithm. Roughly speaking, the algorithm is considered private if the adversary finds it hard to determine the presence or absence of any individual.

Informally, a dataset can be thought of as a matrix, whose rows each contain one individual’s data. Two datasets are said to be neighbors if one can be derived by discarding an individual from the other. As such, the sizes of neighboring datasets differ by oneAlternatively, the neighboring relationship can be defined for datasets of the same size and differing by one individual.. Let $S$ and $S^{\prime}$ be neighboring datasets, and $\varepsilon\geqslant 0,0\leqslant\delta\leqslant 1$ be two numbers, and denote by $M$ a (randomized) algorithm that takes as input a dataset.

A (randomized) algorithm $M$ gives $(\varepsilon,\delta)$-differential privacy if for any pair of neighboring datasets $S,S^{\prime}$ and any event $E$,

To achieve privacy, the algorithm $M$ is necessarily randomized, whereas the two datasets in Definition 2.1 are deterministic. This privacy definition ensures that, based on the output of the algorithm, the adversary has a limited (depending on how small $\varepsilon,\delta$ are) ability to identify the presence or absence of any individual, regardless of whether any individual opts in to or opts out of the dataset.

In essence, the adversary seeks to tell apart the two probability distributions $M(S)$ and $M(S^{\prime})$ using a single draw. In light of this observation, it is natural to interpret what the adversary does as testing two simple hypotheses:

The connection between differential privacy and hypothesis testing was, to our knowledge, first noted in , and was later developed in . Intuitively, privacy is well guaranteed if the hypothesis testing problem is hard. Following this intuition, the definition of $(\varepsilon,\delta)$-DP essentially uses the worst-case likelihood ratio of the distributions $M(S)$ and $M(S^{\prime})$ to measure the hardness of testing the two simple hypotheses.

Is there a more informative measure of the hardness? In , the authors propose to use the trade-off between type I error (the probability of erroneously rejecting $H_{0}$ when $H_{0}$ is true) and type II error (the probability of erroneously accepting $H_{0}$ when $H_{1}$ is true) in place of a few privacy parameters in $(\varepsilon,\delta)$-DP or divergence-based DP definitions. To formally define this new privacy definition, let $P$ and $Q$ denote the distributions of $M(S)$ and $M(S^{\prime})$, respectively, and let $\phi$ be any (possibly randomized) rejection rule for testing $H_{0}:P$ against $H_{1}:Q$. With these in place, defines the trade-off function of $P$ and $Q$ as

A (randomized) algorithm $M$ is $f$-differentially private if

for all neighboring datasets $S$ and $S^{\prime}$.

In this definition, both $T$ and $f$ are functions that take $\alpha\in$ as input and the inequality holds pointwise for all $0\leqslant\alpha\leqslant 1$, and we abuse notation by identifying $M(S)$ and $M(S^{\prime})$ with their associated distributions. This privacy definition is easily interpretable due to its inherent connection with the hypothesis testing problem. By adapting a result due to Wasserman and Zhou , $(\varepsilon,\delta)$-DP is a special instance of $f$-DP in the sense that an algorithm is $(\varepsilon,\delta)$-DP if and only if it is $f_{\varepsilon,\delta}$-DP with

Next, we define a single-parameter family of privacy definitions within the $f$-DP class for a reason that will be apparent later. Let G_{\mu}:=T\big{(}\mathcal{N}(0,1),\mathcal{N}(\mu,1)\big{)} for $\mu\geqslant 0$. Note that this trade-off function admits a closed-form expression $G_{\mu}(\alpha)=\Phi(\Phi^{-1}(1-\alpha)-\mu)$, where $\Phi$ is the cumulative distribution function of the standard normal distribution.

A (randomized) algorithm $M$ is $\mu$-Gaussian differentially private (GDP) if

for all neighboring datasets $S$ and $S^{\prime}$.

2 Properties of f𝑓f-Differential Privacy

Deep learning models are trained using the composition of many SGD updates. Broadly speaking, composition is concerned with a sequence of analyses on the same dataset where each analysis is informed by the explorations of prior analyses. A central question that every privacy definition is faced with is to pinpoint how the overall privacy guarantee degrades under composition. Formally, letting $M_{1}$ be the first algorithm and $M_{2}$ be the second, we define their composition algorithm $M$ as $M(S)=(M_{1}(S),M_{2}(S,M_{1}(S)))$. Roughly speaking, the composition is to “release all information that is learned by the algorithms.” Notably, the second algorithm $M_{2}$ can take as input the output of $M_{1}$ in addition to the dataset $S$. In general, the composition of more than two algorithms follows recursively.

To introduce the composition theorem for $f$-DP, defines a binary operation $\otimes$ on trade-off functions. Given trade-off functions $f=T(P,Q)$ and $g=T(P^{\prime},Q^{\prime})$, let $f\otimes g=T(P\times P^{\prime},Q\times Q^{\prime})$. This definition depends on the distributions $P,Q,P^{\prime},Q^{\prime}$ only through $f$ and $g$. Moreover, $\otimes$ is commutative and associative. Now the composition theorem can be readily stated as follows. Let $M_{t}$ be $f_{t}$-DP conditionally on any output of the prior algorithms for $t=1,\ldots,T$. Then their $T$-fold composition algorithm is $f_{1}\otimes\cdots\otimes f_{T}$-DP. This result shows that the composition of algorithms in the $f$-DP framework is reduced to performing the $\otimes$ operation on the associated trade-off functions. As an important fact, the privacy bound $f_{1}\otimes\cdots\otimes f_{T}$ in general cannot be improved. Put more precisely, one can find an $f_{t}$-DP mechanism $M_{t}$ for $t=1,\ldots,T$ such that their composition is precisely $f_{1}\otimes\cdots\otimes f_{T}$-DP (see the discussion following Theorem 4 in ).

$f_{1}\otimes f_{2}\otimes\cdots\otimes f_{T}\text{ is approximately }G_{\mu}$ (2) if the number of iterations $T$ is sufficiently largeIf $f_{i}=G_{\mu_{i}}$ for $i=1,\ldots,T$, then the $T$-fold composition is exactly $G_{\mu}$ with $\mu=\sqrt{\sum_{i=1}^{T}\mu_{i}^{2}}$.. This central limit theorem approximation is especially suitable for the privacy analysis of deep learning, where the training process typically takes at least tens of thousands of iterations. The privacy parameter $\mu$ depends on some functionals such as the Kullback–Leibler divergence of the trade-off functions. The central limit theorem yields a very accurate approximation in the settings considered in Section 4 (see numerical confirmation in Appendix A). For a rigorous account of this central limit theorem for differential privacy, see Theorem 6 in . We remark that a conceptually related article developed a central limit theorem for privacy loss random variables.

At a high level, this convergence-to-GDP result brings GDP to the focal point of the family of $f$-DP guarantees, implying that GDP is to $f$-DP as normal random variables to general random variables. Furthermore, this result serves as an effective approximation tool for approximating the privacy guarantees of composition algorithms. In contrast, privacy loss cannot be losslessly tracked under composition in the $(\varepsilon,\delta)$-DP framework.

Subsampling.

In training neural networks, the gradient at each iteration is computed from a mini-batch that is subsampled from the training examples. Intuitively, an algorithm applied to a subsample gives stronger privacy guarantees than applied to the full sample. Looking closely, this privacy amplification is due to the fact that an individual enjoys perfect privacy if not selected in the subsample. A concrete and pressing question is, therefore, to precisely characterize how much privacy is amplified by subsampling in the $f$-DP framework.

Consider the following sampling scheme: for each individual in the dataset $S$, include his or her datum in the subsample independently with probability $p$, which is sometimes referred to as the Poisson subsampling . The resulting subsample is denoted by $\mathtt{Sample}_{p}(S)$. For the purpose of clearing up any confusion, we remark that the subsample $\mathtt{Sample}_{p}(S)$ has a random size and as an intermediate step is not released. Given any algorithm $M$, denote by $M\circ\mathtt{Sample}_{p}$ the subsampled algorithm.

if $S$ can be obtained by removing one individual from $S^{\prime}$. Likewise,

As such, the two displays above say that the trade-off function of $M\circ\mathtt{Sample}_{p}$ on any neighboring datasets is lower bounded by $\min\{f_{p},f_{p}^{-1}\}$, which however is in general non-convex and thus is not a trade-off function. This suggests that we can boost the privacy bound by replacing $\min\{f_{p},f_{p}^{-1}\}$ with its double conjugate $\min\{f_{p},f_{p}^{-1}\}^{**}$, which is the greatest convex lower bound of $\min\{f_{p},f_{p}^{-1}\}$ and is indeed a trade-off function. Taken together, all the pieces show that the subsampled algorithm $M\circ\mathtt{Sample}_{p}$ is $\min\{f_{p},f_{p}^{-1}\}^{**}$-DP.

Notably, the privacy bound $\min\{f_{p},f_{p}^{-1}\}^{**}$ is larger than $f$ and cannot be improved in general. In light of the above, the $f$-DP framework is flexible enough to nicely handle the analysis of privacy amplification by subsampling. In the case where the original algorithm $M$ is $(\varepsilon,\delta)$-DP, this privacy bound strictly improves on the subsampling theorem for $(\varepsilon,\delta)$-DP .

Algorithms and Their Privacy Analyses

SGD and Adam are among the most popular optimizers in deep learning. Here we introduce a new privacy analysis of a private variant of SGD in the $f$-DP framework and then extend the study to a private version of Adam.

Letting $S=\{x_{1},\ldots,x_{n}\}$ denote the dataset, we consider minimizing the empirical risk

To facilitate the use of this privacy bound, we now derive an analytically tractable approximation of $\min\{f,f^{-1}\}^{**}$ using the privacy central limit theorem in a certain asymptotic regime, which further demonstrates the mathematical coherence and versatility of the $f$-DP framework. The central limit theorem shows that, in the asymptotic regime where $p\sqrt{T}\to\nu$ for a constant $\nu>0$ as $T\to\infty$,

As an aside, we remark that this new privacy analysis is different from the one performed in Section 5 of . Therein, the authors consider Algorithm 1 with uniform subsampling and obtain a privacy bound that is different from the one in the present paper.

Next, we present a private version of Adam in Algorithm 2, which we refer to as NoisyAdam and can be found in . This algorithm has the same privacy bound as NoisySGD in the $f$-DP framework. In short, this is because the momentum $m_{t}$ and $u_{t}$ are deterministic functions of the noisy gradients and no additional privacy cost is incurred due to the post-processing property of differential privacy. In passing, we remark that the same argument applies to AdaGrad and therefore it is also asymptotically GDP in the same asymptotic regime.

2 Comparisons with the Moments Accountant

It is instructive to compare the moments accountant with our privacy analysis performed in Section 3.1 using the $f$-DP framework. Developed in , the moments accountant gives a tight one-to-one mapping between $\varepsilon$ and $\delta$ for specifying the overall privacy loss in terms of $(\varepsilon,\delta)$-DP under composition, which is beyond the reach of the advanced composition theorem . In slightly more detail, the moments accountant uses the moment generating function of the privacy loss random variable to track the privacy loss under composition. As abuse of notation, this paper uses functions $\delta_{\mathtt{MA}}=\delta_{\mathtt{MA}}(\varepsilon)$ and $\varepsilon_{\mathtt{MA}}=\varepsilon_{\mathtt{MA}}(\delta)$ to denote the mapping induced by the moments accountant in both directionsWe omit the dependence of the functions on the specification of the composition algorithm such as $p,\sigma,T$ as in NoisySGD and NoisyAdam.. For self-containedness, the appendix includes a formal description of the two functions.

Although NoisySGD and NoisyAdam are our primary focus, our following discussion applies to general iterative algorithms where composition must be addressed in the privacy analysis. Let algorithm $M_{t}$ be $f_{t}$-DP for $t=1,\ldots,T$ and write $M$ for their composition. On the one hand, the moments accountant technique ensures that $M$ is $(\varepsilon,\delta_{\mathtt{MA}}(\varepsilon))$-DP for any $\varepsilon$ or, put equivalently, is $(\varepsilon_{\mathtt{MA}},\delta)$-DPThe moments accountant can be applied in the $f$-DP framework. In fact, the moments accountant is defined via a certain moment generating function, which is equivalent to the Rényi divergence. The Rényi divergence can be uniquely deduced from a trade-off function. See Section 2.3 in .. On the other hand, the composition algorithm is $f_{1}\otimes\cdots\otimes f_{T}$-DP from the $f$-DP viewpoint and, following from the central limit theorem (2), this composition can be shown to be approximately GDP in a certain asymptotic regime. For example, both NoisySGD and NoisyAdam presented in Algorithm 1 and Algorithm 2, respectively, asymptotically satisfy $\mu_{\mathtt{CLT}}$-GDP with privacy parameter

In light of the above, it is tempting to ask which of the two approaches yields a sharper privacy analysis. In terms of $f$-DP guarantees, it must be the latter, which we refer to as the CLT approach, because the composition theorem of $f$-DP is tight and, more importantly, the privacy central limit theorem is asymptotic exact. To formally state the result, note that the moments accountant asserts that the private optimizer is $(\varepsilon,\delta_{\mathtt{MA}}(\varepsilon))$-DP for all $\varepsilon\geqslant 0$, which is equivalent to $\sup_{\varepsilon\geqslant 0}f_{\varepsilon,\delta_{\mathtt{MA}}(\varepsilon)}$-DP by recognizing (1) (see also Proposition 2.11 in ). Roughly speaking, the following theorem says that $\sup_{\varepsilon\geqslant 0}f_{\varepsilon,\delta_{\mathtt{MA}}(\varepsilon)}$-DP (asymptotically) promises no more privacy guarantees than the bound of $\mu_{\mathtt{CLT}}$-GDP given by the CLT approach. This simple result is summarized by the following theorem and see Appendix B for a formal proof of this result.

Assume that $p\sqrt{T}$ converges to a positive constant as $T\to\infty$. Then, both $\mathtt{NoisySGD}$ and $\mathtt{NoisyAdam}$ satisfy

For ease of reading, we point out that, in the $(\varepsilon,\delta)$-DP framework, the smaller $\varepsilon,\delta$ are, the more privacy is guaranteed. In contrast, in the $f$-DP framework, the smaller $f$ is, the less privacy is guaranteed.

From the $(\varepsilon,\delta)$-DP viewpoint, however, the question is presently unclear. Explicitly, the duality between $f$-DP and $(\varepsilon,\delta)$-DP shows that $\mu$-GDP implies $(\varepsilon,\delta(\varepsilon;\mu))$-DP for all $\varepsilon\geqslant 0$, whereSee Section 2.4 of for this result. See also .

The question is, therefore, reduced to the comparison between $\delta_{\mathtt{MA}}(\varepsilon)$ and $\delta_{\mathtt{CLT}}(\varepsilon):=\delta(\varepsilon;\mu_{\mathtt{CLT}})$ or, equivalently, between $\varepsilon_{\mathtt{MA}}(\delta)$ and $\varepsilon_{\mathtt{CLT}}(\delta):=\varepsilon(\delta;\mu_{\mathtt{CLT}})$Here, $\varepsilon(\delta;\mu)$ is the inverse function of $\delta(\varepsilon;\mu)$..

Under the assumptions of Theorem 1, the $f$-DP framework gives an asymptotically sharper privacy analysis of both $\mathtt{NoisySGD}$ and $\mathtt{NoisyAdam}$ than the moments accountant in terms of $(\varepsilon,\delta)$-DP. That is,

In words, the CLT approach in the $f$-DP framework allows for an asymptotically smaller $\delta$ than the moments accountant at the same $\varepsilon$. It is worthwhile mentioning that the inequality in this theorem holds for any finite $T$ if $\delta$ is derived by directly applying the duality to the (exact) privacy bound $f_{1}\otimes\cdots\otimes f_{T}$. Equivalently, the theorem says that $\limsup_{T\to\infty}\,\left(\varepsilon_{\mathtt{CLT}}(\delta)-\varepsilon_{\mathtt{MA}}(\delta)\right)<0$ for any $\delta$Write $\delta^{\star}_{\mathtt{CLT}}=\delta_{\mathtt{CLT}}(0)$ and set $\varepsilon_{\mathtt{CLT}}(\delta)=0$ for $\delta\geqslant\delta^{\star}_{\mathtt{CLT}}$. Apply the same adjustment for $\varepsilon_{\mathtt{MA}}$.. As such, by setting the same $\delta$ in both approaches, say $\delta=10^{-5}$, the $f$-DP based CLT approach shall give a smaller value of $\varepsilon$.

Figure 1 shows the flowchart of the privacy analyses using the two approaches and their relationship. In addition, numerical comparisons are presented in Figure 2, consistently demonstrating the superiority of the CLT approach.

Results

In this section, we use NoisySGD and NoisyAdam to train private deep learning models on datasets for tasks ranging from image classification (MNIST), text classification (IMDb movie review), recommender systems (MovieLens movie rating), to regular binary classification (Adult income). Note that these datasets all contain sensitive information about individuals, and this fact necessitates privacy consideration in the training process. Code to reproduce the results using the TensorFlow Privacy library is available at https://github.com/tensorflow/privacy/tree/master/research/GDP_2019.

This section demonstrates the utility and practicality of the private deep learning methodologies with associated privacy guarantees in terms of $f$-DP. In Section 4.2, we extend the empirical study to the $(\varepsilon,\delta)$-DP framework. Throughout the experiments, the parameter $\delta$ we use always satisfies $\delta<1/n$, where $n$ is the number of training examples.

The MNIST dataset contains 60,000 training images and 10,000 test images. Each image is in $28\times 28$ gray-scale representing a handwritten digit ranging from 0 to 9. We train neural networks with the same architecture (two convolutional layers followed by one dense layer) as in on this dataset. Throughout the experiment, we set the subsampling probability to $p=256/60000$ and use a constant learning rate $\eta$.

For all experiments described in Table 1, Figure 3 illustrates the privacy bounds given by the CLT approach and the moments accountant both in terms of trade-off functions. The six plots in the first and third rows are with respect to $\delta=10^{-5}$, from which the $f$-DP framework is seen to provide an analyst with substantial improvements in the privacy bounds. Note that the first row in Figure 3 corresponds to the first three rows in Table 1, and the third row in Figure 3 corresponds to the last three rows in Table 1. For the model corresponding to 96.6% test accuracy, concretely, the minimum sum of type I and type II errors in the sense of hypothesis testing is (at least) $77.6\%$ by the CLT approach, whereas it is merely (at least) $9.4\%$ by the moments accountant. For completeness, we show the optimal trade-off functions over all pairs of $\varepsilon,\delta$ given by the moments accountant in the middle row. The gaps between the two approaches exist, as predicted by Theorem 1, and remain significant.

Next, we extend our experiments to other datasets to further test $f$-DP for training private neural networks. The experiments compare private models under the privacy budget $\mu\leq 2$ to their non-private counterparts and some popular baseline methods. For simplicity, we focus on shallow neural networks and leave the investigation of complex architectures for future research.

Adult income.

Originally from the UCI repository , the Adult income dataset has been preprocessed into the LIBSVM format . This dataset contains 32,561 examples, each of which has 123 features and a label indicating whether the individual’s annual income is more than $50,000 or not. We randomly choose$10\%$ of the examples as the test set (3,256 examples) and use the remaining 29,305 examples as the training set.

Our model is a single-layer multi-perceptron with 16 neurons and the ReLU activation. We set $\sigma=0.55$, $p=256/29305$, $\eta=0.15,R=1$, and use NoisySGD as our optimizer. The results displayed in Table 2 show that our private model achieves comparable performance to the baselines in the MLC++ library in terms of test accuracy.

IMDb.

We use the IMDb movie review dataset for binary sentiment classification (positive or negative reviews). The dataset contains 25,000 training and 25,000 test examples. In our experiments, we prepocess the dataset by only including the top 10,000 frequently used words and discard the rest. Next, we set every example to have 256 words by truncating the length or filling with zeros if necessary.

In our neural networks, the input is first embedded into 16 units and then is passed through a global average pooling. The intermediate output is fed to a fully-connected layer with 16 neurons, followed by a ReLU layer. We set $\sigma=0.56$, $p=512/25000$, $\eta=0.02,R=1$, and use NoisyAdam as our optimizer, which is observed to converge much faster than NoisySGD in this training task. We use the (non-private) two-layer LSTM RNN model in the Tensorflow tutorials as a baseline model. Table 3 reports the experimental results. Notably, the private neural networks perform comparably to the baseline model, at the cost of only one percent drop in test accuracy compared to the non-private counterpart.

MovieLens.

The MovieLens movie rating dataset is a benchmark dataset for recommendation tasks. Our experiments consider the MovieLens 1M dataset, which contains 1,000,209 movie ratings from 1 star to 5 stars. In total, there are 6,040 users who rated 3,706 different movies. For this multi-class classification problem, the root mean squared error (RMSE) is chosen as the performance measure. It is worthwhile to mention that, as each user only watched a small fraction of all the movies, most (user, movie) pairs correspond to missing ratings. We randomly sample 20% of the examples as the test set and take the remainder as the training set.

Our model is a simplified version of the neural collaborative filtering in . The network architecture consists of two branches. The left branch applies generalized matrix factorization to embed the users and movies using five latent factors. The output of the user embedding is multiplied by the item embedding. In the right branch, we use 10 latent factors for embedding. The embedding from both branches are then concatenated, which is fed to a fully-connected output layer. We set $\sigma=0.6,p=1/80,\eta=0.01$, and $R=5$ in NoisyAdam.

Table 4 presents the numerical results of our neural networks as well as baseline models in the Suprise library in their default settings. The difference in RMSE between the non-private networks and the private one is relatively large for the MovieLens 1M dataset. Nevertheless, the private model still outperforms many popular non-private models, including the user-based collaborative filtering and nonnegative matrix factorization.

2 The (ε,δ)𝜀𝛿(\varepsilon,\delta)-DP Perspective

While we hope that the $f$-DP perspective has been conclusively demonstrated to be advantageous, this section shows that the CLT approach continues to bring considerable benefits even in terms of $(\varepsilon,\delta)$-DP. Specifically, by making use of the comparisons between the CLT approach and the moments accountant in Section 3.2, we can add less noise to the gradients in NoisySGD and NoisyAdam while achieving the same $(\varepsilon,\delta)$-DP guarantees provided by the moments accountant. With less added noise, conceivably, an optimizer would have a higher prediction accuracy.

Discussion

In this paper, we have showcased the use of $f$-DP, a very recently proposed privacy definition, for training private deep learning models using SGD or Adam. Owing to its strength in handling composition and subsampling and the powerful privacy central limit theorem, the $f$-DP framework allows for a closed-form privacy bound that is sharper than the one given by the moments accountant in the $(\varepsilon,\delta)$-DP framework. By numerical experiments, we show that the trained neural networks can be quite private from the $f$-DP viewpoint (for instance, $1.13$-GDPThis means that undermining the privacy guarantee is harder than or of the same hardness as testing $H_{0}:\mu=0$ against $H_{1}:\mu=1.13$ based on the observation $\mu+\mathcal{N}(0,1)$.) but are not in the $(\varepsilon,\delta)$-DP sense due to over conservative privacy bounds (for instance, $(7.10,10^{-5})$-DP) computed in the $(\varepsilon,\delta)$-DP framework. This in turn suggests that one can add less noise during the training process while having the same privacy guarantees as using the moments accountant, thereby improving model utility.

We conclude this paper by offering several directions for future research. As the first direction, we may consider using time-dependent noise scales and learning rates in NoisySGD and NoisyAdam for a better tradeoff between privacy loss and utility in the $f$-DP framework. Note that has made considerable progress using concentrated differential privacy along this line. More generally, a straightforward but interesting problem is to extend this work to complex neural network architectures with a variety of optimization strategies. For example, can we develop some guidelines for choosing an optimizer among NoisySGD, NoisyAdam, and others for a given classification problem under some privacy constraint? Empirically, deep learning models are very sensitive to hyperparameters such as mini-batch size in terms of test accuracy. Therefore, from a practical standpoint, it would be of great importance to incorporate hyperparameter tuning into the $f$-DP framework . Inspired by , another interesting direction is to explore the possible relationship between $f$-DP guarantees and adversarial robustness of neural networks. Given $f$-DP’s good interpretability and powerful toolbox, it is worthwhile investigating whether, from a broad perspective, its superiority over earlier differential privacy relaxations would hold in general private statistical and machine learning tasks. We look forward to more research efforts to further the theory and extend the use of $f$-DP.

We are grateful to David Durfee, Ryan Rogers, Aaron Roth, and Qinqing Zheng for stimulating discussions in the early stages of this work. We would also like to thank two anonymous referees for their constructive comments that improved the presentation of the paper. This work was supported in part by NSF through CAREER DMS-1847415, CCF-1763314, and CCF-1934876, the Wharton Dean’s Research Fund, and NIH through R01GM124111 and RF1AG063481.

References

Appendix A Omitted Details in Section 2

We present Equation 3 as the following proposition, which is given in Section 2 but not in the foundational work .

If $M$ is $f$-DP, and $S^{\prime}=S\cup\{x_{0}\}$, then

We first write the two distributions $M\circ\mathtt{Sample}_{p}(S)$ and $M\circ\mathtt{Sample}_{p}(S^{\prime})$ as mixtures.

Without loss of generality, we can assume $S=\{x_{1},\ldots,x_{n}\}$ and $S^{\prime}=\{x_{0},x_{1},\ldots,x_{n}\}$. An outcome of the process $\mathtt{Sample}_{p}$ when applied to $S$ is a bit string $\vec{b}=(b_{1},\ldots,b_{n})\in\{0,1\}^{n}$. Bit $b_{i}$ dependes on whether $x_{i}$ is selected into the subsample. We use $S_{\vec{b}}\subseteq S$ to denote the subsample determined by $\vec{b}$. When each $b_{i}$ is sampled from a Bernoulli$(p)$ distribution independently, $S_{\vec{b}}$ can be identified with $\mathtt{Sample}_{p}(S)$. Let $\theta_{\vec{b}}$ be the probability that $\vec{b}$ appears. More specifically, if $k$ out of $n$ entries of $\vec{b}$ is one, then $\theta_{\vec{b}}=p^{k}(1-p)^{n-k}$. With this notation, $M\circ\mathtt{Sample}_{p}(S)$ can be written as the following mixture:

Similarly, $M\circ\mathtt{Sample}_{p}(S)$ can also be written as a mixture, with an additional bit indicating the presence of $x_{0}$. Alternatively, we can divide the components into two groups: one with $x_{0}$ present, and the other with $x_{0}$ absent. Namely,

Note that $S_{\vec{b}}\cup\{x_{0}\}$ and $S_{\vec{b}}$ are neighbors, i.e. $M\circ\mathtt{Sample}_{p}(S^{\prime})$ is the mixture of neighboring distributions. The following lemma is the perfect tool to deal with it.

Let $I$ be an index set. For all $i\in I$, $P_{i}$ and $Q_{i}$ are distributions that reside on a common sample space. $(\theta_{i})_{i\in I}$ is a collection of non-negative numbers that sums to 1. If $f$ is a trade-off function and $T(P_{i},Q_{i})\geqslant f$ for all $i$, then

To apply the lemma, let the index be $\vec{b}\in\{0,1\}^{n}$, $P_{i}$ be $M(S_{\vec{b}})$ and $Q_{i}$ be $M(S_{\vec{b}}\cup\{x_{0}\})$. Condition $T(P_{i},Q_{i})\geqslant f$ is the consequence of $M$ being $f$-DP. The conclusion simply translates to

which is what we want. The proof is complete. ∎

Since $f$ is convex, Jensen’s inequality implies

Next we use a figure to justify the claim we made in Section 2.2 that “CLT approximation works well for SGD”. Recall that we argued in Section 3 that Algorithms 1 and 2 are $\min\{f,f^{-1}\}^{**}$-DP where

Appendix B Omitted Details in Section 3

The proof is mostly done in the main text, except the composition step. Let $V$ be the vector space that all $\theta_{t}$ live in and $\widetilde{M}=M\circ\mathtt{Sample}_{p}:X^{n}\times V\to V$ be the gradient update. We have already proved (using Proposition A.1) that for both Algorithms 1 and 2, if $S^{\prime}=S\cup\{x_{0}\}$, then $\widetilde{M}$ satisfies

Note that we cannot say $M$ is $f_{p}$-DP because T\big{(}M(S^{\prime}),M(S)\big{)} is not necessarily lower bounded by $f_{p}$. So we need a more specific composition theorem than stated in .

Suppose $M_{1}:X\to Y,M_{2}:X\times Y\to Z$ satisfy the following conditions for any $S,S^{\prime}$ such that $S^{\prime}=S\cup\{x_{0}\}$:

T\big{(}M_{1}(S),M(S^{\prime})\big{)}\geqslant f;

T\big{(}M_{2}(S,y),M_{2}(S^{\prime},y)\big{)}\geqslant g for any $y\in Y$.

Then the composition $M_{2}\circ M_{1}:X\to Y\times Z$ satisfies

for any $S,S^{\prime}$ such that $S^{\prime}=S\cup\{x_{0}\}$.

The theorem can be identically proved as Theorem 3.2 in .

is simply the composition of $T$ copies of $\widetilde{M}$, the above composition theorem implies that

For NoisyAdam, we argued that its privacy property is the same as NoisySGD in each iteration, so the above argument also applies, and we have the same conclusion. ∎

B.2 Justifying CLT for Algorithms 1 and 2

The main purpose of this section is to show the following theorem

Suppose $p$ depends on $T$ and $p\sqrt{T}\to\nu$. Then we have the following uniform convergence as $T\to\infty$

This theorem is the corollary of the following more general CLT on composition of subsample mechanisms and Lemma B.1 below.

Let $\{f_{ni}:1\leqslant i\leqslant n\}_{n=1}^{\infty}$ be a triangular array of (possibly asymmetric) trade-off functions and assume the following limits for some constants $K\geqslant 0$ and $s>0$ as $n\to\infty$:

Proof of this theorem exactly mimics that of Theorem 3.5 in , which we omit here for its length and tediousness.

Let $g(x)=-f^{\prime}(x)-1=|f^{\prime}(x)|-1$. Then

It suffices to compute the limits in the asymmetric Central Limit Theorem 7, namely

As in Lemma B.2, let $g(x)=-f^{\prime}(x)-1=|f^{\prime}(x)|-1$. The assumption expressed in terms of $g$ is simply

In particular, it implies $|g(x)|^{k}$ is integrable in $$for$k=2,3,4$. In addition, by Lemma B.2,

Changing the order of the limit and the integral in (9) is approved by the dominated convergence theorem. To see this, notice that $\log(1+x)\leqslant x$. The integrand in (9) satisfies

We already argued that $g(x)^{2}$ is integrable, so it works as a dominating function and the limit is justified. When $p\sqrt{T}\to\nu$, we have

So the constant $K$ in Theorem 7 is $\nu^{2}\cdot\chi^{2}(f)$.

By a similar dominating function argument,

Adding in the limit $p\sqrt{T}\to\nu$, we know $s^{2}$ in Theorem 7 is $\nu^{2}\cdot\chi^{2}(f)$.

Note the different power in $p$ in the denominator. It means $\kappa_{3}(f_{p})=o(p^{2})$ and hence $T\cdot\kappa_{3}(f_{p})\to 0$ when $p\sqrt{T}\to\nu$.

Hence all the limits in Theorem 7 check and we have a $G_{\mu}$ limit where

We finish the section by proving the formula in Lemma B.1.

The best calculation is done via better understanding. We point out that the functional $\chi^{2}$ is doing nothing more than computing the famous $\chi^{2}$-divergence. Recall that Neyman $\chi^{2}$-divergence (reverse Pearson) of $P,Q$ is defined as

If $f=T(P,Q)$ and $f(0)=1$, $f(x)>0$, for all $x<1$, then $\chi^{2}(f)=\chi^{2}(P\|Q)$.

This lemma is a straightforward corollary of Proposition B.4 in , which gives expressions for all $F$-divergenceWe use capital $F$ to avoid confusion with the notation of trade-off function.. In particular, if $f=T(P,Q)$ and $f(0)=1$, $f(x)>0,\forall x<1$, then $F$-divergence of $P,Q$ can be computed from their trade-off function as follows:

Neyman $\chi^{2}$-divergence corresponds to $F(t)=\frac{1}{t}-1$, so

With this formula, computing $\chi^{2}(G_{1/\sigma})$ is straightforward:

B.3 Proof of Theorems 1 and 2

Recall that Theorems 1 and 2 compare our CLT approach to moments accountant ($\mathtt{MA}$) from two different perspectives: $f$-DP perspective in Theorem 1 and $(\varepsilon,\delta)$-DP perspective in Theorem 2. We first show that Theorem 1 can be derived from Theorem 2. Then we prove a refined version of Theorem 2. To be more precise about the statement, let us first expand the notations used in the main text.

Let $\delta_{\texttt{MA}}(\varepsilon;\sigma,p,T)$ be the $\delta$ value computed by moment accountant method (described in detail below) for NoisySGD algorithm with subsampling probability $p$, iteration $T$ and noise scale $\sigma$. Similarly, $\delta_{\texttt{CLT}}(\varepsilon;\sigma,\nu)$ denotes the $\delta$ value computed for the same algorithm using central limit theorem assuming $p\sqrt{T}\to\nu$.

Let $f_{T}(\alpha)=\sup_{\varepsilon\geqslant 0}f_{\varepsilon,\delta_{\mathtt{MA}}(\varepsilon)}(\alpha)$. It is supported by $f_{\varepsilon_{T},\delta_{\mathtt{MA}}(\varepsilon_{T})}$ at $\alpha$. Theorem 2 says this supporting function is smaller than that of $G_{\mu_{\mathtt{CLT}}}$ at $\alpha$ by a strict gap. Taking the limit, $\limsup_{T\to\infty}f_{T}(\alpha)$ has at least that much gap from $G_{\mu_{\mathtt{CLT}}}(\alpha)$, which proves Theorem 1.

Theorem 2 is a straightforward corollary of the following proposition. Note that the inequality is reversed compared to the statement of Theorem 2 so that the gap is positive, which also turns $\limsup$ into $\liminf$.

Let us first describe how the two methods compute $\delta$ from $\varepsilon$.

In , it has been shown that Algorithm 1 (hence also the Adam variant, Algorithm 2) with subsampling probability $p$, iteration $T$ and noise scale $\sigma$ is $(\varepsilon,\delta)$-DP for each $\varepsilon\geqslant 0$ if $\delta=\delta_{\mathtt{MA}}(\varepsilon;\sigma,p,T)$. To evaluate the infimum, the domain is discretizedCode in tensorflow/privacy discretizes at $[1.25,1.5,1.75,2.,2.25,2.5,3.,3.5,4.,4.5,5,6,7,\ldots,63,64,128,256,512]$.. This results in the numerical moment accountant method that is actually implemented. Since $\delta_{\mathtt{nMA}}(\varepsilon;\sigma,p,T)\geqslant\delta_{\mathtt{MA}}(\varepsilon;\sigma,p,T)$, Algorithm 1 is also $(\varepsilon,\delta)$-DP with $\delta=\delta_{\mathtt{nMA}}(\varepsilon;\sigma,p,T)$.

We have just explained how $\mathtt{MA}$ and CLT works. Next we prove Proposition B.4

On the other hand, using Lemma B.5, we get

Setting $p=\frac{\nu}{\sqrt{T}}$, we would like to take limit on both sides of (10). First notice that $f_{T}$ converge pointwise to $G_{\mu_{\texttt{CLT}}}$, which we have already proven in Section B.2. The limit of $x_{T}$ is taken care of in the following lemma:

Combining these results, we can take limits on both sides of (10):

The Rényi divergence can also be computed from the trade-off function, just like the $\chi^{2}$-divergence. In fact, under the same assumptions as in Lemma B.1, we have

This identity will be the bridge between $\alpha_{\textup{GM}}$ and $f_{T}$.

On one hand, $\alpha_{\textup{GM}}(\lambda;\sigma,p)$ is the maximum of two Rényi divergences, so

The last step is the tensorization identity of Rényi divergence.

Since $f_{T}$ converges uniformly to $G_{\mu_{\texttt{{CLT}}}}$ in $$, we have uniform convergence$f_{T}^{*}\to G_{\mu_{\texttt{{CLT}}}}^{*}$. By convexity of these functions, the convergence also implies the convergence of derivatives (See Theorem 25.7 of ), namely,

We can solve for $x^{*}$ using the expression of $G_{\mu}$ (6). After some algebra, we have