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

We thank the reviewer for their time and comments.

1. I know the linear loss function assumption is common in theoretical analysis but it seems that the proposed method wants to have contributions in the empirical case, so why still make the linear assumption?

Unfortunately, we do not understand this question. We propose a heuristic. It is theoretically justified in the linear case, but we argue that it is still representative for real deep learning settings.

2. While I appreciate the effort to introduce a Heuristic analysis, I remain skeptical about its necessity and effectiveness. The primary benefit of theoretical analysis is its precision and rigor, which often include the flexibility to adjust bounds as needed. If the goal is to find a more relaxed lower bound on privacy risks, this can often be achieved by simply loosening the constraints within the existing theoretical framework. Introducing a separate heuristic analysis seems to complicate matters without providing clear advantages.

It is not clear how we can loosen the constraints within the existing theoretical framework. One natural approach is to make some kind of assumption that makes the privacy analysis easier; this is precisely what we do.

3. I do not think you are using a correct baseline. When you make that only the last iteration model can be seen assumption, it is not fair to use normal DP-SGD analysis. I think it is better to use the theoretical analysis from those hidden state papers you cited. I am curious if you compare your proposed method with those methods, will you still get the same conclusion?

It is difficult to compare to these prior works [FMTT18; CYS21; YS22; AT22; BSA24] for two reasons. First, many of these prior works make an assumption of strong convexity, which is technically incompatible with our linearity assumption. If we try to compare anyway, how would we set the strong convexity parameter for a fair comparison? We could always set the strong convexity parameter in such a way that our numbers are better. Second, most of these prior works are theoretical in nature and it is nontrivial to extract concrete numbers from their theorems to compare with.

4. I find Table 1 in the paper somewhat unclear and would appreciate further explanation from the authors regarding its purpose and implications. The table suggests that similar levels of heuristic $\varepsilon$ are achieved across varying batch sizes, yet there is a noticeable increase in the standard privacy budget for smaller batches to maintain comparable performance. This observation seems to underscore the well-known impact of batch size rather than demonstrating an advantage of the proposed heuristic method. Could the authors elaborate on how this data relates to the efficacy of the heuristic analysis?

The accepted wisdom, e.g. [DBHSB22], is that larger batch size yields better privacy/utility with DP-SGD. However, this is based on the standard DP-SGD analysis. Table 1 questions this accepted wisdom. Our heuristic, like the results of privacy auditing, is relatively insensitive to the batch size.

Training with large batch sizes is computationally costly, so if it is not truly improving privacy, we shouldn’t advise practitioners to do it. Further research is needed to understand whether or not larger batch sizes are truly beneficial.

We hope that we have addressed the reviewers concerns and that they reconsider their recommendation.

Thank you for the clarification.

Is it feasible to apply your proposed method to a non-linear loss like a cross-entropy loss that the community usually uses?

Realistic deep learning losses yield complicated output distributions on the model weights and, unfortunately, it is not possible to give an exact differential privacy analysis. This is why there is a lot of work on privacy auditing, which aims to empirically approximate an exact DP analysis. Thus we compare our heuristic to state-of-the-art privacy auditing methods.

In Section 4.2 we performed an exact analysis of quadratic losses. This is slightly more general than linear losses. But even here the output distribution becomes a mixture of Gaussians which is nontrivial to analyze.

I also wonder why you think a technique theoretically justified in the linear case can be representative of real deep learning.

It is indeed surprising that linear losses yield a good approximation to real deep learning in terms of privacy. The key observation that inspired this paper is that, in the practice of privacy auditing, the strongest membership inference results are achieved by examples ("canaries") with gradients that are the same in each iteration of SGD. This corresponds exactly to the case of a linear loss function.

So our linear approximation is well-justified empirically. Theoretically, Appendix B shows that in the full batch setting our linear approximation is indeed the worst case, although this proof does not extend to the minibatch setting.

For example, I want to train a Vision transformer model on ImageNet with DP-SGD. Do you think it is possible to only use a linear loss? Or in other words, will your proposed method can be applied in this real deep learning case?

Obviously, training with a linear loss would result in non-convergence of DP-SGD, so we don't recommend doing that. :-) Our thesis is that, in the last iterate setting, for the privacy analysis, we can pretend that we have a linear loss to give a heuristic privacy analysis. This heuristic privacy analysis is optimistic, but it may be closer to the "true" privacy loss than the standard pessimistic DP-SGD analysis. We argue that this is a useful/interesting perspective to add to practical private deep learning, although it still leaves open many questions.

