An Adaptive and Fast Convergent Approach to Differentially Private Deep Learning

I Introduction

The past decade has witnessed the remarkable success of deep learning techniques in various machine learning / data mining tasks, such as signal processing , network modeling and traffic analysis . The great success relies heavily on the massive collection of user data, which, however, often raise severe privacy and security issues. For example, Fredrikson et al. , demonstrates that the individual privacy information in the training dataset can be recovered by repeatedly querying the output probabilities of a disease recognition classifier built upon a convolutional neural network (CNN). Existing privacy concerns are likely to discourage users from sharing their data and thereby obstruct the future development of deep learning itself.

This paper studies the problem of user privacy protection in the training process of neural models. We consider the white-box scenario where an adversary has access to the parameters of a trained model. In this scenario, many service providers allow users to download models to their personal devices (e.g., computers and smart phones), and malicious users could analyze the parameters of the model which may expose personal information in the training dataset.

I-B Limitations of Prior Art

To address the privacy issue, several differential privacy (DP) based approaches were proposed, which may be classified into two categories: data obfuscation and gradient obfuscation. Data obfuscation based approaches obfuscate data with noise prior to potential exposure of sensitive information . These approaches may suffer from significant accuracy degradation of the trained model. The reason is that to guarantee the differential privacy bound, the added noise may be excessively intense and make differently labeled training instances almost indistinguishable. In contrast to data obfuscation, gradient obfuscation based approaches add noise to the gradient in the training process . However, they may not circumvent the accuracy degradation issue completely. Although some methods aim to improve the accuracy of gradient obfuscation , they have three key limitations. First, the privacy cost is high because the convergence speed of these methods is slow while the privacy cost is accumulated for each gradient calculation. Second, the accuracy still cannot meet the high-precision requirements of many applications since they add identically distributed noise to all components of the gradient which results in large distortion of the original gradient. Third, these methods are computationally inefficient because they need to evaluate the model multiple times or solve a large-scale optimization problem per iteration which make the task computationally prohibitive.

I-C Proposed Approach

In this paper, we propose AdaDp, an adaptive and fast convergent approach to differentially private deep learning. Our key observation is that different components of the gradient have inhomogeneous sensitivity to the training data. In light of this observation, AdaDp mitigates the influence of noise on the model performance by adaptively sampling noise from different Gaussian distributions, based on the sensitivity of each component. In the first stage, AdaDp adjusts the learning rate in an adaptive manner based on historical gradients such that infrequently updated components tend to have a larger learning rate. Then, AdaDp samples noise from different Gaussian distributions according to the sensitivity of each gradient component and constructs differentially private gradients by adding the sensitivity-dependent noise to the original gradient. In this way, Gaussian noise with a lower variance is added to components with a smaller sensitivity.

Compared to existing data obfuscation and gradient obfuscation based methods, AdaDp has three key advantages.

First, the privacy cost of AdaDp is low because it exhibits remarkable improvement in the convergence speed due to an adaptive learning rate. Since the privacy cost is accumulated on each gradient update, a faster rate of convergence indicates that training a model using AdaDp incurs lower privacy cost.

Second, AdaDp achieves both a provable privacy guarantee and a comparable accuracy to non-differentially private models simultaneously. We will show later that this is attained by adding adaptive noise to different gradient components, depending on their sensitivity. As the model converges, we will see a decrease in the expected sensitivity of each gradient component, which thereby reduces the variance of noise distribution. In other words, in contrast to prior works, the noise distribution of AdaDp is adaptive to not only different gradient components but also different training iterations.

Third, AdaDp is computationally efficient since it does not need to solve any optimization problem to determine the noise distribution at each iteration, in sharp contrast to that requires solving a large-scale non-convex optimization problems. We design an efficient scheme for adjusting the noise distribution and the scheme is evaluated via both theoretical analysis and numerical experiments.

I-D Technical Challenges and Solutions

First, it is technically challenging to mathematically analyze the influence of the noise distribution upon the prediction performance, in light of the complicated nature of deep neural networks. As an alternative, we analyze the sufficient and necessary condition for noise distributions to guarantee the target differential privacy level. The condition involves an inequality with respect to the sensitivity of each gradient component and the variance of each corresponding Gaussian distribution. Based on the analysis, we conduct an experiment to compare the influence of different noise distributions upon the original function which can be seen as a query on a dataset. According to the theoretical and experiment results, we propose a heuristic that adapts the noise distributions to the sensitivity of each gradient component. Finally, we perform another experiment to verify the effectiveness of this heuristic according to the influence of noise on the gradient descent algorithm which is widely used for optimizing deep learning models.

