A Differentially Private Framework for Deep Learning with Convexified Loss Functions

Informally, differential privacy (DP) [5] ensures that two outputs, produced by a randomised algorithm on two neighbouring datasets, are almost indistinguishable.

Two prototypical $\epsilon$-DP mechanisms considered in this paper are the Laplace mechanism (Lap-DP) [5] and the exponential mechanism (Exp-DP) [18]. The former adds additive noise drawn from the Laplace distribution of scale $\Delta f/\epsilon$ to the numeric computation $f(\cdot)$, where $\Delta f$ is the $L_{1}$ global sensitivity of $f$. The $L_{p}$ global sensitivity of $f$ is:

where $\lVert\cdot\rVert_{p}$ is the $L_{p}$-norm. For simplicity, in this paper, $\Delta f$ denotes the $L_{1}$ global sensitivity.

The Exp-DP mechanism is a weighted sampling scheme to generate the output from a set of (arbitrary) candidates, and is well-suited for non-numeric computations. The mechanism simply outputs a given candidate $r$ from a set of candidates $R$ computed over a dataset $X$, with probability proportional to $\exp(\epsilon q(X,r)/2\Delta q)$, where $q(X,r)$ is the score/quality function of the candidate $r$, and $\Delta q$ is the maximum possible change in $q$ over all neighbouring datasets.

An important property of differential privacy is that the mechanisms compose [21]:

The recently proposed $\epsilon$-Gaussian DP ($\epsilon$-GDP) [22], injecting noise following a Gaussian distribution $\mathcal{N}(0,(\nicefrac{{\Delta f}}{{\epsilon}})^{2})$, is a relaxation of traditional $\epsilon$-DP. We have

The composition of GDP is as follows.

Let $A$ be a learning algorithm, $X=(\mathbf{x}_{1},\dots,\mathbf{x}_{n})$ be a training set drawn from a distribution $\mathcal{D}$ ($X\sim\mathcal{D}^{n}$), $W_{X}(=(\omega_{1},\dots,\omega_{|E|})\in\mathbb{R}^{|E|})=A(X)$ be the output of the learning algorithm $A$ on the training set $X$, i.e., trained model parameters, where $|E|$ is the number of model parameters. Once the model parameters are set after training, we predict the class label $y$ of an observation $\mathbf{x}$ as $y=\operatorname*{arg\,max}\{p_{1},\dots,p_{C}\}$, where $\mathbf{p}=\{p_{1},\dots,p_{C}\}=h(W_{X},\mathbf{x})$, $h$ is the learnt hypothesis and $C$ is the number of classes.

We use a loss function $l(W_{X},\mathbf{x}_{i})$ on an observation $\mathbf{x}_{i}\in X\sim\mathcal{D}^{n}$ to measure the empirical error of $W_{X}$ on $\mathbf{x}_{i}$. Note that each $\mathbf{x}_{i}$ is a composition of a set of features and an accompanying class label. Accordingly, we have the following equation to measure the training error of the learning algorithm $A$ on the dataset $X$. The learning algorithm $A$ aims to minimise the training error.

We extend On-Average-Replace-One stability to On-Average-Remove-One stability to fit the neighbouring dataset requirement of Definition 1.

Based on Inequality (5), a less $\sigma(n)$ indicates higher OARO stability.

When using a trained neural network (trained model parameters/weights and given topology) to make prediction for a given data sample $\mathbf{x}=(x_{1},\dots,x_{n})$, we calculate the output of each vertex/neuron, $a_{t,i}$ at layer $V_{t}$ as follows.

where $\phi(\cdot)$ is an activation function for the neurons, $a_{0,i}=x_{i}$ and $a_{t-1,|V_{t-1}|}$ is also known as the bias term. At the output layer, the final prediction probability vector of the given data sample $\mathbf{x}$ would be $\mathbf{p}=(a_{T,1},\dots,a_{T,C})$, where $\sum_{i=1}^{C}a_{T,i}=1$. In our experiments in Section 5, $\phi(\cdot)$ is Tanh for $t<T$, $\phi(\cdot)$ is Softmax for $t=T$.

Furthermore, we also use the concepts of convex set, convex function, $\lambda$-strong convexity and $\rho$-Lipschitzness in this paper. We follow the standard definitions of these concepts.

The goal of Membership Inference (MI) Attacks is to infer the membership of a given data sample by the prediction output of the data sample. In this paper we specify MI attacks as black-box MI attacks implemented via the shadow model technique by Shokri et al. [2]. That is, the MI adversaries only have access to the distribution of the target/private dataset and the prediction output of a given data sample.

