Deep Learning with Plausible Deniability

We thank the reviewer for the feedback and recognizing the empirical contributions of our proposed method. Regarding the identified weaknesses, we believe they stem from miscommunication or misunderstandings. Below, we provide clarifications.

1.Theoretical contributions:

Our theoretical contributions include the proposed definition of plausible deniability as applied to mini-batches and the PD-SGD algorithm, which are novel. Furthermore, the paper is the first to show that a privacy test can be used to achieve differential privacy guarantees in this setting.

More precisely: PD‑SGD is a full training‑time mechanism built around a plausibility test on noisy mini‑batch gradients: an update is kept only if the seed batch has at least $T$ $\alpha$‑similar alternatives. We show that the test’s success probability depends on the $l_2$ distance between gradients and that outlier updates are exponentially suppressed. We also provide two bounded sensitivity (sensitivity=1) test variants (Integer/Bins and Stable/Clique) so adding/removing one batch changes the count by at most 1. We further show that if the test’s threshold is appropriately randomized (e.g., with geometric noise and a ceiling probability), the construction of batch-level deniability yields per data point $(\varepsilon,\delta)$-DP for a single step. From there one can apply advanced composition to obtain end‑to‑end guarantees.

If nothing else, the paper shows a different way to achieve DP‑level protection without per data point gradient clipping. This is noteworthy as it shows a departure from existing approaches for DP in this setting which largely follow DP-SGD in using gradient clipping to bound sensitivity. It is also worth repeating that our method is compatible with non-decomposable losses unlike DP-SGD. It can therefore be applied in cases where DP-SGD cannot.

2. Comparisons of the method in terms of computational resources and memory

PD‑SGD does not require traversing all mini‑batches at each step: the privacy test stops as soon as it finds $T$ $\alpha$‑similar batches.

Moreover, PD-SGD does not require storing gradients long term. In our implementation of the privacy test, we temporarily store the noisy gradients of the seed batch and then compute and store (one at a time) the gradients for alternative batches to perform the counting as described in Alg 1. Once we know if a batch counts as an alternative, its gradient is no longer needed and we discard it. This avoids an unnecessary increase in memory usage.

Appendix F.4 provides measurements of training time. Here we provide measurements of memory usage:

Table: GPU Memory Usage Comparison

Observe that PD-SGD has similar memory usage as SGD (slightly higher but comparable) and uses much less memory compared to DP-SGD.

PD-SGD can be applied to large models as we show below. In particular we can leverage standard engineering tricks for example using low‑rank / per‑layer sketches instead of full gradients.

3. Scalability

To directly address scalability, we added a large‑model experiment: fine‑tuning LLaMA‑2‑7B on SST‑2 with PD‑SGD. Our run reaches 94.76% test accuracy while maintaining stable memory use (peak alloc memory: 6,753.48 MB). It is comparable to 94.8% reported in Table 12 of Zhao et al. [4] with normal training with LLaMA-2-7B and 92.2% with DP-Lora[5] which used another backbone model. This shows PD‑SGD is practical for LLM fine‑tuning and does not incur prohibitive memory overhead. We will add these results to the paper.

4. Threat model in empirical evaluation

Our threat model for the evaluation is black‑box membership inference against the final model. We acknowledge white‑box and property‑inference evaluations as important extensions for future work. However, our choice and the focus of our paper on the black-box setting is explicitly stated and motivated as consistent with existing defenses we compare against. It is also the dominant evaluation setting for MIA and defenses against it such as Shokri et al. [1], Ye et al.[2], Tang et al. [3].

Extension to white‑box attacks requires exposing per‑step gradients/accept/reject decisions, which our setting intentionally withholds. Nevertheless, PD‑SGD’s privacy test rejects anomalous gradients and thus specifically targets the updates that would be most informative under stronger adversaries. In particular, Appendix F shows PD‑SGD selectively rejects intentionally “poisoned/anomalous” batches while preserving normal ones, supporting this intuition and pointing to robustness beyond the evaluated black‑box MIAs. We will expand the discussion to make this connection explicit and plan white‑box or property-inference attacks as follow‑up work.

Reference:

[1] Shokri, Reza, et al. "Membership inference attacks against machine learning models." 2017 IEEE symposium on security and privacy (SP). IEEE, 2017.

