Auditing $f$-Differential Privacy in One Run

Authors: Saeed Mahloujifar, Luca Melis, Kamalika Chaudhuri
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Differential privacy, Auditing privacy

Abstract:
Empirical auditing has emerged as a means of catching some of the flaws in the implementation of privacy-preserving algorithms. Existing auditing mechanisms, however, are either computationally inefficient -- requiring multiple runs of the machine learning algorithms —- or suboptimal in calculating an empirical privacy. In this work, we present a tight and efficient auditing procedure and analysis that can effectively assess the privacy of mechanisms. Our approach is efficient; similar to the recent work of Steinke, Nasr, and Jagielski (2023), our auditing procedure leverages the randomness of examples in the input dataset and requires only a single (training) run of the target mechanism. And it is more accurate; we provide a novel analysis that enables us to achieve tight empirical privacy estimates by using the hypothesized $f$-DP curve of the mechanism, which provides a more accurate measure of privacy than the traditional $\epsilon,\delta$ differential privacy parameters. We use our auditing procure and analysis to obtain empirical privacy, demonstrating that our auditing procedure delivers tighter privacy estimates.

Decision: reject
Reviewer scores: 6, 3, 8, 8

Reviews and discussion:
<thread>
creation date:
1730281710774

thread_type:
official_review

<thread_object>
creator: reviewer_r2zh

<content>
summary:
This paper proposes a computationally efficient privacy auditing procedure by leveraging the f-DP curve, and shows that the resulting lower bounds are tighter than those of previous work.

strengths:
The paper is well-motivated and, for the most part, clearly written. It provides a notable improvement over prior privacy auditing techniques.

weaknesses:
The paper contains some ambiguities and cosmetic errors that should be addressed to improve clarity and overall presentation.
1) clarify that by "one run" you mean a training run (rather than an inference run)
2) explicitly state the limitation of Steinke et al. (2023) that you are addressing (in Line 80-82)
3) change the references to algorithm 3.1 to algorithm 3 (given that that is what the algorithm is called)
4) remove double mentions of Steinke et al. by just using the reference instead (e.g., in Line 420)
5) fix the reading flow in Definition 6 (second bullet point is not a full sentence)
6) correct typos (e.g., Line 194/195, 307, 466, 505/506) and wrong capitalizations in the middle of sentences (e.g., Line 100)

questions:
1) What do you mean by "gubernatorial analysis"? (Line 95)
2) Do you have an intuition why the bound in Steinke et al. (2023) degrades with higher numbers of canaries while your bounds continue to improve?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730708251501

thread_type:
official_review

<thread_object>
creator: reviewer_qcyn

<content>
summary:
The paper presents a novel algorithm designed to audit $f$-DP guarantees within a single execution of a mechanism.
This area of research has become increasingly significant within the privacy community, particularly due to the limitations of existing auditing mechanisms.
Existing empirical auditing methods are either computationally expensive (requiring multiple runs of the machine learning algorithm) or fall short in providing a tight empirical privacy guarantee.
The need to run the mechanism multiple times has hindered practical applications.
Steinke et al. (2023) introduced a pioneering approach that balances the number of runs with the tightness of the audit.
This present work enhances this trade-off further by auditing $f$-DP guarantees, which provide a more precise representation of a mechanism's privacy compared to traditional approximate DP parameters.

strengths:
- Valuable Contribution to Existing Research: There has been extensive work on auditing differential privacy guarantees. This paper distinguishes itself by offering a solution that enhances both computational efficiency and the precision of empirical privacy guarantees. The reliance on multiple runs of the mechanism has been a major obstacle to the widespread application of auditing methods. Their approach, requiring only a single run, makes auditing significantly more practical, especially for complex machine-learning algorithms involving extensive model training.
- Using the $f$-DP framework is a particularly strong aspect of this work. $f$-DP offers a more general and accurate representation of a mechanism's privacy compared to traditional approximate differential privacy. This choice allows for a more fine-grained and robust analysis of privacy. The authors convincingly demonstrate that auditing $f$-DP leads to tighter empirical privacy assessments. By performing the analysis in a single training run, the paper achieves a more comprehensive understanding of the privacy implications within a practical computational framework.

weaknesses:
- The main weakness of this paper is its presentation. The write-up seems very rushed which at times hinders the flow of the reader. Many references are broken e.g. reference to Algorithm B. Lines 300-312 contain many typos and incomplete sentences. These are issues that can be addressed quickly but in the current state I would argue that the presentations limits the value of this work to the community.
- The authors have not provided a code artifact. While the contributions of this work are mostly theoretical, the implementation of the algorithm requires care and it would help reproducibility if a code artifact were supplied.

questions:
- On the section “Empirical Privacy” line no 307, why do the trade off curves need to be ordered? If you have a set of trade off curves $f_i$ that pass couldn’t you build a new trade off curve $f(x) = \min_i f_i(x)$ 
- In what sense are the empirical results tight in Fig 7 and why is that not also evident in Fig 1?
- Can you explain why abstentions are important in this algorithm?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730711711446

