The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD

## Abstract

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. We also empirically support our heuristic and show existing privacy auditing attacks are bounded by our heuristic analysis in both vision and language tasks.

## 1 Introduction

Differential privacy (DP) [] defines a measure of how much private information from the training data leaks through the output of an algorithm.
The standard differentially private algorithm for deep learning is DP-SGD [, ], which differs from ordinary stochastic gradient descent in two ways: the gradient of each 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 [, , , , ]. In particular, it applies to the setting where the privacy adversary has access to all intermediate iterates of the training procedure.
In this setting, the analysis is known to be tight [, ].
However, in practice, potential adversaries rarely have access to the intermediate iterates of the training procedure, rather they only have access to the final model.
Access to the final model can either be through queries to an 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 a third angle via principled heuristics.

A handful of theoretical analyses [, , , , ] 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-based 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 [, , , , , , , ] complements theoretical analysis by giving empirical lower bounds on the privacy leakage.
Privacy auditing works by performing a membership inference attack [, , , ]. 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., $\varepsilon>10$); in this case, privacy auditing may be used as evidence that the “real” privacy leakage is lower.
There are settings where the theoretical analysis is matched by auditing, such as when all intermediate results are released [, ]. However, despite
significant work on privacy auditing and membership inference [, , , , , ], a large gap remains between the theoretical upper bounds and the auditing lower bounds [, , ] 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 $\varepsilon$ 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 to a worst-case theoretical analysis under the assumption that the 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 $\varepsilon$ values
when the gradients of the canaries – that is, the examples that are included or excluded to test the privacy leakage – 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 a privacy perspective, we show that it captures
the state of the art.

We also probe the limitations of our heuristic and give some
artificial
counterexamples 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 a 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 as 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 [], we believe that our heuristic can also be valuable in practice.
In particular, our heuristic 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.)

Figure: Algorithm 1 Noisy Clipped Stochastic Gradient Descent (DP-SGD) [, ]

## 2 Linearized Heuristic Privacy Analysis

Theorem 1 presents our heuristic differential privacy analysis of DP-SGD (which we present in Algorithm 1 for completeness;
note that we include a regularizer $r$ whose gradient is *not* clipped, because it does not depend on the private data $\mathbf{x}$).(^1^11Note that the regularizer is optional as it can be set to zero. We include it for convenience later.)
We consider Poisson subsampled minibatches and add/remove neighbours, as is standard in the differential privacy literature.

Our analysis takes the form of a conditional privacy guarantee. Namely, under the assumption that the loss and regularizer are linear, we obtain a fully rigorous differential privacy guarantee.
The heuristic is to apply this guarantee to loss functions that are not linear (such as those that arise in deep learning applications).
Our thesis is that, in most cases, the conclusion of the theorem is still a good approximation, even when the assumption does not hold.

Recall that a function $\ell:\mathbb{R}^{d}\to\mathbb{R}$ is linear if there exist $\alpha\in\mathbb{R}^{d}$ and $\beta\in\mathbb{R}$ such that $\ell(\mathbf{m})=\langle\alpha,\mathbf{m}\rangle+\beta$ for all $\mathbf{m}$.

###### Theorem 1 (Privacy of DP-SGD for linear losses) .

Let $\mathbf{x},T,q,\eta,\sigma,\ell,r$ be as in Algorithm 1.
Assume $r$ and $\ell(\cdot,x)$, for every $x\in\mathcal{X}$,
are linear.

Letting

$$ $P:=\mathsf{Binomial}(T,q)+\mathcal{N}(0,\sigma^{2}T)~{}~{}~{}~{}\text{ and }~{ }~{}~{}~{}Q:=\mathcal{N}(0,\sigma^{2}T),$ (1) $$

DP-SGD with last_iterate_only satisfies $(\varepsilon,\delta)$-differential privacy with $\varepsilon\geq 0$ arbitrary and

$$ $\delta=\delta_{T,q,\sigma}(\varepsilon):=\max\{H_{e^{\varepsilon}}(P,Q),H_{e^{ \varepsilon}}(Q,P)\}.$ (2) $$

Here, $H_{e^{\varepsilon}}$ denotes the $e^{\varepsilon}$-hockey-stick-divergence $H_{e^{\varepsilon}}(P,Q):=\sup_{S}P(S)-e^{\varepsilon}Q(S)$.

Equation 2 gives us a value of the privacy failure probability parameter $\delta$. But it is more natural to work with the privacy loss bound parameter $\varepsilon$, which can be computed by inverting the formula:

$$ $\varepsilon_{T,q,\sigma}(\delta):=\min\{\varepsilon\geq 0:\delta_{T,q,\sigma}( \varepsilon)\leq\delta\}.$ (3) $$

Both $\delta_{T,q,\sigma}(\varepsilon)$ and $\varepsilon_{T,q,\sigma}(\delta)$ can be computed using existing open-source DP accounting libraries []. We also provide a self-contained & efficient method for computing them in Appendix A.

