Federated Model Distillation with Noise-Free Differential Privacy

Introduction

Federated learning (FL) provides a privacy-aware paradigm of model training, which allows a multitude of parties to construct a joint model without directly exposing their private training data McMahan et al. (2017); Bonawitz et al. (2017); Xu et al. (2021). Nevertheless, recent works have demonstrated that FL may not always provide sufficient privacy guarantees, as communicating model updates throughout the training process can nonetheless reveal sensitive information Bhowmick et al. (2018); Melis et al. (2019).

In order to protect training data privacy in FL, various privacy protection techniques have been proposed in the literature Geyer et al. (2017); McMahan et al. (2018); Bonawitz et al. (2017); Wang et al. (2019b); Zhao et al. (2020); Sun et al. (2020a); Lyu et al. (2020). From the perspective of differential privacy, most works focus on the centralized differential privacy (CDP) that requires a central trusted party to add noise to the aggregated gradients Geyer et al. (2017); McMahan et al. (2018). Moreover, these works are geared to tackle thousands of users for training to converge and achieve an acceptable trade-off between privacy and accuracy McMahan et al. (2018), resulting in a convergence problem with a small number of parties.

To achieve stronger privacy protection, a few recent works start to integrate local differential privacy (LDP) into federated learning. However, most existing approaches can only support shallow models such as logistic regression and only focus on simple tasks and datasets Wang et al. (2019b); Zhao et al. (2020). Bhowmick et al. (2018) presented a viable approach to large-scale local private model training. Due to the high variance of their mechanism, it requires more than 200 communication rounds and incurs much higher privacy cost, i.e., MNIST ($\epsilon=500$) and CIFAR-10 ($\epsilon=5000$). A recent work Sun et al. (2020a) utilized Local Differential Privacy (LDP) into federated learning. However, in order to achieve a reasonable privacy budget, it uses a splitting and shuffling mechanism that split all parameters of a single model and send them individually to the cloud. This special communication requires tons of communication between clients and clouds.

All the above works considered privacy issues in conventional FL that requires parties to share model weights. Compared with sharing prediction via knowledge transfer, conventional FL system McMahan et al. (2017, 2018) suffers from several intrinsic limitations: (1) it requires every party to share their local model weights in each round, thus limiting only to models with homogeneous architectures; (2) sharing model weight incurs a significant privacy issue of local model, as it opens all the internal state of the model to white-box inference attacks; (3) model weight is usually of much higher dimension than model predictions, resulting in huge communication overhead and higher privacy cost.

Inspired by the knowledge transfer algorithms Buciluǎ et al. (2006); Hinton et al. (2015), Federated Model Distillation (FedMD) shares the knowledge of FL parties’ models via their predictions on an unlabeled public set Li and Wang (2019). However, sharing prediction may still leak the privacy of the local data Papernot et al. (2017). Currently, there is no reasonable privacy guarantee for sharing model prediction in FL. A naive approach is to add the differentially private random noise perturbation to the predictions of local models. However, prior works have shown the significant trade-off between privacy budget and model performance Bhowmick et al. (2018). We fill in the above gaps and make the following contributions:

We propose FedMD-NFDP, a novel federated model distillation framework with the new proposed noise-free differential privacy (NFDP) mechanism that guarantees each party’s privacy without explicitly adding any noise.

We formally prove that NFDP with both replacement and without replacement sampling strategies can inherently ensure $(\epsilon,\delta)$-differential privacy, eliminating noise addition and privacy cost explosion issues explicitly in previous works.

Extensive experiments on benchmark datasets, various settings (IID and non-IID data distribution), and heterogeneous model architectures, demonstrate that FedMD-NFDP achieves comparable utility with only a few private samples that are randomly sampled from each party, validating the numerous benefits of our framework.

We remark that sampling can individually serve as a privacy amplification method to tighten the privacy budget of a differentially private algorithm Balle et al. (2018), which is in sharp contrast with the inherent privacy guarantee of sampling given in this paper.

Preliminary

DP has become a de facto standard for privacy analysis. DP can either be enforced in a “local" or “global" sense depending on whether the server is trusted. For FL scenarios where data are sourced from multiple parties, while the server is untrusted, DP should be enforced in a “local" manner to enable parties to apply DP mechanisms before data publication, which we term as LDP. Compared with the global model via DP (CDP) Dwork and Roth (2014); Abadi et al. (2016), LDP offers a stronger level of protection.

