A General Approach to Adding Differential Privacy to Iterative Training Procedures

Introduction

There has been much work recently on integrating differential privacy (DP) techniques into iterative training procedures like stochastic gradient descent [Chaudhuri et al., 2011, Bassily et al., 2014, Abadi et al., 2016, Wu et al., 2017, Papernot et al., 2017]; for completeness we provide a formal definition of DP in Appendix A. Although these works differ in the granularity of privacy guarantees offered and the method of privacy accounting, most proposed approaches share the general idea of iteratively computing a model update from training data and then applying the Gaussian mechanism for differential privacy to the update before incorporating it into the model. Our goal in this work is to decouple, to the extent possible, three aspects of integrating a privacy mechanism with the training procedure:

the specification of the training procedure itself (e.g., stochastic gradient descent with batch normalization and simultaneous collection of accuracy metrics and training data statistics),

the selection and configuration of the privacy mechanisms to apply to each of the aggregates collected (model gradients, batch normalization weight updates, and metrics), and

the accounting procedure used to compute a final $(\varepsilon,\delta)$-DP guarantee.

This separation is critical: the person implementing a) is likely not a DP expert, and this code typically already exists; there are many configuration options for b), which will likely require experimentation, and this configuration logic may become complex; thus isolating the key privacy calculations in c) and keeping them as simple (and well tested) as possible prevents bugs in a) or b) from introducing errors in the calculation of the actual privacy achieved.

While model training is our primary motivation, the approach is applicable to any iterative procedure that fits the following template. We have a database with $n$ records. A record might correspond to a single training example, a “microbatch” of examples, or all of the data from a particular user or entity (e.g., to achieve user-level DP as in McMahan et al. ). On each round, a random subset of records (a sample) is selected and the training procedure consumes the results of a number of vector queries over that sample; see Table 1. Such vector queries may include the average gradient for each layer, updates to batch-normalization parameters, or the average value for different training accuracy metrics. We describe a general approach to allocating a privacy budget across each of these queries and analyzing the privacy cost of the complete mechanism, all respecting the decoupling of concerns described earlier. Our analysis builds on the Moments Accountant approach of Abadi et al. , which applies to a single vector query per round, and generalizes the extension of McMahan et al. to multi-vector queries.

Select a subset of the records $R\subseteq[1,\ldots,n]$ by choosing each record with probability $q$.

Clip each $x^{i}$ for $i\in R$ to have maximum $L_{2}$ norm $S$ using $\pi_{\!S}\!\left(x\right)=x\cdot\min\left(1,S/\|x\|_{2}\right)$.

Output $\hat{x}=\frac{1}{qn}\left(\sum_{i\in R}\pi_{\!S}\!\left(x^{i}\right)+\mathcal{N}(0;\sigma^{2}I)\right)$ where $\sigma=zS$.

Implementations of techniques in this paper may be found in the open-source TensorFlow Privacy framework [Google et al., 2018] for TensorFlow [Abadi et al., 2015], as described in Section 7.

Privacy mechanisms for a group of vectors

In this section, we describe two strategies that can be applied to a single group of vectors, WLOG the first $k$, $(v_{1},\dots,v_{k})$, for $k\leq m$; when $k=1$, the two mechanisms described are identical. Both mechanisms allow individual noise standard deviation parameters to be used for the separate groups. While this might at first seem to preclude the use of the Moments Accountant, which requires spherical noise, we will show how to resolve this issue in the next section.Privacy mechanisms for groups can be used within TensorFlow Privacy [Google et al., 2018] by employing the NestedQuery class, which evaluates an arbitrary nested structure of queries where each leaf query would be a GaussianAverageQuery corresponding to one group of vectors.

This strategy essentially treats the whole group as a single concatenated vector $v=\left(v_{1},\ldots,v_{k}\right)$. The user provides $S_{g}$, a clipping parameter, and $\sigma_{g}$, a noise parameter. For now, assume both of these parameters are simply chosen so as to provide reasonable utility for the resulting average; we will discuss strategies for choosing these parameters in detail in Section 4. The output of the mechanism is