Figure: (a) Keep $Tp$ and $T\sigma^{2}$ constant.
Refer to caption: x1.png

The proof of Theorem 1 is deferred to Appendix A, but we sketch the main ideas:
Under the linearity assumption, the output of DP-SGD is just a 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(^2^22*The canary* refers to the individual datapoint that is added or removed between neighboring datasets. This terminology is used in the privacy auditing/attacks literature inspired on the expression “canary in a coalmine.”) (which is constant).
We can also ignore the gradients of the other examples.
Thus, by rescaling, the worst case pair of output distributions can be represented as in Equation 1.
Namely, $Q=\sum_{t=1}^{T}\xi_{t}$ is simply the noise $\xi_{t}\leftarrow\mathcal{N}(0,\sigma^{2})$ summed over $T$ iterations; this corresponds to the case where the canary is excluded.
When the canary is included, it is sampled with probability $q$ in each iteration and thus the total number of times it is sampled over $T$ iterations is $\mathsf{Binomial}(T,q)$. Thus $P$ is the sum of the contributions of the canary and the noise. Finally the definition of differential privacy lets us compute $\varepsilon$ and $\delta$ 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$.

###### Theorem 1 (Privacy of DP-SGD for linear losses) .

### 2.1 Baselines

In addition to privacy auditing, we compare our heuristic to two different baselines in Figure 1.
The first is the standard, composition-based analysis. We use the open-source library from Google [], which computes a tight DP guarantee for DP-SGD with intermediate_iterates. Because DP-SGD with intermediate_iterates gives the adversary more information than with last_iterate_only, this will always give at least as large an estimate for $\varepsilon$ as our heuristic.

We also consider approximating DP-SGD by full batch DP-GD. That is, set $q=1$ and rescale the learning rate $\eta$ and noise multiplier $\sigma$ to keep the expected step and privacy noise variance constant:

$$ $\underbrace{\text{DP-SGD}(\mathbf{x},T,q,\eta,\sigma,\ell,r)}_{\text{batch size }\approx nq,~{}T\text{ iterations, }Tq\text{ epochs}}\approx~{} \underbrace{\text{DP-SGD}(\mathbf{x},T,1,\eta\cdot q,\sigma/q,\ell,r)}_{\text{ batch size }n,~{}T\text{ iterations, }T\text{ epochs}}.$ (4) $$

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 on privacy amplification by subsampling, it is much easier to analyze its privacy guarantees. Interestingly, there is no difference between full batch DP-GD with last_iterate_only and with intermediate_iterates; see Appendix B.
Full batch DP-GD generally has better privacy guarantees than the corresponding minibatch DP-SGD and so this baseline usually (but not always) gives smaller values for the privacy leakage $\varepsilon$ than our heuristic.
In practice, full batch DP-GD is too computationally expensive to run. But we can use it as an idealized comparison point for the privacy analysis.

Figure: (a) $q=0.01$
Refer to caption: x4.png

Figure: (a) $q=0.01$
Refer to caption: x6.png

Figure: (a) All zero gradient inputs
Refer to caption: x8.png

## 3 Empirical Evaluation via Privacy Auditing

We study how our heuristic compares to the empirical privacy auditing results in well studied settings.
We focus on image classification (CIFAR-10), as this is a well-studied setting for privacy auditing of DP-SGD [, , , , , ]. In Section 3.2 we extend the experiments to language models and show similar results.

### 3.1 Image Classification Experiments

Setup: We follow the construction of Nasr et al. [] 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 [] with a WideResNet model [] unless otherwise specified; in particular, we follow the training setup of De et al. [], where we train and audit a model with $79\%$ test
accuracy and, using the standard analysis, $(\varepsilon=8,\delta=10^{-5})$-DP. For each experiment we trained 512 CIFAR10 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. []. Here we 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 ($\varepsilon$ and $\delta$) are derived.

We implement state-of-the-art attacks from prior work [, ]. These attacks heavily rely on the intermediate steps and, as a result, do not achieve tight results. In the next section, we design specific attacks for our heuristic privacy analysis approach to further understand its limitations and potential vulnerabilities.

Gradient Space Attack:
The most powerful attacks in prior work are gradient space attacks where the adversary injects a 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 []. However, these previous attacks require access to all intermediate training steps to achieve tight results. Here, we 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 ($\approx 0$). This last setting was shown by [] to result in tighter auditing. In all attacks, we assume the distinguisher has access to all adversarial gradient vectors. For malicious gradients, we use Dirac gradient canaries, where gradient vectors consist of zeros in all but a single index. In both cases, the distinguishing test measures the dot product of the final model checkpoint and the gradient canary.

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 are 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 $\varepsilon$ with these values.
We plot the results of this experiment in Figure 3 together with the $\varepsilon$ output by the theoretical analysis and the heuristic, fixing the subsampling probability and varying the number of update steps. We adjust the noise parameter to ensure the standard theoretical analysis produces a fixed $\varepsilon$ bound.
The empirical measured $\varepsilon$ is close to the heuristic $\varepsilon$ 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.