Another technical challenge is to compute the privacy cost without any assumptions on the parameters such as the noise level and the sampling ratio. This is in sharp contrast to prior methods. For example, the moments accountant method requires the noise level $\sigma\geq 1$ and the sampling ratio $q<\frac{1}{16\sigma}$ . To remove the assumptions, we use a technique termed subsampled Rényi differential privacy (RDP) , which computes the privacy cost by analyzing the privacy amplification in the subsampling scenario. And importantly, it requires no assumption on the parameters in the analysis .

I-E Summary of Experiment Results

We evaluated the privacy cost, the accuracy and the computational efficiency of AdaDp and baselines on two real datasets: MNIST and CIFAR-10 . The results show that AdaDp outperforms state-of-the-art methods with 50% privacy cost reduction. On MNIST and CIFAR-10, AdaDp achieves an improvement of up to 4.3% and 3.5%, respectively, in accuracy over state-of-the-art methods. Our experimental results also show that the processing time of AdaDp at each iteration is much less than that of , validating the computational efficiency of AdaDp.

II Related Work

To protect sensitive information in crowdsourced data collection, differentially private crowdsourcing mechanisms were designed . To preclude personal information from being inferred and/or identified from neural models , a line of works emerged which applied DP to deep learning . For instance, integrate DP into a teacher-student framework to protect data on student nodes. study transferring features or gradients with privacy control in collaborative deep learning. apply DP to personal data collection. In the above works, black-box attacks are (implicitly) assumed, i.e., the learned model is inaccessible to adversaries. Other works studied privacy protection in a more realistic white-box model where adversaries may have full knowledge of the model . proposes a differentially private gradient descent algorithm DpSgd by adding Gaussian noise to the gradient. uses an adaptive learning rate to improve the convergence rate and reduce the privacy cost. introduces the Laplace mechanism such that the privacy budget consumption is independent of the number of training steps. allocates different privacy budgets to each training iteration to counteract the influence of noise on the gradient. In all aforementioned works, however, the noise on each gradient component follows the same probability distribution. As a result, the original gradient is distorted to a large extent. Although samples noise from different distributions for each gradient component, solving a large-scale optimization is required at every step.

III Our Approach

To reduce the privacy cost, AdaDp uses an adaptive learning rate for acceleration of the convergence. Additionally, AdaDp adds inhomogeneous and adaptive noise to different coordinates of the gradient based on their sensitivity in order to mitigate the influence of noise on the model performance. The next two subsections elaborate the adaptive learning rate and noise respectively. Then we present AdaDp and show its differential privacy guarantee.

The most popular method for training deep models is the gradient-descent-type algorithms. They iteratively update the parameters of a model by moving them in the direction opposite to the gradient of the loss function evaluated on the training data. The loss function $\mathscr{\mathcal{L}}$ is the difference between the predictions and the true labels. To minimize the loss $\mathscr{\mathcal{L}}(\theta)$, stochastic gradient descent (Sgd) randomly chooses a subset of training data (denoted by $S$) at each iteration and performs the update $\theta\leftarrow\theta-\eta\frac{1}{|S|}\sum_{i\in S}\nabla_{\theta}\mathcal{L}(\theta,\,x_{i})$. Sgd poses several challenges, e.g., selection of a proper learning rate and avoidance of local minimum traps.

More advanced optimizers, including RMSProp, Adam, Adadelta and Nadam, are proposed to address the above issues. They adjust the learning rate on a per-parameter basis in an adaptive manner and scale the coordinates of the gradient according to historical data.

AdaDp uses an adaptive strategy similar to that of RMSProp. Nevertheless, we would like to note that the framework proposed in this paper is applicable to other adaptive gradient-descent-type algorithms. Recall the update of RMSProp

where ${\theta_{t}}$ denotes the parameters at step ${t}$, ${g_{t}}$ denotes the original gradient, ${\eta}$ is the learning rate, and ${\epsilon_{0}}$ is the smoothing term (in case that the denominator is 0).

