Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement
Differentially private stochastic gradient descent (DP-SGD) has been instrumental in privately training deep learning models by providing a framework to control and track the privacy loss incurred during training. At the core of this computation lies a subsampling method that uses a privacy amplification lemma to enhance the privacy guarantees provided by the additive noise. Fixed size subsampling is appealing for its constant memory usage, unlike the variable sized minibatches in Poisson subsampling. It is also of interest in addressing class imbalance and federated learning. However, the current computable guarantees for fixed-size subsampling are not tight and do not consider both add/remove and replace-one adjacency relationships. We present a new and holistic R{é}nyi differential privacy (RDP) accountant for DP-SGD with fixed-size subsampling without replacement (FSwoR) and with replacement (FSwR). For FSwoR we consider both add/remove and replace-one adjacency. Our FSwoR results improves on the best current computable bound by a factor of $4$. We also show for the first time that the widely-used Poisson subsampling and FSwoR with replace-one adjacency have the same privacy to leading order in the sampling probability. Accordingly, our work suggests that FSwoR is often preferable to Poisson subsampling due to constant memory usage. Our FSwR accountant includes explicit non-asymptotic upper and lower bounds and, to the authors' knowledge, is the first such analysis of fixed-size RDP with replacement for DP-SGD. We analytically and empirically compare fixed size and Poisson subsampling, and show that DP-SGD gradients in a fixed-size subsampling regime exhibit lower variance in practice in addition to memory usage benefits.
Paper
Similar papers
Peer review
Summary
The paper studies the Rényi differential privacy (RDP) guarantees of the subsamplied Gaussian mechanism with fixed-sized random minibatches, when the so called add/remove neighborhood relation of datasets is considered. It uses similar techniqes as were used in the paper Mironov, Ilya, Kunal Talwar, and Li Zhang. "R\'enyi differential privacy of the sampled gaussian mechanism." arXiv preprint arXiv:1908.10530 (2019), which augmented the seminar paper Deep Learning with DP (Abadi et al., 2016) and gave rigorous RDP guarantees for the Poisson subsampled DP-SGD. The paper also studies both analytically and numerically the benefits of carrying out subsampling with fixed-sized minibatches instead of Poisson subsampling.
Strengths
- The analysis looks solid, generally a well-written paper - The variance analysis and the numerical experiments showing the benefits of fixed-size subsampling without replacement seem novel and interesting - The analysis for the "with replacement" subsampling seems interesting though it is quite limited
Weaknesses
- Clearly the biggest deficit of the paper is that it does not take into account some of the recent research in this area. Most importantly, it overlooks the work Zhu, Yuqing, Jinshuo Dong, and Yu-Xiang Wang. "Optimal accounting of differential privacy via characteristic function." International Conference on Artificial Intelligence and Statistics. PMLR, 2022. https://proceedings.mlr.press/v151/zhu22c/zhu22c.pdf The main result of this paper is a special case of the Thm. 11 by Zhu et al. (2022) : If $(P,Q)$ are a dominating pair of distributions for the base mechanism in substitute relation, then the fixed-size random subsampling without replacement give a dominating pair $(q P + (1-q) Q, Q)$ for removal neighbours and $(P, (1-q) P + q Q)$ gives a dominating pair for add neighbors. Then, we know the dominating pair $(P,Q)$ of the Gaussian mechanism in case of substiture relation of datasets (pair of one-dimensional Gaussians) and the result of this paper's mmain result (Thm. 3.1) follows since if a pair if dominating pair for the hockey-stick divergence, by the Blackwell theorem it dominates also for other $f$-divergences. Since this "without replacement" result consitutes such a big part of the paper, I think this is a major deficit and there should be a major revision before accepting this paper. This with replacement upper bound seems interesting, however my impression is that it is quite conservative (see e.g. Fig. 7 of the appendix). Only the experimental results for the lower bound in case of "with replacement" are given in the main text.
Questions
Can you comment on the accuracy of the upper bound in case of "with replacement"? Is it still open/unclear, how tight those bounds are? Could you provide "with replacement" upper bounds also for the hockey-stick divergence, i.e., do you obtain a dominating pair of distributions for the hockey-stick divergence?
Rating
4
Confidence
4
Soundness
3
Presentation
3
Contribution
1
Limitations
Yes.
Thanks for the answers. But why would you need a result for replace-one adjacency? You define the neighborhood relation to be the add/remove neighborhood relation. On lines 80-81: > We define datasets $D$ and $D′$ to be adjacent if one can be obtained from the other by adding or removing a single element. Also, the proof of Thm 3.1 clearly shows that $D$ and $D'$ are of different sizes. Then, I think [Zhu et al., Thm. 11b](https://proceedings.mlr.press/v151/zhu22c/zhu22c.pdf) will give your result. On the right hand side of the bound of your Thm 3.1, you exactly have the dominating pair for the Gaussian mechanism under the replacement relation, just as required by [Zhu et al., Thm. 11b](https://proceedings.mlr.press/v151/zhu22c/zhu22c.pdf). Then you can use the results of Section 3 of [Mironov et al.](https://arxiv.org/pdf/1908.10530) to show that one of the Rényi divergences dominates the other which exactly gives your Thm. 3.1 (you also seem to use those results by Mironov et al.).
Thanks for asking for clarification on this. We agree with you that the steps you outline could provide an alternative path to the add/remove result in our Theorem 3.1. What we were highlighting in our last response is that our method of proof leads to a unified method for treating both add/remove and replace-one. The replace-one result is also of significant application value as was pointed out by JRin. Originally, we had the add/remove result in Theorem 3.1 in the main text while discussing replace-one in Appendix D.4. Based on your and JRin's comment, we have changed the main text to highlight the replace-one as well. We have also pointed out that the add/remove result could alternatively be obtained via the method you outline.
Thank you for the replies. In fact, I think the replace one result could also be derived directly from the results by [Zhu et al.](https://proceedings.mlr.press/v151/zhu22c/zhu22c.pdf). If you use their proposition 30, and combine it with the results of Section 3 of [Mironov et al.](https://arxiv.org/pdf/1908.10530) (i.e., onlly on of the cases needs to be considered), you get the RDP bound for that case as well.
Thanks for the answer. It is not immediately clear to us that the calculation you propose can be carried out explicitly in that case, but either way it requires substantial analysis/computation which is not done in Zhu et al. As we noted, the result in Zhu et al, as presented, is not amenable to implementation in practice, while our results are. Specifically, a significant aspect of our proposed method is the use of Taylor series expansions to capture the leading order behavior (when $q$ is small) while providing explicit computable bounds on the error terms to prevent privacy leakage. This aspect of our work is not considered in Zhu et al or Mironov et al.
Thank you for the reply. I confused your Section C.2 with your Section D.4. There, in Section D.4, it is diffiult for me to see why that RDP bounds should hold. Namely, you have a bound with a Rényi divergence between the mixtures $q \cdot \mathcal{N}( \Delta_1, \sigma^2) + (1-q) \cdot \mathcal{N}( 0, \sigma^2)$ and $q \cdot \mathcal{N}( \Delta_2, \sigma^2) + (1-q) \cdot \mathcal{N}( 0, \sigma^2)$. The derivation of this bound is omitted. Recently, [Lebeda et al.](https://arxiv.org/pdf/2405.20769) showed that the bound for the subsampling without replacement under the substiture relation does not at least have a hockey-stick upper bound with mixtures $q \cdot \mathcal{N}( -1, \sigma^2) + (1-q) \cdot \mathcal{N}( 0, \sigma^2)$ and $q \cdot \mathcal{N}( 1, \sigma^2) + (1-q) \cdot \mathcal{N}( 0, \sigma^2)$, one has to use bounds such as Prop. 30 by [Zhu et al.](https://proceedings.mlr.press/v151/zhu22c/zhu22c.pdf). Thus, I am a bit suprised to see this result given in Section D.4, and I think a detailed derivation would be needed. Also, I don't see where the bound of Eq. (108) comes from, why is there no additional factor 2 (or 4 after squaring). I do acknowledge the contribution in making the RDP bound calculations faster, but I think the paper would benefit some polishing and by piutting the results in a context.
Thanks for the question. We want to clarify the notion of "worst-case" in this context that might have created some confusion: Our method gives "an" upper bound vs. the "tightest" bound. Based on your comments and also those of uSpK, we have added additional details to Appendix D to make our derivation clearer. We hope that the following outline clarifies it: To show that the Gaussian mixtures provide an upper bound on the worst case, we use the probabilistic Lemma A1 that decomposes the transition probabilities of mechanism. In the replace-one case the role of $D$ and $D'$ are symmetric and so they both satisfy a decomposition of the form (31). Then using convexity, the Renyi divergence between Eq.31(with $D$) and Eq.31(with $D'$) is bounded above by maximum over $b^\prime,\widetilde{b}$ of the Renyi divergence between Gaussian mixtures, as in Eq.102. The only property of the divergence used in these steps is quasiconvexity, and so they apply to the hockey-stick divergence as well, though our subsequent Taylor expansion calculations that lead to explicit computable bounds are specific to Renyi. We emphasize that we only compute an upper bound and not the tightest upper bound, so there is no conflict with Lebeda et al, though we still obtain tighter bounds than the previous state-of-the-art explicit computable bound in Wang et al. The examples in Lebeda et al. seem to highlight the difficulty of obtaining the tightest possible bound on the hockey-stick divergence, which is an interesting but different theoretical problem than what we achieved in this work. As to your other question, the factor of 4 is contained in our definition of $r_t$; see eq. (34).
Summary
This paper analyzes Differentially Private-SGD with fixed batch size (with and without replacement), through the lens of Rényi-DP. The bounds without replacement have a much better constant than previous ones; the ones with replacement are brand new.
Strengths
- The results are important and likely to be impactful in the niche of DP deep learning. It’s cool to see progress on DP analysis that gets closer to what practitioners actually do. - The paper is really well written and thorough in its discussions. I really enjoyed reading it.
Weaknesses
It’s a bit of a nitpick, but the paper keeps claiming that this analysis is DP-SGD specific, and that’s what enables the tight bounds. It seems like it is specific to: - the Gaussian mechanism (with specific subsampling approaches) - and I guess additive contributions of datapoints to the function? Anyway, it might be good to give the specifics in a slightly more general/abstract fashion, and then discuss why it applies to well to SGD? Just so that the reader doesn’t expect tight couplings with the optimization or something, and also because it may be slightly more broadly useful. Minor: - several citations seem off: the “standard differential privacy (DP)” citation is CDP, poisson sampling from RDP cites the RDP paper instead of this one I assume https://arxiv.org/pdf/1908.10530. - "even without using the convexity technique” p. 6 -> this has never been mentioned before. You need more details here for context.
Questions
Since you reduce to the same intermediary quantity as https://arxiv.org/pdf/1908.10530 (in Eq. 6), does it mean that: - the bound of that paper applies as-is to fixed batches using your proof (i.e., if one were using the Opacus accountant with fixed batches as a heuristic, it’s actually not a heuristic)? - if not, why is that? - if so, how does your new bound compares? (other than enabling the analysis with replacement, which is cool!) I think that the paper would benefit from discussing those to give a bit more context. S4.2 is related, as it gives an interesting discussion of where the different factor comes from (so the quantity is not identical I guess), but not all of this, like whether you could use the previous approximation as is, and how the two numerical procedures compare. After reading S4.2, I am wondering if the difference is a bit artificial, or at least tied to the notion of sensitivity. For instance, Poisson sampling would also pay a factor two under the change one definition (I think?) whereas your approach would mostly not change I believe (I only skimmed the appendix on sensitivity to I’m not completely sure, but intuitively it’d make sense—the section doesn’t seem to discuss the implications on Poisson vs. fixed batch). Is it the case that your approach pays a 2x factor, but also gets the stronger change-one for free, whereas Poisson gets the better guarantee under add/remove, but its equivalent under change-one? It would be an interesting thing if that’s the case I think (change-one is pretty popular in other applications, I don’t think it’s really less conventional as the paper claims).
Rating
7
Confidence
4
Soundness
4
Presentation
4
Contribution
4
Limitations
N/A
Summary
The paper first proves new privacy bound for the subsampled Gaussian mechanism under fixed-size sampling with and without replacement, which improves over the tightest known prior results in (Wang et al. 2019) by a constant of four. The proofs rely on a careful coupling of the sampling processes on neighboring datasets (similar to the design in Wang et al. 2019) to reduce the problem of analyzing divergence between Gaussian mixtures, for which the analyses in (Mironov et al. 2019) are applicable. - For fixed-size sampling without replacement, the paper proves integral upper bounds for the remainder term of the Taylor expansion of the privacy bound, to obtain tighter constants compared to the privacy bound in Wang et al. 2019. - The method extends to fixed-size sampling with replacement. It allows an upper bound that is similar to the upper bound for sampling without replacement in the leading term to sampling probability q. The authors also prove a lower bound under such settings and numerically investigate its dependence on the batch size and the Renyi divergence order. - The authors analytically showed that the empirical gradient variance is larger under Poisson sampling compared to fixed-size sampling, but the privacy bound is smaller under Poisson sampling compared to fixed-size sampling, indicating an interesting privacy-utility trade-off depending on the choice of sampling schemes, when fixing the sampling probability the same.
Strengths
- An interesting way of computing DP guarantee for subsampled Gaussian mechanism, via computing integral upper bounds for the remainder term of its Taylor expansion. - The proposed method yields a tighter RDP guarantee for subsampled Gaussian mechanism under fixed-size sampling without replacement, compared to prior results (Wang et al. 2019) by a constant factor of four. - The method extends to fixed-size sampling with replacement. It allows an upper bound that is similar to the upper bound for sampling without replacement in the leading term to sampling probability q. The authors also prove a lower bound under such settings and numerically investigate its dependence on the batch size and the Renyi divergence order.
Weaknesses
- The reason for the improved constant factor compared to (Wang et al.) is not crystal clear. Is the integral upper bound for the remainder term of Taylor expansion of the DP bound contributing to the tighter constant? Unfortunately, the Taylor expansion is not explained in much detail in the main paper (e.g., in Theorem 3.2, the crucial terms related to $A$ and $M$ are not presented nor explained). - Although it is interesting that the paper shows tighter constant in leading order term of the DP bound (via analytical approach), the value of this contribution in practice needs more explanation. As the divergence between Gaussian mixtures could be tightly computed numerically following (Mironov 2019.), it is unclear why we need an tighter analytical bound given by integral upper bound for the remainder term of Taylor expansion of the DP bound.
Questions
1. The reason for improved tightness of DP bound by a constant factor (see weakness for more details) 2. It is interesting that the paper shows that Poisson sampling enables smaller RDP bound than fixed-size sampling when keeping the sampling ratio the same. However, I wonder if it is a phenomenon that is unique to the add-or-remove-one notion of differential privacy. Could the authors comment on whether there will be a similar gap between Poisson sampling and fixed-size sampling when considering the replace-one notion of differential privacy?
Rating
5
Confidence
3
Soundness
3
Presentation
2
Contribution
3
Limitations
N/A
Summary
This paper studies the Renyi DP guarantees of a with- or without replacement subsampled Gaussian mechanism. Authors present a privacy analysis tailored for the subsampled Gaussian mechanism, which improves the earlier general bound for $\epsilon(\alpha)$ by Wang et al. 2019 by a factor of four. Authors show analytically, that the subsampling induced variance (i.e. the variance of the noise arising from using minibatches instead of full data) is smaller for without replacement subsampling than for the more commonly used Poisson subsampling. Authors also give a theoretical analysis of the differences between WOR and Poisson subsampling, showing that the Poisson subsampling leads to approximately half the $\epsilon$ of the WOR sampling. Authors demonstrate empirically that for fixed noise level, the WOR leads to better accuracy than Poisson subsampling in a CIFAR10 based deep learning task, suggesting that the difference is due to the lower subsampling noise. Finally, authors show that the WOR sampling leads to more stable memory usage.
Strengths
The DP-SGD algorithm is by far the most widely applied tool for DP machine learning. Since WOR sampling is more commonly used in non-DP ML than Poisson subsampling, improving the privacy bounds for WOR sampling is a interesting and important contribution. The theoretical analysis based on Taylor expansion of the Renyi divergence is a novel contribution and allows stricter bounds than the general result by Wang et al. 2019. Furthermore, the fact that WOR results into smaller subsampling noise is an interesting finding as well. The numerical results for the accounting highlight the significant improvement over the current state-of-the-art WOR sampling privacy accounting, showing over a factor of two improvement in the $\epsilon$ after conversion to approximate DP bounds. Also the empirical comparison on memory usage demonstrates the benefits of WOR sampling.
Weaknesses
While the presented analysis provides important insights and improvements over the previous RDP analysis for WOR sampled Gaussian mechanism, I wonder if the problem is already solved with the modern privacy accounting tools. For example, Zhu et al. 2022 solve the WOR sampled Gaussian mechanism in their characteristic function formalism. Given that the conversion from RDP to approximate DP is lossy, I would imagine the bounds presented in this work are more loose than the bounds of Zhu et al when converted to approx DP domain. Since the approx DP bounds are more commonly used than RDP bounds, I'm not sure if the tight RDP analysis is really needed. Or is there some practical reason, e.g. an implementation difficulty, that would not allow using the characteristic function accounting for this problem? Zhu, Yuqing, Jinshuo Dong, and Yu-Xiang Wang. "Optimal accounting of differential privacy via characteristic function." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
Questions
- As you acknowledge towards the end of Section 3.5, Wang et al. 2019 use the substitute neighbourhood relation which differs from the add/remove used in this paper. Can you clarify, is this difference taken into account in Figure 3? - Fig. 2: I'm a bit confused on the upper bounds show in this Figure. It seems that after some $\alpha$, your proposed upper bound exceeds the one from Wang et al. Does this suggest that the Wang et al. bound is tighter in some regime of $\alpha$? - In the Appendix D, you derive the RDP bounds for the substitute relationship using mixture of Gaussians with weight $1-q$ on Gaussian centered at $0$ and weight $q$ for the "adjacent" point. A recent work by Lebeda et al. 2024, suggest that this might not be the worst-case distribution for woR-sampling (see Section 7 in Lebeda et al.). While their analysis is tailored for approximate-DP and not RDP, I wonder if the same holds RDP. **Typos and other minor things** - Eq. 57, extra parenthesis in the expression for $M_{\sigma, 4}$ - I guess the NN abbreaviation is never explained. However, I don't think using it is necessary for the paper to begin with as you analysis applies to any learning task using DP-SGD. - Fig. 2: the caption is overlapping with the axis label. Also, I think this figure is never referred to in text. - "... even without using the convexity technique; ...": which convexity technique are you talking about? - "$a_i = \nabla_\theta L(d_i) \cdot v$", what is the $v$ here? Also, since the gradient is multidimensional, are you talking about dimension-wise variance? - "addtional" Lebeda, Christian Janos, et al. "Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition." arXiv preprint arXiv:2405.20769 (2024).
Rating
4
Confidence
3
Soundness
2
Presentation
2
Contribution
3
Limitations
I think authors should still address whether other accounting tools can solve this problem more efficiently that their method in the approximate DP domain. Other than that I believe the limitations are well addressed.
Thank you for the replies! Thm. 11 by Zhu et al. 11 is independent of any accountant used to compute the privacy profiles. As I have pointed out in my review, from that theorem follows the Blackwell dominance as well and an existence of a post-processing function and furthermore the RDP bound you state in your paper. This unfortunately reduces the relevance of that particular result I think, and therefore I plan to keep my score.
Thanks for further clarification. We investigated the extension of Zhu et al.'s Thm 11 using Blackwell Thm as you suggested to validate if one can obtain our bounds in that manner. In the case of replace-one adjacency relations, we do not believe that the general Blackwell theorem ideas along with the results in Zhu et al are sufficient to reproduce our results. Theorem 11(b) in Zhu et al applies to add or remove adjacency for the subsampled mechanism. Proposition 30 of Zhu et al does address replace-one adjacency, but it does not derive a full dominating pair, as it must break the analysis into two cases based on alpha>=1 and alpha<1. Corollary 32 in Zhu et al does give general theory for constructing a dominating pair, but it is not explicit or readily implementable in practice due to the need to compute a Legendre of transform (Fenchel conjugate) as a function of $x$ for `every' $x\in[0,1]$. Therefore to the best of our knowledge, the result in Zhu et al. cannot be directly used to reproduce our new RDP bound for replace-one adjacency as found in our equation 110.
Thank you. My impression looking at how the theory works in your paper was that it did reduce to the same accounting at Mironov et al. 2019 (Since you reduce to the same intermediary quantity as https://arxiv.org/pdf/1908.10530 (in Eq. 6)). Could you give an intuition / place of divergence in your proof for why that is not the case? Thanks!
Thanks for asking for clarification on this. We get to a similar, but not identical expression, to that of Mironov et al. The difference is in the right-hand side of our eq.6, which differs from Mironov by the factor of 1/4 in the variances. This is due to the effects of fixed-size vs. Poisson subsampling. The key difference in the derivation in our Appendix A is contained in our Lemma A.1, as compered to Theorem 4 in Mironov et al. There we construct the random variables that lead to the appropriate decomposition of the mechanism. In particular, compare the construction of our $J$, $B'$, and $\widetilde{B}$ in the paragraph about Lemma A.1 with the random variable T defined at the start of the proof of Theorem 4 in Mironov, along with (implicitly) the random variable that selects whether the additional element x is included, leading to the mixture at the bottom of page 3 of Mironov. The construction of our $J$, $B'$, and $\widetilde{B}$ are the analogues that lead to the appropriate decomposition of the mechanism in the case of fixed-size subsampling, as proven in our Lemma A.1. This difference then propagates through the derivation, eventually leading to the difference by a factor of 1/4 in the variance as noted above. The key reason for this is that our eq 34-35 shows that the mechanism in the case of fixed-size subsampling has a sensitivity of twice that in the Poisson case. This is because in Poisson subsampling when the minibatch from $D$ differs from that of $D^\prime$ it is due to the inclusion of a single additional element. However, in fixed-size subsampling, when the minibatches are not identical then they differ by a replacement; this contributes more to the difference in means by a factor of $2$. Furthermore, in our analysis of fixed-size subsampling with replace-one adjacency in Appendix D.4 there are even greater differences between our analysis and that of Mironov et al. We added the text to highlight this difference with Mironov et al. and directed readers to our Appendix A and Lemma A.1 in this regard. Also, in our Appendix A, we added the intuition described above.
We thank reviewer uSpK again for their time and helpful feedback. As the discussion period comes to a close we ask the reviewer to consider our responses and whether their concerns are adequately addressed. In particular we have provided extensive discussion relating our work to the work of Zhu et al. in the general comments, as well as in response to reviewer Rv66. Thanks again!
Thanks for your response, and apologies for my very late response! I have now read the rebuttal, and authors have addressed many of my concerns. In your common response you state that "AFA is not specific to DP-SGD". This is of course true, since the particular accounting technique is not tailored for DP-SGD. However, my point was that the accounting of DP-SGD can be carried out with the results of Zhu et al. using the AFA (or any other accountant like the PRV accounting). However, I do acknowledge the possible numerical challenges these methods pose, whereas your method can give at least an upper bound for the privacy cost (when converted to approximate DP). Since the proposed bound is more tight than the one proposed by Wang et al. I believe the proposed method can provide useful insights on the privacy accounting. However, it would be very interesting to see, if the numerical accounting indeed fails for this privacy analysis, or how far it is from your bounds. One more question related to your response **Worst-case bounds for woR-sampling**. I'm not sure where in Appendix D you actually show that the worst-case is what is presented. It seems to me that you just plug in the Gaussian mixtures as the upper bound after eq. 102.
Thanks for the question. For FS-woR under add/remove adjacency the worst case bound is stated in eq. (6) in Theorem 3.1. For FS-woR under replace-one the worst case bound is stated in eq (102) in appendix D4. Both are derived by the method in Appendix A, wherein the mechanisms are decomposed into mixtures via Lemma A1: see eq (31)-(32). Then quasiconvexity is used to bound the mixture over $b',\widetilde{b}$, leaving only the mixture over q, which is the probability that the last sample (the one that can differ) is included. The essential difference that the adjacency relation makes is as follows: - In the add/remove case the first argument of Renyi divergence is decomposed via the mixture (31) while the second via (32) (as D' has one less element). After using quasiconvexity to bound the expectation over $b',\widetilde{b}$ by the maximum one obtains (6). where the Gaussian mixture is only in the first argument of the Renyi divergence. - In the replace-one case, D and D' have the same number of elements and so both arguments of the Renyi divergence are decomposed as in (31) but with different means (coming from D and D'). After using quasiconvexity, this leaves a Gaussian mixture in both arguments of the Renyi divergence. In both cases we then go on to obtain computable worst-case bounds using Taylor expansion with remainder. We have added additional details to Appendix D to make this derivation clearer. Also, we agree with you that investigating the practical boundaries of numerical methods in this context is a fruitful but separate research endeavor.
We thank reviewer kPGW again for their time and useful insights. As the discussion period comes to a close we ask that you consider our responses and whether your concerns have been adequately addressed. We tried to pay particular attention to clarifying remarks about improvement of the constant factor and the value of the contribution. Thanks again!
Thanks for the clarifications. I will keep the score -- I now understand better about the efficiency value of the work (compared to numerical computation for Gaussian mixtures). However, the reason for constant improvement is still not clear to me analytically, and I encourage the authors to add more discussions of the Taylor expansion terms in the main paper.
Decision
Accept (poster)