Input Space Attack:
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 [, ]. For input space attacks, we use the loss of the malicious input as a distinguisher. Similar to 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.

Figure 4 summarizes the results for this setting. Compared to Figure 2, input space attacks achieve tighter results than gradient space attacks. This finding is in stark contrast to prior work. The reason is that input space attacks do not rely on 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

**Table 1: Evaluation of empirical auditing for differential private finetuning of Gemma 2 on PersonaChat varying batch size**
| Batch size | Heuristic $\varepsilon$ | Standard $\varepsilon$ | Perplexity | Empirical $\varepsilon$ |
| --- | --- | --- | --- | --- |
| 2048 | 6.0 | 8 | 24.3 | 2.1 |
| 1024 | 6.1 | 14 | 24.2 | 2.1 |
| 512 | 6.0 | 26 | 24.8 | 2.0 |

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 [] on the PersonaChat dataset [].
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.

Interestingly, we observed that Gemma 2 tokenizer contains many tokens that are not present in the PersonaChat dataset. In this work, we utilize these tokens as differing examples, leaving the design of optimal canaries for language models to future research. Table 1 summarizes the results for the language model setting (cf. Table 2 for the image classification setting). We can see that there is not 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 at Appendix D.

## 4 Counterexamples

We now test the limits of our heuristic by constructing some artificial counterexamples. That is, we construct inputs to DP-SGD with last_iterate_only 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 a provable upper bound on the privacy loss.

### 4.1 Warmup: Zeroing Out The Model Weights

We begin by noting the counterintuitive fact that our heuristic $\varepsilon_{T,q,\sigma}(\delta)$ is *not* always monotone in the number of steps $T$ when the other parameters $\sigma,q,\delta$ are kept constant.
This is shown in Figure 1(c).
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 can use a regularizer $r(\mathbf{m})=\|\mathbf{m}\|_{2}^{2}/2\eta$ so that $\eta\cdot\nabla_{\mathbf{m}}r(\mathbf{m})=\mathbf{m}$.
This regularizer zeros out the model from the previous step, i.e., the update of DP-SGD (Algorithm 1) becomes

$$ $\displaystyle\mathbf{m}_{t}$ $\displaystyle=\mathbf{m}_{t-1}-\eta\cdot\left(\sum_{i\in B_{t}}\mathsf{clip} \left(\nabla_{\mathbf{m}_{t-1}}\ell(\mathbf{m}_{t-1},x_{i})\right)+\nabla_{ \mathbf{m}_{t-1}}r(\mathbf{m}_{t-1})+\xi_{t}\right)$ (5) $\displaystyle=\eta\cdot\sum_{i\in B_{t}}\mathsf{clip}\left(\nabla_{\mathbf{m}_ {t-1}}\ell(\mathbf{m}_{t-1},x_{i})\right)+\xi_{t}.$ (6) $$

This means that the last iterate $\mathbf{m}_{T}$ is effectively the result of only a single iteration of DP-SGD. In particular, it will have a privacy guarantee corresponding to one iteration.
Combining this regularizer with a linear loss and a setting of the parameters $T,q,\sigma,\delta$ such that the privacy loss is non-monotone – i.e., $\varepsilon_{T,q,\sigma}(\delta)<\varepsilon_{1,q,\sigma}(\delta)$ – yields a counterexample.

In light of this counterexample, in the next subsection, we benchmark our counterexample against sweeping over smaller values of $T$. I.e., we consider $\max_{t\leq T}\varepsilon_{t,q,\sigma}(\delta)$ instead of simply $\varepsilon_{T,q,\sigma}(\delta)$.

### 4.2 Linear Loss + + + Quadratic Regularizer

Consider running DP-SGD in one dimension (i.e., $d=1$) with a linear loss $\ell(\mathbf{m},x)=\mathbf{m}x$ for the canary and a quadratic regularizer $r(\mathbf{m})=\frac{1}{2}\alpha\mathbf{m}^{2}$, where $\alpha\in[0,1]$ and $x\in[-1,1]$ and we use learning rate $\eta=1$. With sampling probability $q$, after $T$ iterations the privacy guarantee is equivalent to distinguishing $Q:=\mathcal{N}(0,\widehat{\sigma}^{2})$ and $P:=\mathcal{N}(\sum_{i\in[T]}(1-\alpha)^{i-1}\mathsf{Bernoulli}(q),\widehat{
\sigma}^{2})$, where $\widehat{\sigma}^{2}:=\sigma^{2}\sum_{i\in[T]}(1-\alpha)^{2(i-1)}$. When $\alpha=0$, this retrieves linear losses. When $\alpha=1$, this corresponds to distinguishing $\mathcal{N}(0,\widehat{\sigma}^{2})$ and $\mathcal{N}(\mathsf{Bernoulli}(q),\widehat{\sigma}^{2})$ or, equivalently, to distinguishing linear losses after $T=1$ iteration. If we maximize our heuristic over the number of iterations $\leq T$, then our heuristic is tight for the extremes $\alpha\in\{0,1\}$.

