A Randomized Approach for Tight Privacy Accounting
This work addresses a key bottleneck in differential privacy accounting for researchers and practitioners, offering a novel method to enhance privacy guarantees in machine learning applications.
The paper tackles the challenge of providing strict upper bounds for privacy parameters in differential privacy compositions by introducing the estimate-verify-release paradigm, which uses a randomized Monte Carlo verifier to improve accuracy and efficiency, leading to better utility-privacy tradeoffs in privacy-preserving machine learning.
Bounding privacy leakage over compositions, i.e., privacy accounting, is a key challenge in differential privacy (DP). The privacy parameter ($\eps$ or $δ$) 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. The core component of the EVR is privacy verification. We develop a randomized privacy verifier using Monte Carlo (MC) technique. Furthermore, we propose an MC-based DP accountant that outperforms existing DP accounting techniques in terms of accuracy and efficiency. Our empirical evaluation shows the newly proposed EVR paradigm improves the utility-privacy tradeoff for privacy-preserving machine learning.