We thank reviewer JVDo for their helpful and constructive feedback. In the following, we address their comments and questions and clarify how we believe we can address their concerns regarding weaknesses.

Contributions of crafting worst-case initial model parameters

Although the general idea of looking at initialization was indeed already reported in [10, 18, 26], these works only looked at tweaking the randomization of initialization. Instead, we focus on specifically crafting worst-case initial model parameters, which had not been considered before. We refer the Reviewer to Point 1. of the Global Author Rebuttal comment for a more detailed comparison with prior work.

Experiments’ details

We thank the reviewer for highlighting the gaps in the details of our experimental analysis. In addition to addressing the reviewer’s questions below, please note that we will make the code publicly available with the camera ready; in the meantime, we would be happy to share the code anonymously upon request.

Answers to Questions

Worst-case vs Average-case initialization

We refer the Reviewer to Point 3. of the Global Author Rebuttal comment for details regarding crafting worst-case initial model parameters (i.e., pre-training on half of the dataset). For the random distribution, we follow [18] and use Xavier initialization, which we will clearly explain in Section 5.

Discrepancies in Figure 5

We note that the discrepancy is due to the small number of models and refer the Reviewer to the Point 2. of the Global Author Rebuttal comment, where we explain this in detail.

Canary strategy

We use the blank sample when auditing the full model and the ClipBKD sample [18] when auditing the last-layer only fine-tuning. We experimented with both samples (along with a “one-hot” sample) and used the sample with the tightest audits for both settings. We note that ClipBKD performed better for last-layer only fine-tuning as it was particularly designed and tested for this setting. We will clarify this in the revised version of the paper in Section 5.1.

Success of pre-training strategy

In Figure 2, (a) the average of the gradient norms is only computed on training samples. (b) The gradient norms of other samples are important to the success of our attack as they represent the expected change in the loss function due to the other samples during training. Specifically, when the gradient norms of other samples are close to 0, the loss function is mainly impacted by the presence of the target sample only, making the loss of the target much more distinguishable (when the target sample is present vs. when it is not). Put simply, the gradient norms indicate the level of “noise” in the dataset compared to the “signal.” Note that while prior work [18, 26] does aim to maximize the loss of the target sample by carefully crafting the target sample, this has not been enough to achieve tight audits. In our work, we find that we are able to explain (part of) this gap by using the gradient norms of the other sample taken as “noise.” We hope this provides additional intuition as to why our approach works and will clarify this in Section 5.2 as well. (c) Even if the empty sample is “in distribution,” we can mislabel the sample to make it “out of distribution” and use the mislabelled sample as the target sample, which is also a common method used in prior work.

Loss thresholds

As mentioned in Section 4, the loss thresholds are indeed fine-tuned to maximize privacy leakage. We will explicitly include the EstimateEps function (in the main body if there is space and in the appendix otherwise) and also release the code publicly for reproducibility.

Using [32] for auditing in a single run

We thank the reviewer for making the point that our method can potentially be combined with [32] to audit using a single training run, as also briefly mentioned in Section 6. However, this may not be trivial as a large number of target samples with potentially large gradient norms are used in [32]. This might interfere with our approach to reduce the contribution of other samples. Therefore, we leave this to a future paper to investigate this approach in more detail. In the revised version of the paper, we will additionally state these challenges of combining our work with [32].

We thank reviewer uyKT for their helpful feedback. While their questions are hopefully addressed in Point 2. of the Global Author Rebuttal comment, we address their comments regarding weaknesses here.

Pre-training on another distribution

We apologize as we are not entirely sure what the reviewer is referring to in the first point of the weaknesses in their review. We would be happy to address it if they could kindly clarify. Do they mean to say that it is unclear how our work would apply to the setting where a different dataset (instead of half of the target dataset) is used to craft the initial model parameters?

If so, we believe that it would depend on how close the distributions of the other dataset are to the target dataset. Naturally, datasets with closer distributions would yield tighter audits. However, as we focused on achieving the tightest possible audits within the black-box setting in this work, we have not looked into this aspect yet. Nevertheless, we think it would be an interesting aspect to look into for future work and we will explicitly add this in Section 6.

Insignificant improvements in Figure 5

We believe that one of the reasons why there are not any significant improvements to the audits in this setting is that the audits are already nearly tight when using average-case initial model parameters. For instance, at theoretical $\varepsilon = 10.0$, the $\varepsilon_{emp} = 7.69$ for average-case initial model parameters already. Therefore, there is not much room for improvement in this setting resulting in comparable audits between the average-case and worst-case initial model parameters.

We thank reviewer ncD1 for their helpful feedback. In the following, we address their comments and questions.

Motivation

Thank you very much for your comments re. our motivation. Indeed, our work is primarily focused on the “New Insights” type of motivation, i.e., determining if the analysis of DP-SGD can be improved if considered as a black-box algorithm. To that end, we will follow the Reviewer’s recommendation to center our motivation around this aspect. We will also follow the Reviewer’s recommendation to leave out any motivation that argues about the “practical” aspect of black-box auditing.

Comparison to prior work

We note that previous work [10, 18, 26] considered the setting with subsampling (i.e., $B \neq N$) whereas we consider full batch gradient descent ($B = N$). Nevertheless, we do present a direct comparison with [10, 26], which is the “average-case $\theta_0$” setting – they, too, use the blank same and loss to carry out the audit. Although we did initially experiment with [18] (i.e., using the ClipBKD sample), we did not find that, in our setting, this significantly improved upon the results presented in “average-case $\theta_0$” (probably because [18] was only designed for and tested on Logistic Regression and Fully Connected Neural Networks) and thus left it out of the paper. In Section 5, we will make it clearer that the “average-case $\theta_0$” setting provides a direct comparison to [10, 26].

