Near-Exact Privacy Amplification for Matrix Mechanisms

Thanks to the reviewer for their feedback which has helped us improve the presentation of the paper. Below we respond to individual points raised by the reviewer:

How to derive high-confidence bound for the monte-carlo simulation results?

• For concentration we used Bernstein’s inequality in conjunction with the Wang et al. result. We added Theorem 2.2 and a corresponding appendix to explain this in more detail. In the original submission we did use Theorem 2.2 to guarantee all our empirical results satisfied the desired privacy guarantee via the wrapper of Wang et al. but regretfully neglected to discuss the details. We now emphasize this point in the paper at the start of Section 5.

The paper does not provide a closed-form or asymptotic bound for the amplification rate

• While we agree theoretical bounds on the improvements would be useful for a better understanding of amplification, we feel this is a challenge common to most privacy amplification results and not a major weakness, nor one specific to our paper. For example, even in the most idealized setting of Poisson sampling with independent noise and targeting RDP instead of (epsilon, delta)-DP bounds, the best theoretical results of Mironov et al. (https://arxiv.org/abs/1908.10530) require somewhat complex conditions that only hold when targeting small epsilons, and they still eventually show that approximate numerical computation is much better than their bounds in practice. Correlated noise heavily complicates the problem of computing privacy bounds under amplification for reasons we discuss in the paper, hence we believe it would both be extremely challenging to arrive at any non-trivial theoretical bounds, and simultaneously not very predictive of what we get by doing accounting via numerical methods.

Can the authors provide the noise parameter or the noise variance in Figure 4

• We have added this as a figure in the appendix, “Additional CIFAR Plots”. However, we note that because correlated noise mechanisms with larger noise cancellation require higher noise multipliers, comparing the noise multipliers of different methods is not particularly informative (even when comparing the results for Band MF, as the optimal banded matrix heavily differs between the two amplification methods). The RMSE metric, which is studied extensively in the previous subsection, is a better answer to the reviewer’s question because it accounts for both the noise multiplier and amount of noise cancellation.

Can the authors comment more on why in large eps, the proposed method performs much worse compared to subsampling amplification?

• We believe the reviewer is referring to the setting in Figure 2a, where independent noise is used instead of correlated noise; in all other settings, our method actually is comparable to or better than the result of Choquette-Choo et al. at higher epsilons.
• The intuition for the gap in Figure 2a: Poisson sampling is strictly more random than balls-in-bins sampling (balls-in-bins can be viewed as Poisson sampling conditioned on a single participation per epoch). Since privacy amplification intuitively compounds sampling randomness with noise randomness, we expect Poisson sampling to provide better amplification than balls-in-bins sampling in most settings. This explains the gap in Figure 2a, where independent noise is used.
• The reason this gap doesn’t manifest in other settings is that when we use correlated noise, we defer to the less random version of Poisson sampling proposed by Choquette-Choo et al. that in turn provides less amplification, whereas the amount of randomness in balls-in-bins is the same in all settings in the paper. If we could efficiently compute tight privacy guarantees for “maximally random” Poisson sampling with correlated noise, it’s likely that it would outperform balls-in-bins in most settings. However, an efficient and tight analysis is beyond our current understanding.

Thanks again to the reviewer for your feedback on the paper. Since the discussion period is ending soon, we would appreciate any thoughts from the reviewer on the rebuttal/revisions and whether there are any remaining concerns we could try to address.

Thanks to the reviewer for their questions which have helped us improve the clarity of the paper. We address below individual questions/weaknesses raised by the reviewer:

The paper is not fully polished: I don't see the neighborhood relation of datasets stated anywhere.

• This is a good point. Yes, we are using add/remove. We now make this clear in Section 2 and Lemma 3.2.

What exactly guarantees that (P, Q) dominates the pair (Q, P)

• We now state explicitly in Lemma 3.2 that (P, Q) is the dominating pair for the add adjacency, and (Q, P) is the dominating pair for the remove adjacency. (P, Q) does not necessarily dominate (Q, P), but we can do still accounting for add-remove by taking the worse of the DP guarantees calculated using the two dominating pairs, and by a union bound this at most doubles the failure probability we use in Theorem 2.1 (this is discussed in Appendix E).

I think the proof of Lemma 3.2 could be elaborated to make it more readable.

• We have made the proof more thorough and self-contained.

What would be required to for providing convergence guarantees for the estimates?

• For concentration we used Bernstein’s inequality in conjunction with the Wang et al. result. We added Theorem 2.2 and a corresponding appendix to explain this in more detail. In the original submission we did use Theorem 2.2 to guarantee all our empirical results satisfied the desired privacy guarantee via the wrapper of Wang et al. but regretfully neglected to discuss the details. We now emphasize this point in the paper at the start of Section 5.

How the results might change (or not) for the substitution neighborhood relation.

• The recent work of Schuchardt et al. (https://arxiv.org/abs/2403.04867) allows us to reprove Lemma 3.2 for the substitution adjacency by basically the same proof. It is straightforward to adapt our Monte Carlo sampling code to the resulting pair of dominating distributions, since this only changes the computation of the privacy loss/log likelihood ratio. We will include a discussion of this in the paper.

Thank you for the replies. After these clarifications and modifications to the paper, I am raising my score.

Thanks to the reviewer for their questions which have helped us improve the clarity of the paper. Below we respond to individual weaknesses/questions raised by the reviewer:

What is the ``practical random batching'', and why is the balls-and-bins scheme approximates it better than Poisson sampling?

• We apologize for the lack of clarity. The practical random batching we refer to is just shuffling. We now say shuffling explicitly in the abstract. By “closer”, we mean the amount of overhead compared to shuffling needed to implement balls-in-bins is minimal. e.g., the paragraph “Advantages of balls-in-bins batching” explains how balls-in-bins batching can be implemented by shuffling and then using a variable batch size (as we do in Appendix H).

Proof of monotonicity is missing

• Since we just need to find an (approximate) solution and $\hat{\delta}$ is continuous in $\sigma$, monotonicity is not required for bisection to converge (and perhaps surprisingly, we have found counterexamples for monotonicity of $\hat{\delta}$). Instead, it suffices to have $\sigma_1$, $\sigma_2$ such that $\hat{\delta}(\sigma_1) > \delta$ and $\hat{\delta}(\sigma_2) < \delta$. We have added a discussion of this as a footnote when discussion bisection.
• In more detail: $\hat{\delta}(\sigma_1) = 1$ for $\sigma_1 = 0$, and if we take enough samples then whp $\hat{\delta}(\sigma_2) < \delta$ for $\sigma_2$ set to the sigma achieving the target $(\epsilon, \tau \delta)$-DP guarantee without amplification.

Thanks to the reviewer for their questions which have helped us improve the clarity of the paper. Below we respond to individual weaknesses/questions raised by the reviewer:

Could the authors interpret "near-exact" privacy analysis

• There are two potential sources of looseness: (i) looseness of the dominating pair and (ii) looseness in computing $D_\epsilon(P, Q)$ for the dominating pair. (ii) is merely a looseness in the MC-sampling procedure and can be made arbitrarily tight by increasing the number of samples (as well as runtime). (i) is tight in general: in the case where all examples have scalar gradient 0 except for the differing example, which has scalar gradient 1, the dominating pair (P, Q) is exactly the outputs of the corresponding matrix mechanism. We have added a clarification explaining (ii) to Section 1.1.1.

How does the (sub)optimal choice of $b$ vary

• Generally, as epsilon gets higher the number of bands increases. Effectively, lower bands gives better amplification and higher bands gives better noise cancellation. The former gets worse as the epsilon increases, whereas the latter is independent of noise, so the optimal point in this tradeoff skews towards higher numbers of bands as epsilon increases.
• For comparing Poisson sampling of Choquette-Choo et al. to our balls-in-bins, balls-in-bins will generally use more bands because Choquette-Choo et al.’s sampling scheme uses a less random method, i.e. offers less amplification, as the number of bands increases, whereas balls-in-bins’ randomness does not change with the number of bands.
• We added to the appendix “Additional Figures for Section 5” a figure showing how the optimal number of bands varies with epsilon for the two methods, which confirms the above intuition, and a pointer from Figure 3.a to this appendix.

Suggestions for Figure 1

• We have added a clarification to the caption that says each epoch is one row in the figure.

Will the practical variant of balls-in-bins batching in Appendix H complicate the privacy analysis?

• The privacy analysis of the practical balls-in-bins variant in App H is the same as that of the balls-in-bins we analyze! The zero-padding and trimming are both accounted for in the analysis of balls-in-bins - padding does not matter because our privacy analysis is effectively analyzing sum queries, and truncating is the same as some examples having zero gradient which is accounted for by our analysis.

Should it be $log(1/err)$?

• Yes, the reviewer is correct, thanks for pointing this out. We have fixed the error.

“Could the authors provide the key intuition as to why the banded may restrict utility and efficiency, or discuss any specific scenarios or applications where non-banded C matrices are particularly beneficial?”

• Effectively, the added memory/runtime requirement of using a b-banded matrix is linear in b, and to the best of our knowledge, to achieve within a constant factor of the utility of a full lower-triangular matrix requires b = Omega(n) (e.g. Theorem 6 of Kalinin and Lampert https://arxiv.org/abs/2405.13763). So in general, one must choose between efficiency and utility when using banded matrices. In contrast Dvijotham et al. https://arxiv.org/abs/2404.16706 gives a non-banded matrix family that achieves (1+o(1)) times the optimal utility and the computational overhead is O(log n), which shows we can get the “best of both worlds” by choosing non-banded matrices.

Could the authors further explain why wasted computational resources would be a problem?

• The main reason we pad the batch is to keep the batch size fixed across iterations. This way, we only need to do XLA compilation of the gradient operation once across all of training, as opposed to once for each new batch size. However, the cost of this is we now spend part of our computation on these padding examples, whereas e.g. without DP / random batching we would spend all of our computation on actual examples.