Beyond Membership: Limitations of Add/Remove Adjacency in Differential Privacy
Authors: Gauri Pradhan
Joonas Jälkö
Santiago Zanella-Beguelin
Antti Honkela
Venue: ICLR 2026 Poster (2026)
Keywords: differential privacy
deep learning
privacy auditing
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We show a mismatch between differential privacy guarantees reported by standard accountants and practitioners' expectations.

Abstract: Training machine learning models with differential privacy (DP) limits an adversary's ability to infer sensitive information about the training data. It can be interpreted as a bound on the adversary's capability to distinguish two adjacent datasets according to the chosen adjacency relation. In practice, most DP implementations use the add/remove adjacency relation, where two datasets are adjacent if one can be obtained from the other by adding or removing a single record, thereby protecting membership. In many ML applications, however, the goal is to protect attributes of individual records (e.g., labels used in supervised fine-tuning). We show that privacy accounting under add/remove overstates attribute privacy compared to accounting under the substitute adjacency relation, which permits substituting one record. To demonstrate this gap, we develop novel attacks to audit DP under substitute adjacency, and show empirically that audit results are inconsistent with DP guarantees reported under add/remove, yet remain consistent with the budget accounted under the substitute adjacency relation. Our results highlight that the choice of adjacency when reporting DP guarantees is critical when the protection target is per-record attributes rather than membership.

Published as a conference paper at ICLR 2026
BEYOND MEMBERSHIP: LIMITATIONS OF ADD / REMOVE ADJACENCY IN DIFFERENTIAL PRIVACY
Gauri Pradhan University of Helsinki, Finland gauri, gauri. pradhanha 1s nki .f
Joonas Jälkö
University of Helsinki, Finland
joonas. - ja koohellsiiie linkiinnn.......
Santiago Zanella-Bèguelin Microsoft, Cambridge, UK
Antti Honkela
University of Helsinki, Finland
antti wtr....ooeel@@eee..
ABSTRACT
Training machine learning models with differential privacy (DP) limits an adver- sary's ability to infer sensitive information about the training data. It can be in- terpreted as bound on adversary's capability to distinguish two adjacent datasets according chosen adjacency relation. In practice, most DP implementations use the add/remove adjacency relation, where two datasets are adjacent if one can be obtained from the other by adding or removing single record, thereby protecting membership. In many ML applications, however, the goal is to protect attributes individual records (e-g.. labels used supervised fine-tuning). We show that privacy accounting under add/remove overstates attribute privacy compared to ac- counting under the substitute adjacency relation, which permits substituting one record. To demonstrate this gap, develop novel attacks to audit DP under substitute adjacency, and show empirically that audit results are inconsistent with DP guarantees reported under add/remove, yet remain consistent with the budget accounted under the substitute adjacency relation. Our results highlight that the choice of adjacency when reporting DP guarantees critical when the protection target is per-record attributes rather than membership.
INTRODUCTION
Differential Privacy (DP) (Dwork et al. 2006) provides provable protection against the most com- mon privacy attacks, including membership inference, attribute inference and data reconstruction (Salem et al. 2023). limits an adversary's ability to distinguish between two adjacent datasets based on the algorithm's output. The level of DP guarantee depends the underlying adjacency relation. There exist different notions of adjacency such as the add/remove adjacency, where two datasets differ by the inclusion removal of single record. An alternative is substitute adjacency, where one dataset obtained by replacing record in the other. A special case of the latter is zero-out adjacency, in which record replaced with null entry. In deep learning (Abadi al.) 2016 Ponomareva et al. (202)), the standard approach to DP uses add/remove adjacency, that was designed protect against adversary's ability detect whether individual was part of the training dataset or not.
In this paper. we draw attention the fact that while DP can provide protection against all the common attacks listed above, the add/remove adjacency does not provide protection against infer- ence attacks on data of a subject known to be a part of the training dataset at the level indicated by the privacy parameters. Protection against such inference attacks requires considering substitute adjacency, which protects against inference of single individual's contribution to the data. An add/remove privacy bound implies substitute privacy bound, but with substantially weaker privacy parameters. Most DP libraries (such as Opacus Yousefpour et al. (202T) implement privacy ac- counting assuming add/remove adjacency. A practitioner concerned with attribute label privacy who relies on these libraries to train their model with DP may therefore misled: the guarantees provided by add/remove adjacency overstate the actual protection against attribute inference attacks.

---

