Deep Learning with Plausible Deniability

You seem to have picked Selena, which makes sense, but follow-up works have been proposed which significantly improved the effectiveness of the method [1] since this method is empirical, I wonder why you did not evaluate PATE, which actually does come with privacy guarantees and is based on a similar method? If you are only doing training-based methods, then DKFD could be a good one to consider? AdvReg also does not seem like a strong candidate to compare against since it was already shown (in the original paper) to be mostly effective for data with a small number of classes (i.e. not cifar-100), making some of the comparisons less meaningful.

Our primary objective in comparing our method with empirical defense mechanisms like SELENA and AdvReg is to demonstrate that our method can achieve comparable performance in terms of the privacy-utility trade-off while also providing formal privacy guarantees that these empirical methods lack. (The formal guarantee here is the rejection of implausible gradients which provably protects any sample that induces large changes in L2-norm with respect to its batch gradient as explained in Section 4.2.)

We are not asserting that our method universally outperforms all others on any given dimension (i.e., privacy or utility). Rather, our goal is to highlight its ability to balance privacy and utility effectively.

Regarding your suggestion to evaluate PATE, we acknowledge that it offers strong privacy guarantees. However, PATE requires access to a substantial amount of unlabeled public data from a similar domain as the private dataset. This requirement introduces a different assumption compared to our method and the other baselines we considered. Therefore, we focused on methods that operate under similar conditions to ours, without the need for additional public data.

