The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD
Authors: Milad Nasr
Thomas Steinke
Borja Balle
Christopher A. Choquette-Choo
Arun Ganesh
Matthew Jagielski
Jamie Hayes
Abhradeep Guha Thakurta
Adam Smith
Andreas Terzis
Venue: ICLR 2025 Poster (2025)
Keywords: differential privacy
heuristics
privacy auditing
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We propose a heuristic privacy analysis of DP-SGD based on linearization. We compare it to privacy auditing and theoretical upper bounds.

Abstract: We propose a simple heuristic privacy analysis of noisy clipped stochastic gradient descent (DP-SGD) in the setting where only the last iterate is released and the intermediate iterates remain hidden. Namely, our heuristic assumes a linear structure for the model.

We show experimentally that our heuristic is predictive of the outcome of privacy auditing applied to various training procedures. Thus it can be used prior to training as a rough estimate of the final privacy leakage. We also probe the limitations of our heuristic by providing some artificial counterexamples where it underestimates the privacy leakage.

The standard composition-based privacy analysis of DP-SGD effectively assumes that the adversary has access to all intermediate iterates, which is often unrealistic. However, this analysis remains the state of the art in practice. While our heuristic does not replace a rigorous privacy analysis, it illustrates the large gap between the best theoretical upper bounds and the privacy auditing lower bounds and sets a target for further work to improve the theoretical privacy analyses.

Published as a conference paper at ICLR 2025
THE LAST ITERATE ADVANTAGE: EMPIRICAL AUDITING AND PRINCIPLED HEURISTIC ANALYSIS OF DIFFERENTIALLY PRIVATE SGD
Thomas Steinke," * Milad Nasr," Arun Ganesh, Borja Balle, Christopher A. Choquette-Choo,
Matthew Jagielski, Jamie Hayes, Abhradeep Guha Thakurta, Adam Smith, Andreas Terzis
ABSTRACT
We propose a simple heuristic privacy analysis of noisy clipped stochastic gradient descent (DP-SGD) the setting where only the last iterate is released and the in- termediate iterates remain hidden. Namely, our heuristic assumes a linear structure for the model.
We show experimentally that our heuristic predictive of the outcome of privacy auditing applicd to various training procedures. Thus it can be used prior to training as a rough estimate of the final privacy leakage. We also probe the limitations our heuristic by providing some artificial counterexamples where it underestimates the privacy leakage.
The standard composition- based privacy analysis of DP-SGD effectively assumes that the adversary has access to all intermediate iterates, which is often unrealistic. However, this analysis remains the state of the art in practice. While our heuristic does not replace a rigorous privacy analysis, illustrates the large gap between the best theoretical upper bounds and the privacy auditing lower bounds and sets a target for further work to improve the theoretical privacy analyses. We also empirically support our heuristic and show existing privacy auditing attacks are bounded by our heuristic analysis in both vision and language tasks.
INTRODUCTION
Differential privacy (DP) (Dwork et al., 2006) defines a measure of how much private information from the training data leaks through the output an algorithm. The standard differentially private algorithm for deep learning is DP-SGD (Bassily et al., 2014; Abadi et al., 2016), which differs from ordinary stochastic gradient descent in two ways: the gradient cach example is clipped to bound its norm and then Gaussian noise is added at each iteration.
The standard privacy analysis of DP-SGD is based on composition (Bassily et al., 2014; Abadi et al., 2016; Mironov, 2017: Steinke, 2022: Koskela al., 2020). In particular, it applies the setting where the privacy adversary has access to all intermediate iterates of the training procedure. this setting, the analysis is known to be tight (Nast al., 2021; 2023). However, in practice, potential adversaries rarely have access to the intermediate iterates of the training procedure, rather they only have access the final model. Access to the final model can either be through queries to API or via the raw model weights. The key question motivating our work is the following.
Is it possible to obtain sharper privacy guarantees for DP-SGD when the adversary only has access to the final model, rather than all intermediate iterates?
1.1 BACKGROUND & RELATED WORK
The question above has been studied from two angles: Theoretical upper bounds, and privacy auditing lower bounds. Our goal is to shed light on this question from third angle via principled heuristies.
'denotes equal contribution. Google DeepMind. {steinke, srxzr, arunganesh, bballe, echoquette, jagielski jamhay, athakurta, adamdsmi th, aterzia interziseet googg com. https://arxiv..rg/// 22000.24110000000000 06186

---

Published as a conference paper at ICLR 2025
A handful of theoretical analyses (Feldman et al., 2018; Chourasia et al., 2021; Ye & Shokri, 2022; Altschuler & Talwar, 2022; Bok et al., 2024) have shown that asymptotically the privacy guarantee of the last iterate of DP-SGD can be far better than the standard composition based analysis that applies to releasing all iterates. In particular, as the number of iterations increases, these analyses give a privacy guarantee that converges to a constant (depending on the loss function and the scale of the noise), whereas the standard composition-basee analysis would give a privacy guarantee that increases forever. Unfortunately, these theoretical analyses are only applicable under strong assumptions on the loss function, such as (strong) convexity and smoothness. We lack an understanding of how well they reflect the "real" privacy leakage.
Privacy auditing (Jagielski et al., 2020: Ding et al., 2018; Bichsel et al., 2018: Nast et al., 2021; 2023;
Steinke et al., 2023; Tramer et al., 2022; canella-Béguelle et al., 2022) complements theoretical analysis by giving empirical lower bounds on the privacy leakage. Privacy auditing works by performing a membership inference attack (Shokri et al., 2017: Homer et al., 2008; Sankararaman et al., 2009; Dwork et al., 2015). That is, it constructs neighbouring inputs and demonstrates that the corresponding output distributions can be distinguished well enough to imply a lower bound on the differential privacy parameters. In practice, the theoretical privacy analysis may give uncomfortably large values for the privacy leakage (e.g., E > 10); in this case, privacy auditing may be used as evidence that the "real" privacy leakage lower. There are settings where the theoretical analysis is matched by auditing, such as when all intermediate results are released (Nasr et al., 2021; 2023). However, despite significant work on privacy auditing and membership inference (Carlini et al., 2022; Bertran et al., 2024; Wen et al., 2023; Leino& & Fredrikson, 2020; Sablayrolles et al., 2019; Zarifzadeh al., 2023), a large gap remains between the theoretical upper bounds and the auditing lower bounds (Andrew et al., 2023; Nasr et al., 2023; Cebere et al., 2024; Annamalai & De Cristofaro, 2024) when only the final parameters are released. This observed gap is the starting point for our work.
1.2 OUR CONTRIBUTIONS
We propose a heuristic privacy analysis of DP-SGD in the setting where only the final iterate is released. The heuristic E is always lower than the standard theoretical analysis. Our experiments demonstrate that this heuristic analysis consistently provides an upper bound on the privacy leakage measured by privacy auditing tools in realistic deep learning settings.
Our heuristic analysis corresponds loss functions are linear. This case is simple enough to allow for an exact privacy analysis whose parameters can be computed numerically (Theorem 1). Our consideration of linear losses is built on the observation that current auditing techniques achieve the highest values when the gradients of the canaries- that is, the examples that are included or excluded to test the privacy Icakage- - are constant across iterations and independent from the gradients of the other examples. This is definitely the case for linear losses; the linear assumption thus allows us to capture the setting where current attacks are most effective. Linear loss functions are also known to be the worst case for the non-subsampled (i.e., full batch) case; see Appendix B. Assuming linearity is unnatural from an optimization perspective, as there is no minimizer. But, from privacy perspective, we show that it captures the state of the art.
worst-case theoretical analysis under the assumption that the
We also probe the limitations of our heuristic and give some artificial countercxamples where it underestimates empirical privacy leakage. One class of counterexamples exploits the presence of a regularizer. Roughly, the regularizer partially zeros out the noise that is added for privacy. However, the regularizer also partially zeros out the signal of the canary gradient. These two effects are almost balanced, which makes the counterexample very delicate. In second class of counterexamples, the data is carefully engineered so that the final iterate effectively encodes the entire trajectory, in which case there is no difference between releasing the last iterate and all iterates.
Implications: Heuristics cannot replace rigorous theoretical analyses. However, our heuristic can serve a target for future improvements to both privacy auditing as well as theoretical analysis. For privacy auditing, matching or exceeding our heuristic is a more reachable goal than matching the theoretical upper bounds, although our experimental results show that even this would require new attacks. When theoretical analyses fail to match our heuristic, we should identify why there is a gap, which builds intuition and could point towards further improvements.
Given that privacy auditing is computationally intensive and difficult to perform correctly (Aerni et al., 2024), we believe that our heuristic can also be valuable in practice. In particular, our heuristic
2

