Tighter Privacy Auditing of DP-SGD in the Hidden State Threat Model

We thank the reviewer for their constructive feedback and address their concerns and questions below.

On the contemporaneous work by Annamalai [2024]

To begin, we want to clarify that, in accordance with the ICLR 2025 Reviewer Guideline, this paper should be regarded as contemporaneous work. Consequently, we are not required to compare our own work to that paper. However, we have chosen to cite and discuss this paper in Remark 4 to provide additional context. In particular, we highlight that our work offers a more nuanced and complete picture than Annamalai [2024], as we uncover the existence of two different regimes and reveal the key role of the batch size. We also want to emphasize that the construction presented in Annamalai [2024], like ours, is “synthetic” and it is unclear how to translate it to a practical scenario. We agree that studying how worst-case gradient sequences could be obtained in practical scenarios (i.e., on realistic datasets with commonly used architectures and loss functions) is an important and intriguing direction for future research inspired by our work. Note that, in the context of privacy backdoors, there is exciting progress in achieving arbitrary gradients in practice for specific architectures, see Feng et al. 2024.

Comparison with Gradient Crafting adversary of Nasr et al. 2023:

The gradient crafting adversaries of Nasr et al. 2023 (Dirac, Constant, Random) aim to maximize per-step privacy leakage. Our simulated biased dimension adversary ($\mathcal{A}_{GC}$-S) is a refined Dirac gradient-crafting adversary that seeks to maximize the privacy leakage from the final model. To achieve this, the key difference with the Dirac adversary of Nasr et al. 2023 is that our adversary simulates training to select a favorable dimension (see the detailed presentation in Appendix C, in particular Algorithm 3 therein), rather than selecting the dimension at random as in Nasr et al. 2023. We show that our strategy achieves better privacy auditing for the hidden state model in some scenarios (see Figure 2c).

We thank the reviewer for their positive feedback and address their questions below.

On the usage of PRV accounting

We have used the default numerical accountant implemented in Opacus out of ease, but we agree that we could just use analytical Gaussian accounting, either via Balle et al. 2018 or through $\mu$-GDP composition. For sanity check, we have implemented this and the results are equivalent to the ones obtained with the numerical accountant. We appreciate the feedback and we will switch to analytical accounting in the final version of the paper.

On the craftability of a given sequence of gradients

DP-SGD, by design, protects any sequence of bounded gradients. Therefore, to assess the tightness of these privacy guarantees (which is our main goal), it makes sense to audit with a worst-case gradient sequence. Interestingly, we are not aware of any theory restricting what gradients can be produced by large neural networks; therefore, one cannot rule out the possibility that there exists some input point that can produce an arbitrary sequence of gradients.

That being said, how to craft such an input point is an interesting open question, with recent work providing some first answers to this question [Feng et al., 2024]. This paper belongs to a recent line of work where the model architecture and parameters are chosen adversarially to leak some input points (a privacy backdoor), see the prior work [1, 2, 3] in federated learning. Interestingly, their construction shows that, for a particular choice of architecture/initialisation, a canary point can generate approximately worst-case gradients like the ones used by our gradient-crafting adversaries. In other words, it is sometimes possible to instantiate our adversaries through input-point canaries. However, their work focuses on finding specific instances of models and initializations where this can work and, as far as we know, a general way of crafting arbitrary sequences of gradients has not yet emerged.

[1] Fowl et al. Robbing the Fed: Directly Obtaining Private Data in Federated Learning with Modified Models. ICLR 2022

[2] Boenisch et al. When the Curious Abandon Honesty: Federated Learning Is Not Private. EuroS&P 2023

[3] Boenisch et al. Reconstructing Individual Data Points in Federated Learning Hardened with Differential Privacy and Secure Aggregation. EuroS&P 2023

Constant accounting upper bounds

We insert the canary a fixed number of times (250) and only account for those. We have made this more explicit in lines 343-346 of the revised manuscript.

On the caption of Figure 4

Indeed, thanks for catching the typo! We have fixed it in the revised version.

We thank the reviewer for their constructive feedback and address their concerns and questions below.

On the use of GDP approximation:

