Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions
This work addresses a key bottleneck in differential privacy accounting for researchers and practitioners, offering incremental improvements in accuracy and efficiency.
The paper tackles the problem of approximating privacy loss distributions (PLD) for tighter differential privacy guarantees by introducing a novel discrete approximation method that supports both pessimistic and optimistic estimates, with experiments showing it works with larger discretization intervals and provides better approximations than existing methods.
The privacy loss distribution (PLD) provides a tight characterization of the privacy loss of a mechanism in the context of differential privacy (DP). Recent work has shown that PLD-based accounting allows for tighter $(\varepsilon, δ)$-DP guarantees for many popular mechanisms compared to other known methods. A key question in PLD-based accounting is how to approximate any (potentially continuous) PLD with a PLD over any specified discrete support. We present a novel approach to this problem. Our approach supports both pessimistic estimation, which overestimates the hockey-stick divergence (i.e., $δ$) for any value of $\varepsilon$, and optimistic estimation, which underestimates the hockey-stick divergence. Moreover, we show that our pessimistic estimate is the best possible among all pessimistic estimates. Experimental evaluation shows that our approach can work with much larger discretization intervals while keeping a similar error bound compared to previous approaches and yet give a better approximation than existing methods.