AdaCliP: Adaptive Clipping for Private SGD

Introduction

Machine learning models are widely deployed in various applications such as image classification , natural language processing , and recommendation systems . Most state-of-the-art machine learning models are trained on user data, examples include keyboard models , automatic video transcription among others. User data often contains sensitive information such as typing histories, social network data, financial and medical records. Hence releasing such machine learning models to public requires rigorous privacy guarantees while maintaining the performance.

Of the various privacy mechanisms, differential privacy has emerged as the well accepted notion of privacy. The notion of differential privacy provides a strong notion of individual privacy while permitting useful data analysis in machine learning tasks. We refer the reader to for a survey. Originally used for database queries, it has been adapted to provide privacy guarantees for machine learning models. Informally, for the output to be differentially private, the estimated model and all of its parameters should be indistinguishable whether a particular client’s data was taken into consideration or not.

Differential privacy for machine learning has been studied in various models including models with convex objectives and more recently deep learning methods . One particular set of algorithms for learning differentially private machine learning models can be interpreted as noisy stochastic gradient descent (SGD) . At each iteration of SGD, these algorithms modify the gradients suitably to provide differential privacy.

In this paper, we ask if there is a systematic, theoretically motivated, principled approach to obtain an optimal modification strategy. Motivated by the convergence guarantees of SGD, we propose a new differentially private SGD algorithm called AdaCliP. Compared to the previous methods, AdaCliP achieves the same privacy guarantee with much less added noise by using coordinate-wise adaptive clipping of the gradient. Since the convergence of SGD depends on the variance of the gradient, this approach improves the learned model quality. We empirically evaluate the performance of differentially private SGD techniques on MNIST dataset using various machine learning models, including neural networks. Our experiments show that AdaCliP achieves much better accuracy than previous methods for the same privacy constraints. We also empirically evaluate performance of momentum optimization algorithm in place of SGD and show that momentum does not result in models with better accuracy even though it adds less noise per iteration compared to SGD. We provide a possible explanation for this counter-intuitive phenomenon in Appendix B.

The paper is organized as follows. In Section 2, we overview differential privacy and previous methods. In Section 3, we motivate the need for a new differentially private SGD method. In Section 4, we introduce a general formulation that encompasses previous methods and present Theorem 1 to show the parameters that minimize the amount of noise added. In Section 5, we state our SGD technique AdaCliP that uses optimal parameters derived in Theorem 1. In Section 6, we present our empirical results.

Differential privacy for distributed SGD

We first formally describe differential privacy and the previous differentially private SGD methods. We then motivate the need for a new differentially private SGD algorithm by a simple example.

Let $\mathcal{D}$ be a collection of datasets. Two datasets $D$ and $D^{\prime}$ are adjacent if they differ in at most one user data. A mechanism $\mathcal{M}:\mathcal{D}\rightarrow\mathcal{R}$ with domain $\mathcal{D}$ and range $\mathcal{R}$ is $(\epsilon,\delta)$-differentially private if for any two adjacent datasets $D,D^{\prime}\in\mathcal{D}$ and for any subset of outputs $S\subseteq\mathcal{R}$,

One such privacy-preserving approximation is the Gaussian mechanism that adds Gaussian noise of variance of $S_{\varphi}^{2}\sigma^{2}$, i.e., $\mathcal{M}(D)=\varphi(D)+\mathcal{N}(0,S_{\varphi}^{2}\sigma^{2}I),$ where $\mathcal{N}(\mu,\Sigma)$ represents Gaussian variable with mean $\mu$ and covariance matrix $\Sigma$. We now present a well-known result that relates noise scale $\sigma$ of Gaussian mechanism to parameters $\epsilon$ and $\delta$.

For any $\epsilon<1$, the Gaussian mechanism with noise scale $\sigma$ satisfies $\left(\epsilon,\frac{4}{5}\exp\left(\frac{-(\sigma\epsilon)^{2}}{2}\right)\right)$-differential privacy.

2 Differential privacy for machine learning

Differential privacy definition was originally used to provide strong privacy guarantees for database querying and since used in several applications . Recently it has been extended to machine learning formulations. For the context of machine learning, dataset $D$ is a collection of user data and the function $\mathcal{M}$ corresponds to the output machine learning model parameters. We note that this notion of differential privacy is also called global differential privacy.