---

Published as a conference paper at ICLR 2025
can be used prior to training (e.g., during hyperparameter selection) to predict the outcome of privacy auditing when applied to the final model. (This is a similar use case to scaling laws.)
2 LINEARIZED HEURISTIC PRIVACY ANALYSIS
Theorem presents our heuristic differen- tial privacy analysis of DP-SGD (which we present in Algorithm 1 for completeness; note that include a regularizer r whose gradient is not clipped, because it does not depend on the private data x). We con- sider Poisson subsampled minibatches and add/remove neighbours, as is standard the differential privacy literature.
Algorithm Noisy Clipped Stochastic Gradient De- scent (DP-SGD) (Bassily et al., 2014; Abadi al., 2016)
function DP-SGD(X E X T' E N, E 1 (0, 00), σ E (0, oo). Rd X R, r R R) Initialize model m. E R
for 1.. do
Sample minibatch B, S [m]] including each ele- ment independently with probability q. Compute gradients of the loss V vm ((m,-1,40 for all E B, and of the regularizer
Our analysis takes the form of conditional privacy guarantee. Namely, under the as- sumption that the loss and regularizer are linear, obtain fully rigorous differen- tial privacy guarantee. The heuristic is to apply this guarantee to loss functions that are not linear (such as those that arise deep learning applications). Our thesis is that, in most cases, the conclusion of the theorem still good approximation, even when the assumption does not hold.
V m, mm,.17(mm (mm_r((mmi))
Clip loss gradients: clip (Vm_,e(mm-u
Vm,- f(m, 1.21()
max [1.]] V m, f 2]
Sample noise & + -N((00²1a))
Update
(EEe, cli(( ((m,1,
m, m 11-1--1111 71
+ ?
Recall that function f Rd -> I. linear if there exist E Fd and / E R such that {(m) = (a,, m) + 3 for all m. Theorem (Privacy of DP-SGD for linear losses). Let x. T,
end for
if last iterate only then return mr else if return mo m M1-11, my
then
E, be as in Algo- rithm 1. Assume r and E(,,x), for every E X, are linear.
end if end function
Letting
P Binomial(T, +0 and Q= DP-SGD with last.iterate.onie satisfee (e, -iifferretti privacy with 2 0 arbitrary and
(1)
8= = 6T o == max (e.
(2)
Here, Her denotes the e -ivee--eeii-dieeenneee H.- Q) : P(S) CQQ()).
Equation 2 gives value of the privacy failure probability parameter 8. But it is more natural to work with the privacy loss bound parameter E, which can be computed by inverting the formula:
a.q (6) = min(= 2 0 8T. (E) S 8).
(3)
Both 8T. (E) and ( (Google, 2020). We also provide a self-contained & efficient method for computing them in Appendix A. The proof of Theorem is deferred to Appendix A, but we sketch the main ideas: Under the linearity assumption, the output of DP-SGD is just sum of the gradients and noises. We can reduce to dimension d = 1, since the only relevant direction is that of the gradient of the canary² (which is constant). We can also ignore the gradients of the other examples. Thus, by rescaling, the worst case pair of output distributions
(5) can be computed using existing open-source source DP accounting libraries
be represented as in Equation 1. Namely, Q Σi= - & is simply the noise AN o2) summed over T iterations; this corresponds to the case where the canary is
Note that the regularizer optional as can be set to zero. include convenience later.
The canary refers to the individual datapoint that is added removed between neighboring datasets. This terminology is used in the privacy auditing/atacks literature inspired on the expression "canary in cnalmine."
3

---

Published as a conference paper at ICLR 2025
10
Houristic Standard
10
12
Standard
10'
10-
T.
Heuristic
Standard
Full
100
10a
10a
102
10P
10
10a
100
10*
100
100
100
10'
10
1/q 25/
1/g
(with q= 0.01 and a= 0.5)
(a) Keep Tp and To² constant.
(b) Keep Standard DP constant.
(c) Keep p and constant.
Comparison of our heuristic to baselines in various parameter regimes, Horizontal axis is the number of iterations T and the vertical axis is such that we have (e, 10-9)-DP.
Figure 1:
excluded. When the canary is included, it is sampled with probability in each iteration and thus the total number times it is sampled over T iterations (inomial(T.q)) Thus is the sum of the contributions of the canary and the noise. Finally the definition of differential privacy lets compute e and & from this pair of distributions. Tightness follows from the fact that there exists a loss function and pair of inputs such that the corresponding outputs of DP-SGD matches the pair P and Q
2.1 BASELINES
In addition privacy auditing, we compare our heuristic two different baselines in Figure 1. The first is the standard, composition-based analysis. We use the open-source library from Google (Google, 2020), which computes tight DP guarantee for DP-SGD with inteineee entermedian att.iteertettteeeeee..eeaeeeeeet Because DP-SGD with intermedi adiatteetteraee
gives the adversary more information than with last iterate only, this will always give at least large estimate for as heuristic.
We also consider approximating DP-SGD by full batch DP-GD. That is, set q = I and rescale the learning rate 77 and noise multiplier keep the expected step and privacy noise variance constant:
DP-SGD(x, T, ~ DP-SGD(x, T, 9, o/..//... f.r).
(4)
batch sing, itterations, epechs
batch size iterations, epochs
The latter algorithm is full batch DP-GD since at each step it includes each data point in the batch with probability 1. Since full batch DP-GD does not rely privacy amplification by subsampling, is much easier to analyze its privacy guarantees, Interestingly, there no difference between full batch DP-GD with last.iterate eentte.ont e_only and with inteineede ate ate-ateeeeeeee www.iittttese.. see Appendix B. Full batch DP-GD generally has better privacy guarantees than the corresponding minibatch DP-SGD and this baseline usually (but not always) gives smaller values for the privacy leakage than heuristic. In practice, full batch DP-GD too computationally expensive to run. But we can use it as an idealized comparison point for the privacy analysis.
EMPIRICAL EVALUATION VIA PRIVACY AUDITING
We study how our heuristic compares the empirical privacy auditing results in well studied settings. We focus on image classification (CIFAR-10), as this is well-studied setting for privacy auditing of DP-SGD (Jagielski al., 2020; Nasr et al., 2021; 2023; Tramer et al., 2022: Steinke al., 2023; Cebere et al., 2024). In Section 3.2 we extend the experiments to language models and show similar results.
3.1 IMAGE CLASSIFICATION EXPERIMENTS
We follow the construction of Nasr et al. (2021) where we have 3 entities, adversarial crafter, model trainer, and distinguisher. In this paper, we assume the distinguisher only has access to the final iteration of the model parameters. We use the CIFAR10 dataset (Alex, 2009) with a NeteResNet model (Zagoruyko
Setup:
Komodakis, 2016) unless otherwise specified; in particular, we follow the training setup of De et al. (2022), where train and audit model with 79% test accuracy and,
4

---

Published as a conference paper at ICLR 2025
00-001 Standard (a-1) 111g000111)
(o=2.1.qm0.0B) Standard (ow2.1 (.02..8
Empirical
Empirical
X
10a
10
10'
Number steps
Number of steps
(a) 0.01
(b) g 0.08
Figure 2: Black-box gradient space attacks fail to achieve tight auditing when other data points are sampled from the data distribution. Heuristic and standard bounds diverge from empirical results, indicating the attack's 's ineffectiveness. This contrasts with previous work which tightly auditing with access intermediate updates.
Standard
-%6 Empirical
Heuristic
-+- Standard
Empiriaal
10P
10a
10a
Number of steps
Number of steps
(a) g = 0.01
(b) g = 0.1
Figure 3: For gradient space attacks with adversarial datasets, the empirical epsilon (c) closely tracks the final epsilon except for at small step counts, where distinguishing is more challenging. This is evident at both subsampling probability values we study (q 0.01 and g 0.1).
using the standard analysis, (s 8, 10 SJ--S--DP For each experiment we trained 512 CIFARIO models with and without the canary (1024 total). To compute the empirical lower bounds we use the PLD approach with Clopper- Pearson confidence intervals used by Nasr et al. (2023). Here assume the adversary knows the sampling rate and the number of iterations and is only estimating the noise multiplier used in DP-SGD, from which the reported privacy parameters (s and 5) are derived.
We implement state-of-thed of-tt--art attacks from prior work (Nasr et al., 2021; 2023). These attacks heavily rely on the intermediate steps and, result, do achieve tight results. In the next section, design specific attacks for our heuristic privacy analysis approach to further understand its limitations and potential vulnerabilities.
The most powerful attacks in prior work are gradient space attacks where the adversary injects malicious gradient directly into the training process, rather than an example; prior work has shown that this attack can produce tight lower bounds, independent of the dataset and model used for training (Nasr al., 2023). However, these previous attacks require access to all intermediate training steps to achieve tight results. Here, use canary gradients in two settings: one where the other data points are non-adversarial and sampled from the real training data, and another where the other data points are designed to have very small gradients (+s 0). This last setting was shown by (Nasr et al., 2021) to result tighter auditing. In all attacks, we assume the distinguisher has access all adversarial gradient vectors. For malicious gradients, where gradient vectors consist of zeros in but single index. both cases, the distinguishing test measures the dot product of the final model checkpoint and the gradient canary.
Gradient Space Attack:
Dirac gradient canaries,
5

---

Published as a conference paper at ICLR 2025
8-
7-
0
6
5-
5-
Heuristic
11
4-
-
Standard
Empirical
Eat
3-
3
2-
Heurittic
2-
Standard
Empirical
1
0
10
102
10a
10
10a
10
Number steps
Number of steps
(a) All zero gradient inputs
(b) CIFARIO Dataset
Figure 4: Input space attacks show promising results with both natural and blank image settings, although blank images have higher attack success. These input space attacks achieve tighter results than gradient space attacks in the natural data setting, in contrast to findings from prior work. Figure 2 summarizes the results for the non-adversarial data setting, with other examples sampled from the true training data. In this experiment, we fix noise magnitude and subsampling probability, and run for various numbers of training steps. While prior work has shown tight auditing in this setting, we find an adversary without access to intermediate updates obtains much weaker attacks. Indeed, auditing with this strong attack results even in much lower values than the heuristic outputs.
Our other setting assumes the other data points maliciously chosen. We construct an adversarial "dataset" of m + 1 gradients, m of which are zero, and one gradient is constant (with norm equal to the clipping norm), applying gradients directly rather than using any examples. As this experiment does not require computing gradients, it is very cheap to run more trials, so we run this procedure N 100, 000 times with the gradient canary, and N times without it, and compute an empirical estimate for with these values. We plot the results of this experiment in Figure 3 together with the & output by the theoretical analysis and the heuristic, fixing the subsampling probability and varying the number of update steps. We adjust the noise parameter ensure the standard theoretical analysis produces a fixed E bound. The empirical measured E is close to the hcuristic E except for when training with very small step counts: we expect this looseness to be the result of statistical effects, as lower step counts have higher relative variance at a fixed number of trials.
In practice, adversaries typically cannot insert malicious gradients freely in training steps. Therefore, we also study cases where the adversary is limited to inserting malicious inputs into the training set. Label flip attacks are one of the most successful approaches used to audit DP machine learning models in prior work (Nasr et al., 2023; Steinke et al., 2023). For input space attacks, we use the loss of the malicious input as a distinguisher. Similar our gradient space attacks, we consider two settings for input space attacks: one where other data points are correctly sampled from the dataset, and another where the other data points are blank images.
Input Space Attack:
Figure 4 summarizes the results for this setting. Compared to Figure 2, input space attacks achieve tighter results than gradient space attacks. This finding in stark contrast to prior work. The reason is that input space attacks do not rely intermediate iterates, so they transfer well to our setting.
In all the cases discussed so far, the empirical results for both gradient and input attacks fall below the heuristic analysis and do not violate the upper bounds based on the underlying assumptions. This suggests that the heuristic might serve as a good indicator for assessing potential vulnerabilities. However, in the next section, we delve into specific attack scenarios that exploit the assumptions used in the heuristic analysis to create edge cases where the heuristic bounds are indeed violated.
3.2 LANGUAGE MODEL EXPERIMENTS
While our main results focus on image classification models, our findings extend to other modalities. We also explore fine-tuning language models with differential privacy, specifically Gemma 2 (Team et al., 2024) on the PersonaChat dataset (Zhang et al., 2018). Given several works on auditing differential private image classification works, previous research on images investigated designing optimal canaries to improve empirical auditing in image classification tasks. However, it is unclear how to design such examples for modern language models.

---

the Published as a conference paper at ICLR 2025
Table 1: Evaluation of empirical auditing for DP finetuning of Gemma 2 PersonaChat varying
batch size
Batch size
Heuristic E
Standard e
Perplexity
Empirical
2048
6.0
8
24.3
2.1
1024
6.1
14
24.2
2.1
512
6.0
26
24.8
2.0
Interestingly, we observed that Gemma tokenizer contains many tokens that are not present in the PersonaChat dataset. In this work. utilize these tokens as differing examples, leaving the design of optimal canaries for language models to future research. Table summarizes the results for the language model setting (cf. Table 2 for the image classification setting). We much difference between different modality and our heuristic approach can be a good predictive of the empirical privacy bounds. Additional details about the experiments can be found Appendix D.
that there is not
COUNTEREXAMPLES
We now test the limits of our heuristic by constructing construct inputs to DP-SGD with last_i terate.on such that the true privacy loss exceeds the bound given by our heuristic. While we do not expect the contrived structures of these examples to manifest in realistic learning settings, they highlight the difficulties of formalizing settings where the heuristic gives provable upper bound on the privacy loss.
artificial counterexamples. That is,
4.1 WARMUP: ZEROING OUT THE MODEL WEIGHTS
We begin by noting the counterintuitive fact that our heuristic TT.q, (6) is not always monotone in the number of steps T when the other parameters a, 5 are kept constant. This is shown in Figure Ic. More steps means there is both more noise and more signal from the gradients; these effects partially cancel out, but the net effect can be non-monotone.
We regularizer r(m) |m||// | 2n that v)- Vmr(m) model from the previous step, i.e., the update of DP-SGD (Algorithm 1) becomes
This regularizer
m m1-111
Σ clip Ce ((m;-1, x;)) + V Vm ((m,-)) + & ieB
(5)
= Σ clip (Vm, ((mm-1 + Ex.
(6)
iEB
This means that the last iterate mr effectively the result of only single iteration of DP-SGD. In particular, it will have a privacy guarantee corresponding to one iteration. Combining this regularizer with linear loss and setting of the parameters 7,, q, ar, ō such that the privacy loss is non-monotone - i.e., g..q.o (6) < g. (6) yields a counterexample.
In light of this counterexample, in the next subsection, benchmark counterexample against sweeping over smaller values T'. Le.,, we consider max,<7 (6) instead of simply oT
4.2 LINEAR Loss + QUADRATIC REGULARIZER
Consider running DP-SGD in one dimension (i.e., 1) with a linear loss (mm.)) mr for the canary and quadratic regularizer r(m) = amm? where a E [0, 1] and E [-1, 1] and we use learning rate 7) With sampling probability q, after T iterations the privacy guarantee is equivalent to distinguishing Q == (O, Ø2) and P = NN - (ernoull)) a²).
where 32 = 2 (1
When a = 0, this retrieves linear losses. When a = 1, this corresponds to distinguishing (0,0 a²) and / BBernoull))))) x?) equivalently, to distinguishing linear losses after T iteration. If we maximize our heuristic over the number of iterations < T, then our heuristic is tight for the extremes 10.

---

Published as a conference paper at ICLR 2025
for 1/2 heuristic
for
1/2 heuristic
0.95
0.97
0.87
0.78
0:37
1.0
0.95
0.06
0:78
0.82
07
0.94
1:01
0.87
0.73
0.82
0.88
0.90
0.96
0.84
0.74
88
0.84
0.72
0.83
1.01
0.94
0.82
8-
0.65
0.75
0.91
1.02
0.9
0.8
16
0:45
0.5.
0.05
0.83
0.95
0.8
16
0:4b
0.98
0.74
0.99
0.00
8:/8
0.32
0.38
0.98
0.8
32
0.81
0.09
0.67
0.8
0.52
0.89
0:79
1/2
1/4
1/8
1/16
1/32
1/64
1/2
1/4
1/8
1/16
1/32
1/64
(a) One iteration of DP-SGD satisfies (1, (),10-")-DP.
(b) One iteration of DP-SGD satisfies 10-
Figure 5: Ratio of upper bound for quadratic loss with 0.5 divided by maximum of i iterations on a linear loss. In Figure 5a (resp. Figure 5b), for each choice of is set so I iteration of DP-SGD satisfies (1, 10 1--P (resp (2, 10 -DP).
A natural question is whether the worst-case privacy guarantee on this quadratic is always given by {0, 1}. Perhaps surprisingly, the answer no: we found that for T = = 0.1, 1, instead DP-SGD is (2.182, 10-6)-DP. However, for a' = 0.5 instead the quadratic loss does not satisfy (c, 10-6) -DP for & < 2.274.
DP-SGD is (2.222, 10 10-P For
However, this violation is small, which suggests our heuristic is still reasonable for this class of examples. To validate this, we consider a set of values for the tuple (T.9. For each setting of TTqqqo, a, we compute max,sT o with quadratic regularizer example with a = 1/2 in the same setting. Since the support of the random variable Everry (1 - (Brrnullll(lg) has size 2 for = 1/2, computing exact for even moderate T is computationally intensive. Instead, let X be the random variable equal to Eierr (1 - a) Bernoulli())) except we round up values in the support which are less than .0005 up to .0005, and then round each value in the support up to the nearest integer power of 1.05. We then compute an exact e for distingushing. (0, 6²) (X,, G²). By Lemma 4.5 of Choquette-Choo et al. (2024), we know that distinguishing (N00 a2) vs. NO (EE a) - Bernoulli()). σ²) is no harder than distingushing (0, 6²) vs MXX, G²), and since we increase the values in the support by no more than 1.05 multiplicatively, we expect that our rounding does not increase by more than 1.05 multiplicatively.
(0) at 8 10-6. We then compute for the linear loss
In Figure 5, we plot the ratio of at 8 = 10 10-6 for distingushing between (0, G²) and N x2) divided by the maximum over i E [T] of and N N(Binomial(i, q), 2 We sweep over T and q, and for each g In Figure 5a (resp. Figure 5b) we set such that distinguishing (0, o²) from M(BBeroulli(g), o²) satisfies (1, 10 DD (resp. (2, 10-10-6. DDDP). In the majority of settings, the linear loss heuristic provides a larger e than the quadratic with a = 1/2, and even when the quadratic provides a larger e, the violation small (< 3%). This is evidence that our heuristic is still good approximation for many convex losses.
10-6 6 for distinguishing between A0 in?)
4.3 PATHOLOGICAL EXAMPLE
If we allow the regularizer to be arbitrary - in particular, not even requiring continuity then the gradient can also be arbitrary. This flexibility allows us to construct a counterexample such that the standard composition- based analysis of DP-SGD with inte intermediate. iterattessteetttsseeeeeeeeeeetse is close to tight. Specifically, choose the regularizer so that the update m' = m m does the following: I is large constant. We chose the loss so that, for our canary #1. we have Vm 21 (1,0,0, 0, ... 0) and, for all other examples x;
m' and, for i E Id 1]. m4+1 v m, Here
3, ... ,n)), have V vm((m,x,) 0. Then the last iterate is
mr (Ar Er,1, A v En, v2 Ar Er-221 2.1 P 1,2 ET, (7)
8

---

Published as a conference paper at ICLR 2025
where A f- Bernoullipp) indicates whether not the canary sampled in the t-th iteration and St. denotes the i-th coordinate of the noise & added the f-th step. Essentially, the last iterate my contains the history of all the iterates in its coordinates. Namely, the i-th coordinate of my gives scaled noisy approximation to Ar-
jo-s ji- ~M N (A 11-1-1 1 w-
- mT, = Ar- +
Σ ==
+
Er
(8)
As + 0O, the variance converges o², In other words, if large, from the final iterate, we can obtain (A,, o²) for all i. This makes the standard composition- based analysis of DP-SGD tight.
Concurrent work (Annamalai, 2024) presents counterexample that yields a similar conclusion, although their construction is quite different.
4.4 MALICIOUS DATASET ATTACK
The examples above rely the regularizer having large unclipped gradients. We now construct counterexample without a regularizer, instead using other examples to amplify the canary signal.
Our heuristic assumes the adversary does not have access to the intermediate iterations and that the model is linear. However, we can design nonlinear model and specific training data to directly challenge this assumption. The attack strategy is to use the model's parameters as sort of noisy storage, saving all iterations within them. Then with access only to the final model, an adversary can still examine the parameters, extract the intermediate steps, and break the assumption. Our construction introduces a data point that changes its gradient based on the number of past iterations, making it easy to identify if the point present data points are maliciously selected to ensure the noise added during training doesn't 't impact the information stored in the model's parameters. We defer the full details of the attack Appendix C.
given iteration of training. The rest of the
Figure summarizes the results. As illustrated the figure, this attack achieves an auditing lower bound matching the standard DP-SGD analysis even in the last iitierttteee e.only setting, As result, the attack exceeds our heuristic. However, this is highly artificial example and it is unlikely reflect real-world scenarios.
8
6
||
Heuristic
Standard
Standard
000
Empirical
.00 Empirical
Number of steps
Number of steps
(a) = 0.01
(b) 0.1
Figure 6: In this adversarial example, the attack encodes all training steps within the final model parameters, thereby violating the specific assumptions used to justify our heuristic analysis.
DISCUSSION & IMPLICATIONS
Both theoretical analysis and privacy auditing valuable for understanding privacy leakage in machine learning, but both have limitations. Theoretical analysis is inherently conservative, while auditing procedures evaluate only specific attacks, and may thus underrepresent the privacy leakage.

---

Published as a conference paper at ICLR 2025
Table 2: Previous works showed that large batch sizes achieve high performing models (De et al., 2022). Using our heuristic analysis it is possible to achieve similar performance for smaller batch sizes.
Batch size
Heuristic
Standard
Accuracy
Empirical E
4096
6.34
8
79.5%
1.7
512
7.0
12
79.9%
1.8
256
6.7
14
78.2%
1.6
Our heuristic approach empirically upper bounds the privacy leakage in practical scenarios (Section 3). Although counter-example with higher leakage exist (Section 4), these are highly contrived and not representative of real-world models.
The current best practice for differentially private training is to use high sub-sampling rates (i.e., large batch sizes) (De al., 2022; Ponomareva al., 2023). Our experimental results (Tables 1 and 2) challenge this best practice. We find that batch size does not significantly affect either the model performance or the privacy as measured by the heuristic epsilon or privacy auditing, but it does affect the standard privacy analysis significantly. This indicates that the larger batch sizes may not be necessary for better privacy.
The current trend in training large models is to gather very large datasets and use a small number of epochs. Moreover, as models get larger using large batch sizes becomes impractical as it slows down in the training pipeline. This is the setting where the gap between the standard analysis and our heuristic large (see Figure lb). Furthermore, training large models too costly to perform proper empirical privacy evaluations.
Another trend is to report increasingly large differential privacy epsilon values based on the standard privacy analysis. It is hard to justify such values. Our heuristic analysis, along with empirical privacy evaluation, allows for more grounded claims in such settings. Of course, our heuristic analysis relies on linearity assumptions, but to exceed the bounds of our analysis, adversary would need to break these linearity assumptions in a practical setting. This is currently very difficult with existing attacks on deep learning models.
CONCLUSION
A major drawback of differentially private machine learning is the gap between theoretical and practical threat models. Theoretical analyses often assume the adversary has access to every training iteration, while in practice, training typically occurs in closed environments, limiting adversaries to the final model. This disconnect, in combination with our limited understanding of deep learning loss landscapes, slowed down progress in theoretical privacy analysis of private training of deep learning models. As result many studies supplement theoretical privacy bounds with empirical leakage evaluations justify their choice of epsilon, this entails high computational costs and requires careful attack optimizations, making them both expensive and error-prone.
Our work introduces novel heuristic analysis for DP-SGD that focuses on the privacy implications of releasing only the final model iterate. This approach is based on the empirical observation that linear loss functions accurately model the effectiveness of state of the art membership inference attacks. Our heuristic offers a practical and computationally efficient way estimate privacy leakage to complement privacy auditing and the standard composition based analysis.
Our heuristic avoids the cost of empirical privacy evaluations, which could be useful, e.g., for selecting hyperparameters a priori. More importantly, the scientific value our heuristic is that it sets a target for further progress. Privacy auditing work should aim to exceed our heuristic, while theoretical work should aim to match it.
We acknowledge the limitations of our heuristic with specific counterexamples that demonstrate the heuristic underestimates the true leakage in some contrived examples. However, we show that in practical scenarios, our heuristic provides upper bound on all existing empirical attacks.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pp. 308-318, 2016. URL https:// arxiv. org/vvorrg/aae wtwpg///////aa. aaaaabbs/1110 00133301333....
00133.
Michael Aerni, Jie Zhang, and Florian Tramèr. Evaluations of machine learning privacy defenses /
are misleading. arXiv preprint arXiv:2404.17399, 2024. URL 2404. 17399.
Krizhevsky Alex. Learning multiple layers of features from tiny images. arronto..dd/kr12222 http://eeeeeeteeeeeennnnaeatrree -00 pdf, 2009.
Jason Altschuler and Kunal Talwar. Privacy of noisy stochastic gradient descent: More iterations
without more privacy loss. Advances in Neural Information Processing Systems, 35:3788-3800,
2022. URL pnttps://aree wtt..aas///..11111../ 2tt.bb///2255111....
org//oraass... abs
Galen Andrew, Peter Kairouz, Sewoong Oh, Alina Oprea, H Brendan McMahan, and Vinith Suriyakumar. One-shot empirical privacy estimation for federated learning. arXiv preprint arXiv:2302.03308, 2023. URL https: arxiv. org/ abs 22022 03098.
Meenatchi Sundaram Muthu Selva Annamalai. It's our loss: No privacy amplification for hidden state dp-sgd with non-convex loss. arXiv preprint arXiv:2407.06496, 2024. URL https:
// //arxivv. www.or//aaba... abs/ /200 06496.
Meenatchi Sundaram Muthu Selva Annamalai and Emiliano De Cristofaro. Nearly tight black-box auditing of differentially private machine learning. arXiv preprint arXiv:2405. 14106, 2024.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight eπror bounds. In 2014 IEEE 55th annual symposium foundations of computer science, pp. 464-473 IEEE, 2014. URL https: / arxiv. owg/abgg//.....ooo /4005. 7085.
Martin Bertran, Shuai Tang, Aaron Roth, Michael Kearns, Jamic H Morgenstern, and Steven Z Wu. Scalable membership inference attacks via quantile regression. Advances in Neural Information Processing Systems, 36, 2024. URL https: /awxivvvvv/////////i//aa.////aav org. abs 220//330.0000 03694.
Benjamin Bichsel, Timon Gehr, Dana Drachster-Cohent Petar Tsankov, and Martin Vechev. Dp-finder: Finding differential privacy violations by sampling and optimization. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 508-524, 2018.
Jinho Bok, Weijie Su, and Jason M Altschuler. Shifted interpolation for differential privacy. arXiv preprint arXiv:2403.0022 2024. URL /tt.:ttpp///aaavooott/////////// 2403, 00278.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897-1914. IEEE, 2022. URL https: / arxiv org. http://///////// 21577.377.... 03570.
Tudor Cebere, Aurélien Bellet, and Nicolas Papernot. Tighter privacy auditing of dp-sgd in the hidden state threat model. arXiv preprint arXiv:2405. 14457, 2024. htRttttts://aaa org/ abs/
2405. 14457.
Christopher A. Choquette-Choo, Arun Ganesh, Thomas Steinke, and Abhradeep Thakurta. Privacy amplification for matrix mechanisms, 2024.
Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems, 34:14771-14781, 2021. URL https: /awxiv.vvvv . org/ abs/ 2202. 05855.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. arXiv preprint 2XX1:22044136500 2022.
11

---

Published as a conference paper at ICLR 2025
Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang, and Daniel Kifer. Detecting violations of differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 475-489, 2018.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint arXiv:1905.02333, 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 365-284. Springer, 2006. URL https:
/ www. iacr. org/ archiveecciieeeeeeeeeee /ttp///c//0/////// 387 602202222 66 387 078766666222 pdfff
Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust trace- ability from trace amounts. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 650-669. IEEE, 2015.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018. URL https: httpss//axxvvvorrg. abs/18b8 06651.
Google. Differential privacy accounting, 2020. https://github. com/google differential wttpereentill-pivccyyeeeeee prwiacyytrreeeeeeeeeeeppeeeeeeee www.a//pyttoo//ppacoooooooo
Nils Homer, Szaboles Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muchling, John V Pearson, Dietrich A Stephan, Stanley F Nelson, and David W Craig. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. PLoS genetics, 4()):1000166) 2008
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 33: 19205-22216, 2020.
Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statistics, pp. 2560-2569. PMLR, 2020. URL https:/ /ate:///arxiie /arpaaxxvvvvr..//// org abs / 9066 03049.
Klas Leino and Matt Fredrikson. Stolen memories: Leveraging model memorization for calibrated (White-Box) membership inference. In 29th USENIX security symposium (USENIX Security 20),
pp. 1605-1622, 2020. URL https::tpt........t.. : / / a axxi v. orrg abs / 6906 11798.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263-275. IEEE, 2017. URL https:://rcxv..rrg///ttttt/ /wtp./ 07476.
Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adversary instantiation: Lower bounds for differentially private machine learning. In 202/ IEEE Symposium security and privacy (SP), pp. 866-882. IEEE, 2021. URL https: wrwii.iiiii...i.m www.wiiiiia.aaaa.. abs/ 2101 04535.
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, arXiv preprint arXiv:2302.07900 2023. URL https: http://axxvvvrrree/ee bargg//bssa abs/ 2302. 07956.
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. Journal of Artificial Intelligence Research, 77:1113-1200 2023. URL https: /arxiv/rivvvv//vv///////ee. owgg/bas//////.. /2eee/2333.. 00654.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou. White- box vs black-box: Bayes optimal strategies for membership inference. In International Conference Machine Learning, pp. 5558-5567 PMLR, 2019. URL https: //txxvivvv.////////v///a/////av. www.ii.v...aaaa.eeeeeeee org/ 908 11229.
Sriram Sankararaman, Guillaume Obozinski, Michael I Jordan, and Eran Halperin. Genomic privacy and limits of individual detection in pool. Nature genetics, 41(9):965 2009.
12

---

Published as a conference paper at ICLR 2025
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
Thomas Steinke. Composition differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:22/0.00597, 2022. URL https: /arxivivvvv. wwtpl///ogr/bb///eaeooooo /210 00597.
Thomas Steinke,
Milad Nasr, and Matthew Jagielski. Privacy auditing with one (1) training run. Advances in Neural Information Processing Systems, 36, 2023, URL https::// /ttppv..//rxxxoo///// abs/ abs/2305.. 08846.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXiv preprint arXiv:2403.08299 2024.
Florian Tramer, Andreas Terzis, Thomas Steinke, Shuang Song, Matthew Jagielski, and Nicholas Carlini. Debugging differential privacy: case study for privacy auditing. arXiv preprint arXiv:2202.12211 12219, 2022. URL https:/ aawaaivvvvv... org. http/bb//2200 221./2222222221...
Yuxin Wen, Arpit Bansal, Hamid Kazemi, Eitan Borgnia, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Canary in coalmine; Better membership inference with ensembled adversarial queries. In ICLR, 2023. URL https::/azziii orgg aba// 2210 10750.
Jiayuan Ye and Reza Shokri. Differentially private learning needs hidden state (or much faster convergence). Advances in Neural Information Processing Systems, 35:703-715, 2022. URL https://arxtt ptg/abss////oooooooo/oooooo//oor 2203. 05363.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 17 2016.
Santiago Zanclla-Béguelin Lukas Wutschitz, Shruti Tople, Ahmed Salem, Victor Rühle, Andrew Paverd, Mohammad Naseri, and Boris Köpf. Bayesian estimation of differential privacy. arXiv preprint arXiv:2206.05199 2022.
Sajjad Zarifzadeh, Philippe
Cheng-Jie Marc Liu, and Reza Shokri. Low-cost higer membership inference by boosting relativity. 2023. URL https: //ap/vaaavv./////a///aa/aaaaaaaa wwg.o////aao abs 22122 032
Saizheng Zhang, Emily Dinan, Jack Urbanek, Arthur Szlam, Douwe Kiela, and Jason Weston. Personalizing dialogue agents: have a dog, do you have pets too? In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2204-2213, 2018
A PROOF OF THEOREM
Proof. Let Zx-- be the canary, let D be the dataset with the canary and D' be the dataset without the canary. Since and are linear, wlog we can assume r = 0 and V (mm = for some set of vectors [va}. such that ||v; S 1. We can also assume wlog V; since, if |[ < 1, the final privacy guarantee we show only improves.
We have the following recursion for m,:
Σ v; +5 VEB
& Lid o((0,21aa)
m 17
Unrolling the recursion:
ΣΣ
E~ Noo,Too'la,
m;
mg
[E(T]
13

---

Published as a conference paper at ICLR 2025
By the post-processing property of DP, assume that in addition to the final model my, release my and {B, {x;- f that is we release all examples that were sampled each batch except for the canary. The following f is bijection, computable by an adversary using the released information:
f(mr)
mT
Σ AE(T) (EB
Σ
7
Since f is bijection, distinguishing my sampled using D and D' is equivalent to distinguishing f(my) instead. Now we have ( - To for D', and f(mr) = (O, To + kv; k Binomial q). For any vector orthogonal V,+, by isotropy of the Gaussian distribution the distribution of (f(m)), uj is the same for both D and D' and independent of (f(mr), Vi-), hence distinguishing / (mr) given D and D' is the same distingushing (J(r),, V.+) given D and D'. Finally, the distribution of (f(mr), V.+) is exactly P for D and exactly Q for D'. By post-processing, this gives the theorem.
We can also see that the function 8T.9 is tight (i.e., even if we do not release B, \ {I. }). by considering the 1-dimensional setting, where v; 0 for of i* and V, =-1, 17 m. 0. Then, the distribution of my given D is exactly P, and given D' is exactly Q.
A.1 COMPUTING FROM
Here, we give an efficiently computable expression for the function ( Using P, P,Q as in Theorem 1, let f(y) be the privacy loss for the output y:
P(y)
T
q" -)n cxp(- -1))/1220))
f(y) log
log
Q(y)
k
exp(-1y2 /22
k=n
T
2ky k2
2T )
log
Σ
at 4)*
exp
k
Then for any E, using the fact that S = {y: f(v) 2 2) maximizes P(S) e (SS), we have:
He (P.Q) P((:: f(v) 2 - s()) 2 2))
P(( y f Q(1v y (s)))
Σ k ( 2f Pr 2 f())..
Similarly, S {y: f(y) -e} maximizes Q(S) - e² P(S) have:
PQ. Q(vv: fly) < -=}) - P f(y) < -E})
=Q((v: : & (-())) e² P(1 : S (-(()))))
( 1:
= =Pr[N(0, Top) ) (
(o3 T {-()-)
These expressions be evaluated efficiently. Since f is monotone, it can be inverted via binary search. We can also use binary search to evaluate E as a function Pseudocode for this is provided in the next subsection.
14

---

Published as a conference paper at ICLR 2025
A.2 PSEUDOCODE FOR COMPUTING AND ò VALUES
def fly,n, n, 9, sigma):
"""computes log likelihood ratio of Binomial (n, q) +N (0, sigma "2) over
si0msigma """
3 if q-=1: kmn
return (2xy-n)/ (2*sigmav*2)
5 if q==0: k=0
return
terms [0] x (n+1)
$ terms [k] = log ((n Ychoose k) x q"k
exp / (2ky-k /2 )2))
lognck = # log((n \choose 01)
10
for in range (n):
terms [k] lognek log (n-k) matth.olggy (-q)
(2+y-k) *k/ (2nnvsigmav+2)
in lchoose k+1] in \choose k) (n-k)/ (k+1)
lognck lognck + math. (n-k) - math. log (k+1)
14
assert abs (lognck) <= 1e-9 # log((n Ichoose n))
15
terms [n] asmath.
(2xy-n) an/ (2*nxsigma+*2)
16
# rescale so largest term is max (terms)
return math. log (math, fsum (math, (math.exp (t-at
for in terms))
def finv (eps, q, s
"""computes inverse of f(y) i.e. such that =eps""n
22 if q < and eps <= n math. math. loglp(-q)
23 smallest possible value is f(-inf) = log (1-=) 'n)
so no inverse exists
note q-! implies f(-inf)=-inf so inverse exists return None f() is increasing function of we can use binary search
ymin, ymax = -1, 1
29 while f (ymin, n, sigma) eps:
30
ymin += 2
while (ymax, n, q, sigma) eps:
ymax 2
while True:
y (ymin*ymax) /2
val- = fly, sigma) - eps
if abs (val) < 1e-9:
37
break
elif val > 0:
ymax y
else:
ymin y
return y
44
def taiss_taill (mean, var, threshold):
"""computes P (mean, var) var))=threshhold. m**
return 0, 5*math. erfe (threshold-meent /twata.aagp.ee..ee (2*var)
15

---

Published as a conference paper at ICLR 2025
def binomial saoomial_gaussann dp delta del probability, noise multiplier, eps, sign-0);
"""computes delta corresponding to (eps, delta) -DP of " Binomial (n, q) +N (N, sigma 2) vs N(O, sigma"> 22)
50
n-iterations, geprobability, si
sign=1 computes hockey stick di divergence for Binomial (n, q) +N (0, sigma over N(O, sigma "2),
s sign--i computes hockey stick divergence for NO0, sigma 22) over
Binomial (n, q) (O, sigma"2
sign=0 computes max delta over both cases.
55
56
Note that sigma needs to be multiplied by sqrt (iterations) to match the paper.
if sign != 1 and sign != -1: # return max m
plus aanommal_gaassiine de__deetaaaeeeeeeeeeeeeeeeeeaaed (o (iterations, probability, noise poise_muttiplierr eps, sign-1)
60
delta_minus = binomial aewssiae..__eelttaaeeeeeeeeaaaea
probability,
noise_multiplier, eps, sign=-1)
return m plus, delta_minus) otherwise return delta_sign
finv (sign eps, iterations, probability, noisc_multiplier) if y is None: return 0 $ no inverse, in this case delta=0 sign if probability= or probability=00 # ken or k=0
if probability=11; k iterations
if probability==0; k if sign == 1:
delta_
return gauss tail (k,
math. exp (eps) -gauss_tail hta
if sign == -1: $ delta
return couss_tailll (0, htt.:eatttoosoooiimmmmttiippeeee
+ math.exp ( httala/aiaaatiioooooeeoeeaaataer
terms (iteraatttio)))))
lognck
for in range (iterations):
terms [k] = math. k-math. log (probability)
(iterations-k)
lognck lognck + hun.ssaalllsiioi...eeaotooooooaa
77
Log (k+1)
78
assert abs (lognck) <= 1e-9
terms [iterations] (proaabllltty:::teerrtttom))
gauss_taill (iterations, tttaaaaiiinnenieee..a.ttttlleee. if sign return math. fsum (terms)
(eps) ggauss_taill oo (0t. 82 if sign == -1:
83 return gauss_tail wtw. wwwss_.mttpppllerree222.... - mxth. (eps)
math. fsum (terms)
def iin binomlal__aussiin_.dr (itcrations, probability, noise_muttiplier, delta, sign=0):
16

---

Published as a conference paper at ICLR 2025
computes eps corresponding to (eps, delta) -DP of Ainomia! (n, *N (9, si gma 22 N N0, si sigma *** opsmin, epsmax = 0, 1
88
while binomial gaussian dp_ delta (iteratiion probability,
noise_multipliee epsmax, sign-sign) > delta: epsmax
while Truc:
eps (epsmintepsmax)
val binomial = _at____sssssini___elllllaa (iteration, probability
noisc_multiplier, eps, sign-sign) delta
if abs (val) < 1e-9:
94
return eps
elif val < 0:
epsmax eps
else:
cpsmin cps
B LINEAR WORST CASE FOR FULL BATCH SETTING
It turns out that in the full-batch setting, the worst-case analyses of DP-GD with intermedi ate tterates and with last iterate only are the same. This phenomenon arises because there is subsampling (because q 1 in Algorithm 1) and thus the algorithm is "just" the Gaussian mechanism. Intuitively, DP-GD with int rmedi aeeiiiteiiie eeiiteeteess corresponds to T calls the Gaussian mechanism with noise multiplier while DP-GD with last.iterate.on.e corresponds one call to the Gaussian mechanism with noise multiplier a VT; these equivalent by the properties of the Gaussian distribution.
We can formalize this using the language of Gaussian DP (Dong et al., 2019): DP-GD (Algorithm with q 1) satisfies vT /-DP. (Each iteration satisfies 1/a-GDP and adaptive composition implies the overall guarantee.) This means that the privacy loss is exactly dominated by that of the Gaussian mechanism with noise multiplier a o/VT. Linear losses give an example such that DP-GD with last it witeeateeeee... only has exactly this privacy loss, since the final iterate reveals the sum of all the noisy gradient estimates. The worst-case privacy of DP-GD with intermediar aiteeiaaiiie teeateteeee tes is no worse than that of DP-GD with last_iastttte Last_iterate.only The reverse is also true (by postprocessing).
In more detail: For T iterations of (full- DP-GD on linear losses, if the losses are (wlog) 1 1-Lipschitz and add noise No0 =² 7) to the gradient in every round, distinguishing the last iterate of DP-SGD adjacent databases equivalent distinguishing. NN To²) and ((T, To²). This can be seen as a special case of Theorem for 1, so we do not a give detailed argument here.
If instead we are given every iteration m,, for any I-Lipschitz loss, distinguishing the joint distribu- tions of m; given m,-1 on adjacent databases equivalent to distinguishing N/0 o²) and (111, o²). In turn, distinguishing the distribution of all iterates on adjacent databases is equivalent to distin- guishing NO Ir) and WN1T", of IrIr), where 0" and 17 are the all-zeros and all-ones vectors in RT. Because the Gaussian distribution is isotropic, distinguishing NOOTT _²IT) and N(1 g²IT) is equivalent to distinguishing (x, 12) where x ~ ANO I²Ir) and (x, 12) where A/ Ir). These distributions are (0, (oo)) and (TT,To"), the exact pair of distributions we reduced to for last-iterate analysis of linear losses.
C MALICIOUS DATASET ATTACK DETAILS
Algorithms 2, 3, and summarizes the construction for the attack. The attack assume the model parameters have dimension equal to the number of iterations. It also assumes each data point can reference which iteration of training is currently happening (this be implemented by having
17

---

Published as a conference paper at ICLR 2025
single model parameter which increments in each step, independently of the training examples. without impacting the privacy of the training process). Then we build our two datasets D and D' DU { that all points in dataset D ('repeaters") run Algorithm 3 to compute gradients runs Algorithm 2 to compute its gradient. Our attack relies heavily on
and the canary point DP-SGD's lack of assumptions the data distribution and any specific properties of the model gradients. Algorithm 2, which generates the canary data point, is straightforward. Its goal is to store the model parameters whether it was present in iteration by outputting a gradient that changes only the i-th index of the model parameters by (assuming clipping threshold of 1).
All other data points, the "repeaters", are present in both datasets (D and D'), and have three tasks:
Cancel out any noise added to the model parameters at an index larger than the current iteration. At iteration their gradients for parameters from index i onward will be the same as the current value of the model parameter, scaled by the batch size and the learning rate to ensure this parameter value will be after the update.
Evaluate whether the canary point was present the previous iteration by comparing the model parameter at index i - with threshold, and rewrite the value of that model parameter to large value if the canary was present.
Ensure that all previous decisions not overwritten by noise by continuing rewrite them with a large value based on their previous value.
To achieve all of these goals simultancously, we require that the batch size is large enough that the repeaters updates are not clipped.
Finally Algorithm runs DP-SGD, with repeater points computing gradients with Algorithm 3 and the canary point, sampled with probability computing its gradient using Algorithm 2. In our experiments we run Algorithm 4 100,000 times. And evaluate if the model parameters was from dataset D D' we run hypothesis test on the values of the model parameters. All constants are chosen ensure all objectives of the repeaters are satisfied.
Algorithm 2 Canary data point
1: function ADV(X, i)
2: Initialize a as a zero vector of the same dimension as x
3: Set a, t- 1
Set the i-th component to 1
4: return -a
5: end function
Algorithm 3 Additional data points
Require: model parameters x, iteration number i, batch size N, learning y, previous history threshold (past- last iteration threshold last history amplification value BIG VAI
function REPEATERS(X. N, fpast fast BIG. (AL))
2: h + Xo:
> Parameter "history" up to iteration i, not inclusive Future and current parameters, starting from iteration Remove noise from last iteration By default, zero out entire history
3: f Xcend
4:
f 1-ff((n-a N)
5:
base hietoritor +- Xo.i( N)
6: if (engthhh) > then
7: ho.-1 + BIG VAL/(n .N) (21 [bo 2 tpast 1)
> If an old iteration is large
enough, it was canary iteration, amplify it
8: end
9:
if length(h) > then
10:
h < BIG_VAL//E N) (21 2 huss] - 1) o If the last iteration is large enough,
was canary iteration, so amplify it
11:
end if
h h + base history
Don't zero out canary iterations
13: a - concatenate h,
return -a
15: end function
18

---

Published as a conference paper at ICLR 2025
Algorithm 4 Encoding Attacking
Require: add-diff, whether to add the canary, batch size N, sampling rate learning rate (1))
iteration count/parameter count
1: function RUN_DPScIDaadd-iiff
2: C+1
3: Initialize model 0 of dimension D
4: for 0 to D do
5: Generate uniform random value [0, 1]
6: r 4- repeaters( m, i) |||||
7:
Compute norm
8:
ife 0 then
9:
Normalize t- r/ max(c, C)
10:
end if
Adjusted vector f- x N
12:
Verify condition on
13:
p 5
q and add-diff then
14:
r adv(m, i)
15:
Normalize and update z
16:
end if
17:
Apply Gaussian noise to z Update model m end for
18:
19:
return m
21: end function
D IMPLEMENTATION DETAILS
For image classification model we used De et. al, (De et al., 2022) training approach with different batch sizes. We used Google Cloud A2 A2-megagpu-16 6g machines with 16 Nvidia A 110 40GB GPUs. Overall, we use roughly 60,000 GPU hours for our experiments. To compute the standard theoretical privacy bounds use DP-accuunting library 3, For each experiment trained the model of image classification setting we trained 1000 models with and without the canary (i.e, differing example).
We implemented fine tuning with differential privacy on Gemma 2 (Team et al., 2024) in JAX. The fine tuning is done in FP16. The attack here directly looks at the difference in the embedding table of the model for the tokens used as canaries before and after the finetuning. We trained 128 model with and without carries for language model fine tuning experiments.
For the experiments with different batch sizes, we fixed the training iterations to 60 and epochs for image and text modalities respectively and modified the sub-sampling rates, calculating the noise parameters required to achieve similar privacy guarantee based on our heuristic.
"https:// thub. cttp..com/ooog//////// fferent i /aae///rr///
19


Reviews:
[{"review_id": "tdKSpJGz0s", "reviewer": "Reviewer_PBks", "summary": "The paper introduces a heuristic privacy analysis for DP-SGD when only the final model is released, and intermediate updates are hidden. This heuristic assumes linear loss functions and, when the assumption holds, provides a more accurate estimate of privacy leakage than standard composition-based analyses, which often overestimate privacy loss by assuming adversaries have access to all training iterates. The authors experimentally demonstrate that their heuristic closely predicts the outcomes of privacy auditing tools, serving as a practical upper bound on privacy leakage in deep learning settings (where auditing is usually expensive). They also discuss counterexamples where the heuristic underestimates privacy leakage, highlighting its limitations. By bridging the gap between theoretical upper bounds and empirical lower bounds from privacy auditing, the heuristic sets a more realistic target for both theoretical improvements and practical attacks. It offers a computationally efficient way to estimate privacy leakage, aiding in tasks like hyperparameter selection before training without the overhead of extensive privacy audits.", "questions": "* How does this work relate to other recent results in privacy auditing that perform effective audits under similar threat models? Specifically, could the authors elaborate on the novelty of their approach compared to methods presented in papers [1], [2], and [3], which make assumptions about the adversary and not the loss itself?\n* Could the authors comment on the strength of the linearity assumption compared to other assumptions or heuristics used in privacy auditing? For instance, in [4], an auditing procedure for one-shot auditing is designed under the assumption that the adversary can insert a known random gradient, which can easily be extended to the blacbox setting. How does the linearity assumption compare?\n* Are there practical scenarios or specific types of models where the linearity assumption approximately holds? \n* Theoretical work also addresses this threat model for the non-convex case (see [5]). Is there any connection or similarity between the works?\n\n[1]: https://arxiv.org/pdf/2405.14106\n[2]: https://arxiv.org/pdf/2405.14457\n[3]: https://arxiv.org/pdf/2407.06496\n[4]: https://arxiv.org/pdf/2302.03098\n[5]: https://arxiv.org/pdf/2305.09903", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper presents a new heuristic privacy analysis for DP-SGD when only the final model is released. \n* The heuristic allows practitioners to estimate privacy leakage before training, aiding in hyperparameter selection without the computational cost and complexity of running privacy audits.\n* The heuristic can serve as a benchmark for future improvements in both theoretical privacy analyses and practical attack methods, encouraging the development of stronger privacy attacks against ML models\n* The authors provide a good amount of examples and intuition when the heuristic does not hold", "weaknesses": "* The reliance on linear loss functions is a simplification. This mismatch may limit the applicability of the heuristic to real-world models as a valid upper bound. (see the questions)\n* The paper could position itself within the existing body of work on privacy auditing, particularly recent methods that perform effective audits under similar threat models. A deeper comparison would clarify the novelty and contribution of this work. (see the questions)\n* While formalising the heuristic is helpful, it can be seen as a natural extension of existing observations that independent gradients are optimal for tight auditing when only the last iterate is revealed. The paper may not fundamentally add new knowledge to privacy auditing beyond this formalisation. (see the questions)", "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": "aU4erQsBIp", "reviewer": "Reviewer_SieV", "summary": "This paper tackles a fundamental problem in DP-SGD: the privacy analysis of the last iterate. It is well known that DP-SGD (in the centralized case) makes an artificial assumption that all intermediate iterates are published which can be observed by adversary to ease the privacy analysis through composition. New heuristic auditing methods are presented to approximate the leakage from the last-iterate. Disadvantage and failure cases of proposed methods are discussed.", "questions": "In general, I think there is some interesting results in the paper but more work seems to be needed.\n\n1. Can the author comment or empirically get the truly last-iterate in some practical tasks (it is ok to just run two or three iterations) and then compare it with the estimate from the heuristic auditing proposed? \n\n2. Can the author explain how to generalize the analysis to capture the practical random $v_i$ scenario?\n\n\nminors:\n1. There is overlap in the figures in Fig.1.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well motivated and organized. Interesting examples are presented with good intuitions.", "weaknesses": "My primary concern is with the meaningfulness of the main result in Theorem 1.\n\nIn the proof, the authors appear to use $v_i$ to represent the $i$-th per-sample gradient, assuming $v_i$ is constant. First, I am not aware of any real-world loss function, even in the case of linear regression, that yields or can be framed to yield a constant gradient independent of model weight. Second, in practice, when $v_i$  is treated as a random variable, it is important to note that (a) the variable $v_i$  at different iterations is correlated with $v_j$  , and (b) the distribution of $v_i$ ​  changes when it is derived from a pair of adjacent datasets. Thus, when \n$v_i$  is random, the proof no longer holds, as the divergence cannot simply be reduced to that between the two Gaussian mixtures derived.\n\nThis simplification also leads to non-monotonicity, as discussed by the authors. Although they propose taking the worst-case estimate across all parameter selections, this approach feels somewhat ad hoc. The absence of results demonstrating, at a minimum, the conditions under which the model in Theorem 1 can serve as a provable upper bound for the estimate makes it challenging to evaluate and fully understand this auditing method. \n\nAdditionally, can the authors elaborate on their statement about the justification for focusing on linear losses which stems from the observation that existing auditing techniques achieve the highest epsilon values? The observation itself makes sense as if every time is worst case, the privacy loss seems to be the maximal. But I do not get why this supports the reduction to the linear function,  \n\nMoreover, I believe a ground truth for the last-iterate privacy loss is missing.", "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": "MdbUQyubBb", "reviewer": "Reviewer_YKem", "summary": "This paper derives an exact privacy analysis of DP-SGD for linear models (referred to as the heuristic) when only the last iterate is released. The authors also compare existing empirical privacy auditing methods with the exact heuristic across different regimes, including image classification tasks and language models.", "questions": "See the weakness part.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper introduces a novel approach (named heuristic) to assess the performance of existing empirical evaluations of DP-SGD's privacy guarantees. While empirical evaluation provides a lower bound on the privacy budget of DP mechanisms, it may underestimate the true privacy loss. By comparing it with the heuristic bound for linear models, if the empirical audit bound is loose, it is unreasonable to expect it to hold tightly for more complicated non-linear (or even non-convex) models.", "weaknesses": "The main weakness of this paper is its limited theoretical contribution. In my view, the heuristic bound (Theorem 1) offers a simplified analysis of existing convergence privacy analysis for (strongly) convex loss functions (cf., the literature referenced in the introduction of this paper, which uses both RDP and $f$-DP). Additionally, the linear model is relatively simple, as the last-iterate output has a closed-form representation. Therefore, I propose the following questions or modifications:\n\n1. $\\textbf{Linear Probing as a Benchmarking Method:}$ Linear probing is commonly used for benchmarking when privately fine-tuning a foundation model. Therefore, the proposed heuristic for linear models could be beneficial when fine-tuning the last layer (linear probing) of a foundation model. Besides the well-known paper by De et al., the following recent studies may provide strong support for the utility of linear models in private fine-tuning, potentially strengthening the story for using heuristics for linear models.\n\nDifferentially Private Image Classification by Learning Priors from Random Processes. Tang et al., NeurIPS'23.\n\nNeural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning. Wang et al., ICML'24.\n\n2. $\\textbf{Extension to Convex Loss Functions:}$ Could this heuristic bound be extended to convex loss functions? I understand that the existing convergence bounds for DP-SGD involve complicated constants that are challenging to specify in practice, but a potential comparison between empirical auditing bounds and the theoretical upper bound under convex loss would be more convincing than in the linear case.\n\n3. $\\textbf{Comparison with Privacy Auditing Bound using privacy profiles: }$  It appears that the comparison with the privacy auditing bound is based on a specific value of $(\\epsilon, \\delta)$. What about examining the entire $(\\epsilon, \\delta(\\epsilon))$-curve (or equivalently, the ROC curve or the type I/II error trade-off curve)? My question arises because, even if the privacy auditing bound might be (nearly) tight for specific values of $(\\epsilon, \\delta)$, it may not remain tight across the entire curve.", "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": "D9MBSzOIm4", "reviewer": "Reviewer_MfJb", "summary": "The paper computes heuristic differential privacy parameters $\\varepsilon$ and $\\delta$ for releasing the last iterate of the DP-SGD algorithm. The proposed heuristic relies on computing the DP upper bound under linear loss function, which is always smaller than the DP upper bound under worst-case loss functions.  Numerical experiments show interesting scenarios where the proposed heuristics yield estimates that are significantly smaller than the worst-case DP upper bound. Experiments on image and language datasets confirm that the heuristic estimates lie between the DP upper bound and the lower bounds obtained via privacy auditing. Finally, the authors provide examples where the proposed heuristics underestimate the privacy loss.", "questions": "1. Could the authors comment on why the proposed heuristics give a realistic privacy risk estimate, given that the linear loss function is not commonly used? That is, whether and how often would the proposed heuristics overestimate the last-iterate privacy loss.\n\n2. Besides the small sampling rate and the pathological counterexamples (as discussed in 4.3), are there other regimes where the proposed heuristic is significantly smaller than the DP upper bound? This is to understand the usefulness of the proposed heuristics.\n\n3. Minor questions regarding clarity:\n    - Line 297 - `we expect this looseness to be the result of statistic effects` -- could the authors provide error bars in Figure 3 to validate this hypothesis?\n    - Figure 3 and 4: why is the standard epsilon constant under increasing the number of steps?\n    - What is the exact definition of a heuristic privacy estimate? It seems to be DP's upper bound over a family of loss functions, rather than all loss functions.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- A systematic investigation of using heuristic privacy estimates to study the last-iterate privacy loss of the DP-SGD algorithm, including derivations, numerical experiments, comparison with auditing experiments, and analysis of counterexamples where the proposed heuristics underestimates the privacy loss.\n\n- Numerical experiments show that when the sampling rate is small, the proposed heuristic yields an estimate that is significantly smaller than the standard DP upper bound.\n\n- Auditing experiments illustrated that interestingly, black-box gradient space attacks fail to give tight auditing lower bound for the last-iterate of DP-SGD algorithm under natural datasets, in which case the heuristic estimates and the input-space attack gives more reliable estimates for the privacy loss.", "weaknesses": "- The message of the paper is not fully clear -- why is such a heuristic privacy estimate realistic and useful? Specifically, (1) linear loss is not a commonly used loss function; and (2) the heuristic estimates appear to be roughly the same as DP upper bound in certain auditing experiments (Figure 2). See questions 1 and 2 for more details.\n\n\n- Several terms and plots in the paper are not explained in detail and the claims require more clarification. See question 3 for more details.", "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)