For simplicity, a black-box MI attack via shadow models is a function $\mathcal{A}:\mathcal{D}^{kn+1}\to\{0,1\}$. The adversary performs a shadow models-based MI attack in three steps. Firstly, the adversary trains $k$ shadow models with shadow datasets $X^{\prime}_{i}\sim\mathcal{D}^{n}$, $i\in[1,k]$, mimicking the behaviour of the target model trained with the target/private dataset $X$. Then the adversary uses the $k$ shadow models to make predictions for training data (members) and test data (non-members). These prediction vectors will then be the training data to train an attack model (a binary classifier). Finally, for a given data sample $\mathbf{x}\sim\mathcal{D}$, the adversary queries the prediction probability vector $\mathbf{p}$ of $\mathbf{x}$ from the target model, then feeds $\mathbf{p}$ to the trained attack model to predict the membership ($\{0,1\}$) of $\mathbf{x}$.

Table II summarises the notations used in this paper.

Based on our discussion in the related works section (Section 2), an output perturbation-based DP solution has one potential benefit over gradient and input perturbation-based approaches. In the latter two approaches, the entire privacy budget $\epsilon$ is consumed for model training. Any subsequent use of the trained model does not further consume the privacy budget due to the post-processing property of differential privacy. This, however, means that the utility offered is fixed for any number of queries; whether we ask 10 queries or 10,000 queries (a query means one data sample given as input to the model; the model in turn returns the corresponding probability vector). On the other hand, the output perturbation approach depletes budget per query to the trained model. This means that if the trained model is used for a fixed number of queries (as opposed to an unlimited number of queries), then we can offer better utility by virtue of allocating larger chunks of the budget per query. This motivates our focus on output perturbation.

In this section, we propose an output perturbation-based DP algorithm for general deep learning tasks. To provide a better privacy-utility trade-off, we inject DP noise into a randomly sampled neuron at the output layer. Figure 1 depicts our general idea, where neuron $z_{1}$ is the randomly sampled neuron and the DP noise follows the distribution $\text{Dist}(0,\nicefrac{{\Delta z_{T}}}{{\epsilon}})$. We shall use both the Laplace and the Gaussian mechanisms as examples of this distribution in our experiments, providing $\epsilon$-DP and $\epsilon$-GDP (or $(\epsilon,\delta(\epsilon))$-DP) guarantees, respectively.

Specifically, our DP algorithm works in three steps. Firstly, for a given data sample, we feed this data sample to a trained non-private neural network to calculate the values of the neurons at the output layer. Next, we inject DP noise into a randomly sampled neuron at the output layer. After noise injection, we apply Softmax function on the noisy neuron vector to produce a differentially private probability vector. Algorithm 1 shows the implementation details, where Line 1 to Line 7 are the first step, Line 8 to Line 10 are the second step, and Line 11 to Line 13 are the third step. Note that, Algorithm 1 only introduces marginally more time than the non-private neural network: Lines 9 and 10 to the non-private neural networks. Sampling (Line 9) is efficiently implementable even with a large number of classes. The injected noise does not depend on the number of classes and the number of training data samples.

Also, since noise is not injected into the rest of the neurons in the neural network, the output perturbation technique is useful only in the black-box setting, where model parameters are not released. The key point of implementing Algorithm 1 is to find a tight upper bounds on $\Delta z_{T}$ for deep learning models. In the following sections, we show our upper bound on $\Delta z_{T}$ by analysing the upper bound on the global sensitivity of the model parameters, $\Delta_{2}W$ (which is tighter than existing results [8, 9] subject to the convexity of the loss function). We then show the DP guarantee of Algorithm 1 and the effect of DP against the black-box MI attacks.

This section analyses the upper bounds on the $L_{2}$ global sensitivity of trained model parameters and the $L_{1}$ global sensitivity of an individual neuron at the output layer. We analyse these upper bounds based on the fundamental properties of convex and strongly convex functions.

Based on Lemma 1, Lemma 2 (when $h$ is the loss function and $g$ is the $L_{2}$-norm regulariser) and Lemma 3, we have the following theorem to find the upper bound on the On-Average-Remove-One (OARO) stability (Definition 2) of the loss function and the global sensitivity of the model parameters, where we measure the global sensitivity of the model parameters by $L_{2}$-norm (a.k.a. $L_{2}$-sensitivity [21]).