III-B Adaptive Noise

The intuition of adaptive noise is that different coordinates of the gradient exhibit inhomogeneous sensitivities due to their different values. It significantly affects the direction of the gradient if noise with higher intensity is added to coordinates with a smaller value, and vice versa. In light of this intuition, AdaDp clips the gradient and adds Gaussian noise with a smaller/larger variance to dimensions of the clipped gradient with a smaller/larger sensitivity.

To prove Lemma 1, we need an auxiliary result which involves the sufficient and necessary condition on the privacy loss variable to satisfy $(\epsilon,\delta)$-DP.

A mechanism $M$ is $(\epsilon,\delta)$-DP if and only if for each $D,D^{\prime}$, the following holds:

where $l_{M,D,D^{\prime}}$ is the privacy loss variable defined by $\ln{\frac{\Pr\left(M(D)=o\right)}{\Pr\left(M(D^{\prime})=o\right)}}$.

We are now ready to present the proof of Lemma 1.

The first step is to show that $l_{M,D,D^{\prime}}$ is a Gaussian random variable. Let $(r_{1},\dots,r_{m})=o-f(D)$. We consider the worst case of $l_{M,D,D^{\prime}}$. In this case, we have $(s_{1},\dots,s_{m})=f(D)-f(D^{\prime})$, which yields $(r_{1}+s_{1},\dots,r_{m}+s_{m})=o-f(D^{\prime})$. As a result, the following equations hold

In light of $r_{j}\sim\mathcal{N}(0,\sigma_{j}^{2})$, we obtain that $l_{M,D,D^{\prime}}=\sum_{j}^{m}\frac{s_{j}^{2}}{2\sigma_{j}^{2}}+\sum_{j}^{m}\frac{r_{j}s_{j}}{\sigma_{j}^{2}}$ also obeys a Gaussian distribution. Specifically, we have $l_{M,D,D^{\prime}}\sim\mathcal{N}(\sum_{j}^{m}\frac{s_{j}^{2}}{2\sigma_{j}^{2}},\sum_{j}^{m}\frac{s_{j}^{2}}{\sigma_{j}^{2}})$. If we let $H$ denote $\sum_{j}^{m}\frac{s_{j}^{2}}{\sigma_{j}^{2}}$, it can be re-written as $l_{M,D,D^{\prime}}\sim\mathcal{N}(\frac{H}{2},H)$.

The second step is to show that $\Pr\left(l_{M,D,D^{\prime}}\geq\epsilon\right)-e^{\epsilon}\Pr\left(l_{M,D^{\prime},D}\leq-\epsilon\right)$ is monotonically increasing in $H$. Let us compute the first term

where $A(H)=\frac{\sqrt{H}}{2}-\frac{\epsilon}{\sqrt{H}}$. Similarly, the second term can be re-written as

where $A^{\prime}(H)=\frac{-\epsilon}{\sqrt{H}}-\frac{\sqrt{H}}{2}$.

Then the derivative of $\Pr\left(l_{M,D,D^{\prime}}\geq\epsilon\right)-e^{\epsilon}\Pr\left(l_{M,D^{\prime},D}\leq-\epsilon\right)$ about $H$ is:

Since $(A^{\prime}(H))^{2}=(A(H))^{2}+2\epsilon$, then we have

Therefore, $\Pr\left(l_{M,D,D^{\prime}}\geq\epsilon\right)-e^{\epsilon}\Pr\left(l_{M,D^{\prime},D}\leq-\epsilon\right)$ is monotonically increasing with $H$.

Then if a function $f(\cdot)$ that $\Delta_{f}\leq 1$ satisfies $(\epsilon,\delta)$-DP with $\sigma_{*}$, the privacy loss variable $l^{*}_{M,D,D^{\prime}}$ must satisfy Eq. 2. Note that $l^{*}_{M,D,D^{\prime}}$ is a Gaussian variable that $l^{*}_{M,D,D^{\prime}}\sim\mathcal{N}(\frac{H_{*}}{2},H_{*})$ where $H_{*}=\sum_{j}^{m}\frac{(s^{*}_{j})^{2}}{\sigma_{*}^{2}}=\frac{1}{\sigma_{*}^{2}}$. Since the left part of Eq. 2 is monotonically increasing with $H$, Eq. 2 will hold for $H^{\prime}$ if $H^{\prime}\leq H_{*}$, namely $\sum_{j}^{m}\frac{s_{j}^{2}}{\sigma_{j}^{2}}\leq\frac{1}{\sigma_{*}^{2}}$. ∎

