A Randomized Approach for Tight Privacy Accounting

Jiachen T. Wang, Saeed Mahloujifar, Tong Wu, Ruoxi Jia, Prateek Mittal

TL;DR

The paper introduces Estimate-Verify-Release (EVR), a new paradigm that converts accurate privacy parameter estimates into formal Differential Privacy (DP) guarantees. By using a randomized Monte Carlo verifier, it achieves significantly tighter privacy accounting and better model utility than traditional analytical upper bounds, especially in high-privacy regimes.

What Problem Does This Paper Address?

Differential Privacy (DP) relies on "accounting"—tracking the cumulative privacy loss ($\epsilon, \delta$) as an algorithm (like DP-SGD) repeatedly touches sensitive data. A major challenge is that while it is easy to estimate these parameters, it is mathematically difficult to prove tight upper bounds for them.

Existing tools like the Moments Accountant (MA) or Fast Fourier Transform (FFT) based methods often produce "loose" or conservative bounds. In regimes where $\delta$ needs to be very small (e.g., $< 10^{-10}$ for large-scale datasets), these bounds can become vacuous, even when the actual privacy loss is much lower. This forces researchers to use more noise than necessary, hurting the accuracy (utility) of machine learning models.

Figure 1: Traditional upper bounds (dashed lines) become loose at small $\delta$, while estimates (solid lines) remain accurate.

Methods

The authors propose a three-step workflow called the EVR paradigm:

  1. Estimate: Use an accountant to get a high-quality estimate of the privacy parameters $(\epsilon, \delta^{est})$.
  2. Verify: Use a new randomized Differential Privacy Verifier (DPV) to check if the mechanism actually satisfies that estimate.
  3. Release: If the verifier passes, release the model/query output; otherwise, terminate the program to prevent privacy leakage.

To make this practical, they developed a Monte Carlo (MC) based DP Verifier. Because "privacy-violating" events are rare (that's the point of DP!), naive sampling is inefficient. The authors use Importance Sampling with exponential tilting to specifically target these rare events, making the verifier both accurate and fast. They also introduce an MC Accountant that can track privacy loss iteration-by-iteration (online accounting) much more efficiently than previous methods.

Figure 2: An overview of our EVR paradigm. EVR converts an estimated (ε, δ) provided by a privacy accountant into a formal guarantee. Compared with the original mechanism, the EVR has an extra failure mode that does not output anything when the estimated (ε, δ) is rejected. We show that the MC-based verifier we proposed can achieve negligible failure probability (O(δ)) in Section 4.4.

Datasets

The authors evaluated their approach using:

  • CIFAR-100: Used for fine-tuning a BEiT (BERT Pre-training of Image Transformers) model that was pre-trained on ImageNet.
  • Synthetic Gaussian Compositions: Used to benchmark the accuracy of the MC Accountant against ground-truth analytical curves.

Key Insights and Ideas

  • Verification as a Formal Guarantee: The core "aha" moment is that a randomized verifier with a bounded false-positive rate can be used to enforce a formal DP guarantee. You don't need a perfect analytical proof if you have a reliable "test" that fails rarely.
  • Flipping the Script on Rare Events: By using Importance Sampling, the authors turn the "curse" of small $\delta$ (rare events) into a manageable computational problem. They "tilt" the sampling distribution to make privacy-loss events more frequent during the verification phase.
  • GPU-Native Accounting: Unlike traditional analytical methods that are often CPU-bound, Monte Carlo sampling is embarrassingly parallel. This allows for massive speedups using modern hardware.

Key Results

  • Tighter Privacy Analysis: EVR provides meaningful privacy bounds in regimes where state-of-the-art FFT methods fail. For example, it provides tight guarantees even when $\delta < 10^{-10}$.
  • Improved Utility: In CIFAR-100 fine-tuning experiments, the EVR paradigm achieved a ~7% relative reduction in test error for the same privacy budget $\epsilon$ compared to traditional upper-bounding methods.
  • Speed and Efficiency: The MC Accountant is roughly 5x faster than FFT-based methods for online accounting. Furthermore, using a single NVIDIA A100 GPU provided a $10^3$ speedup in sampling runtime compared to a CPU-only scenario.
  • Negligible Overhead: The time required for privacy verification is often less than $10^{-10}$ seconds per iteration, making it practically "free" compared to model training time.

Limitations and Future Work

  • PRV Requirement: The current MC-based verifier and accountant require the Privacy Loss Random Variable (PRV) of the individual mechanisms to be known and efficiently samplable. While this is true for the most common DP mechanisms (Gaussian, Laplace, Subsampled Gaussian), it limits the approach's immediate use for "black-box" or highly custom DP algorithms.
  • Generalization: The authors note that generalizing the MC-based verifier to a broader class of mechanisms beyond those used in DP-SGD is a key direction for future research.

Summary updated

Abstract

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.
BibTeX
@misc{wang2023randomized,
  author = {Jiachen T. Wang and Saeed Mahloujifar and Tong Wu and Ruoxi Jia and Prateek Mittal},
  title = {{A Randomized Approach for Tight Privacy Accounting}},
  year = {2023},
  eprint = {2304.07927},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.07927},
}
Figure