We note that Chaudhuri et al. [8] provide a similar result to Theorem 4. However, their upper bound on the $L_{2}$ global sensitivity of the model parameters is $\nicefrac{{2\rho}}{{\lambda n}}$ under the condition of a binary classification task and a normalised training set ($\lVert\mathbf{x}_{i}\rVert\leq 1$). In addition, Wu et al. [9] also provide the same upper bound on the global sensitivity of the model parameters as ours. However, their result needs the loss function to be $\beta$-smooth with a decreasing step size during the process of stochastic gradient descent. Once we remove these additional conditions, the two upper bounds become loose. Table I in Section 1 shows a brief comparison between these upper bonds and their conditions. Compared to [8] and [9], when achieving the same tight bound, our result only relies on the convexity of the loss function but not the additional conditions introduced in [8, 9].

Since $\Delta_{2}W$ is the $L_{2}$ global sensitivity, we have $(\Delta_{2}W)^{2}=\sum_{i=1}^{|W_{X}|}(\Delta\omega_{i})^{2}$, where $|W_{X}|$ is the number of edges in a deep neural network. Since each $\Delta\omega_{i}$ has the same upper bound $\Delta\omega$, we have the global sensitivity ($L_{1}$-norm) of an individual model parameter

Once we have the $L_{1}$ global sensitivity of each model parameter/weight, we can further analyse the upper bound on the global sensitivity of the neuron (input to the Softmax function) at the output layer.

In practice, some commonly used activation functions, such as, Tanh, Sigmoid, Binary step and Gaussian functions, provide $a_{u}=1$. In our experiments (Section 5), we use Tanh function as the activation function in the hidden layers, following existing works [2, 4, 23, 1] in MI attacks.

Note that, when $\Delta z_{T}>0.5\ln{2}$, $\Delta p$ becomes trivial, i.e., $\Delta p=1$, which is the maximum change for a probability $p_{v}$ of neuron $v$ at the output layer). However, based on the way the Exp-DP behaves (in Algorithm 1), even if the bound on $\Delta p$ is trivial, the highest probability neuron will still have a relatively high probability of being sampled. That is, Algorithm 1 still guarantees the quality of the sampled neuron. Moreover, in Table VI in Section 5.4.3, we show that there are datasets where this upper bound on $\Delta p$ is non-trivial, and we therefore get even better utility.

In this section, we show how to calculate the upper bound on the Lipschitz constant $\rho$, which is important when computing the upper bound on global sensitivities $\Delta\omega$, $\Delta z_{T}$ and $\Delta p$ (see Equation (18)).

Based on Lemma 4 and Lemma 5, we have Proposition 1 to calculate the upper bound on the Lipschitz constant of the cross-entropy loss function, which is used in our experiments and also a commonly used loss function in existing works [2, 4, 23, 1], for a $(T+1)$-layer neural network.

Based on Equation (21), the Lipschitz constant grows exponentially with the number of layers. However, when calculating the global sensitivities of the parameters $\Delta\omega$, $\Delta z_{T}$ and $\Delta p$, this exponential growth (in the number of layers and the maximum value of neuron per layer), is somewhat compensated by the terms $\sqrt{|W_{X}|}$ and $n$ (the number of data samples in the training set), as can be seen by putting the value of $\rho$ from Equation (21) into Equation (18). This is also empirically demonstrated in Table VI in Section 5.4.3.

In our proofs of the upper bounds on the global sensitivities, a key assumption is that the objective function of the learning algorithm is a combination of a convex loss function and a $\lambda$-strongly convex regulariser. Lemma 1 guarantees the strong convexity for an $L_{2}$-norm regulariser. However, loss functions of deep learning models are non-convex due to a large number of model parameters [27]. To circumvent this, we follow existing results in multi-layer (more than one hidden layers) neural networks convexification [14, 15] by risk-averse optimisation to convexify the non-convex loss functions.

So we have

where $l(W_{X},\mathbf{x})$ can be conventional/commonly used non-convex loss functions, such as quadratic loss and cross-entropy loss. We use the convexified loss function rather than the traditional non-convex loss function in the experimental evaluations.

Intuitively, the convexification constant $\alpha$ might impact the trade-off between privacy and utility of the non-private model against MI attacks (since it might impact the performance/overfitting of the convexified loss function [23]). In this paper, we take $\alpha$ as another hyper-parameter to the machine learning model; hence, studying the relationship between $\alpha$ and the privacy-utility trade-off is left as future work.

In this section, we study the effect of differential privacy, including the DP guarantee of Algorithm 1 and the OARO stability of a DP neural network. In the $\epsilon$-DP proof of the algorithm, we assume the Laplace mechanism as an instance of $\text{Dist}(0,\nicefrac{{\Delta z_{T}}}{{\epsilon}})$. But this guarantee can be converted into an $\epsilon$-GDP guarantee by invoking the advanced composition theorem of $(\epsilon,\delta(\epsilon))$-DP and subsequently applying Theorem 2. Thus, the result holds for both the Laplace and the Gaussian mechanisms.