Thank you for your detailed review and suggestions.

Response to Weaknesses

• Regarding the last expression of the proof of Theorem 8: We thank the reviewer for pointing this out. Indeed this is a typo and should be changed to $e^{\\epsilon_i + \\epsilon'} \\cdot \\mathcal{A}'(o, i)$. We have rechecked the proof and can confirm that, apart from this typo, the proof is correct.

Response to Questions

1. We wish to remark that the two versions (with and without the sum) of the definitions are equivalent for pure-DP (i.e., $\\delta = 0$). One direction (with the sum to without the sum) is obvious by taking $\\mathcal{O} = \\{o\\}$. The other direction can be seen by taking the sum of the inequality over all $o \\in \\mathcal{O}$. We also note that both versions are standard in DP literature; indeed the original DP paper (Dwork et al., 2006) has the definition of pure-DP without the sum, in a similar manner as our Definition 2.

2. Thank you for pointing this out. We will make sure to change this and use $p$ as the success probability in the revised version.

3. This term is actually not a problem since we can choose $\\epsilon’$ to be arbitrarily small, and thus the privacy overhead from this additive term can be made negligible. Note that, to retain similar utility after decreasing $\\epsilon’$, we can simply duplicate the mechanisms so that each mechanism is run multiple times (see Line 178-191); this would result in the same utility and lower privacy at the expense of computational cost. (Note that a similar tradeoff also occurs in ex-ante DP hyperparameter tuning algorithm of Papernot–Steinke; see their Corollary 3.)

4. Note that $\\ell_i$’s are not data dependent so they can be set entirely based on the $\\epsilon_i$’s values; i.e., one may choose $\\ell_i$ that minimizes $(2 + \\ell_i) \\epsilon_i + (1 + \\ell_i) \epsilon’ + \\frac{\\sum_{j \neq i} e^{-\\epsilon_j (1 + \\alpha \\ell_i)}}{\alpha - 1}$ (note that it doesn’t depend on $\\ell_j$ for $j \\neq i$ or the dataset).

5. As alluded to in the paragraph starting at line 92, privacy filter is the typical approach to convert ex-post guarantee into the standard ex-ante guarantee. Here one would have a target ex-ante privacy budget (denoted by $\\epsilon$ in Algorithm 2) and the privacy filter allows us to run multiple ex-post DP subroutines. At the end, the guarantee of the entire algorithm is ex-ante. In other words, this can be thought of as a “composition theorem” for privacy, except that it allows ex-post DP subroutines and yet yields the more traditional final ex-ante DP. Finally, we note that we focus on RDP in Section 4 since a natural privacy filter for e.g. pure-DP is already known (Lebensold et al., 2024).

Thank you for your detailed review and suggestions.

Response to Weaknesses

Note that $\\ell_i$’s are not data dependent so they can be set entirely based on the $\\epsilon_i$’s values; i.e., one may choose $\\ell_i$ that minimizes $(2 + \\ell_i) \\epsilon_i + (1 + \\ell_i) \epsilon’ + \\frac{\\sum_{j \neq i} e^{-\\epsilon_j (1 + \\alpha \\ell_i)}}{\alpha - 1}$ (note that it doesn’t depend on $\\ell_j$ for $j \\neq i$ or the dataset).

Response to Questions

1. Indeed, one of the strengths of our algorithm is that it does not need an a priori threshold since it simply outputs the best response with the highest “score” (based on the ordering of $\\mathcal{O}$ that we can choose). However, if one insists on using a threshold, then our algorithm can be easily adapted: We can assign every output below the threshold with “score” of $-\\infty$ (and every output above the threshold a positive score) and add another 0-DP mechanism $\\mathcal{M}_{d + 1}$ that always output a dummy output with score 0. In this way, we ensure that we only output an element that exceeds the threshold.
2. We apologize for the confusing phrases that we used. You are correct that in our Algorithm 1 description each mechanism is run exactly once. However, as explained in the subsequent paragraphs (Line 178-192), we can run each mechanism more than once by a simple “repetition trick” where we duplicate each mechanism multiple times in the input sequence. Note that, in terms of privacy, there is no cost to such repetition trick since the guarantee in Theorem 8 does not depend on the sequence length.

Thank you for your detailed review and suggestions.

Response to Questions

As alluded to in the paragraph starting at line 92, privacy filter is the typical way to build a system where an adversary is allowed to run ex-ante private subroutines interactively and the filter halts the computation if a target ex-ante privacy guarantee would be violated by request.

However, our paper considers a generalization of this concept to a setting where the subroutines are allowed to be ex-post private. In other words, the filter we consider allows converting ex-post guarantee into the standard ex-ante guarantee. Here one would have a target ex-ante privacy budget (denoted by $\\epsilon$ in Algorithm 2) and the privacy filter allows us to run multiple ex-post DP subroutines. At the end, the guarantee of the entire algorithm is ex-ante. In other words, this can be thought of as a “composition theorem” for privacy, except that it allows ex-post DP subroutines and yet yields the more traditional final ex-ante DP. Finally, we note that we focus on RDP in Section 4 since a natural privacy filter for, e.g., pure-DP is already known (Lebensold et al., 2024).

As for $IT^0$ and $IT^1$, we define them to be the output of Algorithm 2 for $b = 0$ and $b = 1$, respectively. ($IT$ here stands for “interactive transcript”.) We will make sure to include the definition more clearly in the main body in the revised version. Thank you for pointing this out.

Response to Comments

Re variance and Figure 1: Larger variance in the number of invocation of the mechanisms also implies a larger variance in the running time and a larger “variance” in the utility guarantee. This is because the number of invocations of the Papernot–Steinke mechanism is more well concentrated around the expectation, so their running time and utility are also more well concentrated. (This is perhaps the price we pay for the generality of our algorithm–which works for mechanisms with different DP guarantees–compared to their algorithm.)

Re CNN architecture: We didn’t optimize the architecture for MNIST (since it was already outperforming linear models) and used the one from Opacus tutorial: it has two convolution layers and two linear layers with max-pooling (with kernel 2 and stride 1) and ReLU after convolution layers and ReLU after linear layers.

1. The first convolution layer has out channel 16, kernel 8, and stride 2.
2. The second convolution layer has out channel 32, kernel 4, and stride 2.
3. The first linear layer has 32 output features.
4. The second linear layer has 10 output features for each class.

We will make sure to add the architecture to the final text too.

Thank you so much as well for pointing out the other typos.

Thank you for your detailed review and suggestions.

Response to Questions

1. We thank the reviewer for pointing this out. Indeed this is a typo and should be changed to $e^{\\epsilon_i + \\epsilon'} \\cdot \\mathcal{A}'(o, i)$. We have rechecked the proof and can confirm that, apart from this typo, the proof is correct.

2. We find this surprising as well! Our rough intuition is that, since we randomly decide if each mechanism’s result is included in the final computation, this allows mitigating the leak of each individual mechanism. However, as can be seen in our paper (and previous works of Liu–Talwar and Papernot–Steinke), this requires a very careful strategy of how each mechanism is probabilistically included, together with a subtle privacy proof.