Privacy Amplification for Matrix Mechanisms

Thank you for the supportive and thoughtful review. Below we address the weaknesses/questions raised by the reviewer.

“Could the authors discuss more about the computation cost and numerical stability of the proved privacy bound?”

In terms of computation cost, in Appendix F.2, we address the challenge of handling the potentially $2^n$ mixture components mentioned in the reviewer’s weaknesses. Specifically, by rounding the entries of $C$ to the nearest multiple of some discretization parameter $\Delta$, we can substantially reduce the number of mixture components at a small cost in accuracy. While we have not proven the asymptotic runtime of MMCC, we believe with the above discretization it should be $O(n^3 + n^2 \log^2 n \cdot f)$, where $f$ is some function (independent of $n$) of the above discretization and approximation parameters used in the PLD accounting. Furthermore, many parts of our implementation can be vectorized or parallelized.

In addition, for some specific classes of matrices, the computation can be dramatically sped up. For example, in Appendix F.4 we discuss how the calculation is much faster for the binary tree mechanism and for banded Toeplitz C.

For numerical stability, in our implementation, the issues which were inherent to our approach (i.e. that wouldn’t appear when doing PLD accounting for DP-SGD) had to do with the fact that the mixtures of Gaussians arising from product distributions may have components with very small probabilities, even when we use the discretization trick in Appendix F.2 to reduce the number of components. In this case, we can always move these small probabilities around and absorb the cost in our delta term. That is, we can take components with at most, say, $10^{-20}$ of the probability mass in the mixture of Gaussians, delete these components, and increase the probability mass of a different component to make sure the total probability remains 1. Each time we do this, we pay a cost of $10^{-20}$ in the final $\delta$ we report, but this is ultimately negligible compared to e.g. the choice of $\delta = 10^{-6}$ we used throughout the paper.

If there are specific questions the reviewer has about the runtime/implementation that were not discussed here, we would be happy to discuss them in followups.

“Related to the above question, how computationally feasible is it to compute the appropriate noise scale that ensures ($\epsilon, \delta$)-DP of the algorithm?”

The best approach we know of is to use binary search to (approximately) invert the function given by MMCC to compute $\epsilon$ given $\sigma$. So, in the aforementioned settings where MMCC can be run very quickly, one would need to pay a $\approx \log 1 / \Delta$ multiplicative factor to compute $\sigma$ up to precision $\Delta$, but the overall procedure is still quick. For general matrices, a single run of MMCC can take several hours or longer for $n \approx 2000$, and the $\log 1 / \Delta$ overhead may make this binary search infeasible.

Clarifications on Lemma B.4

Yes, this is a typo! Apologies for any confusion this caused and thanks for pointing this out; we will fix it in the revision.

As for the clarification on why the stated inequality suffices to prove the lemma: To clarify, we believe the reviewer’s question can be rephrased as follows: Since the hockey stick divergence for $M$ is $\max_t [ Pr_{x ~ M(D)} [x \geq t] - e^\epsilon Pr_{x ~ M(D’)}[x \geq t]]$, why does it suffice to bound $Pr_{x ~ M(D)} [x \geq t]$ by $Pr_{x ~ M’(D)} [x \geq t]$ and ignore the term depending on $D’$? The answer is that both $M(D’)$ and $M’(D’)$ are $N(0, \sigma^2)$, so the term depending on $D’$ is the same for both mechanisms. The proof can definitely be made more clear even after fixing the typos and we will rewrite it accordingly in the revision.

Thanks to the reviewer for their supportive review.

"This paper could be more easy to understand if the author could define the matrix mechanism formally in the beginning with some intuitive interpretation of each variable.”

Thanks for the suggestion on improving the clarity of the paper. To help the reader understand the matrix mechanism, we will discuss two common instances of the matrix mechanism in Section 1.2, where it is first formally defined. Specifically, we will:

• Move the discussion in Section 5 about the connection between the binary tree mechanism and the matrix mechanism to Section 1.2.
• Make explicit the connection between the workload matrix A and optimization algorithms such as DP-SGD/DP-FTRL. In particular, we will say when A is the all-ones lower-triangular matrix, and x is a stream of gradients computed in DP-FTRL then the rows of Ax are the sums of gradients seen so far. Then, the ith iterate in DP-FTRL is the initialization point plus ith row of Ax+Bz, i.e. the initialization plus the noisy sum of the first i gradients seen, and if C = I, we recover independently noising each gradient / DP-SGD.

(This is a partial duplicate of a response to reviewer 9Vpe)

Thank you for the supportive review. Below we address the question of the reviewer.

Can the author comment about the novelty of Theorem 3.1? It seems to be a simple extension of Lemma A.1 in [1]?

Some of the ideas in Theorem 3.1 by itself may not have high-degree of novelty; as the reviewer mentions Cohen and Lyu state something similar, and similar ideas appeared in Erlingsson et al. and Balle et al. (which we mention in the paper). There are some subtleties in correctly extending their Lemma A.1 to compositions of mechanisms instead of a single round mechanism, in a way that fits our use case. In our opinion, the main contributions of Section 3 are

• Explicitly writing down the general form
• The framework given by combining Theorem 3.1 with Observation 3.2 to analyze correlated noise mechanisms via a series of independent mechanisms, which we demonstrate is versatile in the later parts of the paper.

Thank you to the reviewer for their supportive and thoughtful comments. Here we wish to address some of the weaknesses put forth in the review:

“As compared to other FFT-based accounting methods, this algorithm should be much more time-consuming. It remains an interesting question to reduce the running time for some specific use cases.”

We agree this is an interesting direction, and one we are currently pursuing as followup work. If the reviewer has not done so already, they may be interested to read Appendix F where we discuss some tricks we use to speed up the calculation at a small cost in accuracy in our implementation. In addition, in Appendix F we discuss how for some special classes of matrices such as the binary tree mechanism and banded Toeplitz matrices, the computation can be dramatically sped up.

“I would like to see the authors further improve the clarity of the paper. For now, the paper is not quite friendly to the readers who do not have full background on DP-FTRL or DP accounting. One specific suggestion is to explain how DP-FTRL and binary-tree based algorithm fit into the framework defined in section 1.2.”

Thank you for the suggestion! To improve Section 1.2, we will:

• Move the discussion in Section 5 about the connection between the binary tree mechanism and the matrix mechanism to Section 1.2.
• Make explicit the connection between the workload matrix A and optimization algorithms such as DP-SGD/DP-FTRL. In particular, we will say when A is the all-ones lower-triangular matrix, and x is a stream of gradients computed in DP-FTRL then the rows of Ax are the sums of gradients seen so far. Then, the ith iterate in DP-FTRL is the initialization point plus ith row of Ax+Bz, i.e. the initialization plus the noisy sum of the first i gradients seen, and if C = I, we recover independently noising each gradient / DP-SGD.

(This is a partial duplicate of a response to reviewer 5cQp)