[2] Ye, Jiayuan, et al. "Enhanced membership inference attacks against machine learning models." Proceedings of the 2022 ACM SIGSAC conference on computer and communications security. 2022.

[3] Tang, Xinyu, et al. "Mitigating membership inference attacks by {Self-Distillation} through a novel ensemble architecture." 31st USENIX security symposium (USENIX security 22). 2022.

[4] Zhao, Justin, et al. "Lora land: 310 fine-tuned llms that rival gpt-4, A technical report." arXiv preprint arXiv:2405.00732 (2024).

[5] Yu, Da, et al. "Differentially private fine-tuning of language models." ICLR 2022.

We thank the reviewer for providing insightful feedback and recognizing PD-SGD’s empirical performance. We agree with some of the concerns raised and have conducted additional experiments to directly address them. Other points appear to stem from miscommunication or lack of clarity in our presentation. We aim to clarify these points thoroughly below.

1. PD falls short of a "attack-agnostic" privacy framework

PD‑SGD’s “batch pool” is an internal training-time test, not an assumption about the attacker’s knowledge: the algorithm verifies for every accepted update that there exist at least $T$ alternative batches that would have produced an $\alpha$‑similar noisy gradient; this is an existential indistinguishability claim, so the adversary doesn’t need to know (or share) that pool to be confused. In fact, there is no restriction on the attacker’s knowledge about the batches or the dataset. In Lemma 4 (Appendix C.3) the batches are arbitrary and can be adversarially chosen. Said differently, to satisfy PD the training process must be able to plausibly deny any batch, including not only an adversarially poisoned batch for example but also non-existent batches (if the adversary is wrong and has no idea what kind of data the model trainer is even using).

To clarify: $d$ should not be used as a direct quantifier for the privacy of PD-SGD in the strict sense implied by the reviewer. (It is not similar to the privacy budget $\varepsilon$ for DP, it is more like a sensitivity measure.) Rather, $d$ is the $l_2$ distance between two batches’ gradients, which is a quantity useful to think about the probability of rejection as a function of the similarity between batches or the change introduced by adding/removing a single data point. Lemma 2 shows that as $d$ increases the chance that the other batch can be used to explain the update decreases exponentially (and thus such updates are overwhelmingly likely to be rejected). Satisfying PD (or not) is a property of a training process that is independent of $d$.

The bounds of Lemmas 4 and 7 are more closely related to the privacy leakage in the PD sense. These bounds do not depend on $d$ but depend on the privacy parameters (i.e., $\gamma$, $T$, etc).

2. Baselines in the experiments are quite dated.

Yes, we agree with that. We have conducted new experiments using a new empirical defense mechanism HAMP [1] which is published in NDSS 2024 on the Purchase-100 dataset and show its results with highlight in the following table:

Table: Evaluations for new baseline: HAMP

Two takeaways emerge:1. PD‑SGD (setting 1) attains higher utility than HAMP while delivering comparable privacy. 2. PD‑SGD (setting 2) provides stronger privacy than HAMP at similar utility.

3. The proposed method PD-SGD has an unfavorable privacy-compute trade-off in extreme cases.

The reviewer is correct that the computational cost of PD-SGD depends on its reject rate. However, this is only a concern in cases with extremely high rejection rates (e.g., 99%+) which result from either a lack of parameter tuning, or a case where the data distribution makes it nearly impossible to train a high utility model with bounded privacy leakage.

If hyperparameters are properly tuned, high rejection rates is a telltale sign that it may not be possible to obtain a favorable utility privacy tradeoff.

We describe a strategy for empirical hyperparameter tuning in Appendix D. Before full training, we perform a two-phase search: in Phase 1, we screen $\sigma$ values based on utility; in Phase 2, we conduct short training runs (e.g., 200 steps) across a grid of $\gamma$ and $T$ to discard configurations with degenerate behavior — such as 0% or 100% rejection rates. This early-stage filtering effectively prevents the pathological case the reviewer describes. Moreover, our empirical tuning strategy significantly improves efficiency: instead of exhaustively evaluating all combinations (180 runs taking 110.14 GPU hours), our phased search reduces this cost to just 4.15 GPU hours. Thus, the trade-off between privacy and computation is well-managed in practice.