Answers to Questions

Threat model paragraph

We included this paragraph to delineate the differences between what was done in prior work (active white-box) and what we do (black-box). This also mirrors writing in prior papers [26, 28]. Nevertheless, we will include the worst-case initial parameters assumption in the threat model (and thank the reviewer for suggesting this).

Worst-case target sample

We consider the setting where the rest of the dataset is chosen randomly (“natural dataset”), but the target sample is specifically chosen by the adversary and is not a “natural” sample. To make this clearer, we state that we “assume that the adversary can choose a worst-case target sample as is standard for auditing DP mechanisms.” We hope this clarifies the reviewer’s question.

Clarifying $B = N$

We note that setting $B = N$ is not a constraint of our method; rather, it aims to make auditing easier and is done commonly [26]. Nonetheless, we note that recent work (Cebere et al., 2024) suggests that the privacy analysis when $B \neq N$ might be complicated, and even in stronger threat models, tight auditing may be difficult to achieve.

Clarifying $R$

We will clarify in Section 3.3 that $R$ refers to the number of models/outputs.

Details on worst-case initial model parameters

We refer the Reviewer to Point 3. of the Global Author Rebuttal comment and will clarify this further in the text.

Typos

We apologize for the typos and will fix both of them in the text. We used 36 cores in the cluster (we will also clarify this).

References

Cebere, T., Bellet, A., & Papernot, N. (2024). Tighter Privacy Auditing of DP-SGD in the Hidden State Threat Model. arXiv:2405.14457.

We thank reviewer qSii for their helpful feedback. In the following, we address their comments and questions.

When other samples’ contributions are smaller, auditing is tighter

While the overarching intuitions are similar, our strategy is appreciably different from prior work [18, 27], as we also discuss in Point 1. of the Global Author Rebuttal comment vis-à-vis the novelty of crafting worst-case datasets. In the revised version of the paper, we will discuss this further to clarify how, despite the similarity of the intuitions, our work overcomes some significant challenges compared to prior work.

Near tightness claims

Thank you for your comment. We agree that, in some settings, especially at low(er) $\varepsilon = 1.0$ and $2.0$, it is not entirely clear whether our auditing method improves upon prior work. However, we note that this is mainly due to computational limitations. In fact, there are significant improvements for larger $\varepsilon = 4.0$ and $10.0$ on both the MNIST and CIFAR-10 datasets (e.g., for MNIST, from $\varepsilon_{emp} = 3.41$ in prior work to $6.48$ in our work). This suggests that computational power is a limiting factor as lower epsilon values correspond to FPR/FNR rates that are very close to the random baseline, which would, in turn, require more models to estimate more accurately. Nevertheless, in the final version of the paper, we will tone down our claims of “near tight” audits to specify in which settings the audits are appreciably tighter than prior work.

Stating $B = N$ in the main body

Currently, the setting of $B = N$ is stated in Section 3.2, but we will emphasize/clarify this again in Section 5.

Generalizability to deeper models

Unfortunately, due to both the number of models required for the audit and the large batch sizes, auditing modern deep models (e.g., WideResNet) in the black-box setting tightly is computationally (very) expensive. However, our method is inherently general and does not depend on the model architecture. Furthermore, the crafting of our worst-case initial parameters is efficient as the model has to be only pre-trained once. Therefore, in theory, we do not see any reasons that would prevent the generalizability of our results other than very significant computational costs. In future work, we will look into auditing deep neural networks as soon as we have access to more compute or we can improve the efficiency of the underlying auditing techniques.

Experiments on other datasets

Thank you for this comment. We did indeed think about additional datasets but ultimately settled on MNIST and CIFAR-10, which are considered benchmark datasets for auditing DP-SGD [10, 18, 27]. Moreover, the trends observed (e.g., smaller datasets yielding tighter audits) are the same across both MNIST and CIFAR-10 – due to the different complexities of the datasets, only the scale of the “impact” differs. Nevertheless, on Reviewer qSii’s request, we could add experiments on the FMNIST dataset as well (we are confident this will confirm the same conclusions we draw from MNIST/CIFAR-10).

Answers to Questions

Gradient norm of auditing sample

On average, across all iterations, the gradient norm of the auditing sample, before clipping, is $10.5$ for MNIST and $150.4$ for CIFAR-10. Therefore, we do not believe that this is a “maxing out” issue.

Re-tuning hyper-parameters for clipping norms

The hyper-parameters were re-tuned for the clipping norms.

Explicitly constructing initialization with 0 gradient norm

Unfortunately, even if the other gradients’ norms are exactly 0 on iteration 0, it will no longer be 0 for future iterations as the model weights become “corrupted” by the noise addition step [27]. Therefore, to the best of our knowledge, it is not possible to have an initialization that results in the other gradients’ norms being 0 throughout training. Nevertheless, one setting we did consider (but did not include in the paper) is the worst-case neighboring datasets setting, where $D = \emptyset, D’ = \\{(x, y)\\}$, which is numerically equivalent to what you suggest (the gradient norm of the empty dataset will be 0). While the audits were significantly tighter in this setting ($\varepsilon_{emp} \approx 9$ at theoretical $\varepsilon = 10.0$ for both MNIST and CIFAR-10), we did not include it in our final paper since this setting has limited real-world value.