A randomized mechanism $\mathcal{M}$: $\mathcal{D}\to\mathcal{R}$ with domain $\mathcal{D}$ and range $\mathcal{R}$ satisfies $(\epsilon,\delta)$-differential privacy if for all two neighbouring inputs $D,D^{\prime}\in\mathcal{D}$ and any measurable subset of outputs $S\subseteq\mathcal{R}$ it holds that

A formal definition of record-level DP is provided in Def. 1, which bounds the effect of the presence or the absence of a record on the output likelihood within a small factor $\epsilon$. The additive term $\delta$ allows that the unlikely responses do not need to satisfy the pure $\epsilon$-DP criterion. In FL, each party can individually apply $\mathcal{M}$ in Definition 1 to ensure record-level LDP.

Federated Model Distillation with Noise-Free Differential Privacy

Unlike the existing federated learning algorithms, such as FedAvg McMahan et al. (2017), FedMD does not force a single global model onto local models. Instead, each local model is updated separately. To support heterogeneous model architectures, we assume that an unlabeled public dataset is available, then parties share the knowledge that they have learned from their training data (their model predictions) in a succinct, black-box and model agnostic manner. To protect local model predictions, each party can explicitly apply LDP mechanisms by adding noise to their local model predictions, as shown in FedMD-LDP (Figure 1 (a)), or adopt data sampling before training, which inherently ensures LDP of the sampled subset, and the follow-up local model predictions as per the post-processing property of DP Dwork and Roth (2014), as demonstrated in FedMD-NFDP(Figure 1 (b)).

It should be noted that FedMD-LDP requires each party to explicitly inject noise to ensure DP individually before releasing their local model knowledge to the server. The privacy cost will accumulate as per the dimension of the shared knowledge ($|Y_{p}|*class$), as well as the communication rounds, resulting in huge privacy costs. Here $|Y_{p}|$ is the number of the chosen public set and $class$ refers to the class number. In contrast, our FedMD-NFDP inherently ensures that the released local model knowledge by each party is differentially private via random data sampling process, as indicated in Theorem 1 and Theorem 2.

Algorithm 1 describes our FedMD-NFDP algorithm, which consists of two training phases: (1) during initialization phase, every party $i$ updates its local model weights $w_{i}$ on a randomly sampled subset $(X_{i},Y_{i})\in D_{i}$ from local private training data $D_{i}$ for $T_{1}$ times without any collaboration; (2) during collaboration phase, parties share the knowledge of their local models via their predictions on a subset of public data, $X_{p}$. In each round of the collaboration phase, the detailed procedure proceeds as follows:

Each party uses its local model weights $w_{i}$ to compute prediction $Y_{p}^{i}$ for $X_{p}$ and shares them with the server.

The server aggregates the predictions (separately for each public record), i.e., computes $Y_{p}=f_{\mathsf{Aggreg}}(Y_{p}^{1},\cdots,Y_{p}^{N})$, and sends $Y_{p}$ to all parties for the next round’s local training; $f_{\mathsf{Aggreg}}$ is an aggregation algorithm, which is average function throughout this work.

Each party first updates its local model weights $w_{i}$ by training on the soft-labeled public data $(X_{p},Y_{p})$ to approach the consensus on the public dataset (Digest); then training on its previously sampled local subset (Revisit).

In addition, Algorithm 1 can also support the implementation of FedMD-LDP. The only difference is the output $Y_{p}^{i}[t+1]$ (line 19) should be perturbed by the differentirally private random noise, which can be randomly sampled from either Laplace or Gaussian distribution.

Theoretical Analysis

In this work, we consider record-level DP for each party. Below, we formally stated that NFDP with random sampling from each party’s training dataset satisfies differential privacy guarantee for each party. In particular, random sampling without replacement and with replacement are two most common sampling strategies, and we prove the $(\epsilon,\delta)$-differential privacy for both of them.

[NFDP mechanism: $(\epsilon,\delta)$-differential privacy of sampling without replacement] Given a training dataset of size $n$, sampling without replacement achieves $(\ln{\frac{n+1}{n+1-k}},\frac{k}{n})$-differential privacy, where $k$ is the subsample size.