Lemma 1 shows the condition of differential privacy when we add noise from Gaussian distributions with different variances to different dimensions of a query function. For example, suppose we have a $2$-dimension query function $f^{\prime}(\cdot)$, and $s_{1}=12.0,s_{2}=6.0$. If mechanism $M$ satisfies $(\epsilon,\delta)$-DP with $\sigma_{*}=1.0$, then mechanism $M^{\prime}$ satisfies the same $(\epsilon,\delta)$-DP with $\sigma_{1}=17.0$ and $\sigma_{2}=8.5$ since $\frac{12.0^{2}}{17.0^{2}}+\frac{6.0^{2}}{8.5^{2}}\leq\frac{1}{1.0^{2}}$. Namely, we sample noise with standard deviation $17.0$ for the first dimension and $8.5$ for the second dimension of $f^{\prime}(\cdot)$. In contrast, previous methods sample noise from the same Gaussian distribution $\mathcal{N}(0,13.5^{2})$ for each dimension of $f^{\prime}(\cdot)$ since $\frac{12.0^{2}}{13.5^{2}}+\frac{6.0^{2}}{13.5^{2}}\leq\frac{1}{1.0^{2}}$.

Continue with the above example, we conducted a numerical experiment to compare the influence of different noise distributions on the original query function. Specifically, we calculate cosine similarity between the noisy result ($M^{\prime}(D)$) and the original result ($f^{\prime}(D)$). As a metric of such influence, the higher similarity two results have, the less the influence of noise on the original query function. Without loss of generality, we assume $f^{\prime}(D)=(10.0,5.0)^{T}$ given that $s_{1}=12.0,s_{2}=6.0$. We then sample noise 10000 times and compute the average cosine similarity. When we set $\sigma_{1}=17.0$ and $\sigma_{2}=8.5$, the average cosine similarity between the noisy result and the original result is 0.52. However, when we set $\sigma_{1}=\sigma_{2}=13.5$, the average is only 0.36. Another strategy is to set $\sigma_{1}=12.4$ and $\sigma_{2}=24.8$, the cosine similarity in this scenario is reduced to 0.28. Note that like the third strategy, the optimization techniques in tend to sample noise with higher variance for dimensions with smaller sensitivity. In other words, this numeric experiment shows that coordinates of the query function with larger sensitivity can tolerate noise with higher variance.

To gain more insight into the advantages of adaptive noise, we illustrate and compare the updates of AdaDp, DpSgd, and their non-private counterparts by testing them on the Beale function $f(x,y)=(1.5-x+xy)^{2}+(2.25-x+xy^{2})^{2}\text{+}(2.625-x+xy^{3})^{3}$, as shown in Figs. 1(a) and 1(b). In this experiment, we set $\gamma=0.1$, $\gamma^{\prime}=0.9$, $\beta=1.5$ and $G=10^{-6}$.

We observe that the trajectory of DpSgd exhibits a remarkable deviation from that of its non-private version, while AdaDp and its non-private version display similar trajectories. Quantitatively, We define the distance between two trajectories $P=\{p_{i}\}_{i=1}^{n}$ and $Q=\{q_{i}\}_{i=1}^{n}$ of the same length as $D(P,Q)=\frac{1}{|P|}\sum_{i=1}^{n}{\|p_{i}-q_{i}\|_{2}}$. Note that the length of a trajectory is the number of training iterations. The distance between the trajectories of DpSgd and its non-private version is 0.90 and the distance between AdaDp and its non-private version is 0.21. Experiments on all widely used test functions for optimization also show similar results.

The above experiment suggests that adaptive noise can mitigate the deviation of the noisy result from the original result and the performance of AdaDp is more robust to the privacy-protecting Gaussian noise than DpSgd. Recall that DpSgd adds Gaussian noise with the same intensity to all dimensions. In contrast, AdaDp updates each dimension separately and the intensity of the added Gaussian noise relies on the sensitivity of each dimension of the gradient.

III-C Algorithm and Main Results

Output: ${\theta_{T}}$ and privacy cost ${(\epsilon,\delta)}$

