- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper studies black-box auditing of differentially private machine learning methods under Rényi DP. Using the variational representation of the Rényi divergence, and combine with the existing method on black-box auditing.
Critical strengths
This paper proves the sample complexity and demonstrate tighter results than the prior work.
Critical weaknesses
I think this paper missed an important literature [1]
- The paper said we are the first to directly audit RDP, what about [1]? They also audit RDP.
- This paper uses variational representation approach, [1] also use it.
[1] DP-Auditorium: a Large Scale Library for Auditing Differential Privacy. S&P 2024.
Questions for authors
- Can you clarify the technical difference between yours and DP-Auditorium?
- Does your algorithm need a single run or many run? In Alg 3, each run needs T iterations.
- I see your method has tigher estimation in Table 1-2. But does your method introduce extra overhead than the method you compare?
2 comments
Q2: Algorithm runs: one or multiple?
Thank you for the question. Our auditor operates in the black-box (where we can only observe the final outputs) regime where producing a tighter audit requires several iterations. This is standard in black box auditing when attempting to produce a tight lower bound audit, see [7][8], and see [9][10] where only one run is done but a loose audit is produced.
Q3: Extra overhead when compared to the current SOTA method.
Both methods use the same number of blackbox samples, the main overhead cost in performing the audit (the T iterations). The operations after introduce negligible overhead (over 50 GPU hours on an A100 cluster vs seconds for everything else for both audits) We train a small NN after to estimate the Rényi divergence, while [8] uses a decision threshold to obtain FPR/FNR results which are converted to confidence bounds which are used to calculate a lower bound GDP estimate which is converted to RDP.
Thank you again for your feedback as well as time taken to improve our manuscript. We hope that we have resolved your concerns regarding differences between DP-auditorium [1] and would consider raising your score if so. Please let us know if you have any additional questions, we are happy to answer while the rebuttal period is still open.
References
[1] Kong et al. DP-Auditorium: a Large Scale Library for Auditing Differential Privacy. S&P 2024.
[2] Donsker and Varadhan. Asymptotic evaluation of certain Markov process expectations for large time, IV. Communications on Pure and Applied Mathematics, 1983.
[3] Anantharam. "A variational characterization of Rényi divergences." IEEE TIT
[4] Belghazi et al. "Mutual information neural estimation." ICML 2018.
[5] Birrell et al. "Variational representations and neural network estimation of Rényi divergences." SIMODS 2021.
[6] Jagielski et al. "Auditing differentially private machine learning: How private is private sgd?" NeurIPS 2020.
[7] Nasr et al. "Tight auditing of differentially private machine learning." USENIX Security 2023. Distinguished Paper Award.
[8] Muthu Selva Annamalai et al. "Nearly tight black-box auditing of differentially private machine learning." NeurIPS 2024.
[9] Steinke et al. Privacy Auditing with One (1) Training run. NeurIPS 2023. Best Paper Award.
[10] Mahloujifar et al. "Auditing f-differential privacy in one run." ICML 2025.
[11] Cebere et al. Tighter Privacy Auditing of DP-SGD in the Hidden State Threat Model. ICLR 2025.
[12] Pillutla et al. Unleashing the Power of Randomization in Auditing Differentially Private ML. NeurIPS 2023.
[13] Feng and Tramèr. Privacy Backdoors: Stealing Data with Corrupted Pretrained Models. ICML 2024.
[14] Xiang et al. Privacy Audit as Bits Transmission: (Im)possibilities for Audit by One Run. USENIX Security 2025.
We thank Reviewer NRth for their review and pointing us to relevant work. We are glad you found strength in our theoretical results. Please find our responses to your questions and concerns.
W1: DP-auditorium [1] also auditing Rényi-DP
Thank you for pointing us to this relevant work. We acknowledge the work of [1], and we cite it in section 1.1 of our paper. We mistakenly claim to be the “first” in the open review TL;DR, and in our contributions in which we have updated our manuscript. We again apologize for this mistake and hope it can be overlooked in consideration of our manuscript.
W2: Variational representation of the Renyi divergence used in DP-auditorium [1]
Thank you for this comment. The variational representation of the KL divergence originated in Donsker Varadhan’s representation of the KL divergence [2] and extended to the Rényi Divergence in [3]. Neural network based approaches are used in [4],[5]. These formulations for lower bound estimates are well known to the statistics community [1, section 1.1].
Q1: Technical differences between our work and DP-auditorium [1]
Thank you for asking for this clarification. Both works use the variational representation of the Rényi divergence to estimate RDP. Please find the main technical differences below from our paper below.
Theoretical Differences:
Our confidence bound holding over thee whole critic class vs theirs only holding for a singular critic: Our confidence bound holds over the whole critic class, while theirs only holds for a single fixed critic. Since the critic is chosen by looking at the data, their bound only applies if the critic is trained on one half of the samples and evaluated on the other half. Ours applies directly to the critic the trained neural network finds, using all the samples. This matters in realistic auditing settings (private learning such as dp-sgd), since it would mean setting aside half of the DP-SGD training runs to perform the audit which is very computationally expensive.
Matching lower bound: we also prove a lower bound in theorem 3 showing that any confidence bound that holds over the whole critic class needs at least Ω(d/ε2) samples, so the rate in theorem 2 cannot be improved. [1] does not provide a lower bound and we cannot tell if their sample complexity is tight or not. We also provide more general upper and lower bounds in the appendix for our auditor in Theorems 1,5, and 6 in our manuscript.
Audit algorithms output: Our auditing algorithm outputs a lower bound ε estimate, while [1] outputs a pass / fail against a certain threshold. A pass / fail only tells us if the divergence is above the tested threshold, meanwhile a lower bound ε estimate gives us more insight to how much privacy a mechanism leaks.
Experimental Differences