thread_type:
official_review

<thread_object>
creator: reviewer_cu1c

<content>
summary:
The paper presents a novel algorithm for auditing differential privacy (DP) mechanisms in a single run, building upon and extending the work of Steinke et al. (2023). By leveraging the theoretical framework of f-Differential Privacy (f-DP), the authors provide tighter lower bounds on privacy leakage, thereby enhancing the existing toolbox for f-DP analysis. Notably, their auditing algorithm can be applied to various adversaries beyond the standard membership inference, such as reconstruction attacks.

strengths:
* **Advancement of f-DP Tools**: The paper contributes to the understanding and practical application of f-DP, which could be of independent interest.
* **Interesting Problem**: Auditing DP mechanisms in a one-run scenario is interesting for practical implementations (particularly in the black-box scenario, see the weakness section), and the paper makes significant progress in this area.
* **Experimental Validation**: The experimental results are compelling and demonstrate the effectiveness of the proposed approach.
* **Versatility in Adversarial Models**: Extending the auditing algorithm to handle different adversaries, such as reconstruction attacks.

weaknesses:
The authors investigate exciting problems and provide interesting results. I encourage the authors to continue working on these results, as they are sound and exciting to the DP community. However, I don’t think the work is ready to be published in its current form, as it is somewhat rushed. I sketch my main concerns below.
* **Writing and Presentation Quality**: The manuscript contains several errors and unclear explanations. The authors should revise it before publication, as there are plenty of writing errors and bad citing style.
* **Unreferenced Figures and Results**: Some results, particularly those in Figure 7, need to be adequately referenced or explained within the text, leading to confusion about their significance.
* **Incomplete Explanation of Gaps**: The paper needs to explain the gaps between theoretical and lower bounds. Possible reasons for these gaps should be analysed, such as limitations of the f-DP framework, assumptions made in the analysis, or practical considerations in implementation.
* **Insufficient Experimental Details**: There are no experiments in the black-box setting for which we are compelled to use one-shot auditing. The white-box setting enjoys a tight and efficient auditing algorithm (Nasr et al., 2023), while the black-box algorithms are rather expensive.

questions:
Questions:
* You claim that your approach achieves tighter results as the number of canaries increases, outperforming the empirical privacy results from Steinke et al. (2023), suggesting that the results can be tight as we increase the number of canaries. Could you elaborate on why your bounds continue to improve with more canaries while the bounds in previous work degrade? What underlying mechanisms in your algorithm contribute to this improvement? Citing the authors: ” Figure 1 demonstrates that our approach outperforms the empirical privacy results from Steinke et al. Interestingly, while the bound in Steinke et al. (2023) degrades as the number of canaries increases, our bounds continue to improve.”
* What potential sources contribute to any lack of tightness in your lower bounds? Are there specific aspects of the f-DP framework or your implementation that introduce looseness? How might these be addressed in future work to enhance the tightness of the bounds?
* How does your algorithm perform in the black-box setting compared to the white-box setting? Can you provide detailed experimental results illustrating this performance?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732228020914

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
A summary of changes in our revision

comment:
We thank all reviewers for their constructive feedback. We have updated the paper to address the reviewers concerns and suggestions. To summarize, we have made the following changes:

- Added clarification, discussion and insights on why our bounds behave differently from previous work. (Paragraphs starting in lines 84, 186, 216 , 492, 1185)
- We ran new experiments in the black-box settings and compared our bounds with previous work. (Figures 2 and 4 in the revised paper.)
- We enhanced the presentation of the paper, fixed typos and resolved broken references. 
- Added a definition for empirical privacy estimation to clarify how we exactly measure empirical privacy. (Definition 7 and revised version of definition 6)
- Added code snippet to address the reproducibility concerns raised by reviewers. (Pages 24-27)
- Moved the proof and some of the experiments to appendix to open space for the new discussions and experiments.
- Added more discussion on previous work on privacy attacks and auditing. (Page 5, lines 255-273)

We hope these changes have addressed the reviewers' concerns and would welcome any additional feedback.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732576974544

thread_type:
official_review

<thread_object>
creator: reviewer_xljh

<content>
summary:
This paper proposes an approach for auditing the guarantees of a differentially-private algorithm, which in contrast to other existing auditing schemes, does not require re-training of the model. In addition, the approach provides tighter bounds that the related work by Steinke et al.

strengths:
-The existing literature on privacy auditing is clearly reviewed as well as the main limitations of existing approaches. 

-The paper is well-written and easy to read. The authors have also provide a clear introduction of the notions necessary to the understanding of their work such as the f-DP curve.