A natural question is whether the worst-case privacy guarantee on this quadratic is always given by $\alpha\in\{0,1\}$. Perhaps surprisingly, the answer is no: we found that for $T=3,q=0.1,\sigma=1,\alpha=0$, DP-SGD is $(2.222,10^{-6})$-DP. For $\alpha=1$ instead DP-SGD is $(2.182,10^{-6})$-DP. However, for $\alpha=0.5$ instead the quadratic loss does not satisfy $(\varepsilon,10^{-6})$-DP for $\varepsilon<2.274$.

However, this violation is small, which suggests our heuristic is still a reasonable for this class of examples. To validate this, we consider a set of values for the tuple $(T,q,\sigma)$. For each setting of $T,q,\sigma$, we compute $\max_{t\leq T}\varepsilon_{t,q,\sigma}(\delta)$ at $\delta=10^{-6}$. We then compute $\varepsilon$ for the linear loss with quadratic regularizer example with $\alpha=1/2$ in the same setting. Since the support of the random variable $\sum_{i\in[T]}(1-\alpha)^{i-1}\mathsf{Bernoulli}(q)$ has size $2^{T}$ for $\alpha=1/2$, computing exact $\varepsilon$ for even moderate $T$ is computationally intensive. Instead, let $X$ be the random variable equal to $\sum_{i\in[T]}(1-\alpha)^{i-1}\mathsf{Bernoulli}(q)$, 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 $\varepsilon$ for distingushing $\mathcal{N}(0,\widehat{\sigma}^{2})$ vs $\mathcal{N}(X,\widehat{\sigma}^{2})$. By Lemma 4.5 of Chooquette-Cho et al. [], we know that distinguishing $\mathcal{N}(0,\widehat{\sigma}^{2})$ vs. $\mathcal{N}(\sum_{i\in[T]}(1-\alpha)^{i-1}\mathsf{Bernoulli}(q),\widehat{
\sigma}^{2})$ is no harder than distingushing $\mathcal{N}(0,\widehat{\sigma}^{2})$ vs $\mathcal{N}(X,\widehat{\sigma}^{2})$, and since we increase the values in the support by no more than 1.05 multiplicatively, we expect that our rounding does not increase $\varepsilon$ by more than 1.05 multiplicatively.

Figure: (a) One iteration of DP-SGD satisfies $(1,10^{-6})$-DP.
Refer to caption: extracted/5917394/figures/halfquadraticeps1.png

In Figure 5, we plot the ratio of $\varepsilon$ at $\delta=10^{-6}$ for distingushing between $\mathcal{N}(0,\widehat{\sigma}^{2})$ and $\mathcal{N}(X,\widehat{\sigma}^{2})$ divided by the maximum over $i\in[T]$ of $\varepsilon$ at $\delta=10^{-6}$ for distinguishing between $\mathcal{N}(0,i\sigma^{2})$ and $\mathcal{N}(\mathsf{Binomial}(i,q),i\sigma^{2})$. We sweep over $T$ and $q$, and for each $q$ In Figure 5(a) (resp. Figure 5(b)) we set $\sigma$ such that distinguishing $\mathcal{N}(0,\sigma^{2})$ from $\mathcal{N}(\mathsf{Bernoulli}(q),\sigma^{2})$ satisfies $(1,10^{-6})$-DP (resp. $(2,10^{-6})$-DP). In the majority of settings, the linear loss heuristic provides a larger $\varepsilon$ than the quadratic with $\alpha=1/2$, and even when the quadratic provides a larger $\varepsilon$, the violation is small ($\leq 3\%$). This is evidence that our heuristic is still a good approximation for many convex losses.

### 4.3 Pathological Example

If we allow the regularizer $r$ 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 intermediate_iterates is close to tight.

Specifically, choose the regularizer so that the update $\mathbf{m}^{\prime}=\mathbf{m}-\eta\nabla_{\mathbf{m}}r(\mathbf{m})$ does the following: $\mathbf{m}^{\prime}_{1}=0$ and, for $i\in[d-1]$, $\mathbf{m}^{\prime}_{i+1}=v\cdot\mathbf{m}_{i}$. Here $v>1$ is a large constant. We chose the loss so that, for our canary $x_{1}$, we have $\nabla_{\mathbf{m}}\ell(\mathbf{m},x_{1})=(1,0,0,\cdots,0)$ and, for all other examples $x_{i}$ ($i\in\{2,3,\cdots,n\}$), we have $\nabla_{\mathbf{m}}\ell(\mathbf{m},x_{i})=\mathbf{0}$.
Then the last iterate is