Differential privacy for machine learning models can be obtained in four ways: input perturbation, output perturbation, objective perturbation, and change in optimization algorithm.

In input perturbation, the dataset $D$ is first modified using Laplace or Gaussian mechanism and the resulting perturbed dataset is used to train the machine learning model . In output perturbation techniques, the machine learned model is trained completely and then the final model is appropriately changed by using exponential mechanism or by adding Laplace or Gaussian noise to the final model . In objective perturbation techniques, the objective function is perturbed by the appropriate scaling of Laplace or Gaussian noise and the machine learning model is trained over perturbed objective function .

The fourth method modifies the optimization algorithm for training machine learning models. This includes noisy SGD methods, which we discuss in the next section.

3 Noisy SGD methods

SGD and its variations such as momentum , Adagrad , or Adam are used for training machine learning models. These algorithms can be modified by adding noise to their gradients at each iteration to provide differentially private machine learning algorithms. Even though noisy SGD usually provides global differential privacy, recent works have shown that they can be combined with cryptographic homomorphic encryption techniques to provide stronger privacy guarantees .

Differentially private SGD algorithms is outlined in Figure 1. At each round of SGD, the algorithm selects a subset of data. Using the current model and auxiliary parameters, it computes gradients on each data point, and optionally modifies (e.g. clipping) the gradients. It then computes the mean of the gradients, adds noise to the mean, and uses the noisy gradient to update the model. The analysis of such algorithms can be broken into two parts:

Obtain $(\epsilon^{\prime},\delta^{\prime})$ differential privacy for each round of SGD, by ensuring that any information from the dataset that is used to update the model parameters is differentially-private.

Compute the total privacy cost of all SGD iterations to obtain overall $(\epsilon,\delta)$ parameters.

We first consider the second part. Suppose we show that the noisy gradients sent from the dataset to the server is $(\epsilon^{\prime},\delta^{\prime})$- differentially private. To keep track of accumulated privacy loss over multiple iterations of SGD, a privacy accountant is used . Privacy accountant maintains accumulated privacy loss in terms of $\epsilon$ and $\delta$, which are determined by the composition theorem used, $\epsilon^{\prime},\delta^{\prime}$ used in each iteration. For the Gaussian mechanism, introduced moments accountant, which provides tighter privacy bounds compared to other composition theorems . Recently, proposed adaptive strategies to select privacy parameters $\epsilon^{\prime}$, $\delta^{\prime}$ for each iteration. The differentially private SGD algorithm terminates the training once the privacy budget is reached.

For the first part, recall that a common technique to provide privacy-preserving approximation is to bound the sensitivity of the function and add Gaussian noise proportional to the sensitivity bound. To this end, we need to bound the sensitivity of the gradients at each round of SGD. This can be achieved in several ways.

If the loss function is differentiable (if not differentiable use sub-gradients) and Lipschitz bounded, bounds the gradient norm by the Lipschitz bound and use it to derive the sensitivity of gradients. If the loss function derivative is bounded as a function of input (for example, in the logistic regression case, one can bound the gradient norm by the maximum input norm possible) and hence derive the sensitivity of gradients. If the loss function does not have known Lipschitz bound as in deep learning applications, apriori bounds on gradient norm are difficult to derive. At each iteration of training, proposes to use public data to obtain an approximate bound on gradient norm and clip the gradients at this approximate bound. However the availability of public data is a strong assumption and clip the gradients without the availability of public data. We also assume no access to public data.

Motivation for AdaCliP

We now analyze the performance of differentially private SGD algorithms. At iteration $t$, the gradient with respect to any example $x^{i_{t}}$ is $g^{t}=\theta^{t}-x^{i_{t}}$. Notice that revealing the gradient $g^{t}$ and $x^{i_{t}}$, reveals the same information. Further observe that

Theoretical analysis

Let $f(\theta)=\frac{1}{N}\sum^{N}_{k=1}f_{k}(\theta)$. For a suitable choice of learning rate, iterates of SGD satisfy

where $g^{t}$ is the stochastic gradient at time $t$ and $c$ is a constant.

Previous algorithms added noise to the gradients themselves. In a more general framework, one can transform the gradient by a function, add noise, and apply the inverse of the function back. This may reduce the variance and bias of differentially private gradients and by Lemma 2 yield a better solution. We consider the class of element-wise linear transformations and find the best transformation.

