ABCDP: Approximate Bayesian Computation Meets Differential Privacy

Mijung Park, Wittawat JitkrittumarXiv 2019 · OpenReview

Abstract

Approximate Bayesian Computation (ABC) is a powerful tool for inference in likelihood-free models, yet it presents significant privacy risks when applied to sensitive datasets. We introduce ABCDP, a framework that integrates the Sparse Vector Technique (SVT) into the ABC rejection algorithm. By only consuming the privacy budget when a simulated sample is accepted, ABCDP significantly improves the trade-off between data privacy and posterior accuracy compared to standard noise-injection methods.

Introduction

Approximate Bayesian Computation (ABC) is the standard approach for performing inference on "likelihood-free" models—complex simulations common in epidemiology, cosmology, and genetics where the likelihood function is intractable. However, ABC requires repeated comparisons between simulated data and real-world observations. When these observations contain sensitive information, such as medical records, this process poses a major privacy risk.

Standard Differential Privacy (DP) techniques typically "leak" privacy budget with every query. Because ABC often requires millions of simulations to find a few "accepted" matches, a naive DP approach would exhaust the privacy budget almost instantly, leading to either a total loss of privacy or results too noisy to be useful.

Methodology

The core innovation of ABCDP is the application of the Sparse Vector Technique (SVT) to the ABC rejection algorithm.

SVT Integration

In SVT, a privacy cost is only incurred when a query returns a "positive" result—in this context, when a simulation is "close enough" to the real data to be accepted. "Negative" results (rejected simulations) are essentially "privacy-free." This is particularly effective for ABC because the process is naturally "sparse"; the vast majority of simulations are poor matches and are rejected.

Double Perturbation and Metrics

To guarantee DP, ABCDP adds Laplace noise to two components: the similarity threshold ($\epsilon_{abc}$) and the calculated distance between simulated and real data ($\rho$). The framework utilizes Maximum Mean Discrepancy (MMD) as a distance metric due to its bounded "global sensitivity," which simplifies the calibration of noise needed for privacy guarantees.

Experimental Evaluation

The authors evaluated ABCDP across three scenarios: toy synthetic data, COVID-19 outbreak data ($N=18$), and a Tuberculosis (TB) outbreak model ($N=100$ and $N=1000$).

Flip Probability and Sensitivity

A key theoretical contribution is the analysis of "flip probability"—the likelihood that the DP version of the algorithm accepts a parameter that the non-private version would have rejected. This provides a practical guideline for researchers to choose their sample size $c$ based on their available $N$.

Flip probability analysis across varying dataset sizes (N) and acceptance counts (c) on toy synthetic data.

As shown in the figure above, the flip probability decreases as the total privacy budget (epsilons) increases. Crucially, as the dataset size ($N$) increases, the sensitivity of the distance metric decreases ($O(1/N)$). This allows for higher accuracy with less noise on larger datasets.

Key Results

  • Convergence: Theoretical proofs show that error in the private posterior expectation decays as $N$ increases.
  • TB Model Accuracy: In TB simulations, ABCDP successfully recovered true parameters. With $\epsilon=1$, the mean absolute error dropped from ~4.5 to ~2.1 as $N$ increased from 100 to 1000.
  • Small Data Limits: The COVID-19 experiment highlighted the challenges of extremely small datasets ($N=18$), where high privacy requirements led to high variance, though the mean still tracked the outbreak trend.
  • Algorithm Choice: The variant where threshold noise is fixed (RESAMPLE=False) generally provided better accuracy for a fixed privacy budget than refreshing noise after every acceptance.

Discussion and Limitations

ABCDP demonstrates that ABC can be made private without sacrificing utility by leveraging the inherent sparsity of the rejection process. However, some limitations remain. The theoretical guarantees rely on bounded sensitivity; while "clipping" can address unbounded metrics, it introduces additional hyperparameters. Furthermore, while this work focuses on "pure" $\epsilon$-DP, future research could explore advanced composition techniques like Rényi DP to further reduce privacy loss within $(\epsilon, \delta)$-DP frameworks.

Summary updated

Abstract

We develop a novel approximate Bayesian computation (ABC) framework, ABCDP, that produces differentially private (DP) and approximate posterior samples. Our framework takes advantage of the Sparse Vector Technique (SVT), widely studied in the differential privacy literature. SVT incurs the privacy cost only when a condition (whether a quantity of interest is above/below a threshold) is met. If the condition is met sparsely during the repeated queries, SVT can drastically reduces the cumulative privacy loss, unlike the usual case where every query incurs the privacy loss. In ABC, the quantity of interest is the distance between observed and simulated data, and only when the distance is below a threshold, we take the corresponding prior sample as a posterior sample. Hence, applying SVT to ABC is an organic way to transform an ABC algorithm to a privacy-preserving variant with minimal modification, but yields the posterior samples with a high privacy level. We theoretically analyze the interplay between the noise added for privacy and the accuracy of the posterior samples.
BibTeX
@misc{park2019abcdp,
  author = {Mijung Park and Wittawat Jitkrittum},
  title = {{ABCDP: Approximate Bayesian Computation Meets Differential Privacy}},
  year = {2019},
  eprint = {1910.05103},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.05103},
}
Figure