Deep Learning with Plausible Deniability
Authors: Wenxuan Bao
Shan Jin
Hadi Abdullah
Anderson C. A. Nascimento
Vincent Bindschaedler
Yiwei Cai
Venue: NeurIPS 2025 poster ()
Keywords: Privacy
Plausible Deniability
Privacy-Preserving Machine Learning
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Deep learning models are vulnerable to privacy attacks due to their tendency to memorize individual training examples. Theoretically-sound defenses such as differential privacy can defend against this threat, but model performance often suffers. Empirical defenses may thwart existing attacks while maintaining model performance but do not offer any robust theoretical guarantees.

In this paper, we explore a new strategy based on the concept of plausible deniability. We introduce a training algorithm called **P**lausibly **D**eniable **S**tochastic **G**radient **D**escent (PD-SGD). 
The core of this approach is a rejection sampling technique, which probabilistically prevents updating model parameters whenever a mini-batch cannot be plausibly denied. We provide theoretical results showing that PD-SGD effectively mitigates privacy leakage from individual data points. Experiments demonstrate the scalability of PD-SGD and the favorable privacy-utility trade-off it offers compared to existing defense methods.

Deep Learning with Plausible Deniability
Wenxuan Bao Shan Jin Vincent Bindschaedler
Hadi Abdullah²
Anderson C. A. Nascimento
Yiwei Cai² Visa Research
University of Florida
Abstract
Deep learning models are vulnerable to privacy attacks due to their tendency to memorize individual training examples. Theoretically-soume defenses such differential privacy can defend against this threat, but model performance often suffers. Empirical defenses may thwart existing attacks while maintaining model performance but do not offer any robust theoretical guarantees.
In this paper, we explore new strategy based on the concept of plausible deniability. We introduce a training algorithm called Plausibly Deniable Stochastic Gradient Descent (PD-SGD). The core of this approach is a rejection sampling technique, which probabilistically prevents updating model parameters whenever a mini-batch cannot be plausibly denied. We provide theoretical results showing that PD-SGD effectively mitigates privacy leakage from individual data points. Experiments demonstrate the scalability of PD-SGD and the favorable privacy-utilitty trade-off it offers compared to existing defense methods.
Introduction
Deep learning models are susceptible to privacy attacks such as membership inference 38 45
[ 14 [2 [1 that compromise the confidentiality of training data. Although mitigation strategies exist, the current state of affairs forces practitioners to choose between strong privacy guarantees and high-quality performant models. Differential privacy (DP)-based approaches [16] such as DP-
SGD 1 offer strong mathematical privacy guarantees but often substantially degrade model quality. Empirical defenses (29] 40 better preserve model quality but come without any mathematical guarantees and thus may ultimately prove vulnerable to future (yet-o--beddsseovered) attacks.
This paper introduces new approach for model training inspired by the concept of plausible deniability. The central privacy goal is to ensure that the trained model could be obtained from different data instead (and therefore model developers can plausibly deny using specific data subsets). To satisfy this privacy desideratum, we propose Plausibly Deniable Stochastic Gradient Descent (PD- SGD), a new gradient-based learning algorithm that leverages an efficient privacy test each learning iteration that scrutinizes mini-batch gradients before they are used to update model parameters. The test discards anomalous gradients that are not consistent with the desired deniability level thereby mitigating potential adverse privacy consequences from such updates (as illustrated in Fig. 2).
We formalize batch-level plausible deniability as privacy game focused on single learning iteration. We prove that achieving batch PD also protects individual examples' privacy in the sense of membership inference. With proper instantiation of the privacy test, PD-SGD satisfies batch PD and (s, 8) diiffereenia privacy. Through composition, we obtain guarantee for the entire training process.
In summary, provide new way to conceptualize privacy for model training through plausible deniability and a new algorithm for it that uses rejection-sampling based privacy testing. Compared to DP-SGD, our approach does require per-example clipping (which reduces computational and
Work partially done during internship at Visa Research
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Friecy Tixt foxen
Sub
Pass
Fail
Figure Privacy-Utility Trade-off different methods: We train WRN-16-4 on CIFAR- 10 from scratch with different defense methods. PD-SGD of- fers a better trade-off than all other defenses. Attack Advantage is x (Balanced Attack Accuracy 0.5).
Figure Privacy Test Illustration. Gradients are shown in 2-D. Pass: noisy seed gradient 9. (blue) has T d'alermativesseighhooss bound (red dashed circles). Fail: Too few gradients fall inside the region, the update is rejected.
(black) inside privacy- test
memory overhead) and it is applicable to any loss function (even non-decomposable ones). Compared to empirical defenses (i.e., Adversarial Regularization (29,, SELENA [40), and HAMP (9). our approach not only offers theoretical guarantee but also provides a superior privacy-utility tradeoff. In experiments, we find that models trained with PD-SGD often match exceed the test accuracy of empirical defenses while providing lower attack success rates against state-of-the-al membership inference attacks 45 7). We also show that PD-SGD scales to large models by fine-tuning LLaMA-
2-7B on SST-2 39
Background & Related works
Deep learning. We consider a supervised model represented by a function So where denotes the model's weights/trainable parameters. The model is trained using dataset D of n data points (r4, i E [1,n] and solving for the vector 0 that minimizes the loss function L(-) on D. This is typically done using Stochastic Gradient Descent (SGD) [20] variant 42 We focus mini-batch SGD, which we refer to as (vanilla) SGD. In each iteration, the algorithm partitions the training set into (roughly) equal-sized mini-batches, randomly picks mini-batch, and updates the parameters according to the mini-batch's gradient. Specifically given a mini batch Bj. we let 9j VoC(e, By) E Rd denote the gradient of the loss on B, with respect to the model parameters
0 E IRd. The update at step & therefore: 0₃ = 0x-1 - 7g5. where is the learning rate.
Membership inference attacks (MIAs). MIAs have been extensively studied in recent years 38 35
46
These are privacy attacks where the adversary aims determine if a target example (x, y) was included in the model's 's training set. Specifically, the adversary seeks to discern between two competing hypotheses: Ho ("non-member" or "out"): (x, y) & D, or Hi ("member" or "in"): (ar, y) E D.
33
10
45 28 50 14.
Membership inference attacks were first introduced by Shokri al. 38 employing shadow models trained on data similar to the target's to emulate its behavior and generate attack data. Recent works 45 propose different attack variants aimed at reducing adversarial uncertainty to
like Ye et al. improve attack effectiveness. Carlini et al. 7 propose Likelihood Ratio Attack (LiRA) and advocate for increasing true positive rates at low false positive rates.
Defenses with a provable guarantee. Differentially Private Stochastic Gradient Descent (DP-SGD- Abadi et al. ( provably satisfies differential privacy [17]. DP-SGD updates the model parameters iteratively like SGD, except that it bounds privacy leakage through (1) per-example clipping and (2) noise addition. Each mini-batch gradient is computed as the average over the batch's per-example gradients, but the per-example gradients are first clipped to have bounded no-mo... This ensures that each example has bounded influence on the mini-batch gradient that decreases with the size of the mini-batch. Further, the mini-batch gradient is noised with isotropic Gaussian noise before being used update the parameters.

---

Given clipping threshold C' > O, the noisy gradient is:
C +
Σ 93.4 min(1,
0 = b
[|g [[aaal]
where b is the number of examples in the mini-batch, Ij is the gradient vector of example i in batch By. and is the noise level.
The prediction accuracy of models trained this way often suffers significantly due to the impact of the noise [13] and gradient clipping 88] 31 24]. Careful tuning of hyperparameters, and (or) use of techniques such as data augmentation 12 is critical to obtain favorable utilityy, especially when the amount of training (or fine-tuning) data is limited [43]. Another drawback is increased training time, and larger memory requirements, although recent research attempts to mitigate these issues (
Empirical defenses. To address the problem of low utility while still effectively thwarting member- ship inference, several empirical defense mechanisms have been proposed. These include Adversarial Regularization (AdvReg) [29], SELENA [40] and HAMP [9]. We select AdvReg, SELENA, and HAMP because they are well-known and widely used as baselines [40] These defense mechanisms applied during the training phase, like DP-SGD
These approaches typically employ strategies such as regularization lower the attack score, or applying knowledge distillation to mitigate the attacks. While these empirical defense mechanisms can preserve the model's utility and offer some level of privacy protection, they lack provable guarantees. Consequently, it is unclear to what extent they truly eliminate sensitive information leakage or the degree to which they will be effective against future (possibly adaptive) attacks.
To the best of our knowledge, no existing defense mechanism simultancously offers a theoretically justified guarantee and maintains good model utility. Our proposed method, PD-SGD, is designed to help bridge this gap.
Plausible deniability. It is often said that differential privacy provides plausible deniability. Differential privacy ensures that the probabilities of any output on neighboring datasets (datasets that differ in exactly one example) are tightly bounded in terms of the privacy budget e. Thus, in sense, one can plausibly deny the membership of the differing example.
There are existing attempts at formalizing plausible deniability notions for machine learning such as 332 [5. Rass et al. [32) point out that since the same supervised model can be obtained from multiple datasets (including purely random ones), then one deny the dataset used. Bindschaedler et al. (5] focus on the problem of synthesizing tabular microdata where a synthetic row is produced from single row of database as "seed." The authors propose that synthetic row is plausibly deniable if the original database contains more than T (integer parameter) alternative rows that could generate the synthetic with similar probability.
3 Plausible Deniability for Deep Learning
3.1 Batch-Level Plausible Deniability
In an epoch of a mini-batch learning algorithm such SGD, the dataset is first randomly shuffled and partitioned into m mini-batches of roughly equal size. Then, m iterations are performed and in each: (1) mini-bate batch is selected, (2) the gradient of the loss function (with respect to the parameters) is computed on this mini-batch, and (3) this gradient is used to update the parameters. After the last iteration, the epoch ends.
Let T denote a one iteration learning algorithm that represents steps (1) and (2) as described above. The algorithm takes as input a sequence of batches B (BI...., B.,) and the current model parameter vector 6, and it outputs a gradient vector g. Suppose we invoke this algorithm on batches B. selects batch B (such that B B, for some e [L, m)), and outputs gradient vector g grad B;; 0), which is a function of B, and 0.
TThee are inference phase defenses such as MemGuard 23 training algorithm.
We do not consider them, since PD-SGD
3

---

Game Gu Batch PD
Game G. Singleton-Batch PD
1: (Br, Bz...., Bm) 3. B, + A (Ta) P adversary pick
1: (B., Bz...., Bm), + A (Ta)
adversary pick
batches and uaget batch
batches target data point
2: b (0. 1)
sumple random bit b
2: B, = {2)
batch with only in it
3:
3:
(0. 1]
a sample random his
4: 9 (B,, Ba... B Be)
gradient from T
4: it then
with B3 included
5:
x- Ta Ba Bmg Bc)
gradient from T
5: else
included
6:
+ (B. Bz.... Bm)
D gradient from T
6:
else
without
7:
y To Ba, Bm)
gradient from T
7: end if
wäthout B,
8:
Ala. To, Bi, Ba..... Bus Be)
8:
end
Alg, To. Bi, B2. Bm. Be) 9: 8'
Game G2 Chosen Data, Random Batches (<c Strong MD)
Game Ga - Average Membership Inference
1: S. (Ta) advennary pick dataset (IS) and
1: S S>D"
sample data points i.id. from the data
target data point z
distribution
2: (Br, B2...., Bm) t- Partition (S) randomll shuffle
2: = (To)
adversary picks target data point
and partition
3: (B:, B2...., Bm) c- Partition (S) randomly shuffle
3: B, = {x}
> batch with only it
and partition
4: b 1
sample random bit b
4: B. = {=}
batch with only in it
5: irb 1 then
5: b {U, 1]
6: 9 To (B2, B2..... Ba: Ba)
6: b then
7: else
7:
+ To(BL, Ba...., Ba Be)
8:
9 g To [Bi, Ba...., Bm)
8:
9: end
10: end 4- To Ba...., Bm)
9:
10: + Alg. To Ba)
11: b' Alg. To. B.)
Figure 3: One step privacy games relating batch plausible deniability to average membership inference. The goal of the adversary (4, ) is to guess bit b. We have that adva, 2 adve,4 for i = 0, 1,2.
Intuitively, we can plausibly deny that batch B was used (or was even batch available be selected) if the same (or similar) gradient g could have been obtained from a different (disjoint) mini-batch B' * B. In other words, if there exists B' * B among the set of batches such that g = grad (B': 8). If the gradient is computed deterministically. it would be extremely unlikely that two different batches B, B' have the exact same gradient. But if the process is randomized (e.g., if a small amount of noise is added to the gradient) then observing gradient y that could have been produced by multiple batches does not reveal which batch was used (or if all were even available in the training data).
We formalize this privacy desideratum using a game-based definition (in the style used in prior works [4 46 45)) where the adversary's 's behavior captured by two algorithms and A'. Specifi- cally, A', denotes the procedure by which the adversary chooses the sequence of m > 1 (disjoint) batches (B,, B2, ... Bm) and target batch Br, whereas A denotes the procedure by which the adversary guesses whether B, is included.
The batch PD game (Go) is shown in the top left of Fig. 3] The adversary determines the set of batches B = (B,.... Bmn) and the target batch B,. Then, a random bit b is sampled. If = 1 then the learning algorithm T is given the adversarially chosen of batches and the target batch. Otherwise, it is given only B but not the target batch. In either case, the algorithm produces some output y that is then provided to the adversary procedure A. The adversary guesses bit 1' and wins the game if 8' = b. Intuitively, if no adversary can win at this game with higher probability than random chance, then worlds in which batch is not available) are indistinguishable. Said differently, the model developer (who runs T) can plausibly deny melusion//xxlluion of any batch.
(and the target batch could be utilized) and in which 6 0 (and the target
The advantage of adversary (A, A') for a game G is A') 2Pr(b' = b} - 1 and we omit A, A' when clear from the context. The probability is over the randomness in the learning algorithm T (and the choice of bit b). We denote the advantage of the best adversary for a game G as adva- Informally, we say that a learning algorithm T provides (batch-level) plausible deniability if the adversary's advantage at the batch PD game is bounded. Crucially, batch PD is a property of the algorithm. It does not depend on the data and must hold regardless of the set of batches (which the adversary is allowed to choose).

---

3.2 Relationship to Membership Inference
Batch PD implies protection of individual examples in the sense of membership privacy. The intuition is that protecting "membership" of a batch among the available batches also protects membership of individual examples within that batch.
To show this, we construct a sequence of games Go (batch PD). G1, G2, G3 (average MIA) where the advantage of the best adversary for G; at least large as that of Gi+1- From this, conclude that batch PD implies resilience to membership inference attacks. These games are shown in Fig. and we discuss their construction and relationship in full detail in Appendix B
3.3 Indistinguishabiiity & PD Criterion
Let (.) denote the probability distribution over the output (gradient) from algorithm T. With this notation, Prt, (g (B B1.... Bm)) ) is the probability that 9 is produced when the input of T consists of the batches 2 = (Bi...,, B,n) and the parameters are 0. For conciseness, we will omit To since we will only compare probabilities in the cases where T and are fixed (and clear from the context). So we write Pr(g((B. We define plausible deniability of batches by the "closeness" of the distributions Pr(-123) and Pr(-(23' for two sets of batches B and B' that differ in exactly one batch (e.g.. B = (BI..... Bm) and (B,,,.... Bm. B3) for some batch B").
For distributions and q over the same domain X, we write =x.x' to denote that p and are (A, iiiiiiistiinuuushaall. Distributions p and are (A, iiiiniiiditt for 2 1 and 0 S X s 1 iff for all x E X and S C X we have:
p(x) S >g(x) + (x) and <(x) S xp(z)+ with / [(O)
(I)
Eq. (1) is pointwise condition that relates the two distributions by multiplicative factor À and some slack X((x) 2 0 but the slack has total mass at most X' over the domain.
Definition 1. (one step) learning algorithm T satisfies the PD criterion if for any two sets of batches B and Y' that differ in exactly one batch, we have Pr)(-12) ~x,x' (r)(-1B3) for some 2 and S X < 1.
Definition 1 is sufficient (but necessary) condition get advantage bound on batch PD, i.e.: on advG. S X+1 + X+1
X. We provide more details in Appendix B
Further theory. In Appendix C.3 we discuss the relationship between differential privacy and plausible deniability. In brief, the notions have similarities but are not directly compatible as they operate at different levels. (DP operates points; PD operates on sets of batches and reasons about adding/removing batches.) However, we show later in the paper that the PD-SGD algorithm satisfies (c, d)DDP, although the guarantee is looser than for DP-SGD (we leave improving bounds for future work).
entire datasets and reasons about adding/removing data
4 Plausibly Deniable Stochastic Gradient Descent
We propose a simple modification SGD to achieve batch PD. The idea is combine (1) random- ization of the gradient through noise addition with (2) privacy test that enables discarding (noisy) gradients that are not plausibly deniable given the available of batches. When gradients are not plausibly deniable, they are simply discarded. Otherwise, they are used to update model parameters as usual. Intuitively, this process a way to smooth out the output distribution over the gradient to make it largely insensitive to the availability of any given batch.
4.1 Randomizing Gradients with Gaussian Noise
Adding noise the gradient in SGD a well-known technique that has benefits for convergence B0 52]. In our case, we add isotropic Gaussian noise to the gradient vector g as 9 + Z, where Z ~ (0, I² We can now view each (noisy) mini-batch gradient ğ as a random variable and the probability of producing a fixed gradient vector from a batch B with gradient = grad(B; 0) is denoted p(ğ = p(ğ g) where p denotes the Gaussian pdf for Z ~N(0 o2I).
5

---

For fixed g. we say that two batches B1, B2 are a-similar iff
p B1) B2)
aa,
(2)
where a 2 1 is a privacy parameter. We write B1 ~a B2 to denote this (and omit & when clear from the context). Informally, if B1 = B2, then adversaries observing cannot establish that 9 is more likely to have originated from B1 than from B3 (other than allowed by a).
The larger the number of distinct a-similar batches, the harder it is for the adversary to link observing 9 to a specific batch. The idea of privacy testing to count the number of a-similar batches and compare the count to threshold T. We call such batches "alternativss" since if some batch B originated y then these a-similar batches are alternative explanations (that do not involve B) for the adversary observing Ø.
4.2 Privacy Testing
We construct several privacy tests by considering alternative ways of counting a-similar batches and randomizing the probability that the test passes given a specific count. In An/ppeendix C.I we discuss test variants and their properties in detail.
The privacy test acts as a local Lipschitz condition that bounds the change due to any one hatch. There important properties of privacy test that influence the achieved level of plausible deniability: (1) stability, i.e., sensitivity of the count to ading/emoving/uussttuurg a batch; and (2) bounded increase in passing probability for increasing counts.
In addition, tests that have a ceiling (i.e., a maximum probability of passing the test no matter how large the count of alternatives) are desirable. This is because they limit the information leakage from gradient rejections (failing to pass the test). However, ceilings may not be needed in practical scenarios realistic adversaries may not observe rejections.
Given a partition of the dataset into batches B (B), B2...., B.). We pick a seed batch B randomly and produce a noisy gradient ÿ. Let r = T(g. B, B) denote the count of alternatives. The privacy test takes as input the noisy gradient ÿ. the gradient g from chosen "seed" batch B, and the set of batch gradients G = (91...., Im (where g; grad B,; 0)) The privacy parameters are: a 2 1 (similarity factor), T 2 1 (count threshold), Z (count noise scale), and v/ 2 0 (florr/ceiling)
Privacy Testlg, G; T, b):
1. T + CountSimilar( (j. g, G;
2. Sample ~ Geom
3. If T + 2 7: PASS with probability 1
4. Else: FAIL
The test first computes the number of alternatives т, then it randomizes the threshold by adding an integer from the symmetric Geometric distribution with shape B. If the count matches exceeds the threshold, then the ceiling probability 1 - & is applied and the test passes or fails accordingly. If the count is below the threshold, then the test fails. For - do and v O we recover deterministic test that passes or fails based on whether the number of alternatives is at least T.
We propose three ways to count alternatives (CountSimilar), Let BI...., Bm be disjoint batches and let Bg be the chosen "seed" batch.
Simple counting: 7 is the number of distinct batches that are a-similar to B, (Eq. (2)).
Integer (>bins") counting: T is the number of distinct batches B' such that: llog,, (.) = [log,, (p(ğ
Clique counting: T is the largest le such that there exists distinct batches B1, Bg...., BR that include B., where for any pair i.j E 1,2..... k: B, za B, [5q. (2)).
In experiments, find that all three variants perform similarly (up slight tuning of privacy parameters). The simple counting method performs well in experiments (which is why we often use it). However, the other two counting methods have better theoretical properties: when adding or removing batch, the count for any noisy gradient (originating from any batch) can change by at most (i.e., sensitivity 1).

---

Algorithm 1 Plausibly Deniable Stochastic Gradient Descent (PD-SGD)
Input: Training dataset D. number of batches m. number of training sleps K, loss function [(), privacy parameters (cx, T, T.).
Initialize: Og randomly
for ..,...., K steps do
Randomly split D into { (B....., B.
Pick seed batch B. uniformly at random
9. < [o, B.)
// Compute gradient seed batch // Compute noisy gradient
- Os Z where Z ~N(,0,
Privacy testing and parameter updates
G 4-
for E ml] do
9) V VoL(0--1. B,)
I/ Compute gradient batch Bj
G GU {0;}
end for if PrivacyTestiae G; T, then
0, + 0i-1 7
else
0, 4 0:-1
end if
end for
Evaluating the test is efficient (for all ways of counting). Let exp (7) for some (we think of y as the privacy parameter instead a).
Take the log of the pdf. Checking for a-similarity
Eq. (2) is equivalent to checking if:
llogddf ()) logpdf(ğ 9:) S
(3)
which is easily testable for all batches' gradients gi for = 1, 2,... since the log-pdf of isotropic Gaussian can be computed efficiently.
4.3 Algorithm
Algorithm provides a description of the proposed method. We initialize 9g randomly and iterate for up to K learning steps. In each step, randomly partition the training data D into roughly equal size batches BI...., Bm. We pick a single seed batch B3 among them uniformly at random. We then compute the gradient vector of the loss with respect to the model parameters under seed batch B., which results in 9a. and add isotropic Gaussian noise with scale a on it to obtain noisy gradient ÿ.
Then we evaluate the privacy test, which first involves the computation of the other batches' gradients. the test passes, then we update the model parameters with the noisy gradient ğ. Otherwise, the update is never applied (keep 0; 0;-1) (i.e., we discard the update) and continue to the next step.
It can be seen that
instantiate the test recover (vanilla) SGD: take T (3 + oo and α = 0 (no noise on the gradient).
4.4 Algorithmic Complexity
The computational complexity of SGD, DP-SGD and Algorithm dJdepends on the number of gradient caleulations. SGD computes one gradient per step to update the parameters. DP-SGD computes gradients per step where b is the batch size since it needs to compute per data point gradients for clipping. PD-SGD computes the seed batch gradient (and adds noise to it), and then (up to) m 1 gradients for other batch gradients to run the privacy test.
However, since PD-SGD updates can fail, the complexity for a fixed number &t of successful gradient updates is (mm((1 - p) where is the rejection rate. This is because (1 p)-1 is the expected number of iterations to get one successful gradient update. By comparison, performing i gradient updates requires O(k) gradient computations with SGD and ((kb) with DP-SGD, Thus, for large batches >> m) we expect PD-SGD to be faster than DP-SGD. We observe this in experiments (Appendix G.9). PD-SGD also consumes less memory than DP-SGD, albeit more than SGD. Note that evaluating the privacy test does not require keeping (mm) batches' gradients simultaneously in memory, since after evaluating a-similarity (c.g., through Eg. (3) we can discard them.
7

---

Aside from lower computation and memory usage, not having to compute per data point gradients has other benefits. PD-SGD (unlike DP-SGD) compatible with any loss function, not only decomposable ones. Non-decomposable are those where the batch gradient cannot be written as sum of the individual example gradients. Kong et al. 25 discuss this issue for DP-SGD and how to mitigate it.
4.5 Privacy-Utility Tradeoff & Batch PD
Due to space constraints, we defer full privacy analysis of PD-SGD to Appendix The key results are that: (1) PD-SGD (with suitable privacy parameters) satisfies the batch PD criterion (Definition 1 for A, X such that for any 1 S T: À I a,3(1 + }) (not the exact expression) and X m m='3-((-0) and (2) PD-SGD (again with suitable privacy parameters) satisfies (e, 8.--)f)freentia privacy for e s In À (slightly different than above) and 8 S X' These results for one iteration of PD-SGD, but with DP composition results, we then obtain guarantees for the full training process.
Experiments
5.1 Experimental Setup
Threat Model. For the purposes of comparing PD-SGD against existing membership inference defenses, we assume a black-box membership adversary who knows the complete PD-SGD algorithm and its privacy parameters and the entire pool of candidate training records, but can only interact with the final trained model (or its API); does not see per-iteration mini-batches, noisy gradients, or acceptance decisions.
Setup. We use three of the most commonly used datasets for evaluating membership inference attacks [8 45 40) and DP-SGD [12 3]: CIFAR-10, 10, CIFAR-100, and Purchase- 100. For the models, we fine-tune ViT-B-16 for CIFAR-10 10 and CIFAR- 100, linear model for Purchase- 100, and Wide ResNet for CIFAR-10 and CIFAR-100 training from scratch. Unless otherwise stated, we instantiate the privacy test using simple counting without randomizing the threshold. We found empirically that counting variants performs similarly up parameter tuning variations. We tune privacy parameters T. (= In a), and a according to Appendix E In cases where we randomized the threshold and used ceiling, we set 3 and &b 0.2.
To evaluate the robustness of our defense mechanisms against such adversaries, we employ black-box membership inference attacks using the Privacy Meter We use the Population Attack (P-Attack), Reference Attack (R- Atttkkack), Shadow model Attack (S-Attack) based on [45] and Carlini al. Attack (C-Attack) based on 77. We provide full details in Appendix F
5.2 Evaluations
Privacy-UUie -Utiliy Trade-off. We primarily evaluate utility using the trained models' test accuracies, although we include results on computational overhead in (Appendix G.9 We evaluate privacy using our selected set of membership inference attacks, namely P-Attack, R-Attack, S-Attack, and C-Attack. For the first three, we report the attack AUC score. For C-Attack, we report TPR at 0.1% FPR as advocated for by 77
We use two sets of hyperparameters for PD-SGD. Parameter Setting (PS 1) is designed to optimize utility while maintaining reasonable privacy, while Parameter Setting 2 (PS 2) prioritizes better privacy at the cost of lower accuracy. Appendix Elprovides full details of how we tune parameters, and Table shows the details of hyperparameters we used in experiments.
Our findings, summarized in Table show that PD-SGD achieves a superior privacy-utility trade-off, surpassing both empirical and DP- defenses across all evaluated tasks.
PD-SGD, particularly with PS1, achieves comparable utility to the non- con-private setting, with 96.18% test accuracy on 10 fine-tuning and robust performance on CIFAR-100 and Purchase-100)

---

Table I: Evaluations for PD-SGD: We evaluate PD-SGD on three datasets with four different attacks. We report the average results and standard deviation among three independent runs. FS represents Training from scratch, and FT represents Finetuning. PS and PS represent parameter setting and 2. We can observe that PD-SGD can achieve a better privacy-utiitty trade-off than other empirical defense mechanisms and DP-SGD. In this table, we set e = 8 for DP-SGD, and we provide all experiment setups and full results in the Appendix.
Task
Method
Test acc
P-Attack
R-Attack
S-Attack
C-Attack
Nou-private
87.22%
(=13))%)
0.60 (1:0.01)
(1.000))
0.58 (=00.1)
0.22% (1.0.03%)
AdvReg
75.38%
(-0.09%)
0.53 (+00.00
0.53 (=:01))
0.19% (+00029)
CIFAR-IO (FS)
SELENA
81.04%
(=0.0%%
0.53 (+0.01)
0.53 (++0.0))
0.53 (-0.01)
0.19% (+0018)
DP-SGD
63.31%
(=0.5%%)
0.51 (+0001)
0.50 (2:000))
0,51 (=0.0))
0.13% (=0.02%)
PD-SGD (PS 1)
82.22% (=0.11%)
0.53 (100011)
0.52 (20001)
0,51 (=0.01)
0.19% (10.01%)
PD SGD (PS 2)
79.69% (=0055%%
0.53 (1:0.00)
0.50 (110.1))
0.51 (=0.01)
0.15% (10.01%)
Non-private private
96.09% (=.0.0%%)
0.57(10.01)
0.69(20.01)
0.56 (1.000)
0.37% (10.03))
AdvReg
95.96% (-0.06%)
0.56 (++0.1))
0.59 (+0.00))
0.55 (-0.00)
0.31% (+001%)
SELENA
96.01% (=0004%))
0.55 (1:0.00)
0.51 (10.01)
(1.0.2)
0.33% (10.02%)
CIFAR- 10 (FT)
DP-SGI
94.22% (-0.09%)
0.54 (+0.00)
0.59 0.59 (+0.01)
0.54 (-000))
0.23% (+0028))
PD-SGD (PS
98% (=0.06%)
0.54 (+0001)
0.49 (+0.01)
0,55 (=001)
0.27% (+002%)
PD-SGD (PS 2)
94.73% (=0.0%%)
0.53 (=0.01)
0.49 (=0.01)
0.53 (=0.01)
0.00%
Non-private
74.22%
(=0.03%)
0,73(+00011
0.73++001) 0.68(=0.01)
0.38% (#0.03%)
AdvReg
72.08% (=0.0%%)
0.70(10.01)
0,72(#0.01) 0.60(=0.01)
0.33% (10.02%)
CIFAR- (FT)
SELENA
68.46%
0.63(10.000 (=00.4%%
0.65(10.01) 0.60
0.19% (10.02%)
DP-SGD
27.12%
(-0.05%)
0.51 (+0.01)
0.52 (++001)
0.51 (-0.01)
0.13% (+0.03))
PD-SGD (PS 1)
72.50% (=0.06%)
0.62(=0.0) 0.67(+0.01)
0.64(+0.01)
0.18% (+0.02%
PD-SGD (PS 2)
68.79% (=0.0%%
0.62(10001)
0.59 (=0.01)
0.62 (=0.01)
0.14% (10.02%)
Non-private
68. 0..12%
0.76(+0.01)
0.78(=0.01)
0,77(=0.01)
0.12%(=0.02%)
AdvReg
10.00)
0,70(10.01)
0.70(=0.01)
0.66(10.01)
0.00((0.02%%)
SELENA
64.31% (.09%)
0.63(10.00)
0.66( 0.73(-0.01)
0.07(=
Purchase- 100 (FS)
DP-SGD
47.61% (=0, (2%)
0.56(+0.00
0.56
0.56(+0001)
0.88% (+001%)
PD-SGD (PS
64.83% (=0.0%%)
0.63(+0.01)
0.72(0001)
0,64(00001)
0.06% (20.01%)
PD-SGD (PS 2)
61.16% (=0.7%% 0.61(10.01)
0.59(=0.02)
0.001
0.06% (10.01%)
This high-utility performance extends to training from scratch. To demonstrate generalizability, we trained a Wide ResNet (WRN-16-4) model from scratch on CIFAR-10, with results shown in the row of CIFAR-10 (FS) Table I. Here, PD-SGD (82.22%) surpasses empirical methods like SELENA (81.04%) and AdvReg 733.. In all cases, PD-SGD exhibits stronger membership inference attack resilience than these empirical defenses, with C-Attack performance being among the lowest recorded.
Furthermore, PD-SGD provides a favorable privacy-utility tradeoff even when privacy is paramount (PS2). For instance, on Purchase- 100, there is only approximately a 7% decrease in test accuracy to obtain a reduction in attack AUC of nearly 0.15 compared to the non-private baseline. This is mirrored in the CIFAR-10 from-scratch setting, where the R-Attack AUC score shows a marked decrease from 0.60 to 0.50.
Compared to DP-SGD, the method provides comparable or better membership privacy but with much higher test accuracy. For instance, PD-SGD provides both higher test accuracy and better MIA defense than DP-SGD for 5 == 8 for 10..R-10. This superior trade-off holds in further experiments, including when fine-tuning with more data (Appendix G.TT) and training from scratch on CIFAR- 100 (Appendix G.12), where we find PD-SGD still achieves better utility and comparable membership privacy even when using a large= E like 500 for DP-SGD.
We further illustrate the privacy-utility tradeoff between methods visually in Fig. I The x-axis shows the (empirical) attack advantage, and the y-axis shows the test accuracy for the 16--16-4 model trained on CIFAR- 10. Compared to DP-SGD, PD-SGD provides higher test accuracy for the same attack advantage, even for high privacy cases i.e., attack advantages close to Compared to empirical defenses. PD-SGD not only can provide better utility with comparable attack ad advantage but also offers way to navigate the tradeoff (through the privacy parameter) and not (only) a fixed point on the privacy-utility landscape.
Scalability and Efficiency. To show the scalability of PD-SGD, we fine-tune -LLMMA2--7B 44 on SST-2 [39 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. [51] with normal training and 92.2% with Do-Lora [4]. This shows PD-SGD is practical for LLM fine-tuning and does not incur prohibitive memory overhead.
9

---

Table 2: Impact of Privacy Test and Noise: We keep all hyperparameters the same, only changing the threshold control privacy lest. v means the presence noise or the application a privacy test, means the absence of these components, and & represents the use of random rejection for gradient updates instead of standard privacy testing.
Method
Noise
Privacy Test
Test acc
P-Attack
R-Attack
S-Attack
C-Attack
Non Private
96.08%
0.56
0.68
0.56
0.35%
Only Noise
94.99%
0.54
0.57
0.55
0.30%
Only Privacy Test
96.01%
0.55
0.56
0.56
0.32%
Random Rejection PD-SGD
94.78%
0.55
0.54
0.54
0.28%
94.70%
0.53
0.48
0.53
0.20%
Although the privacy test introduces overhead compared to SGD, PD-SGD is significantly more efficient than DP-SGD. This is because PD-SGD operates at the batch level, avoiding the costly computation and storage of per-example gradients. A single training step is substantially faster, and GPU memory consumption is drastically lower remaining comparable to non-private training and using less than half the memory required by DP-SGD in our experiments. Full details on computational time and memory usage available in Appendiix G.9
Privacy Test and Gradient Noise. Compared to SGD, PD-SGD includes two components: (1) noise addition to the seed batch's s gradient, and (2) a plausible deniability- based privacy test. We create a set of principled experiments to isolate the effect of these two components.
Only Noise: we set T' = 1 (e) = O, 3 + oo), ensuring the privacy test will always pass.
Only Privacy Test: use privacy test normally, but update parameters using the un-noised gradient.
Random Rejection:
seed batches' gradients are randomly rejected at the same rate as PD-SGD.
Table 2 shows the results. Adding noise to the gradient without the privacy test does not effectively defend against membership inference. The R-Attack success rate decreases substantially, but there is no substantial decrease for P-Attack, S-Attack, and C-Attack. Similarly, if the privacy test used but the gradient is un-noised or updates are randomly rejected, we again see no major decrease membership inference attack success rates. By contrast, PD-SGD exhibits the largest effect in mitigating membership inference attacks. The R-Attack success rate drops further to 0.48, and other attack vectors like P-Attack, S- S-Attack, and C-Attack are similarly reduced.
These results demonstrate that it is the combination of both noise addition and privacy testing that results in the observed privacy protection of PD-SGD.
Additional Experiments. In Appendixx G
we explore trade-off's between the privacy parameters,
show the impact of the batch size/number of batches, rejection rate for PD-SGD, and provide additional experiments such as training from scratch on CIFAR-100. We also evaluate how PD-SGD rejects anomalous batches, its computation time and GPU usage per training step, frequency of examples used in PD-SGD, compared to SoTA DP-SGD and new defense mechanism (e.g.. HAMP (9). privacy-test variants, and vulnerable data points identified by PD-SGD.
6 Conclusions
We proposed a new approach for training models with privacy, inspired by the concept of plausible deniability. Our construction, PD-SGD, is based on rejection sampling approach using privacy test. We show that PD-SGD limits membership inference attack success rate and show that PD-SGD can be instantiated meet differential privacy guarantees. In experiments, we find that PD-SGD provides a superior privacy-utility trade-off compared to existing defense methods. This makes PD-SGD promising solution for enhancing privacy protection in practical deep-learning applications.
There are limitations that we plan to alleviate future work. The relationships between batch PD, membership inference, PD-SGD, and differential privacy are per iteration. They can be extended to the entire training process, but we believe that the resulting bounds are loose and that stronger composition results can be derived. Also, we focused on the centralized learning setting, and more work is required for application to collaborative or federated learning.
10

---

Acknowledgments
We thank the anonymous NeurIPS reviewers and area chair for their helpful feedback and suggestions. This work was supported in part by the National Science Foundation under CNS- 123. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.
References
[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and I.. Zhang. Deep learning with differential privacy. In Proceedings the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] M. Aerni, J. Zhang, and F. Tramer. Evaluations of machine learning privacy defenses misleading. In ACM SIGSAC Conference on Computer and Communications Security (CCS), 2024.
[3] W. Bao, F. Pittaluga, V. K. BG, and V. Bindschaedler. Dp-mix: mixup-based data augmentation for differentially private learning. Advances in Neural Information Processing Systems, 36, 2024.
[4] M. Bertran, S. Tang, A. Roth, M. Kearns, J. H. Morgenstern, and S. Z. Wu. Scalable membership inference attacks via quantile regression. Advances in Neural Information Processing Systems, 36:314-330 2023.
[5] V. Bindschaedler, R. Shokri, and C. A. Gunter. Plausible deniability for privacy-preserving data synthesis. Proceedings of the VLDB Endowment, 10(5), 2017.
[6] Z. Bu, J. Mao, and S. Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. Advances in Neural Information Processing Systems, 35:38305-38818,, 2022.
[7] N. Carlini, S. Chien, M. Nasr. S. Song. A. Terzis, and F. Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium Security and Privacy (SP). pages 1897-1914. IEEE, 2022.
[8] X. Chen, S. Z. Wu, and M. Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances in Neural Information Processing Systems, 33:13773 13782, 2020.
19] Z. Chen and K. Pattabiraman. Overconfidence is a dangerous thing: Mitigating membership inference attacks by enforcing less confident prediction. In Network and Distributed System Security (NDSS) Symposimm, 2024.
[10] C. A. Choquette-Choo, F. Tramer, N. Carlini, and N. Papernot. Label-only membership inference attacks. In International conference on machine learning, pages 1964-1974. PMIR, 2021.
[11] J. D. Cook. Upper & lower bounds for the normal distribution function. attpp://www, jow.dwook.cooo..oo /omm blog/norm-dll diorm-dist-bbumne bounds/ 2024.
[12] S. De. L. Berrada, J. Hayes, S. L. Smith, and B. Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 136500 2022.
[13] F. Dörmann, O. Frisk, L. N. Andersen, and C. F. Pedersen. Not all noise is accounted equally: How differentially private learning benefits from large sampling rates. In 2021 IEEE 31st International Workshop on Machine Learning for Signal Processing (MLSP), pages 1-6. IEEF, 2021.
[14] J. Dubiáski, A. Kowalczuk, S. Pawlak, P. Rokita, T. Trzciński, and P. Morawiecki. Towards more realistic membership inference attacks on large diffusion models. In Proceedings of the IEEF/CVF Winter Conference on Applications of Computer Vision, pages 4860-4869, 2024.
[15] L. Duembgen. Bounding standard gaussian tail probabilities. arXiv preprint arXiv:1012.2063. 2010.
[16] C. Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pages 1-12. Springer, 2006.
[17] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265 -844, Springer, 2006.
[18] C. Dwork. A. Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211 14:211--1477, 2014.
[19] A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally meliity-maimizing privacy mechanisms. In
Proceedings the forty-first annual ACM symposium on Theory of computing, pages 351-360, 2009.
11

---

[20] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev. E. Shulgin, and P. Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine Learning, pages 5200-5209. PMLR, 2019.
[21] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEFE conference on computer vision and pattern recognition, pages 770-778, 2016.
[22] Y. He, B. Li, L. Liu, Z. Ba, W. Dong, Y. Li, Z. Qin, K. Ren, and C. Chen. Towards label-only membership inference attack against pre-trained large language models. In USENIX Security, 2025.
[23] Jia, Salem, M. Backes, Y. Zhang, and N. Gong. Memguard: Defending against black-box membership inference attacks via adversarial examples. In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, pages 259 279, 2019.
[24] A. Koloskova, Hendrikx, and S. U. Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pages 17343-17363. PMLR, 2023.
[25] W. Kong, M. Ribero, et al. Differentially private optimization for non-dccomposable objective functions. In The Thirteenth International Conference on Learning Representations.
[26] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[27] Y. Long, L. Wang, D. Bu, V. Bindschaedler, X. Wang, H. Tang, C. A. Gunter, and K. Chen. A pragmatic approach to membership inferences machine leamning models, In 2020 IEEE European Symposium on Security and Privacy (EuroS&P), pages 521-534, IEBE, 2020.
[28] T. Matsumoto, T. Miura, and N. Yanai. Membership inference attacks against diffusion models. In 2023 IEEE Security and Privacy Workshops (SPW), pages 77-83, 2023.
[29] M. Nasr, R. Shokri, and A. Houmansadr. Machine learning with memhership privacy using adversarial regularization. In Proceedings of the 2018 ACM SIGSAC conference computer and communications security, pages 634 646. 2018.
[30] A. Neelakantan, L. Vilnis, Q. V. Le, I. Sutskever, L. Kaiser, K. Kurach, and J. Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint 151 1..5111.000 1,06807, 2015.
[31] J. Qian, Y. Wu, B. Zhuang, S. Wang, and J. Xiao, Understanding gradient clipping in incremental gradient methods. In International Conference on Artificial Intelligence and Statistics, pages 1504-15 1512. PMLR, 2021.
[32] S. Rass, S. König, J. Wachter, M. Egger, and M. Hobisch. Supervised machine learning with plausible deniability. computers & security, 112:102506, 2022.
[33] A. Sablayrolles, M. Douze, C. Schmid, Y. Ollivier, and H. Jégou. White-box vs black-box: Bayes optimal strategies for membership inference. In International Conference on Machine Learning, pages 5558-5567. PMLR. 2019.
[34] A. Salem, G. Cherubin, D. Evans, B. Köpf, A. Paverd, A. Suri, S. Tople, and S. Zanella-Béguelin. Sok: Let the privacy games begin! unified treatment of data inference privacy in machine learning. In 2023 IEEE Symposium on Security and Privacy (SP), pages 327-345, IEEE, 2023.
[35] A. Salem, Y. Zhang, M. Humbert, P. Berrang, M. Fritz, and M. Backes. MI-leaks: Model and data independent membership inference attacks and defenses on machine learning models. arXiv preprint arXiv:1806.00 1180.00066666.. 2018
[36] T. Sander, P. Stock, and A. Sablayrolles. Tan without a burn: Scaling laws of dp-sgd. In International Conference on Machine Learning, pages 29937-29949. PMLR, 2023.
[37] C. Schuhmann, Beaumont, R. Vencu, C. Gordon, R. Wightman, M. Cherti, T. Coombes, A. Katta,
C. Mullis, M. Wortsman, et al. Laion-5b: An open large-scale dataset for training next generation image-text models. Advances in Neural Information Processing Systems, 35:25278-25299 2022.
[38] R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP). pages 3-18. IEEE, 2017.
[39] R. Sucher, A. Perelygin, J. Wu, J. Chuang. C. D. Manning, A. Ng. and C. Potts. Recursive deep models for semantic compositionality over sentiment treebank. In D. Yarowsky. T. Baldwin, A. Korhonen, K. Livescu, and S. Bethard, editors, Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing. pages 1631-1642 1642, Seattle, Washington, USA, Oct. 2013. Association for Computational Linguistics.
12

---

[40] X. Tang. S. Mahloujifar, L. Song. V. Shejwalkar, M. Nasr, A. Houmansadr, and P. Mittal. Mitigating membership inference attacks by (Selt-Distilation) through novel ensemble architecture. In 31st USENIX Security Symposium (USENIX Security 22), pages 1433-1450. 2022.
[41] J. Tao and R. Shokri. Range membership inference attacks. In 2025 IEEE Conference Secure and Trustworthy Machine Learning (SaTML), pages 346-361. IEEE, 2025.
[42] Y. Tian, Y. Zhang, and H. Zhang. Recent advances in stochastic gradient descent in deep learning. Mathematics, 11(3), 2023.
[43] M. Tobaben, A. Shysheya, J. F. Bronskill, A. Paverd, S. Tople, S. Ganella-Beggelee R. E. Turner, and Honkela. On the efficacy of differentially private few-shot image classification. Trunsactions on Machine Learning Rexearch, 2023.
[44] H. Touvron, L. Martin, Stone, Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, Bhargava, S. Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 2023.
[45] J. Ye, A. Maddi, S. K. Murakonda, V. Bindschaedler, and R. Shokri. Enhanced membership inference attacks against machine learning models. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 3093 3106, 2022.
[46] S. Yeom, I. Giacomelli, M. Fredrikson. and S. Jha. Privacy risk in machine learning: Analyzing the connection overfitting. In 2018 IEEE 31st computer security foundations symposium (CSF), pages 268-282. 282. IEEE, 2018
[47] A. Yousefpour. I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, J. Nguyen, S. Ghosh, A. Bharadwaj. Zhao, G. Cormode, and Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109, 12298, 2021.
[48] D. Yu, S. Naik, A. Backurs, Gopi, A. Inan, Kamath, J. Kulkarui, Y. T. Lec, Manoel, L. Wutschitz, Yckhanin, and H. Zhang. Differentially private fine-tuning of language models. In International Conference on Learning Representations, 2022.
[49] S. Zagoruyko and Komodakis. Wide residual networks. british machine vision conference (bmvc), 2016.
[50] S. Zarifzadeh, P. Liu, and R. Shokri. Low-cost high-power power membership inference attacks. In Forty-first International Conference on Machine Learning, 2024.
[51] Zhao, T. Wang. W. Abid, G. Angus, A. Garg, J. Kinnison, A. Sherstinsky, P. Molino, T. Addair, and D. Rishi. Lora land: 310 fine-tuned Iims that rival gpt-4, a technical report. arXiv preprint 20070220.. 2024.
[52] L. Ziyin, K. Liu, T. Mori, and M. Ucda. Strength of minibatch noise in SGD. In International Conference on Learning Representations, 2022.
13

---

Road Map
This appendix structured follows:
Appendix A
Notation: a compact table of symbols used throughout the paper.
Appendix B Batch PD Analysis: more the relationship between batch PD and other
privacy games such as membership privacy, and derivation of bounds on adversary's advantage.
Appendix Privacy-Test Analysis: detailed study of the privacy tests and their properties, and the derivation of the (e, 8DDP guarantee.
Appendix D
What Batch Pass the Test: analysis of gradient rejection and its implications.
Appendix Hyper-parameter Tuning: practical guidance on choosing the noise scale o, threshold 7. and neighbor count T, illlsstrted with privacy-utllity curves.
Appendix F Implementation Details: datasets, model architectures, training settings, and configurations for four black-box membership-inferencc attacks.
Appendix G
Extended Experiments: additional results and ablation studies, including training with larger datasets, training from scratch on CIFAR-100, rejection of anomalous batches, training-time efficiency, parameter sensitivity analyses, frequency of examples used of PD-SGD, comparison to SoTA DP-SGD, privacy-test variants, and vulnerable data points identified by PD-SGD.
A Symbols
Table 3: Table of Symbols.
Symbol
Meaning
Where
(I,
Individual Example From Training Set
Section
0
Model Parameter Vector - 0 Rd
Section 2
B;
SGD Mini-Batch
Section 3.1
B
A sel of batches
Section 3.1
gs
Gradient (of the Loss wrt 0) of Batch
Section
B.
Chosen "Seed" Batch
Section 4.
9s
Gradient of Seed Batch
Section 4.
9
Noisy Gradient Gaussian Noise -0(,0
Section 4.1
7
Section 4.1
T(B,2) B)
The number a-similar batches to
Section 4.2
Privacy Parameter - Noise Scale
Section 4.
7
Privacy Parameter Log-PDF Threshold
Section 4.2
O
Privacy Parameter - 0 = exp(7)
Section 4.2
T
Privacy Parameter Count Threshold
Section 4.2
3
Privacy Parameter Threshold Randomization
Section 4.2
Privacy Parameter - Test Ceiling
Section 4.2
A
PD Indistinguishability /RR Bound
Section 3.3
N
PD Indistinguishabiiity LR Slack
Section 3.3
B More on Batch PD
In this section, we provide more details on the game based construction of Section 3.2 and derive advantage bounds based on the PD criterion Section 3.3
B.1 From Batch PD to Membership Privacy
Consider the series of games from Fig. 3 These games are provided in the style of Salem et al. and connect batch PD to (one-step) MIA. We assume there are at least m > 2 batches that are disjoint and of roughly equal size. We let D denotes the data distribution (used only in some games).
14

---

Difference between Batch PD (Go) and G1: In G1 the adversary does not get to pick a full target batch, but only a single data point.
Observe that: adva. 2 adva, Any adversary that wins G1 with some advantage can play Go and output the same
Bg as it would when playing G1-
Difference between 11 and G2: In G2 the adversary picks the dataset S but does not determine the partitioning into batches (or learn it).
We have: adva, 2 advg,, If adversarial partitioning provides any benefit then adversaries for G1 can use that but those for G2 cannot.
Difference between G2 and Gz: in G3 the adversary picks only the target data 2, not the dataset S (which is sampled randomly).
We have: adva, 2 adva, We conclude: adve, 2 adva. A one-step algorithm T that achieves batch PD also has a bounded (one-step average) membership inference advantage.
Relationship to other privacy games. The Salem et al. 34 SoK establishes the relationship
between a number of data inference games. However, the games Salem al. (34 are (1) not one step; (2) do not model batches and partition; and (3) operate "replace-one" setting (i.e., adversary chooses 20, 21 but 26 is included; c.g., Game in the SoK) not the "add-remove" setting.
Differences (1) and (2) are a consequence of working with batch notion. We need the games to explicitly model the batches. We do not believe (3) is consequential difference. is well-know that the "replace-one" and "add-remove" settings can be related (usually constant factor is the difference between the two). To be consistent with the rest of the paper, we follow the "add-remove" setting.
B.2 Bounding Adversarial Success Rate
We show that the PD criterion is a sufficient (but not necessary) condition to bound the ad advantage of any adversary at the batch PD game. Recall that a learning algorithm T satisfies the PD criterion (Definition I iff for any two sets of batches B and Y that differ in exactly one batch, the distributions (-7() and (r (-123) are (A, -iniiiiitiinn for À Z 1 and X' < 1.
Let H₂ be the hypothesis corresponding to bit b. The likelihood ratio is r(g) = Pr(a] Ho) For conciseness, we write (g) Pr(gl Ha). In this game (and
Consider the batch PD game Go in Fig. 3
Hr)
all the ones we consider in this paper). we have equal priors since Pr(b 1) 1/2 and so the posterior odds are exactly the likelihood ratio, i.e., the best adversary guesses based on the likelihood ratio (b' iff r(g) 2 1 else 6' 0).
Advantage is the total variation distance between the two likelihoods, i.e., adv = adva. = 1 - 4 Alternatively,
reason in terms of type I and type II errors. Define A = [g : r(g) 2 1) {g: 1, (g) 2 [o{g) the region under which the adversary decides in favor of H, Let PD = Hr) (probability of detection), PFA Pr(A Ho) (false alarm), and PMD Pr(A9(Hi
Pp
Since: adv = ,r(A(H, - Pr(A[H)) = PD - PF = 1 -PFA (PMA+PMD) maximizing advantage the same as minimizing the sum of missed detections and false alarms.
Lemma 1. Let Go denote the batch PD game. If a learning algorithm T satisfies the batch PD
criterion Definition Ty for some X Z 1 and X 2 0. Then the advantage of any adversary in the batch PD game is bounded:
A-1
X
A
X
advGo
X+1
A A+1
x
2
We provide the proof in Appendix H.T. SGD construction for X, depending only on the privacy parameters (and the number of batches).
As we show in Appendix C.2 Lemma I applies to the PD-
B.3 Multiple Steps
The definitions and games discussed so far focus on a single learning step. We can extend the batch PD game to k > 1 iterations by keeping b fixed across iterations, but letting the adversary choose different sets of batches and target batch across iterations. The adversary gets all of the gradients produced and guesses bit D' at the end.
15

---

Game G - k-steps Batch PD
1: 0g initialized randomly
2: 6~ (0,0,1}
sample random bit
3: fori= 1,
do (B1, ....... Bm) Bt t (To:..))
4:
> adversary pick batches and the target batch D gradient from T with B, included Di gradient from T without B
5: if = 1 then
6:
9i - To._1 B1, B2...., Bm Bi)
7: else
8:
9: + To; (Bi, B2.... Bm
9: end if
10: Update 02
end for
12:
6' 9k.
Note that the algorithm depends on the current parameters 0 at each iteration and therefore the distribution across iterations, even for the same batches, is not identical.
Because the batches (adversarially chosen) may change at every iteration, not every possible run of this game maps onto realistic training process. In actual training process with SGD-like algorithm, the set of batches changes but is constrained to always be a valid partition the training dataset. However, bound the advantage of the best adversary for this game is bound any adversary (A, A'), including those adversaries that are restricted to choose batches so as to mirror an actual training process (by restriction A'). This allows the game capture numerous scenarios.
For example, this can model the case where there is fixed dataset D and the adversary wants to determine whether small set of "correlated" examples S (I1, v1...... (æ), 31) training data. In this case, can select any partition Bi...., B,, (different at each iteration) such that their union equals D and as the target batch B, any batch that includes all of S (i.e., S C B,).
part of the
This then captures the case where (for whatever reason) the dataset may include all of S in one batch (e.g., the training process is poisoned in some way).
C Privacy: Tests, Batch PD & Differential Privacy
In this section, we explore the relationship between privacy testing and batch PD and between PD-SGD and differential privacy.
C.1 Privacy Testing
Recall from Section 4.2 the different ways of counting alternatives in the privacy test. The integer and clique variants have the property that adding or removing any batch changes the count of alternatives by at most 1. Also recall that we considered a randomized version of the test that also caps the probability of passing the test.
Randomized Thresholds. Given the count t of alternatives, we randomize the test based on noise (3) so that the test passes iff r + 2 2 T. We define Gcom(B) for 3 1 so that Pr(z 8-1 3-14 for any integer This type of geometric noise initially proposed by
Ghosh et al. [19].
The probability passing the test is E[1,+22r] where we can think of r + 2 as a noisy count. For conciseness, write p. Pr(z 2 T T) denote the probability that the test passes given the count T. All our privacy test variants are such that the probability of passing the test only depends on т. When using test such that the sensitivity of is then the probability of passing the test when adding or removing one batch changes only by a bounded amount (e.g., by at most a factor of 3 when increasing by 1).
Adding a Ceiling. We also have a ceiling on the probability of passing the test. If there are enough alternatives (i.e., J + 2 T)) then flip a coin with probability of heads 1 (for some 0). If the coin lands on heads then the test passes. Otherwise the test fails. This means the probability of passing the test is p. (1 Pr(r 2 T). For example, if g/ 0.2 then the test never passes with probability higher than 0.8.
16

---

Properties. With this setup, we obtain the following properties that describe how the probability of passing the test changes for changing number of alternatives.
Lemma 2. Let p+ be the probability of passing the test with randomization Geom(3) and ceiling
0 alternatives for test with
v. We have:
Pr+1 1 1
S and 1 1 pr+1 Pr
Pr
12
The lemma states that p, is non-decreasing as a function alternatives T and then when increasing the count by one (e.g.. if adding batch), the probability of passing the test increases by a factor of at most B. Further, the change in probability of failing the test due to increasing the count by one is lower bounded function of B and vb.
Moreover, when T is far from the threshold T, the test passes with exponentially small probability,
Lemma 3. Let pr be the probability of passing the test with т 0 alternatives for test with randomization Geom( B) and ceiling 1 - v. For any 1 1 t T:
Pt S
1b exp (-E0 t))
where = In B.
The proof' of Lemmas 2 and are in Appendix H.2.
We provide experiments that compare different variants of the privacy test in Appendix G.8
C.2 PD Criterion
Recall from Lemma 1 that any (one-step) learning algorithm T that satisfies the PD criterion has bounded advantage (for batch PD game, membership inference, etc.). We show that the properties of the test in combination with a-similarity Definition
Lemma 4. Let T denote single training iteration of PD-SGD (Algriithm 1) with a privacy test with parameters T 1, a > randomization Gcom (3) and ceiling tb (for 3 2 and 1 + 0). For any integer 1 < t < T: T satisfies the PD criterion DDefnittion 7) (on any partition of m 2 T
batches) for:
A = X(t) = max
m
3
1+
171 + 1
3
1 10
m
m +
31b
m
mbb
and
1 sb (T-1)
X = =()
m
In this lemma, can be freely chosen to trade off between and X. The proof is Appendix H.3 Combining Cembins Lemmas a yields the advantage bound on batch PD.
The À term in Lemma case we expect the term that depends on ot, 33 and / to denominate. For example, we can eliminate the dependence on & by choosing v (8+1) 1)-1 1)-1 in which case the other terms are at most m+11 B. For large enough number of batches, m+1 approaches
be simplified for some constraints the privacy parameters, in which
m behavior is driven by the term B(1 + at 11).
C.3 Differential Privacy
For reasons analogous to PD-SGD satisfying the PD criterion (Lmma 4). we show that the algorithm satisfies (s, ddffffferlltial privacy.
However, we stress that batch PD and differential privacy are not directly compatible in the sense that the input to the learning algorithm T for batch PD a partition of batches, whereas for differential privacy it is a dataset D. This means that for differential privacy, we need learning algorithm T' to first randomly partition into a set of batches before passing those batches T. This straightforward conceptually, but it highlights an important consequence: the batch PD guarantee has to hold for the worst case partitioning (since it's adversarially chosen). In the differential privacy case, the adversary does not know the partition of the dataset into batches.
17

---

Lemma's 5. Let T be as in Lemma 4 with privacy parameters (T. a. G. v) and M the algoritim that first randomly partitions the dataset into 2 T batches (of roughly equal size) before invoking T. For any Two neighboring datasets Dı, D2, any output set S C Range(M) and any integer 1 St < M satisfies (e, diffferrrttia privacy. That is:
Pr(Y)M(Di)) (P(())((()))) +
where E In (1 aa) and - 11 4)) exp (-Eo t)). Here EO -In3, =nx()=)
We provide proof in Appendix H.4
Parameter Tuning. is possible tune the parameters so the guarantee fairly stringent. Similarly
to earlier, we may want to set relatively low ceiling. i.c., & = (3 + 1)= 2 To ensure a small 6, it desirable set & such that T is relatively large. For example, we can set ' and such that
exp(-Eu(T - t)) = Di which requires T In DDi + and ensures that 5 Σ 1 (1 1)) [D That
5 is asymptotically smaller than | if we consider fixed batch size (so that as |D] increases
so does m). In such a case, we get = S 7 + 5o In (1+ 2) + EO + In (1 [1+ (T )
Note that T S m so everything else equal, it more challenging to get good privacy with smaller number of batches.
Composition.
We can apply advanced composition 18
(Theorem 3.20) to obtain an overall
guarantee for the training process. So for K steps we get:
2K In( J. + KE(e" 1) and = K-6 + +8",
where (s',8") is the privacy budget for entire training and control the tradeoff between and 8'
8" 0 can be freely chosen to
As previously mentioned, these DP bounds may be overly pessimistic in the sense that the adversary even knows the partition of data into batches. leave to future work the task of deriving tighter bounds in more realistic settings.
D What Batch Pass the Privacy Test?
So far, we have analyzed the privacy of our approach from the lens of batch PD and differential privacy. Another lens show that gradient updates from anomalous batches are rejected with high probability (even for the simplest variant of the privacy test).
adopt to ask what kind of batches get rejected? In this section,
Consider a seed batch Bg, its associated gradient Ia. and another batch B, with gradient g, Recall that noisy gradient gs Z is plausibly deniable with respect to batch B, iff (2) holds. In other words, we denote plausibility (of 9 with respect to some gi) as the probability that Eq. (2) holds:
p(ğ 9+)
q(s i) = Pr
<
p(g 9:)
where the probability q(8, i) is taken over the randomness of 7 ~ NN0, o21). This probability only depends on batches B3 and B, The following result shows that only depends on the la-distance between the two gradients, i.c., llg. - gill2.
Lemma 6. For any seed batch with gradient gs and any mini-batch with gradient go. let llg. 9:112 The probability that Eq. (2) holds depends only d and we have:
((d) g( Pr (YE P
d d d+ +
20 20vd
where Y N(0 1) and 24
I Lemma 6 shows that y(d) is exactly the probability that a standard normal variable takes value in a-y a+9
20v7' 20 where & 20. We provide proof in Appendix H.5
18

---

Figure 4: Normalized Distance d' for varying a and under different g(d). We observe that for a fixed probability of passing the test q(d), the larger the product of and the larger the normalized distance d' be, meaning that more anomalous batches pass the privacy test. Note that d' / ddk where k is the dimension of the gradient vector (we set & 7680 for this ease).
Intuitively, for a >>> the probability Pr(a b bs a can be reasonably approximated as 25²(a) where o6-) is the standard normal pdf, and thus the probability falls exponentially fast with
The following results derived from tail bounds on Lemma 6|show that plausibility falls off exponen- tially fast with the 12-norm d whenever d is sufficiently large with respect to 7. This immediately implies that any highly anomalous candidate gradient (i.e., gradient with large to-norm to other mini-batch gradients) will be rejected with high probability.
Lemma 7. For any seed batch with gradient and any mini-batch with gradient gs. and let d be defined as in Lemma 6 d 2020 we have that:
[_ +2) )
q(d) < Cania - exp
(S)
8do2
where Can.
22da
exp
( (d 7) (d exp
2
(-2) + 402d "
2
We provide the proof of Lemma in Appendix H.5
E Parameter Tuning
There are two main strategies approach parameter tuning.
Theory-based strategy. We can tune parameters based on the rejection rate theory from Lemma By tuning and 7, can make (d) arbitrarily small. If we have desired bound d, then find combinations of a and that achieve the desired effects. This can, for example, be done through grid search.
To provide intuition and guide parameter tuning, we plot the minimum d such that q(d) is at most some 8
function of and This is shown in Fig. 4/ 5 0.05 and 10 which plots Vd/k. where k is the dimension of the gradient vector (i.e., g E IRa) used here for normalization. We observe that (as expected) we require larger d" for the same and 7 for q(d) < 10 compared to q(d) < 0.05. Moreover, for fixed q(d), the normalized distance d' appears to grow with product of and 7. This is consistent with Lemma 7 which suggests that the asymptotic behavior is driven by the product o²y. Wen tuning the privacy parameters, exploring combinations of a and ? such that o2-y remains roughly constant is sensible strategy.
Alternatively. we can tune parameters based on the connection between PD-SGD and differential privacy (Appendix C.3 In particular, we can set T 2 ED - In [D] + ł to ensure a low enough 5. In that case E = 7 + So + (1 4) so minimizing 7 maximizes privacy. However, if the chosen pair (7, o) does not allow passing the test often enough, then the utility suffers. Keeping σ² constant to ensure reasonable rejection rate and then tuning other parameters is also sensible.
Practical Parameter Tuning. We propose and evaluate an empirical parameter tuning strategy. conducted additional experiments on an NVIDIA B200 GPU.
19

---

Algorithm 2 Hyperparameter Search
Input:
1: Olit
<-
list of candidate noise scales
2: Thit
<- list of candidate gamma values
3: Tisa
list of candidate thresholds
Eim
number epochs for full training
5: Exhort
-
number of steps for short trial (e.g.. (0.)..000)
6: ACCaiesh + accuracy threshold to keep a (e.g., 96%)
7: train fn + training function that returns (reject rate, final accuracy)
Output:
BestConfigs +- list viable (a, 7/ ()) configurations
9:
D. Phase I: Screening with T =
10: Gitereed
11: for each a in Tist do
12: acc +- train ttaint.fnaonnn11.
default, T 1, epochs Biul)) accuracy
13: acc 2 ACCues then
14:
append to Fihered
15: end if
end for
17:
b> Phase 2: Coarse Filtering over (a, T)
18: CandidateConfigs <
19: for each in Fntered do
20: for each in "Mu do
21:
for each 7 in Tia do
22:
(rej. acc) train_fn(a,, T, epochs Eshon)
23:
0 rej then
24:
append (a,, 7, CandidateConfigs
25:
end if 26: end for
27:
end for
28:
end for
29: BestContigs +
30: for each (a, 1') in CandidateConfigs do
31: (rej. acc) train_fu(o, ? T' epochs Ema)
32: record (0, 7, rej, acc) in BestConfigs
33: end for
34: return BestConfigs
As a baseline, we first performed a full grid search over the three main privacy parameters (a, and T), covering 180 combinations in total. This exhaustive search required 110.41 GPU hours to complete.
We then applied our empirically guided two-phase strategy, which significantly reduces tuning cost: Phase (a screening): We fix the threshold T and full training for each candidate We retain only those a values that achieve high utility (final test accuracy 2 96%).
Phase 2 (coarse filtering of and 7'): For each surviving ø, shortened training (200 steps) across the 7 and 7' grid. We discard any configuration that results in degenerate behavior (i.e., reject rate reaches 0% or 100%) early. The remaining viable combinations then trained to convergence. We provide full pseudo-code Algorithm
This procedure reduces total tuning time from 110.41 GPU hours to just 4.15 GPU hours, while still identifying high-peeforming configurations. 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 We believe that the combination of theory- theory-informed constraints, practical heuristics, and structured filtering makes PD-SGD both scalable and practical.
20

---

F Experiments Setup
F.1
Datasets
We use three of the most commonly used datasets for evaluating membership inference attacks and DP-SGD 3].
38
45
40
CIFAR-10 26 contains 60,000 images with 10 classes. We use 50,000 as the full training set and 10,000 the test set as most papers do. Each example has three RGB channels and size 32 x 32 pixels. For fine-tuning tasks, we only use 500 data samples for training and for training from scratch tasks, use 30,000 for training.
CIFAR-100 is a well-known benchmark in the field of computer vision, also collected by [26]. CIFAR- 100 contains 60,000 color images, each with a resolution of 32 x 32 pixels. It is more complex than the CIFAR-10 dataset; the images are organized into 100 distinct classes. The dataset allocation includes 50,000 images for training purposes and 10,000 for testing. For the fine-tuning task, we only use 1000 data samples for training and the rest of training data examples are used for MIA evaluation. For training from scratch, use 25,000 data samples the same setting in [50].
and Purchase- 100 is based on Kaggle's "acquire valued shoppers" challenge and processed and simpli- fied as introduced in [8). The dataset contains shopping records for thousands of individuals and includes 197,324 data entries. For training, we use 25,000 samples and the rest for testing. For MIAs, we use 25,000 samples from test set as shadow dataset.
F.2 Models
We obtain the model from Open Clip and add linear layer as classification head. We only fine-tune this last layer and freeze the weights of other layers. We utilize this model for CIFAR- 10 and CIFAR- 100 fine-tuning tasks.
ViT-B-16 are pre-trained on the LAION-2B dataset 37
Wide ResNet (WRN) 49 is a popular variant of the ResNet (Residual Network) model 21 The architecture increases the number of channels in convolutional layers (width) rather than the number of layers (depth). We use WRN-1664 in experiments which is also commonly used in many DP-SGD related work 12 36). We train the model from scratch on CIFAR-10. We use WRN-28-2 for
training from scratch on CIFAR-100.
Linear model is commonly used for tabular data such as Purchase-100, We use this one-layer linear model for experiments on Purchase-100.
F.3 Setups
We implemented PD-SGD using PyTorch. For DP-SGD, we use Opacus 47
For other empirical
defense mechanisms, we reproduce them using SELENA's [40] original code-basel 6 and HAMP's original code-base For membership inference attack, we use the Privacy Meter toolbox From we use Population Attack (P-Attack), Reference Attack (R Attakk), Shadow model Attack (S- (S-Attack) based on [45) and Carlini et al. Attack (C-Attack) based on 7 We employ these four widely used attacks to comprehensively evaluate empirical privacy leakage and make fair comparisons between different methods. Note that goal here is not the most exotic recent attack, but establish a fair empirical comparison between different defense methods, and thus we use a well-understood set of popular recent membership inference attacks.
We keep the same attack setting for all defense mechanisms for a fair comparison. For all datasets, other than the part we used for training the target models, the rest of training samples are used as shadow datasets for shadow models or reference models. For all shadow models or reference models, we sample the same amount of data samples as target dataset for training. We use
Details for Attacks:
HAMP HAMP
21

---

Table 4: Hyperparameterss setting for experiments in Table 1
Dataset
Param setting
T
Step
Reject Rate
0.1
20000
27.78%
CIFAR-10(FT)
PS 2
0.3
3
20000
30.31%
PS 1
0.1
50
3
20000
44.08%
CIFAR-I00(FT)
PS 2
0.2
10
3
20000
46.35%
Purchase- (0r(h))e-000FFS)
PS 1
0.01
1000
100000
3,91%
2
0.01
750
100000
87.76%
PS 1
0.01
40000
100000
1.06%
CIFAR-10 (FS)
PS 2
0.02
7000
3
100000
3,70%
PS 1
0.01
100000
3
10000
0.49%
CIFAR-100 (FS)
PS 2
0.01
9000
10000
32.81
Table 5: Evaluations for PD-SGD: We evaluate PD-SGD on three datasets with four different attacks. We report the average results and standard deviation among three independent runs. We observe that PD-SGD can achieve better privacy-utility trade-off than other empirical defense mechanisms and DP-SGD.
Dataset
Method
P-Attack
R-Attack
S-Attack
C-Attack
Non-private
87.22% (+-0.13%)
0.60 (+0.00)
(:00.1))))
0.58 (::0.01)
0.22% (+00003%)
AdvReg
75.38% (100.09%)
0.53 (10.00)
0.54
0.53 (3:0001)
0.19% (100.02%)
SELENA
81.04% (+0.07%)
0.53 (+0.01)
(+0.01)
0.53 (+0001)
0.19% (+0.01%)
CIFAR-1O (FS)
DR-SGD (s = 1)
26.53% (=0.48%%
0.50 (20.00)
0.49 (=0.01)
0.50 (=0.01)
0.07% (=:0002%
DP-SGD (c
55.46% (2.0.28%)
0.50 (10.01)
0.49 (1:001)
0.50 (20.01)
0.10% (10.01%)
DP-SGD (e
63.31% (=0.155%)
0.51 (=0.001)
0.50 (2:0000)
0.51 (=0.01)
0.13% (=0.022%
PD DGD (purum setting 1)
82.22% (2:0.11%)
0.53 (100.1)
0.52 (1:0.01)
0.51 (1:0.01)
0.19% (100001)
PD-SGD (puram setting
79.69% (++0.25%)
0.53 (+0.00)
(+0001)
0.51 (+0.01)
0.1% (+0.01%)
Non-pricate
96.09% (+-0.02%)
0.57(+0.01)
0.69(+0.01)
0.56 (+-0.01)
0.37% (+00.03%)
AdvReg
95.96% (=0006%%)
0.56 (+0.01)
0.59 (=0000)
0.55 (=0.00)
0.31% (=0.011)
SELENA
(200.4%%
(10.000
(10000)
(20000)
0.33%
CIFAR- (FT)
DP-SGD (s = 1)
68.97% (=0.1155) 11%)
0.52(=0.01L
0.50(=0.01)
0.52(=00001)
0.17% (=10.01%)
DP-SGD (r
93.53% (1.0.0%%
0.54 (10.01)
0.56 (1:0022)
0.54 (2:0.01)
0. 0.20% (110.03%)
DP-SGD (c
(+-0.09%)
0.54 (+0.00)
0.59 (=0.01)
(=0.01))
0.23% (+00002%)
PD-SGD (param setting 1)
96. 18% (=0.06%))
0.54 (20.01)
0.49 (=0.01)
0.55 (=0.01)
0.27% (=0.02%%
PD-SGD (param setting
94.73% (+0.07%%)
0.53 (+0.0))
(+0.01)
0.53 (+0.00)
0. (-000%)))
Non-private
74.22% (200003%
0.68(10.01) 0.73(20.01)
0.73(2:001)
0.38% (20.003)
AdvReg
72.08% (=0000%%)
0.70(=0.01)
0.68:+0.01)
0.72(=00001)
0.33% (=0.02%)
SELENA
(210.04%
0.63(10.00)
0.60110.01)
0.65(10.01))
0.19% (10.00%%
DP-SGD (c 1)
4.46% (=0.13%)
0.50 (40.00))
0.500+0.00)
0.50 (=:0.01)
0.10% (+:0.019) S)
CIFAR- (FT)
DP-SGD (s
18.37% (+0.06%))
0,50(=0.00)
0.50 (=0001)
0.51 (=:0.D))
0. 0.12% (=+0.02%)
DP-SGD (c
(+00.05%)
0.51 (+0.01)
(+0.01)
0.51 (+0.01))
0.13% (++0.03%)
PD-SGD (param setting 1)
72.56% (=0.06%)
0.67(200.01)
0.62(#0.01)
0.64(=0001)
0.18% (=:0.02%)
PD-SGD (puram setting
68.79% (2.0.05%)
0.62(10.01)
0.59 (20001)
0.62 (2:0.01)
0.14% (10.002%
Non-pricate
68 68.56%(=0.1258 12%%
0.76(20.01)
0.78(10.01)
0.12%(20.0258 0.77(120001
AdvReg
(00.7%)
0.70
0.70
0.66
(.
SELENA
64.31% (=:0:09%)
0.63(+0.00)
0.73;+0.01)
0.06(+00.01)
(.01((-0001))
Purchase- 100 (FS)
DP-SGD (c 1)
DP-SGD (s
43.46% (#:0. 15%)
22.51% (#:0.222%)
0.56(=0.01)
0.53(+0.01)
0.55(+0001)
0.54(10.01)
0.54(+0.000)
0.56(=0001)
0.04% (+000018)
(.07%(=0002%)
(z
(2:0.12%)
0.36(10.00)
0.56(10.01)
0.56(10.01)
PD DDD (puram setting I)
64.39%
(1:0.05%)
0.63(10.01)
0.72(10001)
0.64(1:0.01)
0.06% (10.011)
PD-SGD (puram setting
61.16% (20.07%)
0.61(20.01)
0.59(100002)
0.60(10000)
0.06% (10.01%)
8 shadow models for S-Attack, R-Attack and C-Attack, For the C-Attack, we use the online version of it and adopted from privacy meter When evaluating attacks, we always use balanced evaluation dataset (50% member and 50% non-member). When reporting (balanced) accuracy, we always select the threshold with the highest attack accuracy.
Details for Defenses:
We keep the same parameter setting for all other empirical defense mechanisms SELENA's original code-base and HAMP original code-base. For DGDSGD, we set the clipping threshold to 1 and use the same batch size as PD-SGD and SGD. We also perform a hyperparameter search to identify the best learning rate for every run.
G Additional Experiments
G.1 Hyperparameter settings and Full Experimental Results
We show hyperparameter settings in Table and the full experimental results in Table 5
22

---

G.2
Understanding parameters of PD-SGD
Table 6: Impact of
Table 7: Impact of
Table 8:
Impact of T
Test Acc
Reject Rate
Attack
Test
Reject Rate
Attack
Reject
Best
92.78%
99,54%
0.52
0.1
17.19%
99.95%
0.52
1
64.78%
0.00%
0.76
94.70%
30.31%
0.53
0.15
96.02%
0.15%
0.54
2
64.81%
10.17%
0.75
94.71%
13. 71.70%
0.56
0.2
95.70%
3
64,76%
18.86%
0.71
94.74%
5.78%
0.4
93.67%
0.00%%
0.55
62.66%
84.68%
0.64
94.80%
2,25%
0.59
1.0
85.23%
0.00%
0.56
3.21%
99,90%
0.50
Recall that PD-SGD has three primary parameters - 7, and T - that control the privacy-utility trade-off. In this section, we discuss how these parameters impact the performance of PD-SGD.
We first fine-tune the ViT model on CIFAR-10 with different yy values while keeping all other parameters fixed. The results are presented in Table 6 We observe that decreases, the model's test accuracy experiences a slight decline. However, the Best Attack AUC diminishes substantially. Notably, when decreases from 2 to 1, even though the Best Attack AUC decreases slightly, the reject rate increases sharply to 99.54%, and the test accuracy drops to 92.78%. This suggests that y may be the optimal choice for this parameter setting.
We perform similar experiments with different values and present the results in Table We observe that when is large (i.e., > 0.2), the gradients can easily pass the Privacy Test, but the Best Attack AUC remains high, and the model fails to achieve good test accuracy due to the large noise introduced during training. When a is relatively small, although some gradients are rejected, it provides better defense performance (lower Attack AUC). However, if a is too small, such as 0.1, under the same y and T, it becomes very difficult for gradients to pass the privacy test, resulting in low test accuracy.
We also test different T values while keeping all other parameters fixed. We train the linear model on Purchase- 100 and present the results in Table 8 We observe that as T increases, it becomes harder for gradients to pass the privacy test. Consequently, the reject rate increases, test accuracy decreases, but better defense performance is achieved (lower Attack AUC).
Therefore, based on these tables and results, we find that the observations corroborate our findings in Fig. 4] This demonstrates that PD-SGD can provide a wide range of privacy-utility trade-off's through different parameter settings. On the other hand, to achieve a better privacy-utility trade-off, is advisable to tune all three parameters together rather than adjusting only one parameter.
Table 9: Impact of batch size on Purchase- 100 and CIFAR-10
Dataset
Batch size
Number of Batches
Test Ace
Reject Rate
Best Attack
1024
24
0%
100%
0.5
2048
12
60.10%
94%
0.62
Purchase- 100
3072
8
64.76%
10.41%
0.73
4096
6
64.80%
9.06%
0.74
$120
4
64.73%
0%
0.77
1024
29
60.24%
55.85%
0.51
2048
14
74.35%
73.
0.51
CIFAR-10
3072
9
80.40%
20.07%
0.53
4096
7
80.59%
14.07%
0.53
5120
5
81.57%
7.41%
0.54
G.3
Understanding Batch size in PD-SGD
The batch size plays an important role 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 tradeoff's, and ultimately, the behavior also depends on the chosen privacy parameters.
We conduct experiments on Purchase- 100 and CIFAR-10 and report results in Table 9
Results show that as batch size increases, the rejection rate typically decreases - larger batches more easily pass the privacy test (for fixed privacy parameters). However, this does necessarily translate into better privacy protection, as the potential for individual sample contributions to still be inferred remains.
23

---

3306
Test Accuratt 05)
2.42
3.500
210
33
35
Rojjct rate
Figure 5: Privacy-utility trade-off with fixed Reject rate: We show the privacy utility trade-off with fixed reject rate by using adaptive during training. can observe that with a higher reject rate, defense performance is improved, but utility is lower.
Moreover, we found that adjusting other parameters c.g. a, 7, and threshold can help mitigate these effects, maintaining balance between utility and privacy across varying batch sizes. For example, for a batch size of 1024, we double 7 we can decrease the reject rate 56.98% and achieve test accuracy of 63.87% with Best Attack AUC of 0.68.
G.4 Understanding Reject Rate of PD-SGD
The rejection rate is strongly correlated with the level of privacy protection achievable through PD-SGD. In the extreme case where PD-SGD rejects all updates, we gain perfect privacy at the cost of zero utility. Conversely, if no updates are ever rejected, utility may be high but the risk of increased privacy leakage. Therefore, is crucial to find an appropriate rejection rate.
In our previous experiments, the rejection rate was determined solely by the privacy parameters and could not be predicted before training. To better understand its relationship with privacy, we adaptively adjust y to maintain desired rejection rate set prior to running the experiments. Specifically, during training, we update ? based on the rejection rate observed over the most recent updates, using an exponential moving average increase decrease "
Furthermore, instead of counting every update, we only track the number of successful updates, ensuring that the model trains for the same number of effective steps regardless of the rejection rate. We apply this approach under the same experimental settings described in AApeeddix 1. training WRN-28-2 model from scratch CIFAR-100. We show the results in Fig. 3 We observe that, as expected, a higher rejection rate improves defense performance, reflected in lower best-attack AUC, but also reduces utility (test accuracy). Notably, PD-SGD surpasses a conventional DP- SGD baseline with 500. While that baseline achieves 30.55% test accuracy and an attack AUC of 53.84%, certain PD-SGD configurations (e.g., reject rate near 0.6) maintain higher accuracy while further reducing the attack AUC.
when operating at lower accuracy levels,
G.5 Rejection of Anomalous Batches
How do we know that PD-SGD rejects gradient updates from anomalous batches and only those from anomalous batches? We intentionally generate anomalous batches to evaluate this by flipping the labels of subset of examples ("poisoned examples") and grouping them into single batch with other normal samples. We ensure that throughout training, the poisoned examples are in the same "anomalous" batch. We then record the rejection rates when the anomalous batch is chosen seed and when other batches are chosen as seed, for varying proportions of poisoned examples.
Results are shown in Fig. 6, where we observe that for normal batches the rejection rate remains consistently low, as expected and desired. This means that the privacy test does not discard updates unnecessarily. However, when the anomalous batch is selected as seed, the rejection rate increases significantly and quickly plateaus near 100% as the proportion of poisoned examples increases. This
24

---

103
Rejection anoratee rasratous batch Rajection normal butchea
0
20
50
Figure 6: Rejection rate for anomalous and normal batches. Rejection rate for the anomalous batch increases close 100% as the proportion poisoned examples increases, while the rate for normal batches remains stable. This suggests that, as desired for privacy and utility, only those gradient updates that may cause privacy leaks are rejected.
500
100
Lamberal Accoort Locen Time
Figure 7: Distribution of data samples' successful update: Histogram of all training data samples' successful update. The average count is 107.53 (+10)) and the min max are 72 and 148, respectively.
indicates that PD-SGD effectively identifies and rejects anomalous batches, preventing the model parameters from being updated such cases.
G.6 Frequency examples used PD-SGD
Since PD-SGD works by rejecting implausible gradient updates, some training set examples may be used more frequently to update parameters than others. To investigate this, we record the successful update counts for each data sample in the training set in case where parameters are set to achieve roughly 15% reject rate. show this distribution in Fig. 7 We can observe that, as expected, there is range of update frequencies. However, training set example is used fewer than 72 times, so no example is systematically excluded from influencing the final model.
G.7 Comparison SoTA DP-SGD and HAMP
Although this study is the first to propose PD-SGD and it may not be directly comparable with state- of-the-art (SoTA) SP-SGD methods that have undergone extensive optimization, we nonetheless provide comparative evaluation results. Specifically, we compare PD-SGD against recent SoTA DP- SGD approaches such as those by De al. [12 and Bu et al. [6]. The detailed results are presented in Table 10 Our findings demonstrate that PD-SGD achieves high utility than these established methods under comparable privacy regimes (as measured by MIA success rates).
We also conducted experiments using recent empirical defense mechanism, HAMP 9 on the Purchase- 100 dataset. We show the results in Table 1I PD-SGD (PS attains higher utility than
25

---

Table 10: Compared SoTA DP-SGD: Evaluation of PD-SGD and SOTA DP-SGD: Train WRN-1664 from
scratch on CIFAR-IO.
Method
Test Acc
P-Attack
R-Attack
S-Attack
C-Attack
Non-private
87. 22%
0.60
0.60
0.58
0.22%
DP-SGD
63.31%
0.51
0.50
0.51
0.13%
Bu et al. 6
63.56%
0.51
0.50
0.50
0.13%
De et al. [2]
72.17%
0.52
0.50
0.51
0.12%
PD-SGD(PS 1)
82.22%
0.53
0.52
0.51
0.19%
PD- PD-SGD(PS 2)
79.69%
0,53
0,50
0.51
0.15%
HAMP while delivering comparable privacy. Also PD-SGD (PS 2) provides stronger privacy than HAMP at similar utility.
Table 11: Evaluations for new baseline HAMP 9
Evaluation of PD-SGD and new baseline HAMP on
Purchase-100 100 dataset.
Method
Test Acc
P-Attack
R-Attack
S-Attack
C-Attack
Non-private
68.56%
0.76
0.78
0.77
0.12%
AdvReg
57.56%
0.70
0.70
0.66
0.08%
SELENA
64.31%
0.63
0.73
0.66
0.07%
HAMP
61.66%
0.64
0.74
0.64
0.07%
DP-SGD (s=8)
47.61%
0.56
0.56
0.56
0.08%
PD-SGD (PS
64.83%
0.63
0.72
0.64
0.06%
PD-SGD (PS
61.16%
0.61
0.59
0.60
0.06%
G.8 Variants of Privacy Tests
Table 12: Performance of PD-SGD under different privacy tests: We evaluate different privacy
CIFAR-I0 and follow setting as Table I
We change the y to 2.3 integer test and the clique test.
Privacy Test
4
Test acc
P-attack
R-attack
S-attack
C-attack
Simple
2.0
94.22%
0.53
0.49
0.53
0.20%
Integer
2.3
94.35%
0.54
0.53
0.54
0.20%
Clique
8.0
94.79%
0.52
0.53
0,52
0.22%
We discuss privacy test counting methods in Section 4.2
Here, we measure their performance
empirically on CIFAR-10 and show the results in Table 12 We find that PD-SGD achieves a similar privacy utility trade-off for different tests.
We also analyze the effect of threshold randomization and ceiling. We consider a "comprehensive" test which uses clique counting and threshold randomization and ceiling, and compare to the simple (non-randomized, ceiling) test.
We evaluate this on Purchase- 100. Because the threshold is now perturbed, we must raise to offset the added noise,
decrease the batch size to 500 to increase the total number of batches to 50 and set T 20. We use the geometric mechanism based on the implementation of dffferential-privace library 10 We set the 3 (i.e., En 1) and & 0.2. Since changed the batch size, we reset the to 3800. We show the performance comparison to the original privacy test in Table 13, We can observe that after introducing additional randomness in testing. PD-SGD delivers a comparable privacy-utilie utility trade-off once the hyperparameters are properly calibrated.
G.9 Computational Resources
We evaluate the running time of PD-SGD for one training step. We conduct experiments using CIFAR- by fine-tuning the ViT model, and train the WRN-16-4 model from scratch following the same setup as described for Table The time is averaged over three consecutive steps taken from
mechanisms/ www.aniimmmmeemmttriiip..
26

---

Table 13: Performance of PD-SGD under comprehensive privacy tests: We evaluate different privacy tests
on Purchase-100 and follow setting as TTble
Privacy Test
Test acc
P-attack
R-attack
S-attack
C-attack
Simple 61.16%
0.61
0.59
0.60
0.06%
Comprehensive
62.31%
0.60
0.59
0.61
0.07%
Table 14: Computational Time per step: We measure the GPU time for SGD, DP-SGD, and proposed
PD-SGD for one step with the same model and the same amount of data. We report the average time among steps. For CIFAR-10 (Fine-tuning) we use VIT model and for CIFAR-10 10 (From scratch), we train WRN-16-4 from scratch. We can observe that although PD-SGD is slower than SGD, takes less time than DP-SGD.
Dataset
Method
Time (ms)
DP-SGD
18.86 (=0008)
CIFAR-IO
PD-SGD
7.70 10)
SGD
0.49 (10.03)
DP-SGD
2492.11 (#8.06)
(F)))
PD-SGD
1780. 16 (+ 15.72)
SGD
344.47 (#:0.20)
Table 15: GPU Memory Usage Comparison:
Evaluation of GPU memory usage of PD-SGD against DP-SGD and non-private (SGD) training with the Wide-ResNett-Ie 16-4 model on CIFAR- 10 dataset
Method
alloc
reserved
peak alloc
peak reserved
SGD
37.9 MB
6562.0 MB
4918.2 MB
6562.0 MB
DP-SGD
10345.9 MB
18612.0 MB
10345.9 MB
18612.0 MB
PD-SGD
MB
6712.0 MB
5014.5 MB
6712.0 MB
the middle of the training process. For comparison, we also measure the time of standard SGD and DP-SGD under the same conditions. The results are summarized in Table 14 PD-SGD is noticeably slower than standard SGD but notably faster than DP-SGD for single training step.
We also conducted experiments to measure GPU memory usage of PD-SGD against DP-SGD and non-private (SGD) training with the Ride-ResNNtt-6-1 model on the CIFAR- 10 dataset and show results in Table 15 PD-SGD's memory footprint is slightly higher but comparable to SGD and far below DP-SGD. Thus, on memory-conse constraiee GPUs where DP-SGD may exceed capacity, PD-SGD remains viable.
G.10 Vulnerable Data points recognized by PD-SGD
We hypothesized that data samples most frequently rejected by PD-SGD are inherently nerable to membership inference attacks. To validate this hypothesis, we first identified the six images with the highest rejection rates across three independent PD-SGD trainings. For each of these samples, we ran ten independent per-example MIA trials and recorded the fraction of trials in which "member." The resulting per-sample MIA success
vul-
the adversary correctly classified the sample rates are shown in Fig. 8) Under standard SGD, these six images exhibit an average MIA success rate of 91.67 %. confirming their high vulnerability. When using PD-SGD, however, the average success rate falls to 56.67 %, demonstrating that PD-SGD not only delivers strong per-example privacy protection but also serves as an effective mechanism for detecting the most privacy-sensitive points.
G.11 Training with more data points
To extend our evaluation, we have finetuned ViT model with a larger subset of CIFAR- 100 i.c.. using 10K for training and 10K for testing and the rest of the data for shadow datasets. We report results in Table 16) We can observe that without any defense, the attack AUC is around 0.56, while with PD-SGD, the attack AUC decreases to 0.52-0.51. For utility, PD-SGD can achieve 80.2% test accuracy while SGD with & 8 can only achieve 77.13% test accuracy.
27

---

Table 16: Evaluate PD-SGD CIFAR-100 with training data points: Finetune Vit model with large subset CIFAR-100 (1OK). can observe the similar thing that PD-SGD can achieve better privacy utility trade-off than DP-SGD.
Method
Test
P-Attack
R-Attack
S-Attack
C-Attack
Non-Private
82.94%
0.56
0.57
0.56
0.19%
SGD (PS I)
80.29%
0.52
0.52
0.51
0.11%
PD-SGD (PS
78.25%
0.51
0.51
0.51
0.08%
DP-SGD (s 8)
77.13%
0.52
0.54
0.52
0.13%
Table 17: Evaluate PD-SGD CIFAR-100 for training from scratch: Train WRN-28-2 from scratch with PD-SGD on CIFAR-100. We can observe that: PD-SGD achieves better privacy-utility trade-off than DP-SGD even with large
Method
S-Attack
Non Private
56.27%
81.71%
81.91%
81.85%
0.37%
DP-SGD(e
18.24%
52.29%
51.03%
DP SGDX 100)
29.50%
53.04%
50.57%
51.76%
0.12%
DP-SGDXe
30.55%
53.84%
PD-SGD (PS 1)
53.63%
58.80%
52.81%
57.46%
0.15%
PD-SGD (PS 2)
47.07%
54.27%
50.56%
50.00%
0.12%
Table 18:
Impact of Clipping Threshold of DP-SGD
Clipping Threshold
Test Ace
P-Attack
R-Attack
S-Attack
C-Attack
0.1
93.49%
0.54
0.56
0.54
0.18%
1
93.56%
0.54
0.56
0.54
0.18%
10
93.54%
0.54
0.57
0.54
0.20%
G.12 Train from scratch on CIFAR-100
We used small training set sizes for these experiments to ensure the resulting models would be vulnerable MIA so that it would clear if the desired level of protection was indeed achieved. However, we also included other experiments in our paper where we used much larger training set sizes (e.g.. Table D. In addition, we conducted further experiments using a larger subset of CIFAR-100 We follow the experiment setting in [50] which trains WRN-28-2 from scratch 25k samples of CIFAR-I00, We show the results in Table 17 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 parameter setting PD-SGD.
Compared to DP-SGD, PD-SGD consistently provides substantially better utility, even for large values of e. For instance, with 100 e 500, DP-SGD achieves only about 30% test accuracy. In contrast, our proposed PD-SGD attains significantly higher accuracy - 47.07% (with slightly higher Attack AUC) or approximately 37% (with comparable Attack AUC), as shown in Fig. 5)
SGD
100% 100%
100%
80%
100%
70%
PD-sGD
60%
80%
Figure 8: Samples frequently rejected by PD-SGD face higher MIA risk under standard SGD: Average per-example membership inference attack success rates are 91. 677 but lead to reduced MIA success (56.67%) when using PD-SGD. This shows the usefulness of the method to provide per-example privacy protection, as well as its potential for detecting vulnerable points.
28

---

G.13 Impact of clipping threshold of DP-SGD
To further investigate the impact the clipping threshold in DP-SGD on privacy protection, we fixed all other parameters and varied the clipping threshold, as shown in Table 18 We can observe that even as the threshold changes, the model's utility and privacy remain almost the same. However, during these experiments, we do find that if the threshold is changed, the learning rate also needs to be tuned properly to get the optimal utility.
H
Proofs
H.1 Proof of Lemma 1
Proof of Lemma / We need to prove that if the likelihoods lo satisfy Definition for some 2
and X' 2 0, then the advantage is bounded:
X adv & X+1 X+1
For this first observe that the advantage is bounded by the total variation distance: adv S (V4 2 lu Therefore, we will show that v == TV S A-1
X+1 + X+1
For conciseness, write 1 and to- From Eq. (1) we have that for any in the range of the distribution (of and q):
p(x)= S Xq(x) + c(x) and q(x) s +c(x)+c(x))
for c(x) 2 0 and f c(x)dr= X.
Define A= {u: p(z) 2 (z))). We have v TV = -1 -pp--10 4) = p(A) - -((A). Decompose
the TV over A and A
f (p(x) (p(x))((x))dd)) q(x))drr S (A (A-1) / g(o)do + / c(z)dr.
and
/ (q(x) - p(x)) S () A-
(A- - / p(z)dr + / c(z)dx.
Write pSS), (SS), ((S) to denote the integral over set S we get: v S (2 1){(A) + c(A) and S (A ())( + c(A9). Also, v p(A) ((A), we can plug in p(At) q(A9) v in the second inequality. We obtain:
U (A 1) - ((A) - +) c(A))
which can be reorganized to:
(A-
+ c(A9)
Combining this with the first inequality. we have that:
e S min [A - 1)g(4) + c(A), ((A 1)(1 - s(A)) + c((A))
Writing y = ((A) the above expression upper bounds TV as the minimum of (A - 1)y + c(A) and (( 1)(1 y) + c(A").. These can be viewed as lines/functions of y E [0. 1]. Clearly, the maximum is reached when two lines intersect. It can be seen that the intersection point y" satisfies:
c(AA) X
- x
c(A) +
Replacing the RHS in the first inequality yields:
c(A) + c(A9)
A-1 X
x
x+1
X+1
X+1
which completes the proof.
29

---

H.2
Proofs of Privacy Testing
Proof of Lemma 2
Because T 7 decreases with T, the event f 7
becomes easier as
grows; hence
Pr+1 Pr.
3
Upper ratio.
The geometric tail satisfies Pr(z 2 k]
so for pr+1 < 1 v6 we have
3+1
Pr+1 8-1T---1)
3.
Pr
8-(T-r)
If Pr+1 1 - v, then P.+1/p+ 5 <
Lower bound on - (1-+++11/(1--11 pr).
Based on upper ratio, we have
Pr+1 1 P7
p
2
Pr+1
Since
1- p--1 is monotonically decreasing and p++1 S 1 - vi, We get:
P
P++1
B
Proof of Lemma 3
For <
Pt (1- T (1 - v) 8-1 E 8
B+1 12T
s (1 - 38 ()88 (T-t) (1 exp (-Eo -
H.3 PD Criterion for PD-SGD
Proof of Lemma 4 Take T in Lemma 4, that is the algorithm maps onto single training iteration of Algorithm 1 with a privacy test with parameters a > 1, randomization Geom (3) and ceiling
1 C.
need to prove that satisfies the PD criterion DDfinition 1b with X, X' as in the lemma. The pointwise bounds need to hold for any partition B1 ..., Bm, target batch B₁, and any Range(T).
Consider an arbitrary partition B (B,.... Bm) and target batch B* Let B' (Bi....,BA, B*) = B, B". The likelihood terms are (g)) = Pr B, B*) and lo(g) = (g)
PD-SGD sometimes rejects a gradient. We formalize this as the algorithm outputting 1. Its range is Rd ((L) for d parameters model. Consider the case for arbitrary g E B (g + L) first.
To produce an output, Algorithm first selects seed batch uniformly random, then produces by adding noise to the seed batch gradient, and finally runs the privacy test. Therefore:
Pr)(g = Σ Pr(B) Pr(g] = Σ Pr(B) p(g B) Pr(g.
BE
BEB
Here Pr(B) is the probability of B being selected as seed, Pr B) is the probability of outputting g conditional on B being the seed batch (and is the partition). The latter term, Pr(g[ B), requires that g is sampled from batch B's gradient (p(g) B)) and that the test passes Pr(g.B,B) We
30

---

use T(g, B, B) to denote the number of alternatives. This is because the probability of passing the only depends on (Lemmas 2 and 3
Breaking down the sum for (g) over the seed batches, we have:
1
499)
Σ
Pr(g 23) + Pr(g B" 27)
m +
LEE
1
Σ
B,
1
Σ
p(g B) Pr(a.828)
m +
m m+
BE
BEB
1
Σ
P(g Br(g.B,3)
1
Σ Pr(g B,
m +
m +
m l0(g)
m
The first inequality uses Pr(g] 13", B²) 2 and the second uses the fact that adding batch does not decrease the probability of passing the test for other batches.
This gives the first direction: For the second direction, we proceed similarly:
(1(g//(()) 2 m+1
(1)) = +
B)) + Pr 28)
LEE
Pr(g + Br 2¹)
m + 1
BE
(3 lo(g) Pr B'))
The inequality uses the fact that the rate of increase of the probability of passing the test is most when adding batch (Lemma 2), thus: Pr(g B, B') S (Pr(g]B, B, B).
To proceed from (t). we divide the analysis into two cases based on T(g, B*, B')., i.e., the number of alternatives available to B
Case (7 8", B') > f): We have ((g, B", B) 2 t since t + alternatives in 2 means at least t such batches exist in B. Thus (using the definition of a-similarity):
B(glB") S t
Σ
B)g]
BET
T
For each alternative batch B in this sum, also have that: Pr(g. 2 B-- DT Lemma 2 Therefore:
Br B') S a t
Σ
Pr(g[B,B) S a9 Σ Pr(g|B,B) = a3
t m lo(g).
BEB 21
BE
So for case 1, we have: (g) < m 31 + (o)))
Case 2 (r B*, BD < f): In this case, there are fewer than t alternatives in B (there could be none).
But (by Lemma 3) the probability of passing the test is exponentially small in T t. That is:
(g B", B') S Ptp S (1
Thus: Pr(g] B*, $ p(g
B*) (1 - (T-t) from which we get (for case 2):
(g) - m + (l((g) m + X()
where X'(g) p(g)B*)(1 (1)-
31

---

Observe that for any S S C (g) & {1 - 10- (T-) since lsp(g) B*) S 1.
It remains consider the case ! L.
For this observe that since the test has a ceiling 2 (1(1)) 1 > for 0, 1. We have:
(ma + (1)) EnED Br ) + Pr(lIB*, .B))
m (o(
EBEB Pr( B, 23)
Write s 2
[B, x(2)) = EBES Pr( 11 [B, B) and 8 Pr(lIB*, B))
BeB
From Lemma
we get that 2
212))
2 8-1+6 We also have that for any batch B and par-
Ae
(
tition T: Pr Pr B, B) 2 v.. Thus
2 s and also s(2) 2 mú. It follows that:
Byb
(m + (1L)
+
B 1
+ v
m
m (oL)
mib
Dividing by m+I yields:
m
B
m
1+
1
m. + 3/
m 3-1+
+1
mu
Aggregating the bounds over all the cases completes the proof.
H.4 PD-SGD satisfies DP
The proof of Lemma 5 is similar to that of Lemma 4, except that it must consider random partition and consequently there no additional target batch Br, so we have to couple the partitions under D and D2 and leverage the observation that the additional example (zz y) such that D1 D2 U ((x, y)}
(or D2 = D1 U {z, y) falls into exactly one batch.
Proof of Lemma S Consider adding an example (at, y) to D. Let D' = DU (2x y)}. Observe that no matter how D' gets partitioned (assuming only m batches) the example (r, y) only falls into exactly one batch. Furthermore, is a partition on D and D has n data points, there are S S m batches of size r + 1 and m batches of size for integer r such that obtain a partition B' by selecting a uniformly random batch of size r (i.e., one of the m batches of size r) and adding (z, y) it. (If m q. i.e., all partitions have size exactly n //m then we pick uniformly random batch and add (x, y) to it).
couple partitions on D and D' as follows. If B = (B...... Bm)
mrr + q. Under D' we can take the partition B and
Fix an arbitrary partition B- (BI,.... ....... B,,) of D and let B' -BI, [B...... ................................ Blr)) denote the associated partition under D'. There exists j such that B3 + By (and B3 includes (r,y)) y)) and for + j: B, -= By. Write B (= B3) to denote the differing batch.
Fix an arbitrary g * I.. Since the two partitions have the same number of batches, we can relate the probability of producing g under B to that under B2 by considering the case where the selected seed batch is B* or not. When selecting a seed batch, the probability that we select B is exactly 1 1/m, therefore:
1 B B')
- - B, m
Pr(g (
(6)
m
We proceed similarly to the proof of Lemma 4 For the first direction, we immediately get the first direction:
1M-1Pr(ggB Pr(g 2')
Pr(g|
2 Pr(g|
Pr(g]B)
m
m
m
where the first inequality used the fact that Br(g| .B)) > and the second used Lemma (the probability of passing the test is non-decreasing).
For the second direction, observe that the term Pr B') is related to Pr(gl B3 23) follows:
Pr(g B, B,T)) P(g[B) P+(B,28)
< BBp(g B) P+(B,3) = BPr(g) B),
32

---

where we again usedLemmaa 2 Since B' differs in only one batch from B the number of alternatives increases by at most one and thus the probability of passing the test by factor of at most
Case 1: 7("", (()) > L. In this case for any batch B E B that is a-similar to B we have T(B", 23 2 t (and there are at least such batches in B Bj). Therefore:
Pr I aB
Σ
Pr(g|B,3)
BEB:B==al
aB
Pr
BE
where the first inequality applies the a-similarity and[Lema 2 to the average batch B E 2 that is a-similar B* The second inequality simply uses the fact that Pr(g] B, B) 2 0 for any batch B.
Since Pr(g/B) ( =
1 m
EBE Pr(g|B,B),
1 Br B') m BEB
aB
Σ
Pr(g[B,
ag Pr(g)
m
Putting this together, we have for case 1 that:
Pr(g|B') < aB
Pr(g + m PPr(g/B) 8
m -
-/ Pr(g)
Case 2: T(B", 2¹) S t. In this case, there are less than alternatives in B (e.g., there could be none).
However, since the term Pr(g] (') is bounded by the probability of passing the test according Lemema 3 We have:
Br B) < - (1-1)) exp (-Eo(T - ()) p())B*)
Therefore:
Pr(g| (1 v) exp (- -))))( m
3 Pr(g)
Since m- 3 S B( m-1 4). this completes the second direction and we get:
1 + Pr(g)))) "(g,8*),
Pr(g] 2 (( m
where 8(g, t v exp -o (T' - 1)) B*)
To meet the definition for both directions, we need to consider an arbitrary set Y. It suffices to integrate over the previous results. Since: Pr(Y|B') = Jyev Pr(g/ it follows that:
m
Pr < B)) < B(
a
)r(Y B) - 8(Y,8"),
m
m
where 8* = 1 v exp (T t)) Soev p(g] < 1 (1 - w)) exp (-En (o--T--)) - f))
because JoEY p(g B*) most since is probability.
Noting that Pr(Y|M(()) Biy EBER(D) Pr(Y|2) and the number of partitions in the sum from the coupling is the same for D and D' yields the result with In( ()) and 8 s m L (6) exp (T
I
Finally, consider the case g = L. From the ceiling, we have that for any batch B and partition
B: Pr B) > O. From Lemma we have that for any batch in B E B: 1 2
(T(LI,,B)//PLLII B) 3-1
8
Write:
Pr(LIM(D') EBE Pr(- s(2') + Pr B", BB) Pr(LIM(D) Eneg Pr( B) s(B) + Pr PT(1BB,, BB, B)
(9)
33

---

with s(2²) = BBBBBBBB Pr( 2') and s(B) = EBEB.BAB Pr( B). Both sums are the same batches and have that:
$(28
Bqj 3-1+
From this taking the worst case for the terms involving B and Bj in both directions, we get:
Bu B-1+4
+
8+1
(t) - 8 s
++1
for s s(B). Optimizing as function of [(m - 1)15, (m - 1)), we see that the upper and lower bounds are reached for at its maximum and minimum respectively, from which we conclude:
Bub
m
Pr(LIM(D')
m
B
(m
(m-1)+
which concludes the proof. We get the result as stated in the lemma when the bounds for the g # case dominate (those for 1). For this, it suffices to choose y appropriately.
H.S Proofs of Appendix D
We now prove Lemma 6
Proof of Lemmn 6 Consider the ratio of probabilities bounded by Eq. (2) and expand using the
Gaussian PDE. get:
(-(20²) ΣØ= Zz
p(g 9a)
exp
p(ğ 9)
exp
(202)
k Σラ= (Z₁ + (go. ((
-200 -1
[2] (d, 2,)
exp
j=l
- (2o 2) -1
-d - Σ d,2g
exp
where d, = 9e.j Ji and d Σラ= d2
|1g. -9113
Plugging this into the inequality, taking the log and some reorganization we get that the candidate gradient is plausibly deniable with respect to gi iff:
T0 Vd
Vd
Σ
Zj vd
70
Vd
Since Zj ~ (N o²), the summand for j is distributed as N(0, d' (dddd)). d)). Further, since the sum of i.i.d. Gaussian random variable is distributed a Gaussian random variable with the sum the means and the sum of the variance, we recognize that Y = ΣØ= d, 2i N/ 1).
Thus reducing the plausibility of a candidate gradient to:
Vd
70
20
Vd
S
5
2x
Vd
Vd
2x
and further to
2
d + 2
<Y <
(8)
2
2x vd
where we have used symmetry so that -Y has the same distribution as Y.
Therefore, Y needs to be within band of width 3 completes the proof.
v around vd/2o where 5 = 2007, which
34

---

The proof of Lemma 7 relies on the following standard normal upper and lower tail bounds:
Lemma 8. Let X ~ (O, For 1 > O, we have:
B (V2m) exp (xp(-19/22 <PrXX (lV2T)
exp (-12/2)
Note that tighter bounds available
15
vd and Proof of Lemma 7 Let a 20
20 Vd
We have from Lemma that ((8, Pr(a b S
X aa+t b) for X N(O, 1). Thus:
((8, = Pr(X > b) Pr(X > a ++b) b)
(a-b)/12
(a+ b)
(a+b)//2
(a
2
((a + b)2 1 2T
1
(2-b)
(a + b)
(a+b))/22
fm
(a + b)2 +
-10240²)
cab
(a +++6) 6)
ab
2mm
a
b
(a b)a
Substituting back and in terms d, o, y yields the result.
The following corollary of the lemma provides simple upper bound whenever d> 7.
Corollary 1. Let 2 for some f < 1. Then:
6 2
e2/2
e-1221
q(d) <
20
(9)
2Td
1-
2 2+
Proof Corollary 1 Let d 2 2 which implies a - 2 0. When increases, a increases but decreases. So, bound a and + b as follows:
Suppose b S la where < f < and a 1, then
1
b
a(1 f)
+ b
1 a(2 + f)
aa + b)2
Based on this, can get:
4122 2
ab
(a +
((8,
v 2T
a
(a + b)² +
Rab
eab
2ma
f
2 +
Observe that ab = 7/2, a²
12
020² d
So:
( 2
27/2
e 21/2
q(3,)) <
20
2nd
1- /
+
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims match the theoretical and empirical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss it in appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "LLimitatioss section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
36

---

Justification:
We provide full proofs in appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide all experiments details in main text and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
37

---

Answer: [Yes]
Justification: We provide anonymous github link for the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
Phblitc/guides/CodeSutmmmi
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ l/pipp.cc/public/guiice http://ppbwipcuuuuue//e/de/ttaaa /CodeSubbeiiiccec iitommmsssion ssisnn oeeicccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide all details in appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We provide error bars for the results in main text.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
38

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide all details in appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Our research follows the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss it in appendix.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to
39

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not have such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite all datasets, code bases and models.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
40

---

Answer:
[NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
41

---

The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- standadd components.
Please refer to our LLM policy hattps://neurips: 220t://c/c./coooeeeeeeee//02//// for what should or should not be described.
42


Reviews:
[{"review_id": "L7UK3jAolm", "reviewer": "Reviewer_is7x", "summary": "The paper proposes a variant of DP-SGD/Noisy SGD without clipping and with additional censoring of minibatch gradients that do not pass the so-called \"privacy test\", which ensures that each applied mini-batch gradient is $\\alpha$-indistinguishable from at least $T$ other mini-batch gradients. The paper argues that this definition constitutes a theoretically justifiable notion of privacy, motivated by an observation that the model could plausibly deny an accusation by a party claiming that a specific mini-batch has been used in training (Lemma 4). The paper shows that on CIFAR-10, the proposed variant achieves higher empirical privacy-accuracy trade-off than empirical defenses and DP-SGD.", "questions": "- What are some realistic attack settings that are directly prevented by Lemma 4? What actual adversarial scenarios can be modeled by \"denying an inclusion of a batch\"?\n  - How does Lemma 4 map to privacy of individuals?", "limitations": "The limitations are discussed in the appendix.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Obtaining meaningful relaxations of the strong threat model of differential privacy in a way that is practical and useful is a great open problem. This paper proposes plausible deniabilty of mini-batches as a potential solution, paired with a practical SGD-based algorithm that empirically achieves better privacy-utility trade-offs than DP-SGD and empirical defenses. The paper provides an extensive evaluation of different aspects of the algorithm: performance in different training regimes, with different batch sizes, distribution of example rejection rates, etc. It looks like PD-SGD can outperform the baseline methods in terms of utility and privacy in at least three tasks consistently—assuming carefully tuned parameters. This is a useful result, which could establish PD-SGD a state-of-the-art empirical defense. \n\nDespite the extensive empirical investigation, a core part of the paper is lacking:\n\n- *It's unclear how mini-batch deniability is a meaningful notion of privacy, regardless of possible theoretical guarantees on it.* The proposed theoretical guarantee is not substantiated as a meaningful and valid notion of privacy. In fact, the detailed interpretation of this notion is buried all the way in Appendix C. And that is: we have an (asymmetric) local DP guarantee on any released gradient value as a function of the sequence of mini-batches. Specifically $\\tilde g \\leftarrow M(x)$ satisfies $\\varepsilon$-LDP over the space of two possible inputs $x_0 = \\\\{B, B_1, \\ldots, B_m\\\\}$ and $x_1 = \\\\{B_1, \\ldots, B_m\\\\}$ for some $\\varepsilon = \\log \\lambda(\\alpha, \\sigma, m, T)$, where $\\alpha$ is the likelihood ratio threshold in the privacy test, $\\sigma$ is the Gaussian noise scale, $m$ is the number of batches, and $T$ the minimal number of indistinguishable batches. The problem here is that it is unclear why such guarantee matters in the first place:\n  - 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\"?\n  - How does it exactly map to privacy of individuals? The privacy of \"batches\" is certainly not a useful primary notion of privacy.\n\n  A more substantial motivation for the relevance of this setup to privacy of individuals is needed in the paper, and it should be a part of the main body. The claims of _theoretical guarantees of privacy_ are unsubstantiated, as it is not clear why the guarantee described above is directly relevant to privacy, which is, again, not a per-batch property, but a per-individual property. In particular, the conclusion \"Theoretical results [...] show that PD-SGD provides a superior privacy-utility trade-off compared to [...] DP-SGD\" is wrong as of now as the paper does not explain how the proposed theoretical notion is a meaningful notion of privacy.\n- *Unclear parameterization strategies.* Finding the parameters for PD-SGD seems challenging and require substantial grid search, as there are three primary privacy parameters, in addition to batch size. This seems like a fundamental limitation–which is addressed–but the paper should provide derive concrete Algorithms based on Section D, and ideally evaluate them, as otherwise it is quite unclear how to set the parameters.\n\nOverall, the proposed notion is tailored to SGD's structure. As a result, its interpretation is *retrofitted to an existing algorithmic structure rather than to a meaningful notion of data privacy.* However, this should not take away at all from the fact that PD-SGD with carefully tuned parameters seems like a superior empirical privacy defense strategy in SGD!\n\nTo mitigate this issue, the paper should either drop the claims of theoretical privacy guarantees (e.g., in conclusions), treat the method as empirical even if motivated by batch plausible deniability, and treat the parameter selection strategies as part of the core contributions – or explain how the notion of batch plausible deniability *on its own* constitutes a notion of privacy. Note that the latter option is orthogonal to the observation in the Appendix that with some test instantations a single step of PD-SGD satisfies DP. A possible direction would be to derive the guarantee equivalent to Lemma 4 on the deniability of individual participation based on the batch size/number of batches the individual appears in. \n\nThis reviewer would like to make it clear that the direction is worthwhile, and alternatives to standard DP are critically needed to ensure privacy guarantees in many practical settings. The proposed approach in its current form misses the mark as it is hard to see the relationship of mini-batch deniability to relevant notions of privacy of individuals in the training data – the practical setting in which such deniability would be relevant is unclear, and even if it was, a single individual's data could appear in multiple mini-batches.", "was_revised": true, "final_justification": "In the rebuttal, the authors have provided a simple and convincing proof via a sequence of games, showing that the proposed notion of batch plausible deniability implies average MIA protection for a single step of the algorithm. This provides a clear operational meaning to the framework in terms of a standard privacy threat, which was my main issue with the submitted version of the paper.\n\nIn my opinion, it is crucial that the camera-ready revision prominently showcases this connection.", "rebuttal": "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.\n\n**1. What is a meaningful notion of privacy?**\n\nWe 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. \n\nWe 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). \nWhile our framework is different from DP by design, we believe its value is best seen by evaluating it on the unique scenarios it addresses.\n\n\n**2. Why is batch plausible deniability meaningful, and what attacks does it prevent? What scenarios does it capture?**\n\nAs 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). \n\nWe 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. \n\nIn 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.\n\nNote 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.\n\n**3. Why is a batch notion meaningful?**\n\nA 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.)\n\nThis 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].\n\n\n**4. Why does PD protect individual privacy?**\n\nProtection 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. \n\nWe 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.\n\nAn 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.\n\n\n**5.  What is the threat model for PD-SGD? Why does PD-SGD protect individual privacy?**\n\nAs 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.\n\nIntuitively, 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. \n\nSince 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. \n\nEmpirically, 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.\n\n**6. Concrete parameter–tuning algorithm**\n\nWe 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.\n\nAs 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.\n\nWe then applied our empirically guided two-phase strategy, which significantly reduces tuning cost:\n\nPhase 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%).\n\nPhase 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.\n\nWe will provide full pseudo-code in the revised paper. We omit it here in the initial rebuttal due to character limit.\n\nThis 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.\n\n\n\nReference:\n\n[1] Jia, Hengrui, et al. \"Proof-of-learning: Definitions and practice.\" 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021.\n\n[2] Shumailov, Ilia, et al. \"Manipulating sgd with data ordering attacks.\" Advances in Neural Information Processing Systems 34 (2021): 18021-18032.\n\n[3] Soviany, Petru, et al. \"Curriculum learning: A survey.\" International Journal of Computer Vision 130.6 (2022): 1526-1565."}, {"review_id": "DtY3UTgoyW", "reviewer": "Reviewer_adTA", "summary": "The paper proposes a novel framework that focuses on providing 'plausible deniability' of using the gradient update from a batch by only using that update if there are many other similar batches present in the training dataset. It provides both a theoretical analysis of this framework as well as an empirical investigation. Their technique, PD-SGD, achieves better utility-privacy tradeoffs than existing methods, while the paper also claims to provide theoretical justifications for their technique (arguing some level of protection against even future yet-to-be-discovered attacks).", "questions": "The 'theoretical justification' claim of the paper needs to be clarified.\n\nConsider the following threat model: An adversary, with access to model outputs, is able to determine whether an individual was part of the training dataset or not, i.e., membership inference. Differential privacy provides guarantees that it is not possible to confidently distinguish between two outputs if the underlying dataset differed by exactly one point, i.e., it protects against the membership inference threat model. For a good 'theoretical justification' for privacy, one needs to choose a reasonable threat model and a technique that directly protects against the threat model.\n\nLet's talk about plausible deniability. What exactly is the threat model here?\n\nIs the threat model still membership inference? If so, the guarantees of rejecting highly anomalous batches are not enough, and any theoretical justification needs to be directly connected to differential privacy.\n\nOr is the threat model an adversary not able to tell which exact batch out of T different batches was used for the gradient update at a particular training step? The theoretical guarantees are more in line here, but the threat model itself isn't strong. Since batches are created randomly at every training step, the idea of a 'batch' does not hold meaning across the complete training run. So it is unclear how the threat model of plausible deniability at a single training step translates to the overall training.\n\nI found the empirical aspect of the work more promising. However, since that is not the focus of the paper, there aren't enough experiments or details here to support the claims. For instance, the authors argue that avoiding calculating individual-level gradients, which is a requirement for DP-SGD but not for their technique, PD-SGD, can be computationally beneficial. However, there is no empirical evidence to show how beneficial this difference is, and how much does constant rejection of batches after gradient calculation might affect this.", "limitations": "Please see the comments above.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Quality: The plausible deniability framework does not have the appropriate theoretical justifications that the paper claims, while the empirical results also do not provide an in-depth exploration to support several claims made in the main paper (see 'Questions' section for details). I am optimistic that at least for the theoretical claims, the paper can be improved during the rebuttal phase, to be more precise about these claims.\n\nClarity: The submission is clearly written and well organized for the most part. My comments here are at the intersection of Quality and Clarity, repeating that the theoretical justifications and the threat model are not clear.\n\nSignificance: The empirical results have the potential to be highly impactful, as the paper provides a more computationally efficient technique to achieve privacy that is also shown to be able to improve the privacy-utility tradeoff against some baseline techniques. While the theoretical threat model might be different, it is clear that their technique is more efficient and provides better tradeoffs. A deeper analysis with more experiments and other techniques would definitely improve this aspect of the work. \n\nThe theoretical discussion and the plausible deniability framework, too, are quite valuable, and I believe stand well on their own. As discussed in detail in the 'Questions' below, I feel the value of this framework becomes murky because of the authors' attempts to place it within the existing MIA framework of privacy, but without enough appropriate justifications for the same. As I mentioned above, I am optimistic that the rebuttal phase will either help the authors clarify these connections or acknowledge the distinction between the two and appropriately argue why their framework, too, has value, without forcing it within existing discussions of MIA. \n\nOriginality: The perspective of plausible deniability, to my knowledge, is quite novel and interesting. The paper takes a bold step away from existing privacy frameworks and proposes something new that could have useful implications for privacy protection.", "was_revised": true, "final_justification": "The rebuttal with the authors was quite extensive. Many of my confusions about the plausibility deniability framework itself were clarified, and I very strongly urge the authors to incorporate changes in the final version of the paper based on those discussions.\n\nAt the same time, some of my concerns about the real-world applicability of the framework also became clearer. There is still work to be done to understand whether this framework can indeed have a real-world impact or not. But I believe it can be argued that not everything should be expected from just one paper.\n\nOverall, my decision is still close to borderline accept, i.e., I believe there is value in this work, but I do not feel confident enough to champion for it if other reviewers strongly disagree. However, given all the clarifications provided by the authors and the recommendation by the reviewing guidelines to use 'borderline' decisions sparingly, I feel more comfortable recommending 'accept' now than I did at the start of the rebuttal period. So I will be increasing my score to accept.", "rebuttal": "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.\n\n**1. Threat model?**\n\nIt 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.\n\nFor 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. \n\nThe 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.\n\nSince 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.\n\n\n**2. Why can PD-SGD protect models from black-box membership inference?**\n\nIntuitively, 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. \n\nFor 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.\n\n\n**3. Computational benefits of PD-SGD:**\n\nThanks 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. \n\nWe 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.\n\nFor 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.\n \n**Table:** GPU Memory Usage Comparison\n\n| Method | alloc    | reserved   | peak_alloc | peak_reserved |\n|--------|----------|------------|------------|---------------|\n| SGD    | 37.9 MB  | 6562.0 MB  | 4918.2 MB  | 6562.0 MB     |\n| DP-SGD | 10345.9 MB | 18612.0 MB | 10345.9 MB | 18612.0 MB    |\n| PD-SGD | 145.8 MB | 6712.0 MB  | 5014.5 MB  | 6712.0 MB     |\n\n\n\nResults 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."}, {"review_id": "hiSy0oP35x", "reviewer": "Reviewer_jVqE", "summary": "This paper introduces a novel empirically-effective privacy framework called PD - plausible deniability, and a privacy preserving training algorithm under this framework, PD-SGD. On an intuitive level, models trained under PD have the property that training data points within any mini-batch is not significantly \"different\" under gradient based white-box (i.e. has model weight access, I'm a bit confused by the author's definition of blackbox vs whitebox, but that of tangential interest here) membership inference attacks. Mathematically, this notion can be expressed by the existence of at least T alternative minibatches that falls within a certain Euclidean distance within the target batch, such that their log-density under a normal perturbation model has bounded change. Methodologically, this is implemented by a DP-SGD-like Graussian perturbation followed by rejection sampling of batches with outlier gradients. Empirically, models trained by PD-SGD obtain favorable privacy-utility trade-offs compared to other empirically and theoretically guaranteed defense mechanisms against MI attacks.", "questions": "1. Comparisons against some more recent defense mechanisms would make the experimental contributions more convincing.\n2. Some details on the attack mechanisms are owed, even if in the appendix.\n3. Some training cost comparisons would be good to have.\n4. Table 1 and table 3's font is too smal.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper explains various properties of the proposed PD framework in reasonable detail.\n2. Compared to other empirically motivated defense mechanisms, PD-SGD shows competitive performance while being more up-right under theoretical examination. Compared to DP-based methods, PD-SGD provides clear performance benefits in privacy-utility trade-off. \n3. Experimental evaluations of PD-SGD is fairly thorough on common architectures and datasets, with multiple MI attack methods as benchmark.\n\nWeaknesses:\n1. PD falls short of a \"attack-agnostic\" privacy framework due to it's definition being reliant on a source pool of mini-batches, which seems quite specific to a particular configuration of the MI setting. If the imaginary attacker do not have the same pool of mini-batches as the model provider, (or even better/worse, the attacker has only one target data batch and wants to know if it has been used in the training of the model), then there is no such notion of \"d\" in equation 4, hence no clear way quantify the privacy afforded by PD. This is in contrast to DP, which is agnostic to attacker knowledge.\n2. The baselines in the experiments are quite dated. Various improved alternatives to SELENA and ADVReg have been proposed in the literature since 2023 that also out-perform these two baselines in privacy-utility trade-offs.\n3. The proposed method PD-SGD has an unfavorable privacy-compute trade-off, in that narrowing the threshold $\\gamma$ results in more gradient comparisons needed before a minibatch is rejected. In the extreme case where $\\gamma$ is too low, the algorithm would traverse through the entire dataset for each gradient step. Storing gradients is also not feasible for modern models in the Billions parameter range. Some form of caching, embedding and efficient search strategies should be discussed to make the proposed method more practical.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**1. PD falls short of a \"attack-agnostic\" privacy framework**\n\nPD‑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).\n\nTo 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$.\n\nThe 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).\n\n\n**2. Baselines in the experiments are quite dated.**\n\nYes, 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:\n\n\n**Table:** Evaluations for new baseline: HAMP\n\n| Method                   | Test Acc | P-Attack | R-Attack | S-Attack | C-Attack |\n|--------------------------|----------|----------|----------|----------|----------|\n| Non-private              | 68.56%   | 0.76     | 0.78     | 0.77     | 0.12%    |\n| AdvReg                   | 57.56%   | 0.70     | 0.70     | 0.66     | 0.08%    |\n| SELENA                   | 64.31%   | 0.63     | 0.73     | 0.66     | 0.07%    |\n| HAMP                     | 61.66%   | 0.64     | 0.74     | 0.64     | 0.07%    |\n| DP-SGD (eps=8)           | 47.61%   | 0.56     | 0.56     | 0.56     | 0.08%    |\n| PD-SGD (param setting 1) | 64.83%   | 0.63     | 0.72     | 0.64     | 0.06%    |\n| PD-SGD (param setting 2) | 61.16%   | 0.61     | 0.59     | 0.60     | 0.06%    |\n\n\n\nTwo 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.\n\n\n\n\n**3. The proposed method PD-SGD has an unfavorable privacy-compute trade-off in extreme cases.**\n\nThe 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. \n\nIf hyperparameters are properly tuned, high rejection rates is a telltale sign that it may not be possible to obtain a favorable utility privacy tradeoff. \n\nWe 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.\nMoreover, 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.\n\n\n**4. Storing gradients is also not feasible for modern models in the Billions parameter range.**\n\nPD-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.\n\nAs 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.\n\n\n\n**5. Some details on the attack mechanisms are owed, even if in the appendix.**\n\nWe 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.\n\n\n**6. Some training cost comparisons would be good to have.**\n\nWe 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. \n\n\n**Table:** GPU Memory Usage Comparison\n\n| Method | alloc    | reserved   | peak_alloc | peak_reserved |\n|--------|----------|------------|------------|---------------|\n| SGD    | 37.9 MB  | 6562.0 MB  | 4918.2 MB  | 6562.0 MB     |\n| DP-SGD | 10345.9 MB | 18612.0 MB | 10345.9 MB | 18612.0 MB    |\n| PD-SGD | 145.8 MB | 6712.0 MB  | 5014.5 MB  | 6712.0 MB     |\n\n\nPD‑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.\n\n\n\n**7. Table 1 and Table 3's font is too small.**\n\nWe apologize for that and will fix it in the revised version.\n\n\nReference:\n\n[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.\n\n[2] Zhao, Justin, et al. \"Lora land: 310 fine-tuned llms that rival gpt-4, A technical report.\" arXiv preprint arXiv:2405.00732 (2024).\n\n[3] Yu, Da, et al. \"Differentially private fine-tuning of language models.\"  ICLR 2022."}, {"review_id": "TqxcHR9XpD", "reviewer": "Reviewer_t2cw", "summary": "The paper introduces Plausibly Deniable Stochastic Gradient Descent (PD-SGD), a training procedure that attaches a mini-batch–level “plausible deniability” test to every stochastic-gradient update. Concretely, the seed batch’s gradient is first perturbed with isotropic Gaussian noise; the update is accepted only if at least T other batch gradients fall within a log-density band of width γ around the noisy seed gradient, otherwise the step is rejected altogether. This rejection-sampling view allows the authors to derive an differential-privacy guarantee under mild conditions while avoiding per-example clipping and thus supporting non-decomposable losses. Three hyper-parameters—noise scale, band width, neighbour count—govern the privacy–utility trade-off and can be tuned heuristically by monitoring the rejection rate.", "questions": "See the weakness.", "limitations": "See weakness", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. PD-SGD sounds to be conceptually novel: by enforcing a batch must be indistinguishable from several others before its gradient is used, it turns plausible deniability into a practical optimisation rule.\n2. Experiments on CIFAR-10/100 (Vision Transformers and Wide-ResNets) and Purchase-100 (linear model) show that PD-SGD matches or exceeds the test accuracy of empirical defenses (AdvReg, SELENA) while lowering four standard membership-inference attack scores and vastly outperforming DP-SGD at comparable privacy budgets.\n3. The logic of this paper is clear, the explanatory figures can help readers understand, and the literature review is comprehensive.The experimental section of this paper provides a wealth of details and ablation studies, which enhances its credibility. \n\nWeaknesses:\nThe paper lacks persuasiveness in some places.\n1. Theoretical contributions. The author claims that “to the best of our knowledge, no existing defense mechanism simultaneously offers a theoretically justified guarantee and maintains good model utility.”, which seems to show the significance of this work. However, I suspect that the author has overstated the theoretical contributions of the paper. Although the author elaborates on the theoretical significance in Section 4.1, I would like to know further whether the theory of this paper employs any inspiring mathematical tools or techniques that can distinguish its theoretical contributions from other papers? Otherwise, I will question the novelty of the theory of this paper. Also, the theoretical derivations in the appendix seems to be relatively straightforward, making it difficult to justify the theoretical novelty. \n2. Experiment. The author seems not to have provided comparisons of the method in terms of computational resources and memory. Each iteration still requires computing gradients for all mini-batches to perform the plausibility test, which the authors acknowledge and evaluate in Appendix F.4, implying non-trivial time and energy overhead on large or distributed workloads.\n3. Scalability. Empirical evaluation focuses on black-box membership-inference attacks against medium-scale vision and tabular models; robustness to stronger white-box or property-inference attacks, and scalability to very large language or generative models, remain untested", "was_revised": true, "final_justification": "Despite the additional experiments and clarifications in the rebuttal, the core contributions remain insufficiently substantiated. The proposed “plausible deniability” privacy analysis offers only a superficial repackaging of standard rejection-sampling and advanced-composition techniques, without any novel proof strategies or non-trivial theoretical lemmas to distinguish it from existing DP-SGD work. The computational overhead of the privacy test—potentially requiring gradient evaluations across all mini-batches—remains unbounded and is not accompanied by any formal complexity guarantees or comprehensive runtime benchmarks, especially in distributed or multi-node settings. Furthermore, the empirical evaluation is limited to black-box membership inference and omits stronger white-box or adaptive attacks that would directly challenge the method’s core defense mechanism. Finally, reporting only GPU memory usage without wall-clock timing or communication cost analysis leaves open the question of whether any practical training speedup is achievable. In light of these unresolved theoretical and practical shortcomings, the manuscript does not meet the bar for publication.", "rebuttal": "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.\n\n**1.Theoretical contributions:**\n\nOur 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. \n\nMore 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. \n\nIf 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.\n\n**2. Comparisons of the method in terms of computational resources and memory**\n\nPD‑SGD does not require traversing all mini‑batches at each step: the privacy test stops as soon as it finds $T$ $\\alpha$‑similar batches. \n\nMoreover, 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.\n\nAppendix F.4 provides measurements of training time. Here we provide measurements of memory usage:\n\n\n**Table:** GPU Memory Usage Comparison\n\n| Method | alloc    | reserved   | peak_alloc | peak_reserved |\n|--------|----------|------------|------------|---------------|\n| SGD    | 37.9 MB  | 6562.0 MB  | 4918.2 MB  | 6562.0 MB     |\n| DP-SGD | 10345.9 MB | 18612.0 MB | 10345.9 MB | 18612.0 MB    |\n| PD-SGD | 145.8 MB | 6712.0 MB  | 5014.5 MB  | 6712.0 MB     |\n\nObserve that PD-SGD has similar memory usage as SGD (slightly higher but comparable) and uses much less memory compared to DP-SGD. \n\nPD-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. \n\n**3. Scalability**\n\nTo 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. \n\n\n**4. Threat model in empirical evaluation**\n\nOur 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].\n\nExtension 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.\n\n\nReference:\n\n[1] Shokri, Reza, et al. \"Membership inference attacks against machine learning models.\" 2017 IEEE symposium on security and privacy (SP). IEEE, 2017.\n\n[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.\n\n[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.\n\n[4] Zhao, Justin, et al. \"Lora land: 310 fine-tuned llms that rival gpt-4, A technical report.\" arXiv preprint arXiv:2405.00732 (2024).\n\n[5] Yu, Da, et al. \"Differentially private fine-tuning of language models.\"  ICLR 2022."}]

Author rebuttal:

Meta-review: This paper received extensive discussion, which covered substantial additional theoretical explanation for and justification of the authors' proposed framework, as well as additional experimental results. Two of the reviewers were ultimately very positive about the paper, citing the clarity of the game-based formulations that the authors propose (among other things). 

There is always a danger of accepting a paper based on revisions that have not yet been completed. However, given the energy the authors put into the rebuttal process, I believe they will take the time to incorporate the revisions into the final paper. I also think it is worth giving new conceptual frameworks a chance to be looked at and critqued by the community, even if they are still rough around the edges.

I would encourage the authors to take reviews and subsequent reviewer comments into account carefully, since they reflect the understanding that well-intentioned readers are likely to draw from the paper. In particular, I think the formulation of batch-level guarantees is very confusing, since the authors' proposed algorithm forms batches randomly. I also think that formulating guarantees only at the level of individual iterations is insufficient. DP-SGD works this way since composition theorems for differential privacy (DP) allow one to lift such guarantees to the level of the algorithm as a whole. This type of lifting appears absent here (except in Appendix C which is about DP).
Decision: Accept (poster)