Let $g^{t}=(g_{1}^{t},g_{2}^{t},..,g_{d}^{t})$ be the stochastic gradient vector at iteration $t$. Let $a^{t}=(a_{1}^{t},a_{2}^{t},..,a_{d}^{t})$ and $b^{t}=(b_{1}^{t},b_{2}^{t},..,b_{d}^{t})$ be the auxiliary vectors that will be described later. Transform $g^{t}$ by subtracting $a^{t}$ from it and dividing each dimension of $g^{t}-a^{t}$ by that of $b^{t}$. Let $w^{t}=\frac{g^{t}-a^{t}}{b^{t}}$ be the transformed gradient i.e., $w_{i}^{t}=\frac{g_{i}^{t}-a_{i}^{t}}{b_{i}^{t}}.$ To bound the sensitivity, the transformed gradient is clipped at norm 1. Let the clipped transformed gradient be $\hat{w}^{t}$.

Thus there are two potential sources for gradient modification. The first term in the above equation corresponds to the case when the transformed gradient $w^{t}$ might get clipped. The second term corresponds to the Gaussian noise injected to the clipped gradient. Ideally, we would like to find the best $a^{t}$ and $b^{t}$ that minimize the above expression. However, it is difficult to analyze the effect of clipping on the convergence. Hence we try to limit clipping, by assuming that

Hence it results in the optimization problem,

where last equation follows from constraint $\sum_{i=1}^{d}\frac{(s_{i}^{t})^{2}+(m_{i}^{t}-a_{i}^{t})^{2}}{(b_{i}^{t})^{2}}\leq\gamma$. The last inequality is satisfied with equality when $b_{i}^{t}=\sqrt{s_{i}^{t}/\gamma}\cdot\sqrt{\sum_{i=1}^{d}s_{i}^{t}}$. Further, combined with choice of $a_{i}^{t}=m_{i}^{t}$,

2 Convergence analysis

In this section, we present the convergence analysis for AdaCliP. Our main result is the convergence of this algorithm for general nonconvex functions, the proof of which is provided in the Appendix A.

Note the dependence of convergence result on the variance of stochastic gradients, bias introduced due to clipping and variance due to noise addition. The terms of special interest to us are: clipping bias and noise-addition variance. There is an inherent trade-off between these two terms as observed through the dependence on $b^{t}$. One can decrease the clipping bias by increasing $\|b^{t}\|$ but this comes at the expense of larger noise addition. One can optimize the values of $b^{t}$ to minimize this upper bound. In doing so, our choice of $b^{t}$ in Theorem 1 again becomes quite evident. In particular, observe that clipping bias and noise-addition variance are the two terms in the LHS of Eq. (3). Thus, by Holder’s inequality, their weighted sum is minimized when $b^{t}$ is chosen as per Theorem 1. In the following section, we discuss choices of $a^{t}$ and $b^{t}$ and their convergence bounds. In specific we show how they affect the last term in Theorem 2.

3 Comparison on regression

We now revisit the regression problem shown in (1). Recall that in this example, all gradients have the same norm and hence we can set clipping threshold to $\mu$. Hence, the clipping bias is . With this choice of the clipping threshold, we compare various choices of $a^{t}$ and $b^{t}$.

AdaCliP

In this section, we present the optimal estimator based on the noisy differentially private version of the gradients. First note that, to set the optimal values of $a^{t}$ and $b^{t}$, we need to know the mean and variance of the gradients. We propose to estimate them using noisy differentially private gradients. The full algorithm AdaCliP is presented in Algorithm 1.

AdaCliP minimizes the objective function $f(\theta)=\frac{1}{N}\sum_{k}f_{k}(\theta)$ preserving privacy under $(\epsilon,\delta)$-differential privacy. At each iteration of SGD, AdaCliP selects a minibatch of $B$ users. It then computes the stochastic gradient corresponding to each user and adds noise to the stochastic gradient with optimal choices for transformation vectors $a^{t}$ and $b^{t}$. Later AdaCliP updates the parameters (mean and variance) using noisy gradients. Notice that here the Gaussian noise is added to each individual user gradient separately instead of adding to the mean processed gradient as described earlier. Since the sum of Gaussian noises is also Gaussian noise, adding Gaussian noise to the individual user processed gradient and to the mean processed gradient is essentially equivalent. AdaCliP also updates the mean and variance estimates of the gradients using the noisy gradients.