We thank the reviewer for their thoughtful comments. We address their main concerns:

• I don’t know how useful the heuristic analysis would be in practice.

We believe that such a “sanity check” is useful in practice. In practice, often the standard $\varepsilon$ DP parameter is uncomfortably large and we seek additional validation through methods like privacy auditing. Our heuristic can provide additional validation, which is particularly useful because it is easy to do privacy auditing incorrectly, which gives a false sense of security.

More importantly, beyond immediate practical impact, we hope that our work leads to further scientific exploration of the privacy implications of the last iterate setting. In other words, our work identifies a phenomenon and proposes an explanation (and also challenges that explanation). Thus we believe that our work is valuable as basic science, even if the heuristic is not immediately useful.

• The empirical study of the heuristic looks to be very thorough, but sparse on interpretation. I would have appreciated more discussion on the figures, and didn’t really feel like there was a strong take-home message from the paper.

Space permitting, we will add further discussion of the experimental results in the revision (the camera ready allows an extra page of content).

Overall, we attempted to present the results in a neutral manner, to let readers draw their own conclusions. In particular, we put a lot of effort into probing the limitations of our heuristic. (E.g. Section 4 shows that our heuristic can be too optimistic and Figure 2 shows that it doesn’t fully explain the gap between theoretical analyses and empirical results.)

The take home message is (i) that the last iterate setting is interesting and there is a gap between the upper bounds we can prove and the lower bounds we get empirically; and (ii) that we give a heuristic that seems to capture a major reason for this phenomenon.

• Algorithm 1 is DP-SGD with a regularizer, but in practice it is somewhat rare to use explicit regularization with DP-SGD.

The regularizer can always be set to 0 or incorporated into the loss function, and this is how DP-SGD is usually presented for simplicity. So the regularizer does not change the validity of our heuristic.

The reason we included the regularizer is that it is convenient for the counterexamples in Section 4 to not have gradient clipping. But if we instead removed clipping of the loss gradients, then the standard DP-SGD analysis would be invalid. Having an unclipped regularizer doesn’t invalidate the standard DP-SGD analysis, but allows us to include counterexamples with arbitrary gradients.

• If one of the advantages of the heuristic is that it’s less computationally expensive than privacy auditing, but you’ll have to do the computationally expensive privacy auditing anyway (in order to compare), then what is the point?

One use case would be selecting hyperparameters (noise multiplier, batch size, learning rate, etc.). I.e., use our heuristic to consider many settings of the hyperparameters and select the one that is predicted to work best in terms of privacy auditing. But only actually perform privacy auditing once on the final choice of hyperparameters.

• One of the disadvantages of privacy auditing is that it’s difficult to perform correctly, but the heuristic doesn’t have rigorous theoretical guarantees. If privacy auditing and the heuristic don’t agree, then how would you know which one was wrong?

That is a great question! The standard DP-SGD analysis gives an upper bound on $\varepsilon$, while privacy auditing gives a lower bound. In practice, there is usually a large gap between these numbers. The question that we face is which of the two is closer to the truth. Our heuristic gives a third number which falls between the upper and lower bounds and which has some principled justification. The heuristic thus hopefully helps answer that question.

2. In Figure 3, why does the heuristic $\epsilon$ scale with the number of iterations $T$? Since the heuristic is a last-iterate analysis, I would have imagined that it would converge to a constant?

Note that the heuristic $\varepsilon$ is minimized around $T=1/q$. At this point there is approximately a $e^{-1} \approx 0.36$ probability that the canary example is never sampled, which provides a lot of privacy. As $T$ increases, the probability that the canary is sampled at least once increases, but eventually it does converge.

3. Would it be possible to extend Theorem 1 to non-regularized DP-SGD?

The regularizer can be set to 0.

It’s not obvious to me why the privacy guarantee for an arbitrary loss would be similar to the privacy guarantee for a linear loss (and not even a GLM loss, mind you).

This is the main thesis of our paper and it is indeed surprising!
The main justification is our experimental results which show that linear losses do seem to represent the worst case for real deep neural networks It has been observed in the practice that the worst case examples for privacy auditing have gradients that are constant across iterations, which corresponds precisely to linear loss functions.

Unfortunately, we cannot formally prove that linear losses are representative of general losses, since our counterexamples show that this is not true for pathological examples. However, as discussed in Appendix B, in the full batch setting, we can actually prove that linear losses are the worst case.

I feel like the proof of Theorem 1 is hard to appreciate without knowing more technical preliminaries

