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