Published as a conference paper at ICLR 2026
In order to evaluate practical vulnerability of DP models and mechanisms to substitute-type attacks, we develop a range of auditing tools for the substitute adjacency and apply these to DP deep learning. craft pair of neighbouring datasets, D and D' by replacing target record D
In this setting, with a canary record z'. A canary serves as probe that enables the adversary to determine whether model was trained on D or D'. We find that the algorithms do indeed leak more information to training data inference attacker than the add/remove bound would suggest.
Our Contributions:
We propose algorithms for crafting canaries for auditing DP under substitute adjacency, provid- ing tight empirical lower bounds matching theoretical guarantees from accountants (Section 3 We show that privacy leakage can exceed the guarantees derived from add/remove accountants but (as expected), closely tracks the guarantees predicted by substitute accountants (Section 6
Our results demonstrate that accounting for privacy under the commonly used add/remove ad- jacency overstates the protection against attribute inference, including label inference.
RELATED WORK AND PRELIMINARIES
2.1 DIFFERENTIAL PRIVACY
Differential Privacy (DP) (Doork et al. 2006 is framework to protect sensitive data used for data analysis with provable privacy guarantees.
Definition 1 ((e, 6, -iffferrnnil Privacy). A randomized algorithm M is (c, 5, didfffrrrtil private for all pairs of adjucent datasets DD D', and for events
Pr(M(D) E S] S Pr[M(D') E +
Under add/remove adjacency (~AR). ) is obtained by adding or removing record x from D. In substitute adjacency (~ D' is formed by replacing record in D with another 2'. Kairouz ltt al. (202T) also introduced the zero-out adjacency which corresponds to removing a record from DD and replacing it with a zero-out record (.)) to form DD'. Privacy guarantees for this adjacency semantically equivalent to the add/remove DP.
2.2 DIFFERENTIALLY PRIVATE STOCHASTIC GRADIENT DESCENT (DP-SGD)
Differentially Private Stochastic Gradient Descent (DP-SGD) Rajkumar & Agarwal 2012 Song et al. 2013 Abadi et al. 2016) forms the basis of training machine learning algorithms with DP. It used train ML models while satisfying DP. Given a minibatch B, E DD time step f, DP-SGD first clips the gradients for each sample in B, such that the l norm for per-sample gradients does not exceed the clipping bound C. Following that, Gaussian noise with scale oC' added to the clipped gradients. These clipped and noisy gradients are then used to update the model parameters 0 during training as follows:
044 + 0,
Σ clip(Vol(0:::.C) ZEB.
(I)
where Z, O"C²), [B] is the expected batch size, and r denotes the learning rate of the training algorithm. In this way, DP-SGD bounds the contribution of an individual sample to train the model. this paper, we also use AP-Adam which is the differentially private version of the Adam (Kingma & Ba 2015) optimizer.
DP provides upper bounds for the privacy loss expected from an algorithm for a given adjacency re- lation. Early works used advanced composition (Dwork et al., 2010 Kairouz et al. 2015) to account for the cumulative privacy loss over multiple runs of a DP algorithm. Abadi et al. (2016): Mironov 2017;; Bun & Steinke (2016) developed accounting methods for deep learning al algorithms. How- ever, the bounds on DP parameters provided by these accountants are not always tight. Recently, numerical accountants based on privacy loss random variables (PRVs) (Dwork & Rothblum 2016
Meiser & Mohammadi] 2018) have been adopted across industry and academia (Koskela al.
2020
Gopi et al. 2021) because they offer tighter estimates of DP upper bounds.
2

---

Published as a conference paper at ICLR 2026
2.3 AUDITING DIFFERENTIAL PRIVACY
Privacy auditing helps evaluate the empirical privacy leakage from differentially private machine learning algorithm. DP auditing involves assessing the privacy it affords to worst-case canary records. Jayaraman & Evans (2019) were the first to evaluate the empirical privacy leakage from machine learning models trained with DP-SGD and revealed a large gap between the empirical leak- age and the theoretical bounds guaranteed by DP-SGD. Later, Nasr et al. (202T) audited DP machine learning algorithms under progressively stronger threat models. They show that the empirical pri- vacy leakage from their strongest threat model using worst-case dataset canaries was "tight" with respect to the privacy accounting upper bound for DP. Subsequent works such as Nasr et al. (2023); Steinke et al. (2023); Annamalai & Cristofaro 2024); Zanella-Béguelin al. (2023): Mahloujitar et al. (2025): Cebere et al. (2025) have since been focused on crafting worst-case canary records that could yield tight auditing for models trained with natural datasets with the more recent works
focusing on practical threat models.
Threat models in auditing differ by the adversary's 's level of access: in the White-Bol setting, the adversary can access the intermediate models during training (Nasr et al.) |023 Steinke et al.) 2023]; in the more realistic Hidden--State setting, the adversary can only access the final model but may still perturb inputs to intermediate models (Annamalai 2024]] Cebere et al. 2025); and in the Black-Bol setting (Annamalai & Cristofaro 2024, Boglioni et al. 2025), the adversary can only insert canary sample(s) at the start of training and tracks the final trained model's response these canary sample(s).
[023
AUDITING DP WITH SUBSTITUTE ADJACENCY
Our goal is to design canary sam- ples for auditing DP under sub- stitute adjacency in a hidden-state threat model. In this setting, the adversary can only access the final model any step t, without visibil- ity into prior intermediate models. Table α briefly describes the craft- ing scenarios for canaries used to audit DP with substitute adjacency. In Table2] detail the adversary's s prior knowledge in each scenario. Algorithm|] presents the method to audit DP in a substitute-adjacency threat model.
Algorithm 1 Privacy Auditing With Substitute Adjacency
Requires: Model Architecture Mi, Model Initialization 6.. Dataset D. Target Sample z, Training Loss e, Training Steps I. learning rate
n, Optimizer opt_step(). Crafting Algorithm craft(), DP Parame- (a, C, q). Repeats R, Crafting E [Gradient-Space, Input-Space).
O + OR. B 0R
Adversary as Crafter:
if Crafting = Gradient-S Space then
3. Is.9e' Ir f- craft(M, D, 0o T, T, C, opt_step)
else
z' craft(=, M, D. O, T. spe_step)
r R do
Challenger as Model Trainer:
7: Choose uniformly at random: b ~~ {0, 1}
Bir] b
for f 1,.... T do
Sample B, from D with proh. q ge, <- 0pp
3.1 AUDITING MODELS USING CRAFTED WORST-CASE DATASET CANARIES
11:
12:
for 2, E B, do
ge, + go, + clip(Va(((z)))C)
14: if = then
DP gives upper bound on pri- vacy loss an algorithm. It as- sumes that the adversary can access the gradients from the mechanism. Furthermore, it guarantees that the privacy of a target record (crafted to yield worst-case gradient) holds even when the adversary constructs worst-case pair of neighbouring datasets (D, D'). Thus, any privacy auditing procedure with such strong adversary yields tightest empirical lower bound on privacy parameters. Nasr et al. (2021) were the first to propose an auditing procedure which is provably tight for worst-case neighbouring datasets crafted to audit DP with add/remove adjacency.
90, + 9o, + (ccip((Vo((((;=)))
+os] with prob.
else
ge, + go, + [clip(VV or +g-r with prob, q
17:
g6, + ge, + (O 0²C*1)
18:
19:
0.41 + opt opt_step(O,,..... .))
D Adversary as Distinguisher:
[rr] + 1ogiit(;;;0) 07) logit(z';Or) or 9z (C) (0r 0o)
20
return O, 13
3

---

Published as a conference paper at ICLR 2026
Table 1: Crafting schema for auditing privacy leakage under substitute adjacency with varying ad- versary capabilities. The adversary can either craft canaries that allow them to directly manipulating the gradient input to the DP algorithm or they are restricted input-space perturbations to craft the canary samples.The The adversary's visibility into the training process is defined by the following threat models: (a) Visible-State (commonly known the literature as White-Box, where adver- sary assumes access to gradients from the model, and (b) Hidden-State, where they rely on model parameter updates/ output logits to estimate privacy loss.
Scenario
Crafting Spuce
Type of Canary
Crafting Algurithm
Distinguishubiiit Scure
Threat Model
Craited Dataset
Log( (rrn P1) logl Pr(or]) (27)
Visible-Ntat
S2
Gradient
Crafted Gradient
Algoribim
67
Hidhlen State
Input
Cralted Iaput Sample
Algoritim
logit(2:0,]
1ogii((":00))
Hidden-Stale
S4
Input
Crafted Mislabeled Sample
Algorithm
(ogit(2;0g)
Hidden-State
Input
Adversarial Natural Sample
Algoritmm
logit(2;0r) logit(z';0r)
Hidden-Stute
We craft and D' as worst-case neighbour- ing datasets under substitute adjacency (sce- nario S1 in T. Assuming 'D has sample which yields gradient 9s such that [|9: C' throughout training. For maximum distin- guishability, we form D' by replacing with z' such that | = C' but it is directionally op- posite to Is- For all the other samples in DD and D', assume that they contribute 0 gradients during training. Unlike Nasr et al. (202T). we do not assume that the learning rate 0 for the steps with no gradient canary in the minibatch since this discounts the effect of subsampling bution by the minibatches without z or z', our setting more accurately reflects the true dynamics of DP-SGD. We further assume the adversary cannot access intermediate updates and observes only the final gradients from the mechanism.
Table 2: Adversary's prior knowledge in each au- diting scenario described in Table
Scenario
Priors
S1
S2
S3
S4
Ss
Data Distribution
Target Sample (z)
Model Architecture
Training Hyperparameters
Subsampling Rate (g)
Clipping Bound (C)
Noise Muttiplier (a)
auditing. Since account for the noise contri-
At any step T, given subsampling rate q, the number of times the canary is sampled over T' steps is a binomial, B ~ Binomial q). Conditioned on B = k, the cumulative gradient given by
Pr B = N
(2)
The marginal distribution gr over or D' at step is given by
T
Pr(gr D D')
Σ k=0
(1
q
where C is the gradient contribution of and -C of D'. The adversary can use Equation 3 to compute Log(Pr((r) (D)) log(Pr(pr) as the scores compute the empirical lower bound for Es during auditing.
3.2 AUDITING MODELS TRAINED WITH NATURAL. DATASETS
While DP offers protection to training samples against worst-case adversaries, high-utility ML mod- els are obtained by training on natural datasets. Under substitute adjacency, 'D and D'' differ by replacing target sample in D with z'. Effective auditing for models trained with natural datasets, therefore requires canaries that maximize the distinguishability between the two datasets.
3.2.1 CRAFTING CANARIES FOR AUDITING IN GRADIENT SPACE
Recently, Cebere et al. (2055) propose a worst-case gradient canary for tight auditing on models trained with add/remove DP using natural datasets in hidden state threat model. Adapting their idea to substitute adjacency-
auditing, we first select the train- able model parameter which changes least in terms of its magnitude throughout training.
4

---

Published as a conference paper at ICLR 2026
We then define canary gradients 9= and 92' by setting all other parameter gradients to O, and assigning a magnitude C to the gradient of the selected least-updated parameter. This ensures that I|==ll 11 = C. For max- imum distinguishability between 9= and fz', we orient them in opposite directions in gradient space. The detailed procedure for construct- ing these canaries is provided in Algorithm 2 For computing the empirical privacy leakage, we record change parameter from initializa- tion, 0g - On as scores for auditing. These scores serve as proxies for the adversary's con- fidence that the observed outputs were from model trained on D or D'. This setting corre- sponds to scenario S2 in T Such canaries can be used to audit models trained using fed- erated learning.
Algorithm 2 Generating Crafted Gradient Canary
Pair (fa,9z) 92')
Requires: Dataset D. Training Loss f, Model Initial- ization bo. Training Steps T, Learning Rate v, Clipping
Bound C. Optimizer opt_step().
def craft:
2:
S < S.1. d |00]
8:
for E E, 1,.., T
Sample B. from D Jo, + clip (
6:
oct1 f- opt opt_steppO.. Jo.
for E l......ddd
S₃ - Sj + 4/ 07
9:
j regmin,sssale
10:
Ox f
3.2.2 CRAFTING CANARIES FOR AUDITING IN INPUT SPACE
II:
9: C
9r t O0
9+1 + -C
In practice, adversaries are unlikely to directly manipulate model's gradient space during training. such cases, the adversary is constrained to input-space perturbations where a natural sample E D will be replaced with an adversarially crafted sample E' to form D' prior to training. For instance, an adversary could mount a data-poisoning attack during the fine-tuning of a large model, attempt infer the label of known-in-trailee -itaiinnn user. For input-space canaries, we track logit(2;8)) - logit(''; 0,) as scores for auditing.
return Is.
For auditing using input-space canaries, we begin by selecting a target sample (z) for which the reference model (trained with- out DP) exhibits least-confidence over train- ing. The crafted canary equivalent (2') can then be generated using the following crite- ria:
Algorithm 3 Generating Crafted
Input Canary
(z' ~ (x',y)
Requires: Target Sample (zc, v). Dataset D, Training Loss e. Model M. Model Initialization do. Training Steps T, Crafting Steps N, Learning Rate 17.
1: def craft:
Algorithm is used to generate a crafted input canary z' (a'. com- plementary to the target sample (Sce- nario S3 Table [). It uses the ref- erence model to craft z' such that the cosine similarity between Oд and 9=' is minimized while ensuring that 9s' is similar in scale to 9N so that the model interprets z' as legitimate ple from the data distribution.
3
Or < train(M, Co, D,T, E,
z' ~ (F',3) s.t. x' +- 0z
Tpl(Or:x.y) Vol(Or:z'.))
Leosim(a')) (x') [ Vol(00; y)l
(MSE(#') + MSE(V MSE((Ve((rre) (f Vol(Or;a for n E 1,.... do
a' +-x' n(V Ceosim (x') + A (MMB(<z))
return
Algorithm 4 is used generate crafted mislabeled canary 2' ~ (x. v') complementary to the target sample 2 (Scenario S4 in Table l}. We use the reference model to find a label y in the label space y such that it minimizes cosine similarity between gzr and gz'.
Algorithm 5 is used to select an adversarial natural canary z' ~ (a', yy) from an auxiliary dataset D aux (formed using subset of samples not used for training the model) complementary to the target sample z (Scenario S5 in Table Tb. We use the reference model to find sample z' in Daux which yields minimum cosine similarity between I=' and 92'
USE OF GROUP PRIVACY TO APPROXIMATE SUBSTITUTE ADJACENCY YIELDS SUBOPTIMAL UPPER BOUNDS
By the definition of DP with substitute adjacency (Definition D. D' can be obtained from D by removing record and adding another record z' to D. As such, it is common practice to infer
5

---

Published as a conference paper at ICLR 2026
Substitute adjacency as composition of one Add and one Remove operation (Kulesza al. 2024). According to Dwork & Roth (2014), if an algorithm M satisfies ( ~ AR) AR)D then for any pair of 'D and D' that difter in at most k records, the following relationship holds true
k-1
Pr(M(D) E s e Pr[M(D)) E S]
+
c j
(4)
From Equation 4 it follows that
Theorem 4.1 (Dwork& & Roth (2014), Any algorithum M which satisfies (EAR, 6AR, AR)-DP is (Es, sDP with Eg 2E An and óş (1 e A
Theorem[4.]]]iee an upper bound for substitute DP derived from add/remove DP which is agnostic of the underlying algorithm. For certain algorithms (such as the Poisson-subsampe DP-SGD used in this paper), which can be characterized by privacy loss random variables (PRVs) and their corre- sponding privacy loss distribution (PI.) (Dwork & Rothblum 2016 Meiser & Mohammadi 2018 Koskela et al., 2020), numerical accountants can derive the privacy curve directly. This approach recommended over using general, algorithm-agnostic upper bounds, as provides significantly tighter privacy guarantees, Moreover, Theorem 4.1 assumes scaled ò; with fixed ô, Eş may exceed
EAR (as shown in Figure A5 Appendix A.3)
Algorithm 4 Generating Crafted Mislabeled
Algorithm 5 Selecting Canary From Natural Samples(2' ~ (x',
Canary (2' ~ 3/))
Requires: Target Sample = (ar, u). Dataset 2)
Requires: Target Sample ~ (r. v). Dataset D. Train- ing Loss E, Model M. Model Initialization Oo. Training Steps T. Learning Rate y,. Auxiliary Dataset Daux-
Training Loss L. Model Mi, Model Initialization Oo.
Training Steps T, Learning Rate 1,, Label Space V
def craft:
def craft:
2: Or f- train(M, 0o, D, e.,))
2: Or <- train(M, 0g, E,
3: S O. + 3/
3:
S s.t. d 4- [Daux]
for E do
4:
for 2 E Daux do
~~ (z, 1)
2 ~~ (t, Ú)
Vol(Or; 2) 2) Vol(Tr; [ol(Or;; z)]l V Vol(Or;
VollOr; V Vol(0r; [
ST
jr argmin, (S)
j argmin,sisal$.
8: V' Vbj*
8: 2' + D Danxlj"1
return
return
5 GENERAL EXPERIMENTAL SETTINGS
Training Details:
Training Paradigm: We fine-tune the final layer of ViT-B-16 (Dosovitskiy et al. 1021 model pretrained on ImageNe We also fine-tune a linear layer on top of Sentence-BER (Reimers & Gurevych, 2019) encoder for text classification experiments. We use 3-layer fully-connected multi-layer perceptron (MLP) (Shokri al. 2017) for the from-scratch train- ing experiments.
Datasets: For supervised fine-tuning experiments, we use 500 samples from CIFARIO (Krizhevsky) 2009), widely used benchmark for image classification tasks (De et al. 2022 Tobaben et al. 2023) and 5K samples from SST-2 (Socher et al. (013)) for text classification
task. To train models from scratch, we use 50K samples from Purchase 100 (Shokri et al. 2017).
Privacy Accounting: We adapt Microsoft's prv-account ant (Gopi et al. (021) to com- pute the theoretical upper bounds for substitute adjacency- based DP with Poisson subsampling. We share the code for this accountant in supplementary materials.
Hyperparameters: We tune the noise added for DP relative to the subsampling rate g and train- ing steps T. We keep the other training hyperparameters fixed to isolate the effect of privacy amplification by subsampling (Bassily et al. [0044] Balle al.) 2018) on auditing performance. Detailed description of the hyperparameters used in our experiments is provided in Table [A] Auditing Privacy Leakage / Sttep: We perform step-wise audits by treating the model each training step i as a provisional model released to the adversary. The adversary is restricted to use only current model's 's parameters or outputs to compute the empirical privacy leakage at step t.

---

Published as a conference paper at ICLR 2026
Computing Empirical with Gaussian DP (Dong et al. 2019): DP (by Definition implies upper bound on the adversary' 's capability to distinguish between M(D) and M(D)). For computing the corresponding empirical lower bound E, we the method prescribed by Nast et al. (2023)
which relies on y--DP. This method allows us to get a high confidence estimate of & with reasonable repeats of the training algorithm.
Given a set of observations and corresponding ground truth labels B obtained from Algorithm I the auditor can compute the False Negatives (FN), False Positives (FP), True Negatives (TN), and True Positives (TP) at a fixed threshold. Using these measures, the auditor estimates upper bounds on the false positive rate (FPR) and false negative rate (FNR) by using the Clopper- Pearson method (Clopper & Pearson 1934) with significance level a = 0.05.
Kairouz et al. (2015) express privacy region of DP algorithm terms of FPR and FNR. DP bounds the FPR and FNR attainable by any adversary. Nasr et al. (2023) note that the privacy region for DP-SGD can be characterized by μ JDGDP (Dong al. 2019).. Thus, the auditor can use FPR and FNR to compute the corresponding empirical lower bound μ in μ-GDP,
(5) where represents the cumulative density function of standard normal distribution (O, 1). This lower bound μ be translated into a lower bound given ō in (e, SDDD using the following theorem,
Hlower = -1- FPR) - Φ- (FNR).
Theorem 5.1 Dong et 2019
Conversion from μ-GDP (E,6)-DP). If an algorithm M μ-GDP, then it is also (5, DD 2 0), where
#
E
8(E) +b
+
e
+
(6)
2
p
1=0.0
0=2555
q=0.0625
2
0
2
6
2
8
2
(Accounting)
+ (Group Privacy)
(Audiiing)
(Accounting)
(Accounting)
Figure 1: Auditing DP using worst-case dataset canaries based substitute adjacency. When the adversary crafts the neighbouring datasets as worst-case dataset canaries (S1), we find that the empirical privacy leakage for DP algorithm, (Auditing exceeds the privacy upper bound for add/remove DP, EAR (Accounting). It closely tracks the privacy budget predicted by substitute accountant, g (Accounting). The plot shows that es (Accounting) is tighter when compared that es (Group Privacy) computed using Theorem 4.1 We fix durger = 10-5 C = 1.0 and T 500. The auditing estimates are averaged over 3 repeats. For each repeat, we use R 25K runs estimate (Auditing) at the final step of training. The error bars represent 2 standard errors around the mean computed over 3 repeats of auditing algorithm.
RESULTS
6.1
AUDITING WITH WORST-CASE CRAFTED DATASET CANARIES
Figure [ depicts the relation between Es (Accounting) computed with substitute accountant, (Group Privacy) computed using Theorem 4.1, (Auditing) using crafted worst-case dataset ca- naries from Section 3.T. and eA (Accounting) computed with add/remove accountant for set
7

---

Published as a conference paper at ICLR 2026
of DP parameters. We observe that (Auditing) exceeds EAR (Accounting) but remains tight with respect to Es (Accounting). Thus, mounting a substitute-style attack using worst-case dataset ca- maries enables the adversary detect whether D DD' was used for training model with higher confidence than promised by AN (Accounting).
q=
9 0.25
g == 0.0625
10
ES (Accounting)
(Accounting)
Crafted Canaries
Crafted Mislabeled Canary (84)
con (Accounting)
Inpat Canary (x.3)
Adversarid Natural Canary (6,y) (S5)
Figure 2: Auditing models trained with DP using natural datasets. We fine-tune final layer of VÝT-B-16 models pretrained on ImageNet2IK using CIFARIO. The privacy leakage (e) audited us- ing our proposed canaries for this setting exceeds the add/remove DP upper bounds, EAR (Account- ing). As these canaries are used to mount a substitute-style attack, the figure shows that add/remove DP overestimates protection against such attacks. Efficacy of the canaries decline as subsampling rate q decreases, the effect being most significant for audits using input-space canaries. We plot for every kth step (A= 25) of training averaged over 3 repeats of the auditing algorithm. For each repeat, we train = 2500 models, 1/2 trained with and the remaining with z'. The error bars represent +2 standard errors around the mean computed over 3 repeats of auditing algorithm.
6.2 AUDITING MODELS TRAINED WITH NATURAL DATASETS
In this section, we report auditing results models trained with natural datasets. In fine-tuning experiments with CIFAR10, all are proposed canaries outperform add/remove DP at large subsam- pling rates. With the strongest canaries, we observe that the empirical privacy leakage exceeds the add/remove DP upper bounds for models trained from scratch with Purchase 100. Our proposed canaries have no discernible effect on the utility of the models as shown in Figure A1
6.2.1 USING GRADIENT-SPAR SPACE CANARIES
Figure shows that, when auditing models that are trained using natural datasets, we get the tightest estimates of E by using crafted gradient canaries for auditing. The empirical privacy leakage (s) estimated using these canaries violates E AR (Accounting). The canary gradients, 9= and grr, crafted using Algorithm
(Ig==l = || 2 stay constant over the course of training and have near- saturaatto gradient norms C). This ensures that their effect on the parameter updates of the model consistent and is most affected by the choice of subsampling rate q. As g decreases, the canary is less visible to the model during training, which yields weaker audits.
6.2.2 USING INPUT-SPACE CANARIES
In this setting, the adversary is only permitted insert crafted input record into the training dataset. In Figure we observe that although input-space canaries yield less tight audits when compared to crafted gradient canaries, the privacy leakage audited using the input-space canaries can exceed the guarantees of add/remove DP. We observe that the efficacy of audits with input-space canaries de- creases for later training steps. This deterioration is much more significant at a low subsampling rate (q). Additionally, in Appendix A.2] observe that audits using input-space canaries sensitive to the choice of other training hyperparameters such as clipping bound C' (Figure A2). number of training steps 7' (Figure A3). and learning rate y (Figure A4).
8

---

Published as a conference paper at ICLR 2026
q=0.25
g=0.0625
10
2
2
10
(Accounting)
K3 (Accounting)
es (Accommting)
(S2)
Mislaheled Canary (x.y) (84) Natual Adversarial Canaay (') (85)
PAe (Accounting)
Crafted Iaput Canary (x.y) (83)
Figure 3: Auditing MLP model trained from scratch with random initialization using Pur- chase100. We find that auditing such models using input-space canaries yield weaker audits. We do not observe e from such audits to exceed the privacy implied by EAR (Accounting). However, using crafted gradient canaries, we still get & from auditing which is consistent with Es (Accounting). We plot e for every kth step (k 125) of training. We train It 2500 models, 1/2 trained with and the remaining with z'. We use DP-Adam as the optimizer for training models from scratch.
6.2.3 AUDITING MODELS TRAINED FROM SCRATCH
Training models from scratch with random initialization is non-convex optimization problem. shows that auditing models trained from scratch on Purchase 100 dataset using input-space canaries yields weaker audits. We find that input-space canaries sensitive to model initialization and the choice of optimizer (DP-Adam this case). Subsampling further deteriorates the effec- tiveness of audits with input-space canaries. In this setting, add/remove DP does suffice protect against attacks using input-space canaries as shown in Figure However, our proposed crafted gra- dient canaries still yield strong audits for models trained from scratch with empirical privacy leakage that closely follows Es (Accounting).
6.3 AUDITING MODELS FINE-TUNED TUNED FOR TEXT CLASSIFICATION
We fine-tune a linear layer on top of Sentence-BERT (Reimers & Gurevych, 2019) encoder using 5K samples from Stanford's Sentiment Treebank (SST-2) dataset (Socher al. (013). We present the results for this experiment in Figure A66] The models are trained using DP-SGD. We find that gradient-canary-bsse auditing yields tight results. While the audits using input-space canaries not tight, we do observe that the empirical privacy leakage estimated using them does exceed the privacy guaranteed by add/remove DP.
DISCUSSION AND CONCLUSION
We provide empirical evidence which shows that for certain ML models, DP with add/remove ad- jacency will not offer adequate protection against attacks such as attribute inference at the level guaranteed by the privacy parameters. This is because the threat model for these attacks mimics substitute-se stylle attacks. In Figure 2 for DP models are trained using natural datasets, we observe violations of add/remove DP guarantees with the canaries designed to substitute a target record or target record's s gradient in the training dataset. The resulting empirical privacy leakage from such au- dits closely follows DP upper bound for substitute adjacency. Thus, practitioners seeking attribute or label privacy using standard DP libraries which default to add/remove adjacency-based accountants might risk overestimating the protection add/remove DP affords against substitute-style attacks.
We observe that fine-tuned models (as shown in Figure 2) are more prone to privacy leakage with input-space canaries compared to models trained from scratch (Figure 3). In practice, limited sensitive data makes DP training from scratch challenging, Tramer & Boneh (2021) have shown that given suitable public pretraining dataset, fine-tuning pretrained model on sensitive data yield higher utility than models trained from seratch. This makes results with supervised

---

Published as a conference paper at ICLR 2026
fine-tuning important since reveals that poisoning the fine-tuning datasets once with ipput-space canaries is sufficient to cause privacy leakage exceeding add/remove DP bounds, particularly at large subsampling rates which are often used for improved privacy-utilit trade-off (De et al. 2022 Mehta et al. ).23).
9
0.255
q= 0.0625
10
10
10
107
10
10a
10a
10
10a
10'
of training runs
(Accounting)
Crafted Gradient Canories (S2)
Canury (xy (84)
Sux (Acoomnting)
Crafted Input Canary (x (83)
Adversarial Natural Camry (r (S5)
Figure 4: Effect of number of training runs R on privacy auditing. For VIT-B-16 models with final layer fine-tuned on CIFARIO (T 500, C' 2.0), we record the effect change in on the empirical privacy leakage é, the final step of training. The error bars represent +2 standard errors around the mean computed over 3 repeats of auditing algorithm. each repeat, 1/2 of the models trained with and the remaining with z!.
Our methods to audit DP under substitute adjacency are not without limitations. We note that the efficacy of our proposed input-space canaries depends strongly on the training hyperparameters (see Figures A2 to A4 in Appendix A.2). They provide weaker audits at later training steps, especially when the training problem involves non-convex optimization and a low subsampling rate g. This has been persistent issue with input-space canaries as noted by Nasr et al. (2023). Our results show that canaries with consistent gradient signals and near-saturation gradient norms are most robust to the effect of training hyperparameters. An interesting direction for future work is to design input-space canaries that are robust to training hyperparameters and yield tight audits for models trained with real, non-convex objectives.
Our canaries are tailored to audit gradient-based DP algorithms, such as DP-SGD. We expect the canaries work well with other gradient-basee methods, such DP-Adam, although some per- formance degradation is possible (as seen in Figure 3 We do not expect our proposed auditing approach extend other DP mechanisms which operate differently. For instance, label DP (Chaudhuri Hsu 2011) is a special case of substitute DP, where you only substitute the label of example. Auditing using crafted mislabeled canary is the same threat model as label DP. As substitute DP is a generalization of label DP, it will also be valid for auditing a substitute DP mech- anism, even though it might be optimal for that. While DP-SGD with substitute accounting is valid label DP mechanism, in practice, label DP is implemented using very different methods (Ghazi) al. 2021 2024 Busa-Fekete et al., 2023 Zhao et al. 2025). As such, our auditing techniques would not be suitable for those methods.
Furthermore, our methods for privacy auditing rely on multiple repeats of the training process to obtain high confidence measure of lower bound on In Figure 4 we observe that with limited number runs, there is a risk of underestimating the privacy leakage. At low subsampling rate (ạ), the continuous upward trend of auditing curves show that the process has not converged, even with R = 2500 runs. For a detailed breakdown of the computational cost of the our method, we refer to Table| While method is computationally expensive, it could potentially be optimized by inte- grating single-run auditing approaches (Steinke et al. 2023) Mahloujifar et al. (2025). although this might involve trade-off between computational efficiency and the strength of the resulting audits.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported by the Research Council of Finland (Flagship programme: Finnish Center for Artificial Intelligence, FCAI, Grant 356499 and Grant 359111), the Strategic Research Council at the Research Council of Finland (Grant 358247) as well as the European Union (Project 101070617 7). Views and opinions expressed are however those of the author(s) only and do necessarily reflect those of the European Union or the European Commission. Neither the European Union nor the granting authority can be held responsible for them. This work has been performed using resources provided by the CSC- IT Center for Science, Finland (Project 2003275). The authors acknowledge the research environment provided by ELLIS Institute Finland. We would like thank Ossi Räisä and Marlon Tobaben for their helpful comments and suggestions.
REPRODUCIBILITY STATEMENT
The code for our experiments is available at: httpa://githus: com wwtpC//amce//////ceeaaaappaaaaee limitations of add remove rewove_adjaceeeeeeeeeeeeeeeeeeee adjacency.cc..........a in__ppnddppppppp dp We adapted the code from Tobaben et all. (2023) for the fine-tuning experiments.
ETHICS STATEMENT
The research conducted in the paper conform, in every respect, with the ICLR Code of Ethics hhttps: httpp/aacc/c//Coee//EtM....
USE OF LARGE LANGUAGE MODELS (LLMS)
We used LLMs to polish the content of this manuscript for readability and conciseness. We also used it to improve the presentation of mathematical content with LaTeX. LLMS were not used to generate any novel content.
REFERENCES
Martín Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep Learning with Differential Privacy. In Proceedings the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318, 2016.
Meenatchi Sundaram Muthu Selva Annamalai. It's Our Loss: No Privacy Amplification for Hid- den State DP-SGD With Non-Convex Loss. In Proceedings of the 2024 Workshop on Artificial Intelligence and Security, AlSec, pp. 24-30, 2024.
Meenatchi Sundaram Muthu Selva Annamalai and Emiliano De Cristofaro. Nearly Tight Black- Box Auditing of Differentially Private Machine Learning. In Advances in Neural Information Processing Systems 38: Annual Conference Neural Information Processing Systems 2024,
NewrlPS, 2024.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences. In Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurIPS, pp. 6280- 6290, 2018
Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 464-473, 2014.
Matteo Boglioni, Terrance Liu, Andrew Ilyas, and Zhiwei Steven Wu. Optimizing Canaries for Privacy Auditing with Metagradient Descent. CoRR, abs/2507.15836 2025.
Mark Bun and Thomas Steinke. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. Theory of Cryptography 14th International Conference, TCC 2016-B, Proceedings, Part volume 9985 of Lecture Notes in Computer Science, pp. 635-655 2016.

---

Published as a conference paper at ICLR 2026
Róbert Istvan Busa-Fekete, Andrés Muñoz Medina, Umar Syed, and Sergei Vassilvitskii. Label differential privacy and private training data release. In International Conference on Machine Learning, ICML, volume 202 of Proceedings of Machine Learning Research, pp. 3233-3251 2023.
Tudor Ioan Cebere, Aurélien Bellet, and Nicolas Paperno. Tighter Privacy Auditing of DP-SGD in the Hidden State Threat Model. In The Thirteenth International Conference Learning Repre- sentations, ICLR, 2025.
Kamalika Chaudhuri and Daniel J. Hsu. Sample Complexity Bounds for Differentially Private Learning. In COLT 2011 The 24th Annual Conference on Learning Theory, volume 19 of JMLR Proceedings, pp. 155-186, 2011.
C. J. Clopper and E. S. Pearson. The Use of Confidence Fiducial Limits Illustrated in the Case of the Binomial. Biometrika, 26(4):404-413 12 1934. ISSN 0006-3444.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L. Smith, and Borja Balle. Unlocking High- accuracy Differentially Private Image Classification through Scale. CoRR, abs/2204.136500 2022.
Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian Differential Privacy. CoRR, abs/1905.02283, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. In 9th International Conference on Learning Representations, ICLR, 2021.
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-407 2014.
Cynthia Dwork and Guy N. Rothblum. Concentrated Differential Privacy. CoRR, Abs//6003.,187, 2016.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensi- tivity in Private Data Analysis. In Theory of Cryplography, Third Theory of Cryptography Con- ference, TCC, Proceedings. volume 3876 of Lecture Notes in Computer Science, pp. 265-284, 2006.
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and Differential Privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 51 60, 2010.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep Learn- ing with Label Differential Privacy. In Advances Neural Information Processing Systems 34; Annual Conference on Neural Information Processing Systems 2021, NeurIPS, pp. 27131-27145, 2021.
Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. LabelDP-Pres Learning with Label Differential Privacy via Projections. In The Twelfth Interna- tional Conference on Learning Representations, ICLR, 2024.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical Composition of Differential Pri- vacy. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021. NeurlPS, pp. 11631-11642, 2021.
Bargav Jayaraman and David Evans. Evaluating Differentially Private Machine Learning in Practice. In 28th USENIX Security Symposium, USENIX Security, pp. 1895-1912, 2019.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The Composition Theorem for Differential Privacy. In Proceedings of the 32nd International Conference Machine Learning, ICMI., volume 37 of JMLR Workshop and Conference Proceedings, pp. 1375-1385, 2015.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and Private (Deep) Learning Without Sampling or Shuffling. In Proceedings of the 38th International Conference on Machine Learning, ICML, volume 139 of Proceedings of Machine Learning Research, pp. 5213-5225, 2021. 2021.
12

---

Published as a conference paper at ICLR 2026
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In 3rd Interna- tional Conference on Learning Representations, ICLR, Conference Track Proceedings, 2015.
Antti Koskela, Joonas Jälkö, and Antii Honkela. Computing Tight Differential Privacy Guaran- lees Using FFT. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS, volume 108 of Proceedings of Machine Learning Research, pp. 2560-2569, 2020.
Alex Krizhevsky. Learning Multiple Layers of Features From Tiny Images. Master's thesis, Uni- versity of Toronto, 2009.
Alex Kulesza, Ananda Theertha Suresh, and Yuyan Wang. Mean Estimation in the Add-Remove Model of Differential Privacy. In Forty-first International Conference Machine Learning, ICML, 2024.
Saced Mahloujifar, Luca Melis, and Kamalika Chaudhuri. Auditing SIS-Diffcrential Privacy in One Run. In Forty-second International Conference on Machine Learning ICML, 2025.
Harsh Mehta, Abhradeep Guha Thakurta, Alexey Kurakin, and Ashok Cutkosky. Towards Large Scale Transfer Learning for Differentially Private Image Classification. Trans. Mach. Learn. Res., 2023, 2023.
Sebastian Meiser and Esfandiar Mohammadi. Tight on Budget?: Tight Bounds for r-Fold Approx- imate Differential Privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS, pp. 247-264, 2018.
Ilya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, CSF, pp. 263-275, 2017.
Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adver- sary Instantiation: Lower Bounds for Differentially Private Machine Learning. In 42nd IEEE Symposium on Security and Privacy, SP, pp. 866-882, 2021.
Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight Auditing of Differentially Private Machine Learning. In 32nd USENIX Security Symposium, USENIX Security, pp. 1631-1648, 2023.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Ed- ward Z. Yang, Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High- Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, pp- 2019.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy. J. Artif. Intell, Res., 77:1113-
2023.
Arun Rajkumar and Shivani Agarwal. A Differentially Private Stochastic Gradient Descent Algo- rithm for Multiparty Classification. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, AISTATS, volume 22 of JMLR Proceedings, pp. 933 941, 2012.
Nils Reimers and Iryna Gurevych. Sentence-BERP BERT: Sentence Embeddings using Siamese BERT- Networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP. IJCNLP, pp. 3980-3990, 2019.
Ahmed Salem, Giovanni Cherubin, David Evans, Boris Köpf, Andrew Paverd, Anshuman Suri, Shruti Tople, and Santiago Banella-Bégueliy SoK: Let the Privacy Games Begin! A Unified Treatment of Data Inference Privacy in Machine Learning. In 44th IEEE Symposium on Security and Privacy, SP, pp. 327-345, 2023.
13

---

Published as a conference paper at ICLR 2026
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership Inference At- tacks Against Machine Learning Models. In 2017 IEEE Symposium on Security and Privacy, SP, pp. 3-18, 2017.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng. and Christopher Potts. Recursive Deep Models for Semantic Compositionality Over Sentiment Treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631-1642, Seattle, Washington, USA, 2013.
Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with dif- ferentially private updates. In IEEE Global Conference on Signal and Information P Processing, GlobalSIP, pp. 245-248, 2013.
Thomas Steinke, Milad Nasr, and Matthew Jagielski. Privacy Auditing with One (1) Training Run. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Infor- mation Processing Systems 2023, NeurlPS, 2023.
Marlon Tobaben, Aliaksandra Shysheya, John Bronskill, Andrew Paverd, Shruti Tople, Santi- ago Zanella Béguelin, Richard E. Turner, and Antti Honkela. On the Efficacy of Differentially Private Few-shot Image Classification. Trans. Mach. Learn. Res., 2023. 2023.
Florian Tramèr and Dan Boneh. Differentially Private Learning Needs Better Features (or Much More Data). In 9th International Conference on Learning Representations, ICLR, 2021.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: Friendlyy Differential Privacy Library in Py ToTchh. CoRR, abs/2109.12298, 2021.
Santiago Zanella- Zénella-Béguelin, Lukas Wutschitz, Shruti Tople, Ahmed Salem, Victor Rühle, Andrew Paverd, Mohammad Naseri, Boris Köpf, and Daniel Jones. Bayesian Estimation of Differential Privacy. In International Conference on Machine Learning, ICML., volume 202 of Proceedings of Machine Learning Research, pp. 40624-40636, 2023.
Puning Zhao, Jiafei Wu, Zhe Liu, Li Shen, Zhikun Zhang. Rongfei Fan, Le Sun, and Qingming Li. Enhancing Learning with Label Differential Privacy by Vector Approximation. In The Thirteenth International Conference on Learning Representations, ICLR, 2025.
A APPENDIX
A.1 EXPERIMENTAL TRAINING DETAILS
Table details the hyperparameters used for training the models for our experiments. We use Opa- cus Youseefourr et al. (021) to facilitate DP training of models with Pytorch (Paszke et al. (2019).n In our experiments, we vary the seed per run, which ensures randomness in mini-batch sampling and, the case of models trained from scratch, also ensures random initialization per run.
We find that adding canary the gradients datasets does not compromise the utility of the trained models which we measure in terms of their accuracy on the test dataset. cogupresrccmppres the test accuracies for models poisoned using gradient canaries (Algorithm 2 and crafted input canary (Algorithm B) to models trained with the target record. With g = I, the model "sees" the canary at each step of training. Despite that, observe minimal difference in test accuracies averaged across 5 models trained with target record and models trained with either gradient or crafted input canaries.
A.2 EFFECT OF TRAINING HYPERPARAMETERS ON AUDITING
Choice of the clipping bound C only affects audits done using input-space canaries significantly. This because gradient-space canaries are crafted using Algorithm 2 which ensures that I! and || C. (that is, they have near-saturation gradient norms) throughout the training process.
14

---

Published as a conference paper at ICLR 2026
Table Al: Hyperparameters used for the experiments in the main paper. We use these as default hyperparameters for a given dataset unless otherwise specified.
Hyperparameters
CIFARIO
Purchase100
SST-2
DP Optimizer
DP-SGD
DP-Adam
DP-SGD
Trainable Parameter Count (0))
768
89828
384
Initialization (0))
Fixed
Random
Fixed
Subsampling Rate (q)
(1.0, 0.25, 0.0625)
(0.25, 0.0625)
(1.0,0.55)
Clipping Bound (C)
2.0
5.0
2.0
Training Steps (T)
500
2500
2500
Learning Rate
0.001
0.0018
0.01
Common Settings
Loss Function
Cross Entropy Loss
Subsampling
Poisson 2500
Auditing Runs (R)
10-5
0.9
0.9
Accuracy on the test datasct
0.8
0.8
0.7
0.7
0.6
0.5
0.4
0.3
0.3
Models Traized on
Models Trained on
0.2
Models Trained on
0.2
Models Trained
100
200
300
400
500
100
200
300
400
T
(a)
(b)
Figure A1: Auditing with our proposed canaries does not compromise model utility. The figure depicts test accuracies as observed over the course of training for (a) models trained with gradient canaries (Algorithm 2 and (b) models trained on crafted input canary (Algorithm B). The model is ViT-B-16 pretrained on ImageNet2IK with final layer fine-tuned on CIFAR1O. We train the model with q = for 500 steps with 10, 10-5 for substitute DP.
Thus, the crafted gradient canaries are minimally affected by clipping during training. In contrast, input-space canaries, specifically, crafted input (Algorithm 3) and adversarial natural canaries (Al- gorithm (5) show high sensitivity to the choice of C. High C' corresponds to higher noise added during DP which affects the distinguishability between target sample and the canary.
In Figure A3 we find that, keeping subsampling rate q fixed 0.0625), if we vary the number of training steps T, it affects the auditing with input-space canaries. For fixed g, larger 7 means that the canary is "seen" more number of times during training. we keep the total privacy budget constant, larger 7 for fixed g also implics an increase in the noise accumulated over intermediate steps. We observe that the audits done with crafted input canary and adversarial natural canaries suffer with increase in T. especially later training steps.
Similarly, Figure A4 demonstrates that auditing done with input space canaries is affected by the choice of learning rate. Thus, find that canaries crafted/ chosen to mimic samples from training data are susceptible to the training hyperparameters, In auditing, we assume that the adversary has access to the hyperparameters. However, in practice, the model trainer might choose keep these
15

---

Published as a conference paper at ICLR 2026
hyperparameters confidential. This means that the audits done using such canaries underestimate privacy leakage suggested by formal DP guarantees.
C= 1.0
C= 2.0
C= 10.0
6
4
2
ES (Accounting)
(Accounting)
Crafted Gradient Canaries
Crafted Mislabeled Canary (x.y (84)
SAR (Accounting)
Crafted Input Canary (x' -J) (S3)
Adversarial Natural Canary (x,y) (85)
Figure A2: Effect of clipping bound on privacy auditing. For ViT-B-16 models with final layer fine-tuned on CIFARIO (with = 1.0, T 500), varying C causes crafted input and adversarial natural canary to loose their effectiveness as increases. Higher C leads to higher per-step noise added during training. This adversely affects the audits using crafted input and adversarial natural canary. Crafted gradient and crafted mislabeled canary show relatively less sensitivity to C. We plot for every kth step (k 25) averaged over 3 repeats of the auditing algorithm. For each repeat, train = 2500 models, 1/2 trained with and the remaining with z'. The error bars represent +2 standard errors around the mean computed over repeats of auditing algorithm.
A.3 RELATIONSIII BETWEEN EXPECTED PRIVACY LOSs UNDER SUBSTITUTE DP AND ADD/REMOVE DP
Typically, the privacy loss under substitute DP is expected to be 2x the privacy loss under add/remove DP. However, as shown in Equation (4), this holds true when the 8 is also scaled appro- priately when moving from add/remove to substitute DP. If we keep the d constant for add/remove and substitute DP, ESR can be AR, especially when large, that is, when we use large subsampling rate (g) and low noise (a), as shown in Figure A5 We also show that this ratio is dependent on changes in q and ø.
A.4 ADDITIONAL RESULTS/ TABLES
16

---

Published as a conference paper at ICLR 2026
7=500
7=2500
10
8
2
0
2
8
10
10
ES (Accounting)
ES (Accounting)
4 (Accouating)
Crafted Gradient Canaries (S2)
Crafted Mislabeled Canary (x,y) (S4)
FAR (Accounting)
Crafted Inpul Canary (x J² (S3)
Adversarial Natural Canary (x y)) (85)
Figure A3: Effect of training steps 7 on privacy auditing. For ViT-B-16 models with final layer fine-tuned on CIFAR10 (with 0.0625, C 2.0), varying T with subsampling leads to an increase in the noise accumulated over intermediate steps between successive canary appearances during training. This most significantly affects auditing with crafted input and adversarial natural canary. They yield relatively stronger audits for = 500 but with = 2500, they loose their efficacy for later training steps. As the total privacy budget is fixed for T 500 and T 2500, the degradation in audits for input-space canaries can be attributed to the higher per-step noise associated with larger T. We plot for every kth step (k 25 for T 500 and k: 125 for T' = 2500) averaged over repeats of the auditing algorithm. For each repeat, we train R = 2500 models, 1/2 trained with and the remaining with z'. The error bars represent 12 standard errors
around the mean computed over repeats of auditing algorithm.
Table A2: Computational cost breakdown for different phases the auditing schema (Algorithm)
Phase I: Crafting Canaries for Auditing
Computational Cost
Common cost for all canary types
Training the reference model
Q(T Ptrain)
Additional cost (incurred only if the corresponding canary is crafted)
Crafting Gradient Canary (Algorithm
((Ptrain)
Crafting Input Canary (Algorithm 3)
+ O x Purain)
Crafting Mislabeled Canary (Algorithm Crafting Adversarial Natural Canary (Algorihhm)
( x Purain)
+ θ ( x Perain)
Phase II: Training Multiple Instances of Target Model
Training R instances of the target model
+ QR x T x Perain)
Phase III: Computing Empirical
Post pest-processing an R x T array of distinguishability scores
+ +Z( x T)
17

---

Published as a conference paper at ICLR 2026
y 0.0000
2
0
2
8
10
ES (Accounting)
Eş (Accounting)
&y (Accomnting)
Crafted Gradient Canarics (S2)
Crafted Mislabeled Canary (r,y)) (S4)
(Accounting)
Crafted Input Canary (x (S3)
Canary (x.y) (85)
Figure A4: Effect of learning rate on privacy auditing, For ViT-B-16 models with final layer fine-tuned on CIFARIO (with q 1.0, T 500), change r reduces the effectiveness of audits with input-space canaries. We plot ε for every kth step (A: 25) averaged over 3 repeats of the auditing algorithm. For each repeat, we train R 2500 models, 1/2 trained with z and the remaining with z', The error bars represent +22 standard errors around the mean computed over repeats of auditing algorithm.
With 7=500
2.6
a=5
#= 12.5
25
2.4
ES
2.3
2.2
2.1
1.00
0.80
0.60
0.40
0.20
0.01
Sampling Probability (q)
Figure A5: Relationship between Eş (Accounting) and EAR (Accounting) for varying Subsam- pling Rate (q) and Noise (a). The relationship between Es and EAR as defined by Equation (4) is expected to hold when ög = + e 6 However, for fixed öş δAR 10-5 we find that Ey can be > 25 AR. especially for large 9 and low a.
18

---

Published as a conference paper at ICLR 2026
4.0.0
9=2.25
10
2
8
2
ES (Accounting)
ES (Accounting)
ey (Acconnting)
Crafted Gradient Canaries (82)
Crafted Mislabeled Canary (r,y)) (S4)
6AR (Accounting)
Input Canary (x.,3) (S3)
Natural Adversarial Canary (x'y) (85)
Figure A6: Auditing Models Trained For Text Classification. We audit Sentence- BERT models with final linear layer fine-tuned on SST-2 dataset (C' = 2.0, T 2500). We find that using our canaries,
extract privacy leakage from these models which may exceed the privacy guaran- teed by add/remove DP but is in line with the guarantees of substitute DP. We plot & for every kth step (k 125) of training. For each repeat, train R 2500 models, 1/2 trained with and the remaining with z'.
19


Reviews:
[{"review_id": "lH781QyEdA", "reviewer": "Reviewer_hf2R", "summary": "This paper examines how current differential privacy accounting, based on add/remove adjacency, fails to reflect real privacy risks in machine learning. The authors argue that when an attacker already knows a record is in the dataset and wants to infer attributes such as labels, the correct notion is substitute adjacency. They design a set of empirical canary audits in gradient space and input space to measure empirical lower bounds of $\\epsilon$. Experiments on image and tabular data show that substitute adjacency leads to about twice the reported privacy loss of standard accounting. The work demonstrates that existing DP practices overestimate protection against attribute inference.", "questions": "- Would the tight bound derived under substitute adjacency remain valid when compared with mechanisms built on Label Differential Privacy, which is specifically designed to protect labels?\n- Could the authors more precisely define the attacker’s prior knowledge in each auditing setup?\n- Could the authors analyze the computational cost of their auditing approach and provide empirical approximations or results demonstrating its scalability to larger applications?\n- How does the observed privacy loss behave when only part of the input features are assumed known to the adversary?\n- For a fixed noise parameter, is there a typical ratio between substitute and add/remove privacy losses?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper makes a valuable empirical contribution by quantitatively showing how privacy guarantees differ under two adjacency definitions. This is an important clarification for the community and helps link theoretical concepts to practical implications in training differentially private models.\n\n- The originality of the work lies primarily in the empirical auditing framework. The audited privacy loss values align closely with the theoretical upper bounds, supporting the validity of the approach.\n\n- Experimental details and configurations are described clearly, making the study repeatable.", "weaknesses": "- The paper discusses attribute inference but does not evaluate or contrast its findings with other DP formulations that also target label or feature privacy, for example, label-DP.  \n\n- It remains unclear what information the attacker is assumed to know. The experiments appear to assume full feature knowledge except for the sensitive attribute, but this is not formally stated or varied.\n\n- Each privacy point requires many repeated training runs. The feasibility of scaling such auditing to larger settings remains unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pmSGIsS7Hy", "reviewer": "Reviewer_GPRK", "summary": "The paper shows that when we are interested in attribute DP, add/remove adjacency overstates privacy. Substitute adjacency, which allows replacing a record, better captures attribute privacy. Using canary-based attacks to audit DP under substitute adjacency, the authors find that the privacy leakage can exceed add/remove guarantees but aligns with substitute bounds, thus choice of adjacency is critical for per-record attribute protection in practical deployments.", "questions": "1. Given the high computational overhead, what is the authors' estimated potential reduction in the required number of training runs that could be achieved by integrating robust canaries with a single-run auditing technique?\n\n2. \"The mislabeled canary is relatively less sensitive to $C$, likely due to systematic misalignment with the task objective\", can you elaborate on this?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1) The authors provides a clear and rigorous demonstration that standard add/remove adjacency overstates privacy when the goal is to protect individual labels. Through extensive experiments (Section 5), the authors quantify the gap between theoretical DP guarantees and the actual leakage observed in practice, showing that models can leak significantly more information about labels than add/remove accounting would suggest. \n\n2) The main strength of the work is its development of a novel auditing framework under substitute adjacency. The authors design canary-based attacks that can replace target records to probe privacy leakage, with Algorithm 4 being effective in estimating tight lower bounds. By crafting canaries in both the input and gradient spaces, the study establishes a robust methodology that reliably captures attribute-level privacy loss.", "weaknesses": "Computational Cost: High-confidence audits require multiple retrainings, which can be resource-intensive. The authors acknowledge this and suggest potential optimizations using single-run approaches (Steinke et al., 2023).\n\n(minor) Title: The title does not explicitly mention attribute or label privacy. Adding terms like “attribute DP” or “label DP” could make the paper’s setting immediately clear to readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g0BRqMA77r", "reviewer": "Reviewer_Hu7w", "summary": "The paper argues that when the goal is to protect per-record attributes (e.g., labels) rather than just membership, reporting DP guarantees under the standard add/remove adjacency can be misleading. The authors propose auditing methods under substitute (replace-one) adjacency—including worst-case “canary” constructions in gradient space and input space—and show empirically that models trained with DP-SGD can leak more than the add/remove accountant would suggest, while the leakage aligns with a substitute-adjacency accountant.", "questions": "I have no questions about this paper.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper spotlights a real deployment pitfall: most libraries/accountants default to add/remove adjacency, yet many fine-tuning scenarios care about attribute privacy for users already known to be in the training data.\n\nThe gradient-space and input-space canaries (plus mislabeled and natural choices) are well-motivated and easy to reproduce. The “worst-case dataset canary” analysis gives intuitive mixture-of-Gaussians distinguishers and ties directly to the accountant.", "weaknesses": "The paper mixes hidden-state audits, crafted gradients, and input-space canaries; readers may struggle to map these to real-world attacker access. Suggestion: Add a single table that contrasts black-box / hidden-state / white-box access (what the adversary sees, what they can inject) and mark which canaries apply to each, plus a “practical examples” column (e.g., data-collection poisoning during SFT; known-in-training user seeking label privacy).\n\nCIFAR-10 fine-tuning and Purchase100 MLP are reasonable, but the paper’s practical claim (“attribute privacy can be overstated”) would be stronger with at least one text or tabular SFT workload with label privacy relevance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z6vXdmpg0P", "reviewer": "Reviewer_tuq2", "summary": "This paper identifies an important gap between the privacy guarantees provided by add/remove adjacency and the actual protection needed for attribute inference in differential privacy. The authors develop novel auditing techniques for substitute adjacency and demonstrate empirically that standard add/remove accounting can significantly overstate attribute privacy protection.", "questions": "1. Whether this can be generalized to other mechanisms rather than just DP-SGD?\n2. How robust are the empirical ε estimates to randomness in mini-batch sampling and initialisation?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses a critical misconception in practical DP deployments where practitioners may unknowingly overestimate protection against attribute inference when using standard libraries.\n2. The paper explains with examples and citations (Sections 1–2, pp. 1–2), why add/remove adjacency may fail for attribute privacy. This makes the motivation persuasive. \n3. Experiments in Section 6 demonstrate that empirical ε values from auditing exceed add/remove accountant bounds. This supports the paper’s key claim with direct quantitative evidence.\n4. Reproducibility is good since a public anonymized code repository is provided, and Appendix Table A1 includes detailed hyperparameter.", "weaknesses": "1. The attacks are targeting DP-SGD; Whether they are applicable to other mechanisms (e.g., DP AdamW, DP sampling-based methods) are not clear.\n2. Although empirical ε values are averaged over multiple runs (Figure 1, p. 7), the paper does not report confidence intervals or variance across repetitions, making it hard to assess statistical robustness.\n3. The auditing method requires training thousands of models (e.g., R = 2500 per setting). This raises concerns about scalability and applicability to larger models or datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)