How Well Can Differential Privacy Be Audited in One Run?

Thank you for taking the time to read our work and share your feedback!

Your point about the challenges of squeezing so much content into the conference format is well-taken. Thanks to your comment, we have been working on streamlining the content of the main body so that the reader will not need to turn to the appendix for essential definitions. (For example, we have moved the definition of the “Count-In-Sets” algorithm (including the $s(n)$ notation) to the main text.) These changes have significantly improved readability, so thanks!

You are correct that in the typical high-dimensional settings, the interference between random canaries is small. Dirac canaries simply completely eliminate this interference and therefore have a small advantage (as studied by Nasr et al. in their Appendix B.1), and hence we (and Steinke et al.) focus on this model. It’s a nice point, though, and we have added a brief mention of it. The approaches we introduce and the phenomena we analyze, such as the tradeoff when increasing the number of elements beyond the dimension, generalize beyond DP-SGD and beyond this specific attack, and will have similar consequences if one were to use random canaries in a high-dimensional setting.

Thanks for reading our work and sharing your detailed feedback!

We completely agree that our paper, which maps one-run auditing’s fundamental capabilities and limitations, highlights the importance of future work that will further explore the empirical performance of one-run auditing in a range of real-world settings. While this is out of scope for our paper, there is clearly a lot that could be done.

We would be glad to use some of the one additional page in the camera-ready version to move up some of the results we have on Adaptive One-Run Auditing from the appendix to the main body—on its validity, its maximal efficacy improvement, and on Adaptive ORA of the Count-In-Sets algorithm (the simplified algorithm that captures the essence of auditing DP-SGD). This will help the reader appreciate how AORA is not only immune to the increased interference when adding more elements per coordinate, but actually can only benefit from such added elements. We also have some additional experimental results on Adaptive ORA of DP-SGD (in the same setting as the other DP-SGD experiments) that we omitted from the submission; this felt like too much to try to squeeze into the paper to us, but if you think it is important, we can try to also fit it in.

Thanks for the PANORAMIA reference; we’ll check it out and incorporate it.

We actually don’t think our modeling assumptions (focus on pure DP, case-study with arbitrary gradients) represent a weakness. Since our goal is to expose the limitations of one-run auditing, we intentionally study a setting that is favorable to one-run auditing.

The $S$ vector is randomly sampled to determine the input dataset and the guesser has no access to it, as in the ORA setting that Steinke et al. define.

Thanks for the formatting and notation suggestions—those are well-taken and we’ll incorporate them.

Regarding your specific questions:

• Data distribution - We follow the setting of Steinke et al. (“Privacy Auditing with One (1) Training Run”) in which the canaries are sampled independently uniformly. A recent work by Swanberg et al. (“Beyond the Worst Case: Extending Differential Privacy Guarantees to Realistic Adversaries“, Sections 3.1 and 3.2) extends their method to arbitrary product distributions. The gaps that we discuss also exist with this sampling scheme - the guesser still faces non-worst case output, non-worst-privacy for elements, and it still suffers from the uncertainty about the other elements. Therefore, our analysis can be extended to this case, taking into account the non-uniform input distribution.

  Auditing with real data (as canaries or as non-canaries) does not change the sampling (the distribution of the sampled vector S) so our analysis covers this case.

• Threshold selection - Choosing the threshold is an interesting problem, and it is a non-trivial task even in classic auditing. However, it is somewhat orthogonal to our focus on the inherent limitations of ORA. As Steinke et al. (“Privacy Auditing with One (1) Training Run”, Section 6) point out, one can use sample splitting to choose an optimal guessing threshold, that is, use a different set of observations to select the threshold and another set of the data for the auditing itself. Formalizing a way to choose the threshold without sample splitting is an interesting research direction.

• f-DP and Renyi-DP - We analyze the ORA method of Steinke et al. (“Privacy Auditing with One (1) Training Run”), which audits pure DP and approximate DP. As we discuss in the introduction, we focus on auditing pure DP to zoom in on the limitations of ORA, as auditing approximate DP may create additional gaps. The work of Mahloujifar et al. on auditing f-DP in one run focuses on bridging these additional gaps resulting from the lack of tightness in the approximate DP analysis, and hence doesn’t speak to the pure-DP gaps that our paper studies. Our work shows that average-case relaxations characterize the efficacy of ORA, even though ORA aims to measure the pure DP level, which is characterized by the max divergence.