$$ $\mathbf{m}_{T}=(A_{T}+\xi_{T,1},vA_{T-1}+v\xi_{T-1,1}+\xi_{T,2},v^{2}A_{T-2}+v ^{2}\xi_{T-2,1}+v\xi_{T-1,2}+\xi_{T,3},\cdots),$ (7) $$

where $A_{t}\leftarrow\mathsf{Bernoulli}(p)$ indicates whether or not the canary was sampled in the $t$-th iteration and $\xi_{t,i}$ denotes the $i$-th coordinate of the noise $\xi_{t}$ added in the $t$-th step.
Essentially, the last iterate $\mathbf{m}_{T}$ contains the history of all the iterates in its coordinates. Namely, the $i$-th coordinate of $\mathbf{m}_{T}$ gives a scaled noisy approximation to $A_{T-i}$:

$$ $v^{1-i}\mathbf{m}_{T,i}=A_{T-i}+\sum_{j=0}^{i-1}v^{j+1-i}\xi_{T-j,i-j}\sim \mathcal{N}\left(A_{T-i},\sigma^{2}\frac{1-v^{-2i}}{1-v^{-2}}\right).$ (8) $$

As $v\to\infty$, the variance converges to $\sigma^{2}$. In other words, if $v$ is large, from the final iterate, we can obtain $\mathcal{N}(A_{i},\sigma^{2})$ for all $i$. This makes the standard composition-based analysis of DP-SGD tight.

Concurrent work [] presents a counterexample that yields a similar conclusion, although their construction is quite different.

### 4.4 Malicious Dataset Attack

The examples above rely on the regularizer having large unclipped gradients. We now construct a 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 a nonlinear model and specific training data to directly challenge this assumption. The attack strategy is to use the model’s parameters as a 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 was present at a given iteration of training. The rest of the data points are maliciously selected to ensure the noise added during training doesn’t impact the information stored in the model’s parameters. We defer the full details of the attack to Appendix C.

Figure 6 summarizes the results. As illustrated in the figure, this attack achieves an auditing lower bound matching the standard DP-SGD analysis even in the last_iterate_only setting. As a result, the attack exceeds our heuristic. However, this is a highly artificial example and it is unlikely to reflect real-world scenarios.

Figure: (a) $q=0.01$
Refer to caption: x10.png

**Table 2: Previous works showed that large batch sizes achieve high performing models []. Using our heuristic analysis it is possible to achieve similar performance for smaller batch sizes.**
| Batch size | Heuristic $\varepsilon$ | Standard $\varepsilon$ | Accuracy | Empirical $\varepsilon$ |
| --- | --- | --- | --- | --- |
| 4096 | 6.34 | 8 | 79.5$\%$ | 1.7 |
| 512 | 7.0 | 12 | 79.9$\%$ | 1.8 |
| 256 | 6.7 | 14 | 78.2$\%$ | 1.6 |

## 5 Discussion & Implications

Both theoretical analysis and privacy auditing are valuable for understanding privacy leakage in machine learning, but both have limitations.
Theoretical analysis is inherently conservative, while auditing procedures
underrepresent the privacy leakage.

Our heuristic approach empirically upper bounds the privacy leakage in practical scenarios (Section 3). Although counter-examples 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) [, ].
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 is large (see Figure 1(b)). Furthermore, training large models is 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, an adversary would need to break these linearity assumptions in a practical setting. This is currently very difficult with existing attacks on deep learning models.

## 6 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 a result many studies supplement theoretical privacy bounds with empirical leakage evaluations to 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 a 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 to estimate privacy leakage to complement privacy auditing and the standard composition-based analysis of DP-SGD.

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 of 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 an upper bound on all existing empirical attacks.

## Appendix A Proof of Theorem 1

###### Proof.

Let $x_{i^{*}}$ be the canary, let $D$ be the dataset with the canary and $D^{\prime}$ be the dataset without the canary. Since $\ell$ and $r$ are linear, wlog we can assume $r=0$ and $\nabla_{\mathbf{m}_{t-1}}\ell(\mathbf{m}_{t-1},x_{i})=\textbf{v}_{i}$ for some set of vectors $\{\textbf{v}_{i}\}$, such that $\|\textbf{v}_{i}\|_{2}\leq 1$. We can also assume wlog $\|\textbf{v}_{i^{*}}\|=1$ since, if $\|\textbf{v}_{i^{*}}\|<1$, the final privacy guarantee we show only improves.

We have the following recursion for $\mathbf{m}_{t}$:

$$ $\mathbf{m}_{t}=\mathbf{m}_{t-1}-\eta\left(\sum_{i\in B_{t}}\textbf{v}_{i}+\xi_ {t}\right),\qquad\xi_{t}\stackrel{{\scriptstyle i.i.d}}{{\sim}}\mathcal{N}(0, \sigma^{2}I_{d}).$ $$

Unrolling the recursion:

