About the bisection method used for converting RDP to approximate DP

[spliew]

Thanks for the great work! Not sure if I should submit the issue here, but let me just do it anyway.

In the paper, it is suggested that one should use bisection to solve Equation 2 efficiently, inferring that the sum of a monotonically increasing function and a monotonically decreasing function is quasi-convex/unimodal (Corollary 38). This however does not seem to be correct as the sum of these functions is not always quasi-convex/unimodal. See this example.

Therefore, it seems to me that one could not use bisection to convert RDP to approximate DP to arbitrary precision since the optimization is not quasi-convex/unimodal?

[yuxiangw]

Thanks for the question! Maybe take a look at the proof of Corollary 32 here: https://journalprivacyconfidentiality.org/index.php/jpc/article/view/723/702

It doesn't work for any arbitrary RDP bound, but if they are instantiated by one pair of distributions, i.e., they are the Renyi divergence (or log-CGF) of a particular pair of distributions then it works.

The other thing is that if you have weirdly looking RDP bound that doesn't satisfy the properties, you may consider projecting it first into a feasible region using what we wrote on Page 24 of the above paper titled Projecting a CGF upper bound.

Lastly, even if you do not do any projection, the bisection approach will return some solution (not necessarily optimal alpha), but the resulting approx-DP bound you to get will be a valid DP guarantee.

Happy to discuss further.