Before presenting our main results on the privacy guarantee of AdaDp, let us review the definition of differential privacy.

A randomized mechanism $M$ satisfies $(\epsilon,\delta)$-differential privacy, if for any two neighboring datasets $D$ and $D^{\prime}$ that differ only in one tuple, and for any possible subset of outputs $\mathcal{O}$ of $M$, we have

where $\Pr(\cdot)$ denotes the probability of an event. If $\delta=0$, $M$ is said to satisfy $\epsilon$-differential privacy.

We now show the privacy guarantee of AdaDp in Theorem 1.

Let $\binom{\cdot}{\cdot}$ denote the binomial coefficient and $B(l)=\sum_{i=0}^{l}(-1)^{i}\binom{l}{i}e^{(i-1){i}/{(2\sigma_{*}^{2})}}$. Given a privacy budget $(\epsilon,\delta)$, the sampling ratio $q=\frac{L}{N}$ and any integer $\alpha\geq 2$, if the noise scale $\sigma_{i}$ in Algorithm III-C satisfies $\sum_{i}^{m}\frac{s_{i}^{2}}{\sigma_{i}^{2}}\leq\frac{1}{\sigma_{*}^{2}}$ and $\sigma_{*}$ satisfies

then Algorithm III-C is $(\epsilon,\delta)$-differentially private.

To prove Theorem 1, we use the techniques of RDP to analyze the privacy cost of the composition of Gaussian mechanisms. The results that we obtain via RDP are later translated to DP.

Given two probability distributions $P$ and $Q$, the Rényi divergence between $P$ and $Q$ with order $\alpha>1$ is defined by

Our proofs are based on the three key properties of RDP, as stated in Lemmas 3, 4 and 5.

If $\|f(\cdot)\|_{2}\leq 1$, then the Gaussian mechanism $M(D)=f(D)+\mathcal{N}(0,\sigma^{2})$ satisfies $(\alpha,\alpha/(2\sigma_{2}))$-RDP.

For two randomized mechanisms $f,g$ such that $f$ is $(\alpha,\epsilon_{1})$-RDP and $g$ is $(\alpha,\epsilon_{2})$-RDP, the composition of $f$ and $g$ which is defined as $(X,Y)$ (a sequence of results), where $X\sim f$ and $Y\sim g$, satisfies $(\alpha,\epsilon_{1}+\epsilon_{2})$-RDP.

Lemma 6 analyzes the privacy amplification in the subsampling setting.

Define function $B(\epsilon,l)=\sum_{i=0}^{l}(-1)^{i}\binom{l}{i}e^{(i-1)\epsilon(i)}$. Given a dataset $D$ of $n$ records and a Gaussian mechanism $f$ satisfying $(\alpha,\epsilon(\alpha))$-RDP, define a new randomized mechanism $f\circ\mathbf{subsample}$ as: (1) subsample $m$ records where $q=m/n$, (2) apply these $m$ records as the input of mechanism $f$, then for any integer $\alpha>1$, $f\circ\mathbf{subsample}$ satisfies $(\alpha,\epsilon^{\prime}(\alpha))$-RDP, where:

Before showing the proof of Theorem 1, we need to establish the following important lemma. In Lemma 7, we bound the noise level $\sigma$ of a Gaussian mechanism in the subsampling setting.

Given the sampling probability $q=L/N$, the number of steps $T$, the Gaussian mechanism $M=f(\cdot)+\mathcal{N}{(0,\sigma^{2})}$ where $\|f(\cdot)$ $\|_{2}\leq 1$, then the composition of $T$ these mechanisms satisfies $(\epsilon,\delta)$-differentially private if $\sigma$ satisfies:

where $\alpha$ can be any integer satisfying $\alpha\geq 2$ and the function $B$ is defined as $B(l)=\sum_{i=0}^{l}(-1)^{i}\binom{l}{i}e^{(i-1){i}/{(2\sigma^{2})}}$.

By Lemma 3, we could compute $B(\epsilon,l)$ defined in Lemma 6 on Gaussian mechanisms as