$$ $\mathbf{m}_{t}=\mathbf{m}_{0}-\eta\left[\sum_{t\in[T]}\sum_{i\in B_{t}}\textbf {v}_{i}+\xi\right],\qquad\xi\sim N(0,T\sigma^{2}I_{d}).$ $$

By the post-processing property of DP, we can assume that in addition to the final model $\mathbf{m}_{T}$, we release $\mathbf{m}_{0}$ and $\{B_{t}\setminus\{x_{i^{*}}\}\}_{t\in[T]}$, that is we release all examples that were sampled in each batch except for the canary. The following $f$ is a bijection, computable by an adversary using the released information:

$$ $f(\mathbf{m}_{T}):=-\left[\frac{\mathbf{m}_{T}-\mathbf{m}_{0}}{\eta}-\sum_{t \in[T]}\sum_{i\in B_{t}\setminus\{x_{i^{*}}\}}\textbf{v}_{i}.\right]$ $$

Since $f$ is a bijection, distinguishing $\mathbf{m}_{T}$ sampled using $D$ and $D^{\prime}$ is equivalent to distinguishing $f(\mathbf{m}_{T})$ instead. Now we have $f(\mathbf{m}_{T})=\mathcal{N}(0,T\sigma^{2}I_{d})$ for $D^{\prime}$, and $f(\mathbf{m}_{T})=\mathcal{N}(0,T\sigma^{2}I_{d})+k\textbf{v}_{i^{*}}$, $k\sim\mathsf{Binomial}(T,q)$. For any vector u orthogonal to $\textbf{v}_{i^{*}}$, by isotropy of the Gaussian distribution the distribution of $\langle f(\mathbf{m}_{T}),\textbf{u}\rangle$ is the same for both $D$ and $D^{\prime}$ and independent of $\langle f(\mathbf{m}_{T}),\textbf{v}_{i^{*}}\rangle$, hence distinguishing $f(\mathbf{m}_{T})$ given $D$ and $D^{\prime}$ is the same as distingushing $\langle f(\mathbf{m}_{T}),\textbf{v}_{i^{*}}\rangle$ given $D$ and $D^{\prime}$. Finally, the distribution of $\langle f(\mathbf{m}_{T}),\textbf{v}_{i^{*}}\rangle$ is exactly $P$ for $D$ and exactly $Q$ for $D^{\prime}$. By post-processing, this gives the theorem.

We can also see that the function $\delta_{T,q,\sigma}$ is tight (i.e., even if we do not release $B_{t}\setminus\{x_{i^{*}}\}$), by considering the 1-dimensional setting, where $\textbf{v}_{i}=0$ for $i\neq i^{*}$ and $\textbf{v}_{i^{*}}=-1,\eta=1,\mathbf{m}_{0}=0$. Then, the distribution of $\mathbf{m}_{T}$ given $D$ is exactly $P$, and given $D^{\prime}$ is exactly $Q$.
∎

###### Proof.

### A.1 Computing δ 𝛿 \delta italic_δ from ε 𝜀 \varepsilon italic_ε

Here, we give an efficiently computable expression for the function $\delta_{T,q,\sigma}(\varepsilon)$. Using $P,Q$ as in Theorem 1, let $f(y)$ be the privacy loss for the output $y$:

$$ $\displaystyle f(y)=\log\left(\frac{P(y)}{Q(y)}\right)$ $\displaystyle=\log\left(\sum_{k=0}^{T}\binom{T}{k}q^{k}(1-q)^{n-k}\frac{\exp(- (y-k)^{2}/2T\sigma^{2})}{\exp(-y^{2}/2T\sigma^{2})}\right)$ $\displaystyle=\log\left(\sum_{k=0}^{T}\binom{T}{k}q^{k}(1-q)^{k}\exp\left( \frac{2ky-k^{2}}{2T\sigma^{2}}\right)\right).$ $$

Then for any $\varepsilon$, using the fact that $S=\{y:f(y)\geq\varepsilon\}$ maximizes $P(S)-e^{\varepsilon}Q(S)$, we have:

$$ $\displaystyle H_{e^{\varepsilon}}(P,Q)$ $\displaystyle=P(\{y:f(y)\geq\varepsilon\})-e^{\varepsilon}Q(\{y:f(y)\geq \varepsilon\})$ $\displaystyle=P(\{y:y\geq f^{-1}(\varepsilon)\})-e^{\varepsilon}Q(\{y:y\geq f^ {-1}(\varepsilon)\})$ $\displaystyle=\sum_{k=0}^{T}\binom{T}{k}q^{k}(1-q)^{k}\Pr[\mathcal{N}(k,T \sigma^{2})\geq f^{-1}(\varepsilon)]-e^{\varepsilon}\Pr[\mathcal{N}(0,T\sigma^ {2})\geq f^{-1}(\varepsilon)].$ $$

Similarly, $S=\{y:f(y)\leq-\varepsilon\}$ maximizes $Q(S)-e^{\varepsilon}P(S)$ so we have:

$$ $\displaystyle H_{e^{\varepsilon}}(Q,P)$ $\displaystyle=Q(\{y:f(y)\leq-\varepsilon\})-e^{\varepsilon}P(\{y:f(y)\leq- \varepsilon\})$ $\displaystyle=Q(\{y:y\leq f^{-1}(-\varepsilon)\})-e^{\varepsilon}P(\{y:y\leq f ^{-1}(-\varepsilon)\})$ $\displaystyle=\Pr[\mathcal{N}(0,T\sigma^{2})\leq f^{-1}(-\varepsilon)]-e^{ \varepsilon}\sum_{k=0}^{T}\binom{T}{k}q^{k}(1-q)^{k}\Pr[\mathcal{N}(k,T\sigma^ {2})\leq f^{-1}(-\varepsilon)].$ $$

These expressions can be evaluated efficiently. Since $f$ is monotone, it can be inverted via binary search. We can also use binary search to evaluate $\varepsilon$ as a function of $\delta$.

## Appendix 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 intermediate_iterates and with last_iterate_only are the same. This phenomenon arises because there is no subsampling (because $q=1$ in Algorithm 1) and thus the algorithm is “just” the Gaussian mechanism.
Intuitively, DP-GD with intermediate_iterates corresponds to $T$ calls to the Gaussian mechanism with noise multiplier $\sigma$, while DP-GD with last_iterate_only corresponds to one call to the Gaussian mechanism with noise multiplier $\sigma/\sqrt{T}$; these are equivalent by the properties of the Gaussian distribution.

We can formalize this using the language of Gaussian DP []: DP-GD (Algorithm 1 with $q=1$) satisfies $\sqrt{T}/\sigma$-GDP. (Each iteration satisfies $1/\sigma$-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 $\sigma/\sqrt{T}$.
Linear losses give an example such that DP-GD with last_iterate_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 intermediate_iterates is no worse than that of DP-GD with last_iterate_only. The reverse is also true (by postprocessing).

In more detail:
For $T$ iterations of (full-batch) DP-GD on a linear losses, if the losses are (wlog) $1$-Lipschitz and we add noise $\mathcal{N}(0,\frac{\sigma^{2}}{n^{2}}\cdot I)$ to the gradient in every round, distinguishing the last iterate of DP-SGD on adjacent databases is equivalent to distinguishing $\mathcal{N}(0,T\sigma^{2})$ and $\mathcal{N}(T,T\sigma^{2})$. This can be seen as a special case of Theorem 1 for $p=1$, so we do not a give a detailed argument here.

If instead we are given every iteration $\mathbf{m}_{t}$, for any 1-Lipschitz loss, distinguishing the joint distributions of $\mathbf{m}_{t}$ given $\mathbf{m}_{t-1}$ on adjacent databases is equivalent to distinguishing $\mathcal{N}(0,\sigma^{2})$ and $\mathcal{N}(1,\sigma^{2})$. In turn, distinguishing the distribution of all iterates on adjacent databases is equivalent to distinguishing $\mathcal{N}(\textbf{0}^{T},\sigma^{2}I_{T})$ and $\mathcal{N}(\textbf{1}^{T},\sigma^{2}I_{T})$, where $\textbf{0}^{T}$ and $\textbf{1}^{T}$ are the all-zeros and all-ones vectors in $\mathbb{R}^{T}$. Because the Gaussian distribution is isotropic, distinguishing $\mathcal{N}(\textbf{0}^{T},\sigma^{2}I_{T})$ and $\mathcal{N}(\textbf{1}^{T},\sigma^{2}I_{T})$ is equivalent to distinguishing $\langle\textbf{x},\textbf{1}^{T}\rangle$ where $\textbf{x}\sim\mathcal{N}(\textbf{0}^{T},\sigma^{2}I_{T})$ and $\langle\textbf{x},\textbf{1}^{T}\rangle$ where $\textbf{x}\sim\mathcal{N}(\textbf{1}^{T},\sigma^{2}I_{T})$. These distributions are $\mathcal{N}(0,T\sigma^{2})$ and $\mathcal{N}(T,T\sigma^{2})$, the exact pair of distributions we reduced to for last-iterate analysis of linear losses.

## Appendix C Malicious Dataset Attack Details

Algorithms 2, 3, and 4 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 can be implemented by having a 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^{\prime}=D\cup\{x\}$ so that all points in dataset $D$ (“repeaters”) run Algorithm 3 to compute gradients and the canary point in $D^{\prime}$ runs Algorithm 2 to compute its gradient. Our attack relies heavily on DP-SGD’s lack of assumptions on the data distribution and any specific properties of the model or gradients. Algorithm 2, which generates the canary data point, is straightforward. Its goal is to store in the model parameters whether it was present in iteration $i$ by outputting a gradient that changes only the $i$-th index of the model parameters by 1 (assuming a clipping threshold of 1).

All other data points, the “repeaters”, are present in both datasets ($D$ and $D^{\prime}$), and have three tasks:

- •
Cancel out any noise added to the model parameters at an index larger than the current iteration. At iteration $i$, 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 0 after the update.
- •
Evaluate whether the canary point was present in the previous iteration by comparing the model parameter at index $i-1$ with a threshold, and rewrite the value of that model parameter to a large value if the canary was present.
- •
Ensure that all previous decisions are not overwritten by noise by continuing to rewrite them with a large value based on their previous value.

To achieve all of these goals simultaneously, we require that the batch size is large enough that the repeaters’ updates are not clipped.

Finally Algorithm 4 runs DP-SGD, with repeater points computing gradients with Algorithm 3 and the canary point, sampled with probability $p$, computing its gradient using Algorithm 2. In our experiments we run Algorithm 4 100,000 times. And to evaluate if the model parameters was from dataset $D$ or $D^{\prime}$ we run a hypothesis test on the values of the model parameters. All constants are chosen to ensure all objectives of the repeaters are satisfied.

Figure: Algorithm 2 Canary data point

Figure: Algorithm 3 Additional data points

Figure: Algorithm 4 Encoding Attacking

## Appendix D Implementation Details

For image classification model we used De et. al, [] training approach with different batch sizes. We used Google Cloud A2-megagpu-16g machines with 16 Nvidia A100 40GB GPUs. Overall, we use roughly 60,000 GPU hours for our experiments. To compute the standard theoretical privacy bounds we use DP-accounting library (^3^33[https://github.com/google/differential-privacy/tree/main](https://github.com/google/differential-privacy/tree/main)). For each experiment we 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 [] 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 2 epochs for image and text modalities respectively and modified the sub-sampling rates, calculating the noise parameters required to achieve a similar privacy guarantee based on our heuristic.

## Peer Reviews

confidence: 5
contribution: 2
initial_rating: 5
presentation: 3
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?
* 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?
* Are there practical scenarios or specific types of models where the linearity assumption approximately holds? 
* Theoretical work also addresses this threat model for the non-convex case (see [5]). Is there any connection or similarity between the works?

[1]: https://arxiv.org/pdf/2405.14106
[2]: https://arxiv.org/pdf/2405.14457
[3]: https://arxiv.org/pdf/2407.06496
[4]: https://arxiv.org/pdf/2302.03098
[5]: https://arxiv.org/pdf/2305.09903
soundness: 3
strengths: * The paper presents a new heuristic privacy analysis for DP-SGD when only the final model is released. 
* The heuristic allows practitioners to estimate privacy leakage before training, aiding in hyperparameter selection without the computational cost and complexity of running privacy audits.
* 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
* The authors provide a good amount of examples and intuition when the heuristic does not hold
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.
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)
* 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)
* 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)