We will endeavor to make the proof more accessible to different audiences.

We hope that the reviewer reconsiders their recommendation in light of our responses.

Thank you for the comment. We respond below. We hope that we have been able to clarify all the issues before the discussion ends.

Using the heuristic for hyperparameter selection is an interesting idea. But I’m a little unclear on the exact set-up, and why the hyperparameters would be chosen according to privacy auditing (instead of according to utility).

Hyperparameters would need to be chosen to achieve both high utility and low privacy loss. The "ideal" is to calibrate the hyperparameters so that the standard analysis of DP-SGD gives a good privacy parameter $\varepsilon$.

For better or worse, it is becoming accepted practice to set the standard $\varepsilon$ to large-ish values (e.g. $10$ or $20$). One way to justify this practice is to perform privacy auditing on the final model to argue that this large $\varepsilon$ is overly conservative. This is one of the practical motivations for work on privacy auditing.

The use case for hyperparameter tuning that we envisage is that one has dual privacy constraints, say, $\varepsilon_{\text{standard}} \le 10$ but also $\varepsilon_{\text{auditing}} \le 1$. Our heuristic would help evaluate the latter constraint during the hyperparameter selection phase. This use case is analogous to scaling laws on the utility side.

That said, we reiterate that we think this work is more about basic science than about immediate applications. Progress on both sides -- provable DP upper bounds for ML and empirical privacy auditing lower bounds -- has been slowing down without converging. The goal of our work is to offer a fresh (if somewhat unorthodox) perspective -- our heuristic is neither a provable upper bound nor a lower bound; it should be somewhere in between.

if I’ve understood correctly, Theorem 1 implies that the heuristic will always be smaller than the existing -DP bound.

Yes. This is true by the postprocessing property of DP. (The standard analysis assumes all intermediate iterates are revealed. Our result is tight for when only the sum is revealed, which is a postprocessing.)

But there doesn’t seem to be a strong connection between privacy auditing and the heuristic apart from the empirical observation that the heuristic is larger than the privacy auditing bound

This is supported by the experimental evidence, plus the observation repeated in the literature that the best privacy auditing results (i.e. worst case for privacy) are when the canary examples have the same gradient in each iteration, which corresponds to linear losses. (I.e., prior work shows that "gradient space attacks" are better than "input space attacks.") The best theoretical justification is the fact that we know that linear losses achieve the worst case in the special case of full batch training (as discussed in Appendix B).

I hate to say that 33,000 GPU hours aren’t enough to convince me on this, but I do feel that I would need to see the empirical observation validated across a wider range of problems and datasets (i.e., not just CIFAR10)

That is a fair point. But this limitation is also true of the privacy auditing literature more generally. The vast majority of experimentation is on CIFAR10 and smaller datasets. This is simply because privacy auditing generally requires many training runs, which is prohibitive for anything larger.

It's important to note that the claim that our heuristic upper bounds privacy auditing results for "realistic" models & datasets is falsifiable (at least to the extent that "realistic" is clearly-defined). Our hope is that any future privacy auditing work would compare to our heuristic. If they fail to exceed our heuristic, then the claim gains more weight. If they do exceed our heuristic, then that would represent significant progress on privacy auditing.

We thank the reviewer for their time and comments. We address their points below.

the fact that the privacy adversary has access to all intermediate iterates of the training process makes DP-SGD overly conservative is quite well-known.

The reviewer’s claim that this phenomenon is well-known is debatable. While there are a handful of papers that prove separations between the standard analysis and the last iterate setting, there are also papers that tell the opposite story by proving that DP-SGD (with the standard analysis) is optimal in some sense. We believe that many practitioners are not aware of this limitation of the standard analysis of DP-SGD.

In any case, the contribution of our work is to not only identify the phenomenon, but also to provide a heuristic that helps explain why this phenomenon arises and to study it experimentally.

I find its applicability limited since it cannot be extended to general ML tasks where the loss functions are not linear.

Our manuscript is forthcoming about the fact that our analysis is only a provable bound for linear loss functions and is only a heuristic when applied to general ML tasks. Our thesis is that, in terms of privacy of DP-SGD, linear loss functions are a reasonable model for most general ML tasks, which is supported by experimental evidence.

We hope that our work inspires further research into the last iterate setting of DP-SGD.

Why does the example provided in Section 4.2 show linear loss is a good approximation of many convex losses? Could you please provide some more insights?