Joint clipping.

Here we introduce a new mechanism that allows us to clip less aggressively than applying the previous strategy to each vector individually, while still letting different vectors live on different multiplicative scales. The user supplies as input scale parameters $\alpha_{1},\dots,\alpha_{k}$, which may be thought of as bounds or reasonable $L_{2}$ norm clip parameters on the individual $v_{i}$, were they to be clipped individually. The strategy first does a pre-processing step via the scaling operator $\mathbf{s}(v;\alpha_{1:k})=(v_{1}/\alpha_{1},\dots,v_{k}/\alpha_{k})$. If $\|v_{j}\|_{2}\leq\alpha_{j}$ for all $j\in[k]$, then the joint norm $\|\mathbf{s}(v;\alpha_{1:k})\|_{2}\leq\sqrt{k}$, however it may typically be much less. Then joint clipping and noising is performed using a total clipping parameter S_{g}\in\big{[}0,\sqrt{k}\big{]} and noise with the standard deviation of $\alpha_{j}\sigma_{g}$. The mechanism’s output then scales the vectors back by the $\alpha_{j}$ factor in post-processing:

To see where this mechanism might be superior to the first, suppose $v_{1}$ and $v_{2}$ have $\|v_{1}\|_{2}\leq 1$ and $\|v_{2}\|_{2}\leq 100$, and suppose they can tolerate noise standard deviations of $0.01$ and $1$ respectively. Additionally, assume it is known that either $v_{1}^{i}$ or $v_{2}^{i}$ will be zero for any record $i$. We could clip these separately, but this ignores the (useful) side information that one of the vectors is always zero. On the other hand, if we treat them as a single group, we cannot take into the account the fact they are on very different scales; in particular, we must pick a single noise value which will either be insufficient to add privacy for $v_{2}$, or will completely obscure the signal in $v_{1}$. The joint mechanism proposed here lets us directly handle this situation using $\alpha_{1}=1$, $\alpha_{2}=100$, $\sigma_{g}=0.01$, and $S_{g}=1$.

Composing privacy guarantees for multiple vector groups

The final expression is a simple post-processing on the output of a single Gaussian sum query with parameters $(S^{*},\sigma=1)$. Thus, we can apply the privacy accountant to bound the privacy loss of iterative applications of this mechanism.

Hyperparameter selection strategies

Typically, a value of $z\approx 1$ will provide a reasonable privacy guarantee. If $z$ is too small for the desired level of privacy, the user has several knobs available: clip more aggressively by decreasing the $S_{g}$’s; noise more aggressively by scaling up the $\sigma_{g}$’s; or increasing $q$. When datasets are large and the additional computational cost of processing larger samples $R$ is affordable, this last approach is generally preferable, as observed by McMahan et al. . If additionally the total number of iterations $T$ is known, then since the privacy cost scales monotonically with any of these adjustments to $z$, a binary search can be performed using the privacy accountant repeatedly with different parameters to find e.g. the precise value of $q$ needed to achieve a particular $(\varepsilon,\delta)$-DP guarantee.

Typical approaches to setting $S_{g}$ include: 1) using an a priori upper bound on the $L_{2}$ norm; 2) choosing $S_{g}$ so that “few” vectors are clipped; or 3) running parameter tuning grids to find a value of $S_{g}$ that does not reduce utility (e.g., the accuracy of the model) by too much. If private data is used in 2) or 3), the privacy cost of this should be accounted for. Similar strategies can be used to choose $\sigma_{g}$, e.g., selecting a value that will introduce an a priori acceptable amount of error, or more likely for model training, running experiments to find the largest amount of noise that does not slow the training procedure.

Sampling policies

The basic update step of the SGD algorithm operates on a small subset of records (the minibatch). Convergence guarantees of the standard optimization theory hold under the assumption that each minibatch is an i.i.d. sample of the training dataset, and the original Moments Accountant by Abadi et al. supported privacy analysis in this regime.