-The proposed approach has the benefit of only requiring a single run of the mechanism. The relationship with the method of Steinke at al. is also clearly explained. One of the main novelty of the approach is also to connect the privacy auditing procedure with previous works bounding the accuracy of reconstruction attacks.

-The experiments conducted demonstrate that the approach proposed performed better in terms of the tightness of the bound estimated when the noise added is a a low to high regime.

weaknesses:
-Some notions such as the concept of empirical privacy could have been more formally defined. Other important details are missing such as the relationship between the way canaries are designed and the quality of their possible reconstruction as well as the design of the function f that should be considered for the auditing. 

-The number of canaries needed for the experiments is very high and is likely to have a significant impact on the utility of the classifier learnt. While an experiment has been conducted with CIFAR-10 to measure the impact of the introduction of 5000 canaries more experiments should be conducted by varying the number of canaries to observe in a more fine-grained manner the impact of the introduction of canaries.

-The approach has been validated empirically only on one dataset. Additional experiments at least two other datasets should be conducted to validate how well the approach generalizes to other settings. 

-There are some minor typos that could be corrected in a future revised version. For instance, "(e.g., [1])." seems to refer to a different bibliography style. Other typos : "an attack algorthm A" should be "an attack algorithm A", "in Essene" should be "in essence" and "augumented multiplicity" should be "augmented multiplicity"

questions:
-Can you discuss more how the design of the set of canaries impact the reconstruction games?

-Apart from the classical example of differential privacy, can you provide a few other examples of function f that could be audited using your framework?

-Can the approach be used on classifiers for other types of data such as for example tabular data?
</content>
</thread_object>

</thread>


Metareview:
metareview:
## Summary of Contributions

This paper studies auditing of differential privacy (DP) with one run of the algorithm. Previous work (e.g. (Steinke et al., 2023)) studies the setting where we wish to test whether the algorithm satisfies $(\epsilon, \delta)$-DP for a single pair of $(\epsilon, \delta)$. This work extends the test to the setting of *$f$-DP*, which--roughly speaking--gives an entire curve for the values of $(\epsilon, \delta)$. By deriving sharper bounds on the accuracy of the guessing game assuming $f$-DP (Theorem 9), the authors show that $f$-DP allows for a better auditing compared to $(\epsilon, \delta)$-DP; this (partially) answers an open question from (Steinke et al., 2023). The authors also demonstrate this numerically, showing improvements in auditing the Gaussian mechanism and DP-SGD.

## Strengths

- The paper makes a clear contribution towards privacy auditing in one run, using an additional concept of $f$-DP. This is novel as previous works have only consider a single $(\epsilon, \delta)$ pair when auditing. Furthermore, $f$-DP is an important concept that has led to tight numerical privacy accounting in recent years and, thus, this is a well motivated and important setting.

- Empirically, the method has shown to significantly improve the empirical privacy from auditing compared to previous work.

## Weaknesses

- **Presentation**: Multiple reviewers find the presentation qualities to be inadequate. Some central concepts (e.g. empirical privacy) and details were not defined in the original version of the submission. Discussions on the experiment details and effects of different parameters were also insufficient.

- **Significant Changes in the revision**: Although these have been added in the revision, the changes are quite significant (as can be seen by the diff in the latest supplementary material; perhaps ~30% of the main text). Some of the potential issues--which are only apparent after the change--are listed below. Due to this, it might be best if the paper is re-submitted and fully reviewed again rather than accepted as is.

- **Possible Flaw in Empirical Privacy**:  The "empirical privacy" (Definition 7) used in this paper might be flawed and incomparable with previous work e.g. Steinke et al. (2023). To explain this, let us assume that the accuracy is 100% and consider the scenario where the test fails; what Steinke et al. (2023) works say is that the algorithm is *not $(\epsilon, \delta)$-DP*. However, what the test in this paper shows is that the algorithm is *not $f$-DP*. In this latter scenario, we do *not* know where the failure comes from; it could be that it fails for $\delta = 10^{-5}$ or at $\delta = 10^{-7}$ etc. As a result, we cannot simply pick a single $\delta$ and report the $\epsilon$ at that $\delta$, because the violation might not happen there. Due to this, it is unfair to compare to previous work in a manner done in Section 4.1 (and this is not discussed at all in the paper).

- **Practicality / Limitations**: Related to the above, this also highlights the fact that we need to pick the $f$ curve very carefully to get any meaningful result from such a testing at all. This will likely limit the practicality of the algorithm significantly since, for more complicated algorithms other than Gaussian mechanism, the $f$ curve is not well understood and computing them can be numerically challenging. (The choice of $f$ is mentioned briefly before Section 4.1 but the discussion does not dive into such subtlety.)

## Recommendation

Although auditing $f$-DP is an important direction and this paper provides some interesting initial work, more investigation / clarification should be done before the paper is ready for publication. Furthermore, it would be useful for the paper to get another proper full end-to-end review it deserves, given the significant changed during rebuttal. Due to these, we recommend rejection.