Section 4 probes the limitations of our heuristic. In Section 4.2 we tried to find a convex loss function that violates our heuristic.The largest violation we could construct is an $\varepsilon$ that is 3% higher than our heuristic. While this technically violates our heuristic, the violation is quite small, which overall supports our thesis that the heuristic is a good approximation.

We thank the reviewer for their thorough reading of our paper and thoughtful comments. In particular, we appreciate the reviewer spotting several typos, which we will fix. We respond to the main questions:

• I am confused by L234. The authors propose to maximize their heuristic over all $t \le T$, while beforehand (e.g. in Figure 1/Section 2) they advocated to computing the heuristic for a single $T$. Which one is the exact proposed heuristic by the paper?

This is in Section 4, where we probe the limitations of our proposed heuristic. Section 4.1 illustrates the limitations of computing the heuristic for only the total number of iterations $T$. Thus in Section 4.2 we maximize over $t \le T$ to show limitations that go above and beyond what is in Section 4.1.

The heuristic that we propose is simply to run with a single number of iterations $T$, but with the caveat that it is a heuristic and has known limitations, including non-monotonicity in $T$.

• In Figure 2, I am not sure how we adapt existing techniques to the last-iterate-only setting? Can the authors explain in more details?

We are not sure we understand this question. The line labeled “standard” in our figures is not adapted to the last iterate setting. The figures illustrate that there is a large gap between the existing upper and lower bounds, which motivates our work, and our heuristic partially explains this gap.

• Can the authors explain in Figure 1, what network and dataset were used?

Figure 1 does not include NN experiments (unlike the other figures). It simply compares our heuristic to some mathematical baselines in different parameter regimes.

I am not sure if the structure of the proposed DP counterexamples in Section 4 is novel,

To the best of our knowledge these counterexamples are novel. However, after the NeurIPS submission deadline we have learned of subsequent related work that may reproduce some of these.

What I am not as confident in is if the heuristic, which by authors' own admission does not provide rigorous upper or lower bounds, will be useful in practice.

This is a very important question. :-) We believe that our heuristic can be useful in practice as a “sanity check.” E.g., in practice, the standard $\varepsilon$ DP parameter is often uncomfortably large (e.g., $\varepsilon=20$) and additional validation, such as privacy auditing, is used to justify tolerating this. Our heuristic can provide additional validation, which is particularly useful because it is easy to do privacy auditing incorrectly, which gives a false sense of security.

More importantly, beyond immediate practical impact, we hope that our work leads to further scientific exploration of the privacy implications of the last iterate setting. In other words, our work identifies a phenomenon and proposes an explanation (and also challenges our own explanation). Thus we believe that our work is valuable as basic science, even if the heuristic is not immediately useful.

We hope that we have addressed the reviewer’s comments and that they reconsider their recommendation.

Re: I am confused by L234.
Ans: My confusion stems from the fact that by maximizing $\epsilon$, the authors take the most sound and least tight (I am using these terms here loosely, referring to their meanings for the empirical and provable DP guarantees cases, respectively) prediction they make across all $t$. Thus, despite the heuristic producing too low $\epsilon$s for many $t$, the authors report that for the “best” $t$ they are close to the counterexamples they find.

Re: In Figure 2, I am not sure how we adapt existing techniques to the last-iterate-only setting? Can the authors explain in more details?
Ans: My question is regarding the Empirical attack in Figure 2. The authors say they adapt the empirical attack to the last-iterate DP setting. My question was if the authors could provide details on how this is done?

Re: Can the authors explain in Figure 1, what network and dataset were used?
Ans: Can the authors describe how the plot and the heuristics themselves are compiled in more detail?

Re: I am not sure if the structure of the proposed DP counterexamples in Section 4 is novel.
Ans: I would also like to ask other reviewers who are more familiar with SOTA DP research to confirm this. Also, I would request that if they also find it novel, to take this into account in their reviews.

Re: What I am not as confident in is if the heuristic, which by authors' own admission does not provide rigorous upper or lower bounds, will be useful in practice.
Ans: I find the first part of the author’s answer here very useful. I would suggest that they include it more prominently in the paper. Regarding the second part of the answer --- I think the proposed counterexamples in Section 4 strongly suggest that general last-iterate DP guarantees are likely the same as full DP. That said, they also suggest that they are the same only for very artificial examples that only happen for extremely unrealistic models. Do the authors have any suggestions on how the DP definitions in the last-iteration case can be amended to make their worst case closer to DP-SGD executed on real networks? Maybe something related to progressing the loss during training?