A Randomized Approach for Tight Privacy Accounting

Understand

Bounding privacy leakage over compositions, i.e., privacy accounting, is a key challenge in differential privacy (DP).

• The privacy parameter ($\eps$ or $\delta$) is often easy to estimate but hard to bound.
• In this paper, we propose a new differential privacy paradigm called estimate-verify-release (EVR), which addresses the challenges of providing a strict upper bound for privacy parameter in DP compositions by converting an estimate of privacy parameter into a formal guarantee.
• The EVR paradigm first estimates the privacy parameter of a mechanism, then verifies whether it meets this guarantee, and finally releases the query output based on the verification result.