Auditing $f$-Differential Privacy in One Run

We thank the reviewer for their careful reading of the paper and constructive feedback.

clarify that by "one run" you mean a training run (rather than an inference run)

We clarified in the abstract and also added a footnote to clarify whenever we say one run, we mean one training run. (Line 106) explicitly state the limitation of Steinke et al. (2023) that you are addressing (in Line 80-82). We explicitly discuss the limitation now. Here’s our updated paragraph: “Steinke et al. highlighted a limitation in their approach in auditing specific mechanisms, such as the Gaussian mechanism. They correctly argue that simplifying the mechanism's behavior to just two parameters, $(\epsilon,\delta)$, results in sub-optimal auditing of specific mechanisms. In other words, the effectiveness of membership inference attacks against the Gaussian mechanism differs significantly from predictions based solely on the $(\epsilon,\delta)$ parameters. To overcome this limitation, we propose auditing the entire privacy curve of a mechanism, rather than focusing solely on $(\epsilon,\delta)$. “

change the references to algorithm 3.1 to algorithm 3 (given that that is what the algorithm is called)

We fixed this problem. Thanks for your careful reading.

remove double mentions of Steinke et al. by just using the reference instead (e.g., in Line 420)

We corrected our references.

Reading flow and typos:

We enhanced the writing and also reading flow in the paper. We thank the reviewer for their suggestions!

What do you mean by "gubernatorial analysis"? (Line 95)

This was a typo (created by autocorrect!). We meant “combinatorial analysis”. This refers to the part of analysis where we randomly shuffle the order of canaries and use the fact that this ordering and perform a double counting argument.

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?

We have a discussion about this in the experiment section. See page 10 line 490). The reason the bound of Steinke et al degrades as the number of samples increases beyond a certain point is because of the way their bound depends on the $delta$ term. Specifically, they have an $O(m\delta)$ term in their upper bound that starts to dominate as $m$ increases. For us, this effect does not happen because our analysis does not rely on $delta$ at a single $\epsilon$ to bound the probability of bad events. Our reliance on $f$-curve enables us to keep improving with more canaries.

We thank the reviewer for their constructive feedbacks. Addressing your comments has improved our paper and we appreciate that.

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?

Thank you for raising this question. We added a discussion on why this effect happens (See page 10 line 490). The reason the bound of Steinke et al degrades as the number of samples increases beyond a certain point is because of the way their bound depends on the $delta$ term. Specifically, they have an $O(m\delta)$ term in their upper bound that starts to dominate as $m$ increases. For us, this effect does not happen because our analysis does not rely on $delta$ at a single $\epsilon$ to bound the probability of bad events. Our reliance on $f$-curve enables us to keep improving with more canaries.

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?

This is a great question. We also touched on this in the same paragraph referenced above (Page 10 line 516). We believe our Theorem 9 is tight. However, the way we use theorem 9 to bound the tail is still subject to improvement. There is a subtle point of sub-optimality in our Algorithm 10. In this algorithm, we make use of the fact that the expectation of correct guesses, conditioned on the correct guesses being greater than c divided by the expectation of incorrect guesses conditioned on the same event is greater than c/c′. This step is not tight as we cannot have a mechanism where the adversary makes exactly c correct guesses with probability greater than 0, while making more than c correct guesses with probability exactly 0.

We again emphasize that our Theorem 9 is tight, we only need to find a more optimal way to find the worst case profile that is consistent with 9. Currently Algorithm 10 is the best we have, but that could improve in future work.

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?

Thank you for this suggestion. We have performed two sets of experiments in the black-box setting and provided the results in the Experiments section. In the first experiment, we use the same setup to that of Steinke et al with m=n=1000 and perform black-box attacks against models trained on CIFAR10 using DP-SGD. We use the same black-box membership inference attacks as them and obtain empirical privacy. We outperform their bounds in all settings. (See Figure 2)

We also performed an experiment on non-private models trained on CIFRA10. A benefit of empirical privacy is that it can be calculated on models that are not theoretically private but are hypothesized to be private. Hence, we use the state-of-the-art for membership inference attacks on CIFAR10 to obtain numbers on attack success and calculated empirical privacy. In these experiments we also outperform Steinke et al in our empirical privacy measurements. (See Figure 4)

Writing and Presentation Quality:

We enhanced the quality of text and resolved the typos and missing references. We appreciate your feedback.

I appreciate the effort that went into rewriting the paper. However, I would have appreciated it if the authors had respected the guidelines and appropriately highlighted the changes they made to the manuscript.

I would most likely champion acceptance if the current version was the initial final one. However, I am tempted to keep my reject stance, as the rebuttal is meant to discuss and marginally improve the manuscript, not provide a new one. I feel like the authors have abused the rebuttal phase to heavily rewrite the main body of the paper, which now would require a new review. This defeats the purpose, in my opinion, of rebuttals.

That being said, I find the work valuable, but I think it is only fair to resubmit it directly in this new version.

We thank the reviewer for their careful read of the paper and constructive comments. They helped us improve the quality of the paper.

The main weakness of this paper is its presentation.

We have significantly enhanced the presentation of the paper. These improvements are both in writing quality and also some new discussions and definitions to enhance the readability. We appreciate your feedback.

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.

We agree with the reviewer that implementation of the algorithms requires care. We added code snippets for all of the key algorithms for our auditing procedure. These can be found in appendix (pages 23-28).