4. Storing gradients is also not feasible for modern models in the Billions parameter range.

PD-SGD does not require storing gradients. To implement the test, it suffices to compute the noisy gradients of the seed batch and then compute (one at a time) the gradients for alternative batches to perform the counting in Alg 1. This means that we only ever need to keep in memory the gradients for at most two batches at any given time. We believe this is feasible in many practical applications, even for large models.

As evidence of the scalability of PD-SGD, we added a large‑model experiment: fine‑tuning LLaMA‑2‑7B on SST‑2 with PD‑SGD. Our run reaches 94.76% test accuracy while maintaining stable memory use (peak allocated memory 6,753.48 MB). It is comparable to 94.8% reported in Table 12 of Zhao et al. [2] with normal training and 92.2% with DP-Lora[3]. This shows PD‑SGD is practical for LLM fine‑tuning and does not incur prohibitive memory overhead. We will add these results to the paper.

5. Some details on the attack mechanisms are owed, even if in the appendix.

We thank the reviewer for the suggestion. Details of our attack setup are provided in Appendix E.3, where we describe how we implement membership inference attacks using the Privacy Meter framework. Each attack closely follows the design choices in its original paper, as cited. If there are specific aspects of the attack mechanisms the reviewer would like to see elaborated, we would be happy to clarify or include them in the revised version. We appreciate any guidance on which details would be most helpful.

6. Some training cost comparisons would be good to have.

We provide the training time per step comparisons in Appendix F.4. and Table 8. We also add additional experiments to measure the GPU memory usage against DP‑SGD and non‑private training as follows.

Table: GPU Memory Usage Comparison

PD‑SGD’s memory footprint is comparable to SGD and far below DP‑SGD. Thus, on memory‑constrained GPUs where DP‑SGD may exceed capacity, PD‑SGD remains feasible.

7. Table 1 and Table 3's font is too small.

We apologize for that and will fix it in the revised version.

Reference:

[1] Chen, Zitao, and Karthik Pattabiraman. “Overconfidence Is a Dangerous Thing: Mitigating Membership Inference Attacks by Enforcing Less Confident Prediction.” Network and Distributed System Security (NDSS) Symposium, 2024.

[2] Zhao, Justin, et al. "Lora land: 310 fine-tuned llms that rival gpt-4, A technical report." arXiv preprint arXiv:2405.00732 (2024).

[3] Yu, Da, et al. "Differentially private fine-tuning of language models." ICLR 2022.

We thank the reviewer for acknowledging the novelty and empirical contributions of our work, as well as for the comprehensive review and insightful feedback. We apologize for any confusion regarding our theoretical analysis. We provide clarification and address the questions below.

1. Threat model?

It is important to distinguish between the threat model employed for empirical evaluation and the threat model implicit in a privacy notion. These can be different, as is the case for papers evaluating black-box MIA on models trained with DP, for example. What is important is that the former matches attacks used to evaluate a defense empirically.

For the purpose of empirical evaluation, as mentioned in section 5.1, we consider a black‑box membership adversary (first threat model as you mentioned). The adversary knows the full PD-SGD algorithm and parameters, but only interacts with the final model; the training dynamics (noisy gradients, pass/fail decisions) remain hidden. This allows us to fairly compare against existing empirical defenses.

The implicit threat model in the definition of plausibility deniability is captured in the discussion in Appendix C.3 and Lemma 4. It corresponds to an adversary different and in many cases much stronger than the black-box membership inference adversary. The crucial point that “batches being created at random” as the reviewer puts it, is the way algorithms SGD (and PD-SGD) work. It is not an assumption about the power of the adversary. In Lemma 4 the batches are arbitrary and possibly adversarially chosen. Stated differently, with plausible deniability, a model trainer has to be able to defend themselves against a claim from an unusually strong adversary that crafts the batches. For example, the adversary may choose to cram all the data points with gradients pointing in a conspicuous direction in the same batch so as to maximize influence on the gradient update. The model trainer still must be able to plausibly deny use of that batch.

Since existing defenses do not satisfy plausible deniability, it does not make sense to evaluate them against the PD adversary. However, our work shows that PD-SGD empirically provides protection against black-box membership inference.

2. Why can PD-SGD protect models from black-box membership inference?