where $\beta_{1}$ is a decay parameter of the exponential moving average.

However, the above quantity can be quite noisy. Hence we ensure that the quantity is both upper and lower bounded as follows:

where $h_{1}$ and $h_{2}$ are small constants. We use an exponential moving average of the above quantity to estimate the variance as

We observed that our algorithm is robust to parameters $\beta_{1}$, $\beta_{2}$, $h_{1}$, and are thus, set to $0.99$, $0.9$, $10^{-12}$ in all our experiments. We only tune $h_{2}$ in our experiments.

Experiments

We now compare AdaCliP to the previous methods on the MNIST dataset . MNIST consists 60,000 training images and 10,000 test images. We divide each feature value by 255.0 to standardize it to $$. We use mini batch size of 600 in all the experiments, fix$\delta=10^{-5}$, and compare accuracy values for different$\epsilon$. We use moments account to keep track of privacy loss, as it is known to give tight privacy bounds for the Gaussian mechanism.

We then consider a neural model similar to the one in . 784 dimensional input is projected to 60 dimensions using differentially private PCA and then a neural network with a single hidden layer of 1000 units is trained on the 60 dimensional input. The privacy budget is split between PCA and neural network training. As suggested in , for , we clip the gradient norm of each layer at 4.0. Table 2 shows that AdaCliP consistently performs better than the previous methods. The accuracy gains for AdaCliP over ranges from $0.4\%$ at $\epsilon=2.0$ to $1.6\%$ at $\epsilon=0.2$.

Conclusion

We proposed AdaCliP, an $(\epsilon,\delta)$- differentially private SGD algorithm that adds smaller amount of noise to the gradients during training. We compared our technique with previous methods on MNIST dataset and demonstrated that we achieve higher accuracy for the same value of $\epsilon$ and $\delta$. It would be interesting to see if instead of using a coordinate-wise gradient transform, using a matrix or low rank matrix gradient transform would give better results.

References

Appendix - AdaCliP: Adaptive Clipping for Private SGD

Appendix A AdaCliP Convergence Analysis

For the ease of exposition, we define the following quantities:

The second inequality uses the fact that $\|\Delta^{t}\|^{2}\leq 2G^{2}$. Plugging in these bounds into Equation (A), we get

Adding the above inequalities from $t=0$ to $T-1$ and by using telescoping sum, we get

Here, we used the condition $\eta<\tfrac{1}{3L}$. The desired result is obtained by using the fact that $f(\theta^{T})\geq f(\theta^{*})$. ∎

We first observe that $\Delta^{t}=0$ when $\|g^{t}-a^{t}\|\leq\|b^{t}\|$. Thus, we essentially have to bound the probability that $\|g^{t}-a^{t}\|\geq\|b^{t}\|$. This follows from a simple application of Chebyshev’s inequality:

Appendix B Comparison of SGD with momentum

One can ask if we can obtain benefits similar to AdaCliP by simply using momentum. We provide an intuitive reasoning why this may not be the case. Momentum maintains accumulation vector $\nu^{t}$ that keeps track of exponentially weighted averages of previous gradients.

where $\beta$ is the momentum parameter. Notice that since $\nu^{t}$ is an exponentially weighted average of previous gradients, it can also be expressed as

Notice that noise added per update is factor $\sqrt{\frac{1-\beta}{1+\beta}}$ smaller than that in SGD. This might lead one to believe that deferentially private momentum optimization might reach better model parameters compared to vanilla SGD.

To evaluate this, consider the logistic regression task on MNIST in Section 6. To avoid clipping, we add noise proportional to maximum gradient norm i.e., 28. In Figure 4(a), we aim for $(0.5,10^{-5})$-differential privacy. Figures 4(b) and 4(a) show that SGD and momentum with various momentum factors ($\beta$) converge to almost similar accuracies.

We hypothesize that this behavior is due to the fact that under momentum, noises added across iterations are dependent. Hence, even though the noise added per iteration is small, overall noise added to sum of all gradients is the same for both SGD and momentum. For SGD, the total amount of noise added is $\sum^{T}_{t=0}N^{t}$. Observe that the same holds for momentum as

It would be interesting to provide better theoretical understanding for this behavior.