On the section “Empirical Privacy” line no 307 (line 383 in the revision), why do the trade off curves need to be ordered? If you have a set of trade off curves that pass, couldn't you build a new trade off curve $f(x)=min_i f_i(x)$.

You are right, they don't have to be ordered. We can find the maximal set of all privacy curves that pass and calculate the empirical privacy based on that. The only problem with your formulation is that we need to take the max, and not the min (this is because smaller $f$ translates to a weaker privacy guarantee). We formulate this in a new definition (see Definition 7 for empirical privacy and other corresponding definitions) and clarify that we don't need to have an ordered set.

In what sense are the empirical results tight in Fig 7 (Fig 11 in the revision) and why is that not also evident in Fig 1?

We rephrased our claim. We now state that our estimation of delta and epsilon captures the true behavior of epsilon and delta whereas for Stineke et al it does not. The reason Fig 7 (Figure 11 in revised draft) looks much tighter than Fig 1 is because we were using a different set of confidence intervals to calculate the bounds in figure 7 (Figure 11 in revised draft). We realized that this particular plot was created with 1-confidence instead of confidence. We regenerated the plot and updated the paper with the new plot (see Figures 10 and 11). The curves still reflect the true behavior of $(epsilon, \delta)$ but with a larger gap from the ground truth.

Thank you for your careful review of the paper! Also note that we have moved this experiment to appendix to open space for other discussions and experiments. We will be happy to bring them back if you find them necessary.

Can you explain why abstentions are important in this algorithm?

Consider a random variable representing the ratio of correct guesses ($c$) to total guesses ($c'$). Note that the core component of our auditing procedure is a way of calculating tail bounds on this random variable. If we reduce the number of guesses the variance of this ratio tends to decrease because the ratio approaches 1 (the adversary can make more correct guesses when we decrease $c'$). Conversely, if we increase the number of guesses, the variance can also decrease because having more guesses generally leads to a more stable average, owing to the law of large numbers. This balance makes the number of guesses a crucial factor to optimize for. We have added a discussion about this right after our ablation on the number of guesses. (Note that this experiment and the ablation is now in the appendix, page 22, line 1185.

We thank the reviewer for their valuable comments and feedback. We have completed some experiments per your suggestions and are in the process of running more. We plan to include all these in the next iteration of the paper. Please find our responses to individual questions below.

• Some notions, such as the concept of empirical privacy, could have been more formally defined.

  We have updated our draft with more details on how we define the notion of empirical privacy. Definition 7 in the revised version of the paper precisely defines empirical privacy. To calculate empirical privacy, we find the strongest $f$-DP curve that will pass our audit and then calculate $\epsilon$ and $\delta$ for that curve.

• Additional experiments on at least two other datasets should be conducted.

  Thank you for your suggestion. We performed a new experiment on the Purchase dataset. Purchase is a tabular dataset consisting of 600 numerical columns. We used 25,000 canaries and varied the number of guesses. We achieve an empirical $\epsilon \approx 7$, while Steinke et al.'s approach achieves $\epsilon \approx 4.5$. We are also in the process of running experiments with the AGNews dataset and will include it in the final version. Note that for all experiments, we expect to perform better than Steinke et al. due to our tighter analysis.

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

  We agree with the reviewer that the design of canaries is important. However, it is orthogonal to our work. Our auditing procedure can be instantiated with any set of canaries and any attack. Our contribution lies in analyzing empirical privacy better than prior work, for any given instantiation of attack and canary selection. For our black-box experiments on CIFAR-10, for example, we choose samples from the dataset as our canaries. These canaries will not degrade the quality of the model because they are from the same distribution.

• Discuss the design of the function $f$ that should be considered for the auditing.

  We have added a new discussion on how to choose this function $f$. In the revised paper, we state:

  The family of trade-off functions should be chosen based on the expectations of the true privacy curve. For example, if one expects the privacy curve of a mechanism to be similar to that of a Gaussian mechanism, then they would choose the set of all trade-off functions imposed by a Gaussian mechanism as the family. For example, many believe that in the hidden state model of privacy (Ye & Shokri, 2022), the final model would behave like a Gaussian mechanism with higher noise than what is expected from the accounting in the white-box model (where we assume we release all the intermediate models). Although we may not be able to prove this hypothesis, we can use our framework to calculate the empirical privacy while assuming that the behavior of the final model would be similar to that of a Gaussian mechanism.

• Can the approach be used on classifiers for other types of data, such as tabular data?

  Yes, as mentioned above, we have new experiments on the Purchase dataset. In these experiments, our set of canaries is selected from the data distribution, and we use state-of-the-art membership inference attacks (https://github.com/privacytrustlab/ml_privacy_meter) to obtain empirical privacy. Our empirical privacy numbers are better than Steinke et al.'s estimates.

• 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?

  We can audit any $f$-DP curve. In this work, we focused on Gaussian and sub-sampled mechanisms. However, we can also consider mechanisms such as Laplace, Exponential, and randomized response mechanisms. As long as we have the $f$-DP curve for the mechanism, we can plug it into our Algorithm 3 and obtain empirical privacy. We are in the process of running some experiments with the Laplace mechanism to demonstrate this and will include it in the next iteration of the paper.

• There are some minor typos.

  Thank you for pointing out these typos. We have fixed them all in our revised version.

I would appreciate if the authors could answer the questions that were raised in my review.