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$.
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