Indeed, our Gaussian approximation can underestimate the privacy guarantees when trade-off curves are not symmetric, especially for subsampled or shuffled mechanisms (as underlined by [A]). The main difficulty here is that we do not have a closed-form expression for the Privacy Loss Distribution (PLD) and, in contrast to [Nasr et al. 2023], we cannot use the intermediate steps information to audit a PLD with a known structure. Thus, we use the CLT to approximate the mechanism's output after several optimization steps. As we increase the number of steps in the hidden state, the trade-off function indeed becomes well approximated by a Gaussian trade-off function, as shown in Appendix E. We appreciate the feedback and have added a clarification in Remark 3 of the revised paper along with a reference to [A]. We note that [B] requires convexity similar to the classic privacy amplification by iteration result. We have cited [B] in the relevant part of the related work section (line 224).

We thank the reviewer for their constructive feedback and address their concerns and questions below.

Explanations for the empirical results:

While we have tried to give some explanations and interpretations for the observed gaps (see lines 414-421 for the gap between $k=1$ and $k>1$ and lines 490-494 for the small batch size regime), we agree with the reviewer that some of these could be expanded.

Here is more intuition regarding the privacy amplification phenomenon occurring at small batch sizes that you specifically ask about. In our worst-case construction, the crafted gradient influences all subsequent gradients computed on genuine points. Recall that gradient updates belong to $[-BC, BC]$ where $B$ is the batch size and $C$ is the clipping threshold. Therefore, as gradient updates are bounded by $[-BC, BC]$ and the noise remains independent of $B$, increasing $B$ allows the adversary to retain more ``signal'' about the canary's presence in subsequent gradients. We have integrated these additional explanations in the revised version of the paper (lines 490-495).

If there are other points where the reviewer would appreciate additional explanations, we would be happy to expand these to clarify our results further.

Details on the auditing technique and adversaries:

Regarding auditing, we provide a succinct description in Section 2.2, with more details in Appendix A for the methodology and Appendix D for the experimental details. We believe this is adequate, since we reuse an existing auditing methodology from prior work (Nasr et al., 2023).

On the adversaries, in addition to the description in Section 4, we provide additional details on the implementation of our adversary in Appendix C and more experimental details in Appendix D.

It will not be possible to move these sections into the main body of the paper due to the page limit, but if the reviewer believes it is important to add specific details in the main text, we would be happy to do so.

On the existence of a data point yielding a worst-case gradient sequence:

DP-SGD, by design, protects any sequence of bounded gradients. Therefore, to assess the tightness of these privacy guarantees (which is our main goal), it makes sense to audit with a worst-case gradient sequence. Interestingly, we are not aware of any theory restricting what gradients can be produced by large neural networks; therefore, one cannot rule out the possibility that there exists some input point that can produce an arbitrary sequence of gradients.

That being said, how to craft such an input point is an interesting open question, with recent work providing some first answers to this question [Feng et al., 2024]. This paper belongs to a recent line of work where the model architecture and parameters are chosen adversarially to leak some input points (a privacy backdoor), see the prior work [1, 2, 3] in federated learning. Interestingly, their construction shows that, for a particular choice of architecture/initialisation, a canary point can generate approximately worst-case gradients like the ones used by our gradient-crafting adversaries. In other words, it is sometimes possible to instantiate our adversaries through input-point canaries. However, their work focuses on finding specific instances of models and initializations where this can work and, as far as we know, a general way of crafting arbitrary sequences of gradients has not yet emerged.

[1] Fowl et al. Robbing the Fed: Directly Obtaining Private Data in Federated Learning with Modified Models. ICLR 2022

[2] Boenisch et al. When the Curious Abandon Honesty: Federated Learning Is Not Private. EuroS&P 2023

[3] Boenisch et al. Reconstructing Individual Data Points in Federated Learning Hardened with Differential Privacy and Secure Aggregation. EuroS&P 2023

We thank the reviewer for their positive feedback and relevant suggestions!

We will clarify in Section 4 that, to our knowledge, there is no restriction on the gradient sequences generated by a neural network. We also agree that it would be useful to explicitly integrate the concrete auditing algorithm for our proposed adversaries in the generic template described by Algorithm 1.

We will incorporate these updates in the final version of our manuscript, as we cannot upload a revised version during this part of the discussion phase.