Intuitively, denying a batch was used is more difficult than denying a specific data point was included in some batch. Informally, PD‑SGD protects membership privacy by refusing to move the parameters on the basis of anomalous, high‑influence batches and only accepting updates that many other batches could have plausibly produced, thereby blurring attribution and shrinking member/non‑member loss gaps.

For a data point used during training (a member) to eventually result in successful membership inference attack once the model is trained, it must be such that it distorts the gradient of at least one batch that includes it during training. Since PD-SGD discards parameter updates unless at least T other batches make the noisy observation almost as likely (within factor $\alpha$), the leakage of any given data point at any given iteration is bounded. As Lemma 2 shows, the chance that another batch explains the observation depends on the $l_2$-distance between gradients and the greater than gradient distortion $d$ (due to adding the data point to the batch) the higher the probability of rejecting the update.

3. Computational benefits of PD-SGD:

Thanks for pointing it out. We evaluated the computation time per step for PD-SGD, SGD and DP-SGD in Appendix F.4 and Table 8. PD-SGD is noticeably slower than standard SGD but notably faster than DP-SGD for a single training step.

We agree that the rejection rate plays a significant role in training time and therefore it is worth evaluating as the reviewer suggests. Avoiding a very high rejection rate is desirable as it saves computational resources. However, the goal is not to minimize the rejection rate as some rejection as necessary for privacy. The rejection rate depends on privacy parameters $\sigma$, $\gamma$, and $T$ and therefore hyperparameter tuning can be used to strike a balance between computational complexity and memory consumption and utility and privacy. We will add a discussion of this in the revised paper.

For now, we conducted experiments to measure GPU memory usage of PD-SGD against DP‑SGD and non‑private (SGD) training with Wide-ResNet-16-4 model on CIFAR10 dataset.

Table: GPU Memory Usage Comparison

Results show that PD‑SGD’s memory footprint is slightly higher but comparable to SGD and far below DP‑SGD. Thus, on memory‑constrained GPUs where DP‑SGD may exceed capacity, PD‑SGD remains feasible. We believe the high memory usage for DP-SGD is due to per data point gradient computations, which are not necessary for PD-SGD.

We thank the reviewer for their valuable feedback. It is clear that our paper was confusing in its explanations of plausible deniability and what it provides. We apologize for the confusion due to the presentation. We will correct this in the revised version, including removing the sentence in conclusions which is misleading.

1. What is a meaningful notion of privacy?

We believe that plausible deniability, as defined in our paper, is a meaningful privacy notion that captures important practical considerations. By this we mean that the notion is well-defined, has desirable properties, and such that if satisfied then specific privacy-related violations cannot occur. That said, we acknowledge that plausible deniability frames its desideratum differently than DP and its variants and that perhaps makes it less intuitive. PD does not attempt to reason about neighboring datasets directly. Instead it reasons about the evidence we have that certain batches were or were not used.

We would respectfully ask that the reviewer reconsider our claims and proposed notion in light of our clarifications below. When considering new privacy notions it is beneficial to remain open to frameworks beyond established approaches (e.g., DP and its variants). While our framework is different from DP by design, we believe its value is best seen by evaluating it on the unique scenarios it addresses.

2. Why is batch plausible deniability meaningful, and what attacks does it prevent? What scenarios does it capture?

As explained in Appendix C, plausible deniability captures scenarios where a model trainer has to defend themselves against claims of having used some illicit/copyrighted/sensitive data for training. The model trainer provides evidence (e.g., alternative batches) to refute the accusation. If such evidence exists, then the influence on the model parameters of whatever batches were actually used for training (whatever they are) must necessarily be limited (and thus leakage is bounded).

We argue that this privacy framing is meaningful as it naturally maps onto important real-world scenarios. For example, there are several ongoing high profile copyright lawsuits where a model trainer is accused of having used prohibited data during training. Another scenario is that of incremental/online learning where new “incremental” data becomes available and is used by a model to update the model. One or more individuals in the incremental data could later decide to withdraw consent for their data and therefore the question of whether the same model could be obtained without the batch that contained this data becomes critical.

In these scenarios (and others) there is at bottom a claim that some prohibited data was used during the training (in one or more batches). And the question is: how much did that influence the final model? We think plausible deniability, i.e., denial of batches, is a reasonable way to approach this and formalize such scenarios.