[NFDP mechanism: $(\epsilon,\delta)$-differential privacy of sampling with replacement] Given a training dataset of size $n$, sampling with replacement achieves $((k\ln{\frac{n+1}{n}},1-\left(\frac{n-1}{n}\right)^{k})$-differential privacy, where $k$ is the subsample size.

Algorithm 1 using sampling with replacement is consistently more private than using sampling without replacement for any $n>0$ and $0<k\leq n$.

All the related proofs of lemma and theorems can be referred to the Appendix. The nice property of NFDP with random sampling once and the post-processing property of differential privacy Dwork and Roth (2014) removes the privacy dependence on the number of queries on the public dataset, allowing a more practical deployment of our NFDP in FEDMD.

Experimental Evaluation

In the experiment, we evaluate on paired datasets, i.e., MNIST/FEDMNIST and CIFAR-10/CIFAR-100. For MNIST/FEMNIST, the public data is the MNIST, and the private data is a subset of the Federated Extended MNIST (FEMNIST) Caldas et al. (2018), which is built by partitioning the data in Extended MNIST based on the writer of the digit/character. In the IID scenario, the private dataset of each party is drawn randomly from FEMNIST. In the non-IID scenario, each party only has letters written by a single writer, and the task is to classify letters by all writers.

For CIFAR-10/CIFAR-100, the public dataset is the CIFAR-10, and the private dataset is a subset of the CIFAR-100 Krizhevsky et al. (2009), which has 100 subclasses that fall under 20 superclasses, e.g., bear, leopard, lion, tiger, and wolf belong to large carnivores Li and Wang (2019). In the IID scenario, each party is required to classify test images into correct subclasses. The non-IID scenario is more challenging: each party has data from one subclass per superclass but needs to classify generic test data into the correct superclasses. Therefore, it necessitates knowledge sharing among parties.

Each party’s local model is two or three-layer deep neural networks for both MNIST/FEMNIST and CIFAR-10/CIFAR-100. All experiments are implemented by using Pytorch. A single GPU NVIDIA Tesla V100 is used in the experiments. FEMNSIT and CIFAR-10 can be done within an hour at $N=10$ parties. A summary of the public and private datasets used in this paper is provided in Table 1.

In each communication round, we use a subset of size 5000 that is randomly selected from the entire public dataset. We empirically validate FedMD-NFDP largely reduces the communication cost without degrading the utility. The number of training epochs in Algorithm 1 and the batch size in the Digest and the Revisit phase may impact the stability of the learning process. We empirically choose $R=20,T_{1}=20,T_{2}=2,T_{3}=1$ via grid search. We initialize all parties with the same pre-trained model on some labelled data in the same domain. For example, parties training on the private FEMNIST are initialized with the same pre-trained model on some labelled MNIST data.

We demonstrate the effectiveness of our proposed FedMD-NFDP by comparison with the following three frameworks. We omit the comparison with FedAvg as it delivers similar utility as the Centralized framework.

Non-private Federated Model Distillation (FedMD-NP) framework: all parties train on all their local private data, collaborate the public data distillation, and use the aggregation feedbacks to update the local model as same as FedMD. It should be noted that there is no privacy guarantee in this framework.

Centralized framework: the private data of all parties were pooled into a centralized server to train a global model. We use this as an utility upper bound.

FedMD-LDP framework: FedMD-LDP requires each party to explicitly add Gaussian noise to locally ensure $(\epsilon,\delta)$-DP before releasing their local model knowledge to the server.

2 Performance Analysis

It can be observed from Figure 2(a) that FedMD-NFDP can ensure strong privacy protection during training and communication. For each party in FedMD-NFDP we fixed $k=3$, which means we only randomly sample three private data points from each private local dataset. While more parties participate in the training and communication, the number of each private local dataset becomes smaller, since each party’s data size equals to the total number of private data $n$ divided by the number of parties $N$. Due to that, when we increase the number of the parties, the privacy budget $\epsilon$ will increase even with a fixed random sample size $k$. However, the $\epsilon$ is still very small, its log 10 scale is close to -2 for CIFAR-10 and -3 for FEMNIST, when the number of parties $N$ is 10.

Evaluation on δ𝛿\delta

: Similar to $\epsilon$, $\delta$ is defined based on Theorem 2. Figure 2(b) shows that the increasing number of parties will increase the $\delta$. The $\delta$ is small, its log 10 scale is close to -2 for CIFAR-10 and -3 for FEMNIST, when the number of parties $N$ is 10. Note that, in real life, the private data are collected by each party independently, so more parties would not decrease the local data size in practice.

Evaluation on σ𝜎\sigma in FedMD-LDP.

Besides our proposed approach, the most naive solution is FedMD-LDP. Unlike FedMD-NFDP, Fed-LDP can use all the private dataset for training and only protect the distillation information on the public dataset, as shown in Figure 1(a). However, FedMD is cursed by a massive number of queries and multi-round communications as per the sequential composition in DP Dwork and Roth (2014). Given the same $\epsilon$, $\delta$ as in FedMD-NFDP, the $\sigma$ is a huge number from 4 to 7 in the log 10 scale, compromising the utility of the original information. Due to this reason, we do not report the experimental results of FedMD-LDP in this work, since the prediction results are close to random guess with a huge noise scale of $\sigma$ for both FEMNIST and CIFAR-10. The only way to maintain utility is to set a very large $\epsilon$ and $\delta$ for FedMD-LDP, but it will result in meaningless privacy guarantee.

Evaluation on model convergence.

Figure 3 presents the accuracy trajectories of each party in our FedMD-NFDP. As shown in Figure 3, all parties can converge to a decent performance within 20 communication rounds, largely reducing communication cost. Due to the complexity of the tasks, FEMNIST shows a slightly better performance than CIFAR-10.

Evaluation on distillation approaches.

In the original FedMD Li and Wang (2019), they use logits as the distillation approach. However, in our implementation, besides the logits, we also build the distillation with softmax and argmax approaches. Softmax approach returns the soft labels and argmax approach returns the hard label for each query. From Table 3, we can see that the results did not differ too much across different approaches in general. However, we recommend argmax label approach for both FedMD and our system. There are two main reasons: (1) argmax shows slightly better performance than the other two approaches; (2) more importantly, argmax can save much communication cost of each query. Both softmax and logits need to send the float vectors, but argmax only needs to send the integer during communication.

Evaluation on IID and Non-IID distributions.

Table 4 shows the evaluation on Non-IID dataset. FedMD-NFDP can achieve a superior performance with a low privacy cost because of the noise-free differential privacy mechanism. Compared with IID, non-IID is definitely more challenging due to the incomplete data information of each class. The detailed settings of our experiments are well introduced in the appendix. From the results, we can see that FEMNIST can do better on Non-IID tasks. The main reason is for CIFAR-10 task, we only use one sub-class during training which hardly train the local model well for other classification. For example, one party has the wolfs dataset during training, but it is hardly to help classify lions correctly as large carnivores.

Evaluation on number of parities.

It is not hard to see that more parties can help improve the utility in the federated learning. Figure 2(d) shows that more collaboration can effectively improve the performance of each local model. Although we only have 10 parties in total, but it already can achieve a good performance on complex image dataset, i.e. CIFAR-10. Compared with FedMD-NFDP, previous private collaborate learning framework requires at least hundreds of parties to be robust to the noise perturbation from previous DP and LDP mechanisms Papernot et al. (2017); Geyer et al. (2017); Bhowmick et al. (2018); Sun et al. (2020a). In that sense, FedMD-NFDP also is the work that firstly provides a private collaboration system with a small number of parties.

Comparison on with replacement and without replacement samplings.

The results in Figure 4 demonstrate the correctness of the lemma 1. It is not hard to see that, while we fix the number of the parties, the increasing number of sampling examples will require a larger privacy budget. Meanwhile, the without replacement sampling spends much more privacy loss than with replacement sampling with the same size of the sampled subset. Furthermore, we evaluate the performance of both sampling strategies, and the results are shown in Table 2. From the results, we find there is no much difference between these two sampling strategies. In summary, we recommend using with replacement sampling for private model training, since it costs less privacy budget than without replacement sampling but achieves the same performance.

Comparison with baselines.

Table 2 shows that FedMD-NFDP can achieve a superior performance with a low privacy cost because of the noise-free differential privacy mechanism. For all methods, we report the average accuracy of 10 parities. When we increase the privacy budget, it can even outperform the FEDMD-NP approach and be comparable to the Centralized approach. Meanwhile, we observe that given a very small ($\epsilon$,$\delta$) with $k=16$, we can still achieve a competitive performance on CIFAR-10. None of the previous works related to differential privacy in federated learning Geyer et al. (2017); Bhowmick et al. (2018); Sun et al. (2020a) can achieve comparable performance on CIFAR-10 with such a small $\epsilon$ as ours.

Note that, we did not list the utility of the FedMD-LDP, since the utility of each model is close to random guess while we use the same privacy budget as FedMD-NFDP. Put in another way, FedMD-LDP requires an extremely large noise scale to ensure the same level of ($\epsilon,\delta$)-DP as FedMD-NFDP, resulting in poor utility. However, it no longer becomes a problem in FedMD-NFDP. After the random sampling with replacement approach in the first step, FedMD-NFDP is already $((k\ln{\frac{n+1}{n}},1-\left(\frac{n-1}{n}\right)^{k})$-differential privacy due to the post-processing property Dwork and Roth (2014).

Comparison with previous works.

Our results are competitive comparing to the previous works that adopt CDP and LDP. Currently, most of the popular differential privacy approaches, such as DP-SGD Abadi et al. (2016), PATE Papernot et al. (2017), are cursed by the number of queries and communication rounds when they are applied to FL. Since each query touches the private information, the large number of queries will cost huge privacy budget in FL with multi-round communications.

Discussion

In federated model distillation, the public dataset requires careful deliberation and even prior knowledge on parties’ private datasets. The distribution of the unlabeled public dataset could either match, or differ from the distribution of the private training data available at the parties to some degree. It needs to know how the gap widens when the public dataset becomes more different from the training dataset, the worst case could be from different domains without any overlap. There is also a potential to use the synthetic data from a pre-trained generator (e.g. GAN) as public data to alleviate potential limitations (e.g. acquisition, storage) of real unlabeled datasets. This may open up numerous possibilities for effective and efficient model distillation.

Diversity of local models.

FedMD-NFDP allows local models in FL to not only differ in model structure, size, but also numerical precision, offering great benefit for the Internet of Things (IoT) that involves edge devices with diverse hardware configurations and computing resources.

Weighted aggregation.

The aggregation step in Algorithm 1 is based on directly averaging of parties’ predictions, i.e., $f_{\mathsf{Aggreg}}$ corresponds to the average function with equal weight $1/N$, where $N$ is the number of parties. However, parties may contribute to the consensus differently, especially in the extreme cases of model and data heterogeneity. Allocating all the parties with the same weight may negatively impact system utility. We remark that there may exist more advanced weighted average algorithms that can further boost utility. These weights can be used to quantify the contributions from local models, and play important roles in dealing with extremely different models.

Limitations.

Based on the privacy analysis of NFDP mechanisms, for both with replacement and without replacement sampling strategies, we require each local party has an adequate size of the dataset. For example, if each local data only has one label, our mechanism can not protect any privacy due to the private training data’s size limitation.

In this case, NFDP could be very useful for three scenarios. First, one party is required to provide machine learning as a service (MLaaS) for others, i.e., teacher-student learning framework. While this party contains a large size of private data, NFDP could help it train a privacy guaranteed model. Second, one party has a large dataset, but the data itself is lack of diversity. The model still can not achieve a good performance due to the data diversity limitation. In this case, they need to communicate with others for a better model utility, and we can use NFDP to protect them during their communications. Finally, some learning tasks only require a small fraction of the private training data, such as FedMD Vinyals et al. (2016); Snell et al. (2017). NFDP can perform well on these tasks with adequate privacy protection. Besides FedMD, traditional one-shot learning and few-short learning tasks are also suitable to use NFDP for privacy protection for the same reason.

Related Work

Differential privacy Dwork et al. (2006); Dwork and Roth (2014) provides a mathematically provable framework to design and evaluate a privacy protection scheme. Recently, differential privacy has been applied to FL Bhowmick et al. (2018); Geyer et al. (2017); McMahan et al. (2018). Previous works mostly focus on the centralized differential privacy mechanism that requires a trusted party Geyer et al. (2017); McMahan et al. (2018); Yang et al. (2021), or local differential privacy, in which each user randomizes its gradients locally before sending it to an untrusted aggregator Sun et al. (2020a), or the hybrid mechanism by combining distributed differential privacy (DDP) with crypto system Lyu (2020).

2 Knowledge Distillation

Knowledge distillation Buciluǎ et al. (2006); Hinton et al. (2015) is originally designed to extract class probability produced by a large DNN or an ensemble of DNNs to train a smaller DNN with marginal utility loss. It also offers a powerful tool to share knowledge of a model through its predictions. Knowledge of ensemble of teacher models has been used to train a student model in previous works Hamm et al. (2016); Papernot et al. (2017); Wang et al. (2019a); Sun et al. (2020b). For example, Papernot el. al. Papernot et al. (2017) proposed PATE, a centralized learning approach that uses ensemble of teachers to label a subset of unlabeled public data in a differentially private manner, then trains a student in a semi-supervised fashion Dwork and Roth (2014). We remark that our focus is fundamentally different from the setting of PATE, which requires a trusted aggregator to aggregate the prediction label made by the teacher ensemble and conduct DP mechanisms.

3 Federated Learning

Federated learning (FL) has emerged as a promising collaboration paradigm by enabling a multitude of parties to jointly construct a global model without exposing their private training data. In FL, parties do not need to explicitly share their training data, they have full autonomy for their local data. FL generally comes in two forms McMahan et al. (2017): FedSGD, in which each client sends every SGD update to the server, and FedAVG, in which clients locally batch multiple iterations of SGD before sending updates to the server, which is more communication efficient.

More recently, FedMD Li and Wang (2019) and Cronus Chang et al. (2019) attempted to apply knowledge distillation to FL by considering knowledge transfer via model distillation, in which, the logits on an unlabeled public dataset from parties’ models are averaged. In FedMD, each model is first trained on the public data to align with public logits, then on its own private data. In contrast, Cronus mixes the public dataset (with soft labels) and local private data, then trains local models simultaneously. One obvious benefit of sharing logits is the reduced communication costs, without significantly sacrificing utility. However, both works did not offer any theoretical privacy guarantee for sharing model prediction.

Conclusion

In this work, we formulate a new federated model distillation framework with noise-free differential privacy guarantee for each party. We formally prove that NFDP both with replacement and without replacement sampling can inherently ensure $(\epsilon,\delta)$-differential privacy, eliminating explicitly noise addition and privacy cost explosion issues in the previous works. Empirical results on various datasets, settings, and heterogeneous model architectures demonstrate that our framework achieves comparable utility by using only a few private samples that are randomly sampled from each party, confirming the effectiveness and superiority of our framework.

In the future, we hope NFDP could support more privacy-preserving machine learning methods, such as semi-supervised learning, pre-training learning, meta-learning, and few-shot learning. Another direction is that we could optimize the random sampling approach with the advanced data analysis for a better promising and practical privacy guarantee mechanism. Last but not least, we could use the NFDP mechanism with advanced machine learning methods to support more applications in real life, such as natural language processing, graph analysis, and medical diagnosis.

References

Appendix

In this appendix, we first prove the privacy guarantee of random sampling without the replacement and then with the replacement.

$D$ and $D^{\prime}$ are two neighbouring datasets in the data space $\mathcal{D}$. $|D|=n$ is the size of the dataset. There are two cases including $D=D^{\prime}\cup\{u\}$ and $D^{\prime}=D\cup\{u\}$, where $u$ is the the additional sample. Let $\mathcal{M}$ be the random sample mechanism that randomly returns a subset of the data without replacement here. Let $\mathcal{S}$ denotes the all subsets in the joint domain of $\mathcal{M}(D)$ and $\mathcal{M}(D^{\prime})$. Then, we use $\Gamma(D)$, $\Gamma(D^{\prime})$ denote all subsets of $\mathcal{M}(D)$ and $\mathcal{M}(D^{\prime})$ respectively. $S\in\mathcal{S}$ is a subset in the domain, where $|S|=k$ denotes the size of the subset. Then, for a random subset $S$, we have,

Case 1 ($D^{\prime}=D\cup\{u\}$): Due to $D\subseteq D^{\prime}$, then we have,

Let $R$ is a random subset of $\mathcal{S}$ and $R$ is composed by two disjoint subsets, i.e., $R=R_{D}\cup R_{D^{\prime}\setminus D}$, where $R_{D}\subseteq\Gamma(D)$ and $R_{D^{\prime}\setminus D}\in\Gamma(D^{\prime})\setminus\Gamma(D)$. Then, we have

Case 2 ($D=D^{\prime}\cup\{u\}$): Due to $D^{\prime}\subseteq D$, then we have,

Let $P$ is a subset of $\Gamma(D)\setminus\Gamma(D^{\prime})$, then we have

Let $R$ is a random subset of $\mathcal{S}$ and $R$ is composed by two disjoint subsets, i.e., $R=R_{D^{\prime}}\cup R_{D\setminus D^{\prime}}$, where $R_{D^{\prime}}\subseteq\Gamma(D^{\prime})$ and $R_{D\setminus D^{\prime}}\subseteq\Gamma(D)\setminus\Gamma(D^{\prime})$. Then, we have

Now, we merge the Case 1 and 2 together. Then we have $e^{\epsilon}=\max(\frac{n+1}{n+1-k},\frac{n-k}{n})=\frac{n+1}{n+1-k}$ and $\delta=\max(0,\frac{k}{n})=\frac{k}{n}$. Therefore, NFDP without replacement statisfies $(\ln{\frac{n+1}{n+1-k}},\frac{k}{n})$-differential privacy. ∎

Here we use the same notation as the last proof. The proof of replacement is almost similar to the without replacement. First, for a random subset $S\in\mathcal{S}$, we have

Case 1 ($D^{\prime}=D\subseteq\{u\}$): Due to $D\in D^{\prime}$, then we have,

Let $R$ is a random subset of $\mathcal{S}$ and $R$ is composed by two disjoint subsets, i.e., $R=R_{D}\cup R_{D^{\prime}\setminus D}$, where $R_{D}\subseteq\Gamma(D)$ and $R_{D^{\prime}\setminus D}\in\Gamma(D^{\prime})\setminus\Gamma(D)$. Then, we have

Case 2 ($D=D^{\prime}\cup\{u\}$): Due to $D^{\prime}\subseteq D$, then we have,

Let $P$ is a subset of $\Gamma(D)\setminus\Gamma(D^{\prime})$, then we have

Let $R$ is a random subset of $\mathcal{S}$ and $R$ is composed by two disjoint subsets, i.e., $R=R_{D^{\prime}}\cup R_{D\setminus D^{\prime}}$, where $R_{D^{\prime}}\subseteq\Gamma(D^{\prime})$ and $R_{D\setminus D^{\prime}}\subseteq\Gamma(D)\setminus\Gamma(D^{\prime})$. Then, we have

Now, we merge the Case 1 and 2 together. Then we have $e^{\epsilon}=\max(\left(\frac{n+1}{n}\right)^{k},\left(\frac{n-1}{n}\right)^{k})=\left(\frac{n+1}{n}\right)^{k}$ and $\delta=\max(0,1-\left(\frac{n-1}{n}\right)^{k})=1-\left(\frac{n-1}{n}\right)^{k}$. Therefore, NFDP with replacement statisfies $(k\ln{\frac{n+1}{n}},1-\left(\frac{n-1}{n}\right)^{k})$-differential privacy. ∎

Sampling with replacement is $(k\ln{\frac{n+1}{n}},1-\left(\frac{n-1}{n}\right)^{k})$-differential privacy and sampling without replacement is $(\ln{\frac{n+1}{n+1-k}},k/n)$-differential privacy. Let $n\geq 1$, and then if $k=0$ or $k=1$,

Briefly, we can prove above two inequalities by mathematical induction. First, if $k=2$, above two inequalities are correct. Then we assume the inequalities are correct while $k=n-1$. Last, we easily prove if $k=n$, the above two inequalities are still correct. Therefore, for any fixed $n$, $0\leq k\leq n$, sampling with replacement is more private than Sampling without replacement. ∎