As for DKFD and the follow-up works to SELENA that have shown significant improvements, we found that they are conceptually similar to SELENA in that they employ distillation techniques to mitigate sensitive knowledge leakage. Additionally, some of these recent works are not open-source, which poses challenges for reproducibility. Moreover, there is recent evidence that DKFD exhibits a worse privacy-utility trade-off than SELENA in certain scenarios (see https://arxiv.org/pdf/2404.17399). That said, we decided we are running the experiments to evaluate DKFD and will update the results when the experiments are finished.

We included AdvReg in our comparisons because it has been used as a baseline in prior works like SELENA and represents a different category of empirical defense mechanisms. Including it allows us to provide a broader perspective on how our method performs relative to various defense strategies.

it would be beneficial for paper's contextualisation to establish some more concrete links between the parameters of PD-SGD and the comparable DP-SGD parameters (i.e. have a simple graph comparing just these two methods as the only 'properly' quantifiable ones showing at which point PD-SGD starts showing better privacy-utility trade-off).

It is difficult to compare the parameters of PD-SGD with DP-SGD directly because these two methods hold different assumptions and the meanings of their parameters are quite different. For example, $\sigma$ in PD-SGD and DP-SGD are analogous but they are different scales — $\sigma$ of DP-SGD is scaled with batch size while $\sigma$ of PD-SGD is not. $\gamma$ and $T$ in PD-SGD serve a similar function to the clipping threshold of DP-SGD because they are both used to bound the influence of "outlier samples", they are not one-to-one mappings — and clipping is a deterministic operation whereas our privacy test is probabilistic.

Stepping back, PD and DP are aiming to protect privacy at a different level and in different ways (although they both protect membership privacy) so it is not clear how to directly map their parameters in a meaningful way. But we can compare the two techniques from an empirical privacy perspective as we shown in Figure 2.

It is clear that the method is comparable, but it is also not outperforming all of the baselines, making the abstract a bit misleading with respect to the favourable trade-offs.

The particular phrasing in the abstract was meant to refer to observations such as the one in Figure 2. However, we agree with the reviewer that this could be somewhat misleading and therefore we will soften our claims in the revised version.

Thank you for your valuable comments and suggestions.

Firstly, it is not clear what exactly happens if the gradient is implausible - do you remove it or convert all values to 0's or something else entirely? Because 'removal' in a normal sense of a word would result in different sampling for the rest of the users and would cost them more epsilon, making some of them more vulnerable (which has knock-on effects on disparate vulnerability to MIA and how the method affects that).

This is an important point to clarify. Whenever the noisy gradient obtained from the seed batch is implausible, we skip it for model updates for that iteration. However, we do not remove or alter any data samples. The training set and model weights remain unchanged.

In the next learning step, the algorithm reshuffles the training data and so it is free to select a seed batch that includes any data sample. This means that our algorithm does not prevent any sample from having an influence on the final model parameters, unless that sample itself always causes implausible gradients (which if not prevented would lead to privacy leakage).

To clarify this, we conducted a new experiment in which we record the successful update counts for each data sample in the training set and show the distribution in Figure 4 in the appendix of the revised pdf. We can observe that although there is some variation between samples (mean is 107.53 and std is 10.27), no data sample is systematically excluded (min count is 72) when training with PD-SGD.

Secondly, this has an effect on the fairness of the algorithm: the benchmarks you used only consider the standard (somewhat easy and mostly balanced) datasets. In order to see how the method performs with respect to privacy attacks and subgroup utility, more analysis needs to be done and I request that the authors add a section on how performance imbalance is affected under PD-SGD.

While our PD-SGD method does not discard any data points and ensures all have comparable sampling rates — thus not being designed to have side effects on fairness — we acknowledge that evaluating performance imbalance and subgroup utility is important for understanding how the method performs under privacy attacks. As our paper introduces PD-SGD for the first time, we consider a thorough analysis of its fairness implications to be a valuable direction for future research but outside of scope of this work. We will include a discussion of these considerations in our paper and plan to explore them in depth in subsequent work.

There is also an issue with the way the paper is positioned. I admit I had to re-read the work because it is not immediately clear this method is, in fact, not designed to be differentially private (primarily because of the discussion on adding the gaussian noise and the privacy guarantees afterwards). Just to make it more clear to the reader, I would suggest you point this out early in the text. Especially since following claim only gets introduced in 2.4: 'With some additional randomisation this can be made epsilon-delta DP' What is this additional randomisation and where does it come from? Where is it discussed and how do you convert the guarantees? This sounds (in crude terms) a little bit like k-anonymity here, where you have a rejection sampling based on the number of rows that could have been used to produce the synthetic row (i.e. a probabilistic notion of k). Could you elaborate on why this is/isnt the case and what exactly needs to be done to establish the mapping between the methods?

We apologize for any confusion. To clarify we purposefully focused our efforts away from connecting PD-SGD to DP guarantees, and we will revise the text to make this clear early on in the paper. The mention of additional randomness in Section 2.4 refers to prior work by Bindschaedler et al. (2017) who add noise to the threshold of their test. In our case, we add Gaussian noise to the gradients but do not add noise to the threshold. That said, exploring how we may adapt PD-SGD to achieve differential privacy is indeed an interesting avenue for future work.

Thank you for your valuable comments and suggestions.

The main assumption behind plausibly deniable updates is that there is no privacy leakage when an update closely resembles updates from other batches. While this assumption is intuitive, it may not hold uniformly across all scenarios. For example, consider the training of large models with very large batch sizes, where individual sample contributions are averaged out. In this case, even tiny noise may cause the gradients of two large batches to appear deniable, but not necessarily prevent individual samples from being memorized.

How does the rate of deniability scale with batch size across different datasets? What impact do varying batch sizes have on the overall privacy guarantees?

Regarding the role that batch size plays in terms of privacy, there are extreme edge cases that are unrealistic where the batch size is the entire training set or the batch size is a single example. For more realistic batch sizes there are several tradeoffs and ultimately the behavior depends also on the chosen privacy parameters.

Our findings indicate that as batch size increases, the rate of deniability typically decreases—larger batches more easily pass the privacy test (for fixed privacy parameters) due to the averaging effect you described across different datasets. However, this does not necessarily translate into better privacy protection, as the potential for individual sample contributions to still be inferred remains.

Impact of batch size on Purchase-100

Impact of batch size on CIFAR-10

Moreover, we found that adjusting other parameters—e.g., $\sigma$, $\gamma$, and threshold can help mitigate these effects, maintaining a balance between utility and privacy across varying batch sizes. For example, for the batch size = 1024, if we double the $\gamma$, we can decrease the reject rate to 56.98% and achieve a test accuracy of 63.87% with Best Attack AUC of 0.68.

These results underscore the importance of carefully tuning all parameters in relation to batch size to uphold robust privacy guarantees while preserving utility.

In Table 2, the CIFAR-10 and CIFAR-100 experiments use only 500 and 1000 training samples, respectively. While the performance of plausibly deniable updates in these settings is notable, these sample sizes are too small for a fair comparison with DP-SGD. How do plausibly deniable updates compare with DP-SGD when scaling the training set size for CIFAR-10/CIFAR-100?

We used small training set sizes for these experiments to ensure the resulting models would be vulnerable to MIA so that it would be clear if the desired level of protection was indeed achieved. However, we also included other experiments in our paper where we use much larger training set sizes (e.g., Table 3). In addition, we conducted further experiments in response to your question using a larger subset of CIFAR-100. We follow the experiment setting in RMIA which trains a WRN-28-2 from scratch on 25k samples of CIFAR-100. We show the results in the table below. It can be observed that PD-SGD can successfully defend different MIA attacks for example Attack AUC is decreased significantly from around 81% to 54% by using param setting 2 of PD-SGD. Compared to DP-SGD, PD-SGD provides much better utility.

Evaluate PD-SGD on CIFAR-100

[RMIA] Zarifzadeh, Sajjad, Philippe Liu, and Reza Shokri. "Low-Cost High-Power Membership Inference Attacks." Forty-first International Conference on Machine Learning. 2024.

As discussed in Appendix F, the privacy guarantee for plausibly deniable updates applies on a per-update basis, and the composition of these guarantees over an entire training run remains unclear.

That’s a fair point. Our proposed method is based on privacy testing per update. The composition of all the updates is interesting and we leave formal investigation of this part for future work.

The intermediate results of training with plausibly deniable updates must remain private, as revealing whether an update was skipped provides side information to the adversary. This limitation may restrict the applicability of the approach in certain scenarios, such as federated learning.

The reviewer is correct. Our solution assumes that no model intermediate updates are accessible to an adversary. While such assumptions may prevent our solution from being used in a setting such as Federated Learning, we intend our technique to mostly be used in a centralized learning environment where adversaries only observe the final model weights (or run inference with the trained model as a black-box). Note that this is a similar setting as hidden state differential privacy analyses [1-3] that focus on the privacy of the final model parameters while assuming the confidentiality of the training dynamics. We will further emphasize this fact in the final version.

[1] Ye, Jiayuan, and Reza Shokri. "Differentially private learning needs hidden state (or much faster convergence)." Advances in Neural Information Processing Systems 35 (2022): 703-715.

[2] Altschuler, Jason, and Kunal Talwar. "Privacy of noisy stochastic gradient descent: More iterations without more privacy loss." Advances in Neural Information Processing Systems 35 (2022): 3788-3800.

[3] Chen, Ding, and Chen Liu. "Differentially Private Neural Network Training under Hidden State Assumption." arXiv preprint arXiv:2407.08233 (2024).

When comparing the empirical privacy protection of plausibly deniable updates with DP-SGD, even if a fixed privacy parameter is used for DP-SGD, the clipping threshold still affects the robustness against membership inference attacks. It could be beneficial to tune the clipping threshold to identify the optimal empirical protection for DP-SGD.

Following your suggestion, we have fixed all other parameters and tuned the clip threshold for DP-SGD as shown in the following table. We can observe that even though the clip threshold changes, the model’s utility and privacy are almost the same. However, during these experiments, we do find that if the clip threshold is changed, the learning rate also needs to be tuned properly to get the optimal utility. It makes sense that the impact on privacy of the clipping threshold should not be substantial since in DP-SGD the noise added to the gradient is scaled by the clipping norm.

Impact of Clip threshold of DP-SGD

Thank you for your valuable comments and suggestions.

what does plausible deniability mean for, e.g., membership inference, attribute inference, or reconstruction robustness?

We define plausible deniability as a new privacy notion in our setting, with the main goal of protecting membership privacy for the training data. However, the notion is in principle more general. It guarantees gradient updates can be plausibly denied in the following sense. Imagine someone comes to the model trainer and accuses them of using a particular data point (x,y) at a specific training iteration. If the model was trained with PD-SGD, the owner can (in principle) readily deny that (x,y) was used (regardless of whether it was in fact used) by showing that pairs of batches from the training data that contain (x,y) and some that do not and showing they both have similar gradients updates to the ones used to update the model parameters. We demonstrate through experiments that such a notion of privacy does offer concrete protection against membership inference attacks.

if values of d in practice happen to be close enough to the noise scale, the test will have high error rates, meaning that the T plausibly deniable candidates could actually be relatively different from the seed gradient.

If values of d are close to the noise scale then it becomes difficult for adversaries to detect differences between batches given the noise. More generally, our technique like other techniques requires careful parameter tuning to achieve its objectives.

The definition concerns itself with plausible deniability of the mini-batch gradients and not individual per-sample gradients. What is the protection for individual samples? In particular, the test boils down to approximately verifying whether there exist other mini-batches within an L2 ball around the seed mini-batch. What if there exist many mini-batches with similar L2 norm, but it is the direction of the gradient that is significantly impacted by a single outlier example in the seed mini-batch? The paper lacks both formal and informal discussion on the level of protection for individuals, and the discussion in Sec 4.2 does not address this sufficiently.

Ensuring plausible deniability of the mini-batch gradients does protect individual samples. If there are multiple mini-batches with similar norms but different directions the test will behave as intended, because the condition checking plausible deniability is on the gradients, not their norm. (It is not the norm of the gradients that matters but rather the norm of gradient pair differences. For such norms to be small so that the test passes the two gradients have to point in a similar direction or both have small norms.). We will revise our paper to expand on this discussion, following the reviewer’s recommendations.

As the parameters are not immediately interpretable, the parameter tuning process lacks clarity. The authors give a rationale for their choices in Section 4.2 and Appendix D.2, but it’s still hard to see how someone would apply this method in real-world situations.

We will expand our discussion of privacy parameter tuning for our PD-SGD method. Section 4.2 discusses theoretical guidelines for parameter tuning. If one has a desired bound on $d$ then the results in that section can be applied with a grid search to find optimal parameter combinations. However, we recognize that there are practical complexities and one may not have a bound on $d$. In practice, we have found that the following strategy is easy to follow and yields good tradeoffs. Step 1: tune the noise scale $\sigma$ to achieve acceptable utility, ignoring the privacy test. This first step helps establish an upper limit for utility. Step 2: tune $\gamma$ and the threshold $T$, which allows for fine control over the privacy-utility tradeoff. This sequential tuning approach was used in our experiments.

why define advantage as 2 AUC - 1 if the standard definition is 2 balanced_accuracy - 1 = TPR - FPR?

Apologies. Our goal was not to redefine advantage but to express attack success rate in a [0-1] range for ease of comparison. We have revised Figure 2 according to your suggestion.

isn't there a parameterization of AdvReg that could be used to produce a curve instead of a single point?

Following your suggestion, we added more points for AdvReg to produce a curve in the updated Figure 2.

Experimental Setting is not described in detail

Due to the page limit, we list details of datasets, models and our experiments setup in Appendix C. Following your suggestion, we added more details about the attacks and defense mechanisms which is highlighted in the revised pdf Appendix C.3.

ml_privacy_meter change

We acknowledge that the ml_privacy_meter codebase has undergone significant changes since our submission. To ensure the exact replication of our experiments, we are providing the specific git commit hash of the version we used. It can be accessed directly at ml_privacy_meter at commit 173d4ad. Also, here is a direct link to the main.py file where the LiRA attack implementation as reference_in_out_logit_pdf_fixed can be reviewed as used in our evaluations. More description about the method can be found here. We hope this addresses your concerns.

In line 158 you say that plausible deniability can be made DP. Is this applicable to your method as well?

This specific statement is about the method proposed by Bindschaedler et al. (2017) in the context of synthetic datasets and described in Section 2.4 as part of the background. In our setting, we believe similar reasoning may apply, but we intentionally steered away from drawing a formal connection of our method to differential privacy (which we leave for future work). Also note that our technique does not randomize the threshold. Our focus in this paper is demonstrating the potential of our technique both through its analytical connection to L2 norm differences between batches' gradients and as an empirical defense against membership inference attacks achieving a better utility vs privacy trade-off compared to DP.

Could you provide some intuition on how to pick the hyperparameters in practice for your method? DP hyperparameters can be connected to MIA success bounds (e.g., Kairouz et al. [5]). How would it be for your method?

Thank you. We have expanded our discussion of privacy parameter tuning for our PD-SGD method. There is a theoretically-guided method for hyperparameter tuning discussed in Section 4.2. However, in practice we recommend as an alternative to tune the noise scale $\sigma$ first to obtain acceptable utility and then tune $\gamma$ and $T$ to achieve the desired privacy level.

Regarding the connection of DP hyperparameters to MIA success bounds, we are not sure what the reviewer means. Could you expand on that point?

Could you provide access to your code please? I would be interested in reviewing the details of that implementation.

We are providing a link to an anonymous GitHub to be shared only to reviewers due to institutional restrictions at this stage.

Thank you for your valuable comments and suggestions.

Comparison to other defenses without any error bars

We agree that this is important in demonstrating the robustness of our results through statistical measures such as error bars, particularly when comparing our PD-SGD method against other defenses across multiple metrics. We have started additional experiments to calculate standard deviations for all reported metrics.

Please see the revised version, where we have already incorporated error bars for the test accuracy and membership inference attack metrics for CIFAR-10 and CIFAR-100, as shown in the updated Tables 2. Our conclusions remain the same. Experiments for other datasets and settings are still running. But we will ensure that all results throughout the paper include this level of detail. This additional data will allow us to more precisely assess the performance of PD-SGD relative to other methods like DP-SGD and SELENA.

We also appreciate your references to related literature and we will cite them.

Runtime Comparison

This is a critical point regarding runtime comparisons. In our experience runtime can vary substantially based on several factors including model architecture specifics, training settings, and computational environment (such as CUDA versions and the specifics of the hardware used). As stated in the paper, we are using off-the-shelf Opacus. We believe differences in training setting account for discrepancies between our results and other papers' results. (For example, we are only finetuning the last layer of Vit model and [4] are finetuning the whole model; we are using open clip vit-b-16 model while [3] use a different version of Vit model from timm.)

We decided to conduct further measurements to investigate this. We measured the running time for the WRN-16-4 model and trained it from scratch with batch size=1024. We find that even though PD-SGD is slower than SGD, it is still faster than DP-SGD. And the factor between DP-SGD and SGD also changes to around 7X due to a different model architecture and training from scratch setting.

Computational Time per step for WRN-16-4 on CIFAR-10

Regarding works that attempt to speedup DP-SGD, we appreciate the pointer and are happy to cite them. We can include a comparison if the reviewer feels it is warranted. However, we emphasize that our proposed method avoids the main bottleneck of every implementation of DP-SGD, which is the necessity to store individual gradients in memory. Also, on top of avoiding storing individual gradients in memory and thus improving runtime, the main contribution of our work is to propose a novel approach for obtaining privacy for deep learning, yielding a favorable privacy utility trade-off. An exact characterization of the runtime benefits of our privacy notion is left as future work.