Note that unlike DP, plausible deniability is a constructive notion in that the model trainer can (in principle) provide concrete evidence to refute the accusation. With DP there is no such evidence other than stating a DP training process was used. This means a model trainer could explicitly provide alternative batches for the training process. In a similar way as researchers proposed proof-of-learning to prove a model was obtained from some specific dataset [1], one could imagine building a “proof of deniability” using our framework.

3. Why is a batch notion meaningful?

A crucial point (not sufficiently emphasized in our paper; we will fix) is that the batch being denied (and the other batches) are arbitrary and can even be adversarially chosen (see Lemma 4). (We only assume that the seed batch is selected uniformly at random.) Therefore PD is also applicable in scenarios where the dataset was not split/sampled i.i.d. from the training distribution or for some reason a batch’s content is biased or composed of samples from a different distribution/dataset. (Note that in PD-SGD we use a shuffle-and-partition process which results in disjoint batches.)

This allows us to model attack scenarios where the adversary claims that the model trainer (whether true or not) purposefully crammed prohibited/sensitive data in specific batches. We believe that only “batch notions” can capture such scenarios and DP notions (in particular) cannot because they consider privacy in terms of neighboring datasets and do not consider batching or ordering of data — but batching and ordering has a substantial impact on learning (e.g., see work on ordering attacks such as [2]). Furthermore, such scenarios are important to capture because there are practical reasons why data may not be distributed “i.i.d.” across batches such as online/incremental learning or curriculum learning [3].

4. Why does PD protect individual privacy?

Protection at the level of a batch leads to protecting individual privacy. This the case for plausible deniability and many other reasonable batch notions we could consider.

We thank the reviewer for the suggestion of adapting Lemma 4 to capture individual leakage at a given step. This is interesting for future work. We point out that Lemma 4 already limits leakage for individuals consistent with the above argument. Because batches are disjoint, any individual data point appears in at most one batch per iteration. Consequently, the strongest evidence an attacker can ever observe is a single accepted update—yet that update is just as compatible with $T-1$ alternative batches that do not contain the record, leaving the attacker no firmer footing to confirm the record’s presence.

An individual’s data may appear in different batches across different training iterations. We have left for future work the case of deriving strong composition results (e.g., following Lemma 4) since our focus in this paper is mostly empirical. However, Lemma 4 can already (naively) be composed, or one can use the relationship with DP to obtain and readily derive composition results.

5. What is the threat model for PD-SGD? Why does PD-SGD protect individual privacy?

As we mentioned in section 5.1, we evaluate PD-SGD assuming a black-box membership adversary that knows the full algorithm and parameters, but only interacts with the final model; the training dynamics (noisy gradients, pass/fail decisions) remain hidden. This is consistent with related work and allows for fair comparison against existing empirical defenses.

Intuitively, PD-SGD is designed to reject high-leakage anomalous updates from batches: an update is discarded if too few alternatives can explain it. This means that when an update is accepted, the likelihood-ratio advantage for the hypothesis that a particular batch was used is bounded (by a factor depending on $\gamma$ and $T$ as shown in Lemma 4). This caps the attacker’s evidentiary lift at each step.

Since the data is partitioned into disjoint batches at every iteration, any additional data point will fall into exactly one batch, and any update from a batch cannot be uniquely attributed to any data point in that batch, which therefore limits the leakage of any data point at each step.

Empirically, we show in Appendix F.12 that the most frequently rejected data points are exactly those that have high per-example MIA success rate. With standard SGD these “vulnerable” points have 91.67% average success, which drops to 56.67% under PD‑SGD. This is direct empirical evidence that PD‑SGD protects individuals most at risk.

6. Concrete parameter–tuning algorithm

We agree that tuning PD-SGD’s parameters can be complex, as it involves three interacting privacy parameters ($\sigma$, $\gamma$, and $T$). To address this challenge, our paper provides both theoretical guidance (Section 3.1, Appendix D) and empirical strategies (Appendix F).To further evaluate the effectiveness of our empirical strategy, we conducted additional experiments on an NVIDIA B200 GPU.

As a baseline, we first performed a full grid search over all three privacy parameters ($\sigma$, $\gamma$, and $T$), covering 180 combinations in total. This exhaustive search required around 110.41 GPU hours to complete.

