Response to reviewer aP5d
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.