In practice, there are valid reasons for using alternative policies for sampling minibatches, with implications for privacy analysis. We list three of the most common sampling policies below.

Privacy of this sampling procedure is analyzed by Abadi et al. and it is used by the federated learning framework where decisions of whether to participate in a particular update step are made locally [McMahan et al., 2018]. If the privacy accountant is dependent on the secrecy of the sample (as in the case of the Moments Accountant), then the size of the sample cannot be released without applying a privacy-preserving mechanism, which can be as simple as additive noise. The variability of the sample’s size makes this sampling policy a poor fit for hardware accelerators. It can be repaired by sampling subsets of a fixed size from the training set without replacement, which leads us to the next policy.

Minibatches are equally sized and independent.

The basic SGD corresponds to this sampling policy and minibatches of cardinality 1. Recent works analyze composition of this sampling policy with a mechanism satisfying RDP [Wang et al., 2018] or tCDP [Bun et al., 2018]. Independence of minibatches makes analysis of multiple iterations of SGD straightforward via application of composition rules for differential privacy.

Minibatches are equally sized and disjoint.

In practice, the most common manner of forming minibatches is permuting the training dataset and partitioning it into disjoint subsets of a fixed size. After a single pass (an epoch) the process is repeated. This sampling policy can be efficiently implemented, and has intuitive semantics: an epoch corresponds to a training cycle when all examples were visited exactly once. Quantitatively tight analysis of DP-SGD in this model is not known. (A related problem of analyzing randomized response followed by a random permutation is addressed by Erlingsson et al. .)

Privacy ledger

There are two main advantages of this approach. First, bugs in the hyperparameter selection strategy code cannot affect the privacy estimate. Second, it allows the privacy accounting mechanism to be changed and the ledger reprocessed if, for example, a tighter bound on the privacy loss is discovered after the data has been processed.

TensorFlow Privacy

TensorFlow Privacy [Google et al., 2018]Available from https://github.com/tensorflow/privacy under Apache 2.0 license. is a Python library that implements TensorFlow optimizers for training machine learning models with differential privacy. The library comes with tutorials and analysis tools for computing the privacy guarantees provided. From an engineering perspective, the implementation of differentially private optimizers found in the library leverages the decoupled structure outlined above to make it easier for developers to both (a) wrap most optimizers into their differentially private counterpart and (b) compare different privacy mechanisms and accounting procedures.

Perhaps the library is best illustrated by one of its main use cases: training a neural network with differentially-private stochastic gradient descent [Abadi et al., 2016]. Given the stochastic gradient descent optimizer class, tf.train.GradientDescentOptimizer, implemented in the main TensorFlow library, one first wraps it into a new optimizer that implements logic for both the clipping and noising of gradients needed to obtain privacy. This is done by having the optimizer estimate the gradients via an instance of a class implementing the DPQuery interface. A DPQuery is responsible for clipping gradients computed by the optimizer, accumulating them, and returning their noisy average to the optimizer. This introduces two additional hyperparameters to the optimizer: the clipping norm and the noise multiplier. The PrivacyLedger class maintains a record of the sum query events for each sampling event which can then be processed by the RDP accountant.

In addition, our implementation leverages microbatches, as defined in Table 1. This implies that gradients are computed over several examples before they are clipped, and once all microbatches in a minibatch have been processed, they are averaged and noised. This introduces a third additional hyperparameter to the optimizer: the number of microbatches. Increasing it often improves utility but typically slows down training.

TensorFlow Privacy is also designed to work with training in a federated context in the vein of McMahan et al. . In that case the “gradients” supplied to the DPQuery would in fact be the model updates supplied by the users in a given round.

Finally, to compute the $(\varepsilon,\delta)$ differential privacy guarantee for the model, an implementation of the RDP accountant is provided. Given the sampling fraction $q$ and the noise multiplier $z$, the RDP is computed for a step. Summing the RDP over the steps, it can then estimate $\varepsilon$ for a fixed $\delta$.

Floating-point arithmetic and randomness source