---

confidence: 5
contribution: 2
initial_rating: 5
presentation: 3
questions: In general, I think there is some interesting results in the paper but more work seems to be needed.

1. 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? 

2. Can the author explain how to generalize the analysis to capture the practical random $v_i$ scenario?


minors:
1. There is overlap in the figures in Fig.1.
soundness: 2
strengths: The paper is well motivated and organized. Interesting examples are presented with good intuitions.
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.
weaknesses: My primary concern is with the meaningfulness of the main result in Theorem 1.

In 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 
$v_i$  is random, the proof no longer holds, as the divergence cannot simply be reduced to that between the two Gaussian mixtures derived.

This 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. 

Additionally, 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,  

Moreover, I believe a ground truth for the last-iterate privacy loss is missing.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: See the weakness part.
soundness: 4
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.
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.
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:

1. $\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.

Differentially Private Image Classification by Learning Priors from Random Processes. Tang et al., NeurIPS'23.

Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning. Wang et al., ICML'24.

2. $\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.

3. $\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.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
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.

2. 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.

3. Minor questions regarding clarity:
    - 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?
    - Figure 3 and 4: why is the standard epsilon constant under increasing the number of steps?
    - 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.
soundness: 3
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.

- 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.

- 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.
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.
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.


- Several terms and plots in the paper are not explained in detail and the claims require more clarification. See question 3 for more details.

Meta-review: The paper investigates the privacy of DP-SGD when only the last iterate is provided (and intermediate model states are hidden). It shows a heuristic analysis for linear functions which is found to be predictive of the privacy obtained via auditing on various training procedures. The heuristic is evaluated on image and language datasets and the paper shows that it consistently upper bounds the privacy loss obtained via auditing. Though the proposed technique is a heuristic and is not rigorous, I think it provides an interesting avenue for future research. There are clearly gaps between the current theoretical upper bounds in DP and results obtained via auditing, and the work could be a step towards rigorously closing it.

I also suggest that the authors incorporate the recent contemporaneous work in the related work in the revision of the paper.

Decision: Accept (Poster)