Since a lot used in AdaDp is a subsample of the training dataset, each step is $(\alpha,\epsilon^{\prime}(\alpha))$-RDP where $\epsilon^{\prime}(\alpha)$ satisfies (6) in Lemma 6. Then after $T$ training steps of AdaDp, we could obtain the total privacy cost $(\alpha,T\epsilon^{\prime}(\alpha))$ via composing such $T$ subsampled Gaussian mechanisms depending on Lemma 4. Then by substituting the function $B(\epsilon,l)$ in (6) with (11), $T\epsilon^{\prime}(\alpha)$ can be clearly expressed as

At last, through converting $(\alpha,T\epsilon^{\prime}(\alpha))$ to DP representation via Lemma 5, AdaDp satisfies $(T\epsilon^{\prime}(\alpha)+\frac{\log(1/\delta)}{\alpha-1},\delta)$-DP. Let $T\epsilon^{\prime}(\alpha)+\frac{\log(1/\delta)}{\alpha-1}\leq\epsilon$ where $\epsilon$ is the given privacy budget and combine this with (III-C) as follows:

Combining Lemma 1 and Lemma 7, Theorem 1 is easy to prove. Suppose we use $M(D)=f(D)+Z$ as a Gaussian mechanism at training step $t$ in Section III-C, then the composition of such $T$ mechanisms satisfies Eq. 9. Based on Lemma 1, if we use $M^{\prime}(D)=f^{\prime}(D)+Z^{\prime}$ at each training step $t$ in which $\sum_{i=1}^{m}\frac{s_{i}^{2}}{\sigma_{i}^{2}}\leq\frac{1}{\sigma_{*}^{2}}$, then $M^{\prime}(D)$ satisfies the same differential privacy guarantee as $M(D)$. Therefore, the proof of Lemma 7 is also suitable for $M^{\prime}(D)$. Combine this fact with the post-processing property of DP , the proof is completed.

We would like to remark that Theorem 1 covers the realm of small noise and high sampling ratio that the moments accountant method omits (which requires $\sigma\geq 1$ and $q<\frac{1}{16\sigma}$). For instance, if we train a model using AdaDp with $L=600$ and $\sigma_{*}=0.9$ on a dataset of $N=60000$ examples, Theorem 1 bounds the privacy cost by choosing the optimal $\alpha=6$ and implies that the model achieves $(4.0,10^{-5})$-differential privacy after 1800 training steps.

IV Experimental Results

We evaluate the privacy cost, the accuracy and the computational efficiency of AdaDp compared with state-of-the-art methods: DpSgd , AGD and DpOpt on two real datasets: MNIST and CIFAR-10. We implemented all these algorithms using TensorFlow with a GTX 1080Ti GPU.

MNIST is a standard dataset for handwritten digit recognition, which consists of 60,000 training examples and 10,000 testing examples. Each example is a $28\times 28$ gray-level image. CIFAR-10 consists of 60,000 labeled examples of $32\times 32$ RGB images. There are 50,000 training images and 10,000 testing images.

The model for MNIST task first performs a 60-dimensional differentially private PCA (DpPCA) projection and then applies a single 1,000-unit ReLU hidden layer . For the CIFAR-10 task, we use a variant of AlexNet , which contains two convolutional layers followed by two fully connected layers and one softmax layer. The first convolutional layer includes 64 filters of size $5\times 5$ with stride 1. The layer is followed by the ReLU activation, $2\times 2$ max pooling, and local response normalization. The structure of the second convolutional layer is identical to that of the first one except that the local response normalization is performed before max pooling. The output is then flattened into a vector as the input for the following fully connected layer.

As outlined in Section III-C, we compute gradients for each training example. However, it is prohibitive to compute per-example gradients due to the parameter sharing scheme of convolutional layers. Since convolutional layers are shown to be well transferred , we pre-train the model on CIFAR-100 and initialize the network with the trained parameters. When we train it on CIFAR-10, the parameters of convolutional layers are maintained and updates happen to the fully connected layers and the softmax layers.

We use the result of Theorem 1 to calculate the privacy cost. Specifically, given $\epsilon$, $\sigma_{*}$, and $q$, at each iteration, we select $\alpha$’s from $\{2,3,\dots,64\}$ and determine the smallest $\delta_{*}$ that satisfies (1) in Theorem 1. The privacy cost is the pair $(\epsilon,\delta_{*})$.