We then applied our empirically guided two-phase strategy, which significantly reduces tuning cost:

Phase 1 ($\sigma$ screening): We fix the threshold $T=1$ and run full training for each candidate $\sigma$. We retain only those $\sigma$ values that achieve high utility (final test accuracy $\geq$ 96%).

Phase 2 (coarse filtering of $\gamma$ and $T$): For each surviving $\sigma$, we run shortened training (200 steps) across the $\gamma$ and $T$ grid. We discard any configuration that results in degenerate behavior (i.e., reject rate reaches 0% or 100%) early. The remaining viable combinations are then trained to convergence.

We will provide full pseudo-code in the revised paper. We omit it here in the initial rebuttal due to character limit.

This procedure reduces total tuning time from 110.41 GPU hours to just 4.15 GPU hours, while still identifying high-performing configurations. In practice, this makes PD-SGD much more efficient to tune than standard grid search. Notably, we used the full grid primarily to ensure fair comparison across baselines, not because PD-SGD requires it. We believe that the combination of theory-informed constraints, practical heuristics, and structured filtering makes PD-SGD both scalable and practical for deployment.

Reference:

[1] Jia, Hengrui, et al. "Proof-of-learning: Definitions and practice." 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021.

[2] Shumailov, Ilia, et al. "Manipulating sgd with data ordering attacks." Advances in Neural Information Processing Systems 34 (2021): 18021-18032.

[3] Soviany, Petru, et al. "Curriculum learning: A survey." International Journal of Computer Vision 130.6 (2022): 1526-1565.

Concrete parameter–tuning algorithm

The proposed solution seems like a reasonable empirical way to tackle the problem.

What is a meaningful notion of privacy?

I understand this wording on its own is ambiguous but what I meant by "a meaningful notion of privacy" is a concrete connection of the proposed notion of batch plausible deniability to relevant attack settings, as probed through the questions 'What are some realistic attack settings that are directly prevented by such guarantee? What actual adversarial scenarios can be modeled by "denying an inclusion of a batch"? How does it exactly map to privacy of individuals? The privacy of "batches" is certainly not a useful primary notion of privacy.' By this I do not mean differential privacy, as the response seems to suggest.

Let me re-frame what I was looking for in a more technical way, so that there's less room for interpretation. Let's pick any survey of privacy threats, say Salem et al., 2023. They list as such membership inference, attribute inference, record reconstruction, DP distinguishability (another kind of membership inference), and property inference. In their work, the success rates of these are well-defined through games. Let's say I have trained a model with PD-SGD with $\alpha$, $\sigma$, $\gamma$, and $T$. What can I then say about success rate of any of these threats? If not success rate, can we plausibly deny membership of an example in general – as in the original paper on plausible deniability? It does not have to be specifically these threats, but a concrete connection to any other well-known attack setting or notion, e.g., re-identification, would do.

We argue that this privacy framing is meaningful as it naturally maps onto important real-world scenarios. For example, there are several ongoing high profile copyright lawsuits where a model trainer is accused of having used prohibited data during training. Another scenario is that of incremental/online learning where new “incremental” data becomes available and is used by a model to update the model.

It does not seem to me that batch plausible deniability neatly matches the cited cases. For these ones, membership inference or denying membership of an example (not batch) seems like a more appropriate model. Although I do not think it maps to the cases cited above, I agree that batch plausible deniability is an interesting setting and it could be useful. However, it is non-standard and its relevance is still unclear. I believe it is fair to list denying an adversarially selected batch as one of the implications of satisfying the proposed notion, but without further justification, e.g., a case study, it is not sufficient for some of the strong non-empirical claims in the paper, as detailed in the original review.

In sum, what I was seeking is a concrete connection to well-understood privacy threats. Intuitively, it does seem that the proposed notion should be related to denying membership of a specific example, as the response suggests in the statement "protection at the level of a batch leads to protecting individual privacy." If it were possible to make this informal intuition concrete by bounding the success rate of any of the attacks listed above or other standard attacks studied in ML, using $\alpha$, $\sigma$, $\gamma$, and $T$ in general, this would completely resolve my issue.

I will retain my score for now, because, as mentioned in the original review, the issue with the meaning of the theoretical notion is the most substantial (see the "overall, the proposed notion..." part of the review).