The hallmark feature of the definition of differential privacy is that it is uncoditional, in other words, it makes no assumptions about the adversarial knowledge or capabilities. It also puts a high burden on a differentially private implementation: its output distribution must have effectively infinite entropy. In practice, the distribution is defined over only a finite domain (such as a vector of single-precision floating-point numbers) and the source of randomness is guaranteed (at best) to be computationally secure. We consider these issues in turn.

The problem of achieving differential privacy by means of standard floating-point arithmetic has been addressed for the additive Laplace mechanism by Mironov . We leave open the task of developing a provable floating-point implementation of DP-SGD and integrating it into an ML library.

Sources of randomness.

Most computational devices have access only to few sources of entropy and they tend to be very low rate (hardware interrupts, on-board sensors). It is standard—and theoretically well justified—to use the entropy to seed a cryptographically secure pseudo-random number generator (PRNG) and use the PRNG’s output as needed. Robust and efficient PRNGs based on standard cryptographic primitives exist that have output rate of gigabytes per second on modern CPUs and require a seed as short as 128 bits [Salmon et al., 2011].

The output distribution of a randomized algorithm $A$ with access to a PRNG is indistinguishable from the output distribution of $A$ with access to a true source of entropy as long as the distinguisher is computationally bounded. Compare it with the guarantee of differential privacy which holds against any adversary, no matter how powerful. As such, virtually all implementations of differential privacy satisfy only (variants of) Computational Differential Privacy introduced by [Mironov et al., 2009]. On the positive side, a computationally-bounded adversary cannot tell the difference, which allows us to avoid being overly pedantic about this point.

A training procedure may have multiple sources of non-determinism (e.g., dropout layers or an input of a generative model) but only those that are reflected in the privacy ledger must come from a cryptographically secure PRNG. In particular, the minibatch sampling procedure and the additive Gaussian noise must be drawn from a PRNG for the trained model to satisfy computational differential privacy. In contrast, microbatches need not be chosen using a randomized process.

Conclusion

We have shown how the Gaussian mechanism can be applied to vectors of different types with different norm bounds and noise standard deviations, enabling training over heterogeneous parameter vectors, as well as simultaneous privacy-preserving estimation of other statistics such as classifier accuracy, or the number of instances in each class. By implementing iterative training algorithms in terms of a series of Gaussian sum queries and then recording for each query privacy events to a ledger to be processed by a privacy accountant, we separate the three major concerns of implementing privacy-preserving iterative training procedures while allowing flexibility in the specification of clipping strategy and noise allocation. The techniques described in the paper can be easily implemented using the Tensorflow Privacy library.

References

Appendix A Differential Privacy

The formal definition of $(\varepsilon,\delta)$-differential privacy is provided here for reference:

A randomized mechanism $\mathcal{M}\colon\mathcal{D}\mapsto\mathcal{R}$ satisfies $(\varepsilon,\delta)$-differential privacy if for any two adjacent datasets $X,X^{\prime}\in\mathcal{D}$ and for any measurable subset of outputs $\mathcal{Y}\subseteq\mathcal{R}$ it holds that $\Pr\left[\mathcal{M}(X)\in\mathcal{Y}\right]\leq e^{\varepsilon}\Pr\left[\mathcal{M}(X^{\prime})\in\mathcal{Y}\right]+\delta.$

The interpretation of adjacent datasets above determines the unit of information that is protected by the algorithm: a differentially private mechanism guarantees that two datasets differing only by addition or removal of a single unit produce outputs that are nearly indistinguishable. For machine learning applications the two most common cases are example-level privacy (e.g., Chaudhuri et al. , Bassily et al. , Abadi et al. , Wu et al. , Papernot et al. ), in which an adversary cannot tell with high confidence from the learned model parameters whether a given example was present in the training set, or user-level privacy (e.g., McMahan et al. ) in which adding or removing an entire user’s data from the training set should not substantially impact the learned model. It is also possible to consider $X$ and $X^{\prime}$ to be adjacent if they differ by replacing a training example (or an entire user’s data) with another, which would increase the $\varepsilon$ by a factor of two.