For AdaDp, we set $\gamma=0.1$, $\gamma^{\prime}=0.9$ and $G=10^{-6}$ in all experiments. For AGD, since it was only evaluated on shallow machine learning tasks in , its privacy computation is not suitable for deep learning as it does not consider the privacy amplification due to subsampling. Therefore, we use Theorem 1 to compute the privacy guarantee for AGD to give a fair comparison. To implement DpOptIn the equation that precedes (10a) in , the quadratic term in the moment generating function of a Gaussian distribution was missing. This equation should be $\sum_{i}^{d}\frac{\Delta_{i}^{2}}{\sigma_{i}^{2}}\leq\frac{2\epsilon}{1+\lambda}+\frac{2}{\lambda+\lambda^{2}}\ln{\delta}$., we use the projected gradient descent algorithm and optimize the objective function with 50 steps as the same as .

IV-B Privacy Cost

To illustrate the trade-off between the privacy cost and the accuracy, we measured the privacy cost of AdaDp and DpSgd to attain a pre-specified accuracy level. We set the noise level $\sigma_{*}=3.0$ and $\sigma_{p}=6.0$ on MNIST and $\sigma_{*}=4.0$ on CIFAR-10, where $\sigma_{p}$ is the noise level for DpPCA .

Compared with DpSgd (as a representative method with a non-adaptive learning rate), AdaDp achieves an average reduction of 54% and 46% in privacy cost on MNIST and CIFAR-10 respectively. Table I summarizes the results, where $\epsilon_{D}$ and $\epsilon_{A}$ denote the minimum privacy cost required by DpSgd and AdaDp, respectively, to attain the pre-specified accuracy level. We observe that AdaDp always requires much lower privacy cost than DpSgd to achieve the same accuracy level. This is mainly due to the faster convergence and fewer training steps of AdaDp.

IV-C Accuracy

The accuracy achieved by AdaDp significantly outperforms that of DpSgd, AGD and DpOpt under all three privacy levels on both MNIST and CIFAR-10 datasets. Fig. 2 illustrates how the accuracy varies with the number of epochs and $\delta_{*}$ on MNIST. The gray line and the black line (please refer to the right vertical axis) denote the accumulating privacy cost for AGD and other methods respectively in terms of $\delta_{*}$ given a fixed $\epsilon$. We observe that the final test accuracy of AdaDp on the MNIST achieves an increase of $5.9\%$, $2.7\%$ and $1.0\%$ respectively compared with DpSgd, $8.8\%$, $9.5\%$ and $6.7\%$ respectively compared with AGD, $4.3\%$, $1.5\%$ and $0.7\%$ respectively compared with DpOpt. The results on CIFAR-10 are shown in Fig. 3. In all three settings, AdaDp achieves an accuracy increase of 3.2%, 5.3% and 4.8% respectively compared with DpSgd, $8.5\%$, $8.0\%$ and $6.9\%$ respectively compared with AGD, $2.1\%$, $3.5\%$ and $3.2\%$ respectively compared with DpOpt.

We now analyze how we achieve higher accuracy than each state-of-the-art method respectively. Compared with DpSgd, the performance improvement of AdaDp is achieved by both the adaptive learning rate and the adaptive noise. As to AGD, $\sigma$ in this algorithm can only decrease gradually which cannot be reversed such that the privacy budget is consumed too fast. Generally, a few epochs of training are not enough to guarantee the convergence for deep learning models. Therefore, AGD performs poorly in deep learning. For DpOpt, on the one hand, AdaDp adopts an adaptive learning rate to improve the convergence. On the other hand, as our first numeric experiment indicates, AdaDp samples noise with higher variance for dimensions of the gradient with larger sensitivity which mitigates the influence of noise significantly. In addition, the expected variance of each noise distribution will gradually decrease as the training progresses.

IV-D Computational Efficiency

In addition, we evaluate the average processing time of AdaDp, DpSgd, AGD and DpOpt per iteration, as a measure of computational efficiency. The time involves processing a whole batch where we set the batch size as 120 on MNIST and 32 on CIFAR-10 respectively. Other settings are the same as Fig. 2(a) and Fig. 3(a) respectively.

AdaDp is much more computationally efficient than both AGD and DpOpt. The results are shown in Table II. We observe that for each iteration, the average processing time of AdaDp is close to that of DpSgd which is far shorter than the other two algorithms. Note that AGD repeatedly evaluates the model multiple times to obtain the best update step size while DpOpt needs to solve a non-convex optimization problem with variables as many as the parameters of the deep learning model. In contrast to AGD and DpOpt, AdaDp adopts a heuristic to avoid heavy computation at each iteration.