• Informing auditing in practice - Great point, thanks. We will add something on this to the conclusion. Our results indeed can be used to guide a privacy auditor on when to use ORA, how to use it, and how to interpret the results:

  • ORA should be used only if ORA has high optimal efficacy with respect to the audited algorithm. When auditing algorithms that severely suffer from the gaps of ORA (e.g., an algorithm for releasing noisy counting queries), multi-run auditing should be used.
  • Our results can guide the choice of the canaries and the guesser, and our multiple canaries per dimension and Adaptive ORA approaches can increase the efficacy of auditing.
  • Our results highlight that auditing results should not be treated as privacy level estimations, but rather only as lower bounds, and should be interpreted in light of the optimal efficacy.

  When using ORA, we recommend reporting the number of canaries used, the optimal efficacy of ORA with respect to the audited algorithm, and other details which are important for the interpretation of the results (aligned with the “Auditing Card” approach proposed by Annamalai et al. (“The Hitchhiker’s Guide to Efficient, End-to-End, and Tight DP Auditing”, Section 7.3).

• Auditing under distribution shift - We have not considered post-hoc privacy auditing methods under distribution shift. We will explore this complementary approach.

Thanks so much for answering my questions and incorporating the suggestions esp regarding related work and distribution shifts use case. I have increased my score.

Thank you for taking the time to read our work and share your feedback!

We completely agree that our paper, which maps one-run auditing’s fundamental capabilities and limitations, highlights the importance of future work that will further explore the empirical performance of one-run auditing in a range of real-world settings. While this is out of scope for our paper, we think you lay a good roadmap for what some of that future work could do.

We also agree that there is room for future research extending our formal results to approximate DP. That said, our results should already have strong relevance to the approximate DP setting, since for reasonable values of delta, the reasons for the gaps still apply and similar results will hold. For example, consider the Name and Shame algorithm that randomly selects an element and outputs it. When applying ORA, the auditor can guess only one element better than random, and hence for any reasonable value of $\delta << \frac{1}{n}$ that one sets as input for auditing, ORA would discover a bound on epsilon close to $0$ (despite the true value being infinity). More generally, for very small delta, an $(\epsilon, \delta)$-DP algorithm "most of the time’’ must behave "similarly" to an $(\epsilon, 0)$-DP algorithm with respect to any element of its input, which doesn’t leave much opportunity for ORA to leverage.

On the empirical side, in our DP-SGD experiments we set $\delta=10^{-5}$. We note that for this delta, with the number of elements and guesses that we use, the "fixing term" (derived by Steinke et al. in "Privacy Auditing with One (1) Training Run") that adjusts the epsilon-DP bounds of ORA to account for delta is negligible. For example, with $1,000$ elements, and $70$ accurate guesses out of $100$ taken guesses, the difference between the resulting epsilon bounds (accounting for the delta vs. not accounting for the delta) is approximately $2.5 \cdot 10^{-3}$. In addition, Steinke et al. (Figure 12) have empirically explored the effect of delta on their auditing results. Their results align with our observation that when $\delta << \frac{1}{n}$, the effect of delta is negligible.

Thanks for the concrete suggestion to include more on Adaptive One-Run Auditing in the main body of the paper. We would be glad to use some of the one additional page in the camera-ready version to do exactly this, moving up some of the results we have in the appendix on its validity, its maximal efficacy improvement, and on Adaptive ORA of the Count-In-Sets algorithm (the simplified algorithm that captures the essence of auditing DP-SGD). This will help the reader appreciate how AORA is not only immune to the increased interference when adding more elements per coordinate, but actually can only benefit from such added elements. We also have some additional experimental results on Adaptive ORA of DP-SGD (in the same setting as the other DP-SGD experiments) that we omitted from the submission; this felt like too much to try to squeeze into the paper to us, but if you think it is important, we can try to also fit it in.

We liked your suggestions for further enhancement and are working on implementing them. We actually already created such a diagram in slides on this work, and agree that it would be nice to include it in the paper. We agree that more algebraic details can be pushed to the appendix to improve flow and free up space for other content that is more essential to the main body. And a table of symbols is also a nice idea.

Thank you for taking the time to read our work and share your feedback!

We agree that, following on from this paper, larger-scale empirical studies of one-run auditing, including in the black-box setting, are an important avenue for future work.

A few brief thoughts on these directions:

• We expect that ideas we have explored in the white-box auditing model will also prove relevant in the black-box model. For example, similar phenomena when increasing the number of canaries were empirically observed in the black-box setting by Steinke et al. Furthermore, our theoretical analysis of the sum of the gradients should also be relevant for black-box auditing. (Black-box membership inference attacks using the gradient [1] or Hessian [2] at the final model are known to be stronger than attacks that use only the model predictions [1, 2], and under the KKT conditions the model can be represented as a weighted sum of the gradients of the loss w.r.t. the training points [3].)
• A thorough investigation of Adaptive ORA for the black-box setting will require the development of more sophisticated black-box attacks designed to exploit partial knowledge about other elements, a challenging (and fascinating) future direction.

[1] Pang, Yan, et al. "White-box Membership Inference Attacks against Diffusion Models." Proceedings on Privacy Enhancing Technologies (2025).

[2] Suri, Anshuman, Xiao Zhang, and David Evans. "Do Parameters Reveal More than Loss for Membership Inference?" Transactions on Machine Learning Research.

[3] Smorodinsky, Guy, Gal Vardi, and Itay Safran. "Provable Privacy Attacks on Trained Shallow Neural Networks." arXiv preprint arXiv:2410.07632 (2024).

Thanks for answering my question. I will keep my positive score.