Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions
Authors: Vadym Doroshenko (Google), Badih Ghazi (Google Research), Pritish Kamath (Google Research), Ravi Kumar (Google Research), Pasin Manurangsi (Google Research)
Volume: 2022
Issue: 4
Pages: 552–570
DOI: https://doi.org/10.56553/popets-2022-0122
Abstract: 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 [18–20, 24] has shown that PLD-based accounting allows for tighter (ε, δ)-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 ε, 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 an existing method [24].
Keywords: privacy loss distribution, pessimistic approximation, optimistic approximation, privacy accounting, composition
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