IV-E Micro Benchmarks

Considering there are two components in AdaDp, namely the adaptive learning rate and the adaptive noise, we study their independent contribution to the final performance in this subsection. We call the methods with only one component AdaL (only adaptive learning rate) and AdaN (only adaptive noise) respectively. AdaL uses global clipping method to clip the original gradient and samples noise for each dimension from the same Gaussian distribution. The only difference between AdaL and DpSgd is that AdaL adjusts the learning rate based on Eq. 1. As to AdaN, we implement it directly by removing the adaptive learning rate part in AdaDp. For the experiment on MNIST, the learning rate is set to 0.1 and 0.001 for AdaN and AdaL respectively. Other settings are the same as Fig. 2(a). On CIFAR-10, the learning rate is set to 0.05 and 0.001 for AdaN and AdaL respectively and other settings are the same as Fig. 3(a).

Both adaptive components contribute to the performance gain of AdaDp while the adaptive noise component contributes more. As illustrated in Fig. 4(a) and Fig. 4(b), we observe that AdaN achieves a higher accuracy than AdaL, showing that, compared with the adaptive learning rate, the adaptive noise component has a more significant impact on the performance of AdaDp.

Additionally, as aforementioned, given the expected sensitivity of the gradient decreases with the training progresses, each $\sigma_{i}$ will also decrease gradually. We select the $\sigma_{i}$ in AdaDp at the $100$th iteration and the $1000$th iteration respectively to illustrate this property. All the settings are the same as Fig. 2(a).

The standard deviation of most noise distributions for each coordinate of the gradient gradually decreases as the training progresses. As shown in Fig. 4(d) (the area of each circle is proportional to the value of $\sigma_{i}$), we observe that most $\sigma_{i}$ at the $1000$th iteration (the figure below) are more concentrated in the range less than 10 while there are many $\sigma_{i}$ distributed from 10 to 20 at the $100$th iteration (the figure above). Therefore, the noise distributions in AdaDp are adaptive not only to each dimension of the gradient, but also to different iterations during training.

IV-F Impact of Parameters

Learning Rate. As shown in Fig. 5(a), the accuracy stays consistently above 93%, irrespective of the learning rate ranging from $0.08\times 10^{-2}$ to $0.5\times 10^{-2}$. When the learning rate is lower than $2\times 10^{-2}$, the accuracy increases with the learning rate. When it is higher than $2\times 10^{-2}$, a higher learning rate results in a lower accuracy.

Noise Scale. The noise scale determines the amount of Gaussian noise added to the update term at each step. Although a smaller noise scale mitigates the effect of noises, it results in fewer training steps and the model is hard to converge. Meanwhile, setting a larger noise scale allows more training steps, but excessive noise will ruin the original gradient. Results achieved with different noise scales are shown in Fig. 5(c), where our model attains the most superior performance with $\sigma_{*}=7.0$. Compared with DpSgd, which reaches the highest accuracy at $\sigma_{*}=4.0$ , we attribute the much larger value of $\sigma_{*}$ of AdaDp to adaptive noises which alleviate the impact of the differential privacy mechanism and a larger noise scale yields more training steps.

Lot Size. The lot size controls the sampling ratio. A large lot size yields a higher sampling ratio and reduces the number of training steps. If the noise intensity is fixed, a smaller lot size results in a more notable effect of Gaussian noise. Fig. 5(d) shows the accuracy vs. the lot size. It can be observed that as the lot size grows, the performance increases initially, peaks at $L=800$, and finally declines. The result agrees with the above analysis that too high too low sampling ratio will incur performance degradation.

V Conclusions

In this paper, our key contribution is three-fold. First, we propose a differentially private deep learning algorithm which leads to a faster convergence and higher accuracy in comparison with prior methods. Second, we intuitively analyze advantages of AdaDp over DpSgd and mathematically prove that AdaDp satisfies differential privacy by more advanced analytic tools. Third, we applied AdaDp, DpSgd, AGD and DpOpt for model training of deep learning networks with real-world datasets and experimentally evaluate the better performance of AdaDp.

References