An Adaptive Mechanism for Accurate Query Answering under Differential Privacy

By Chao Li, Gerome Miklau. 2012

127 citations recorded by the source corpus.

We propose a novel mechanism for answering sets of counting queries under differential privacy. Given a workload of counting queries, the mechanism automatically selects a different set of "strategy" queries to answer privately, using those answers to derive answers to the workload. The main algorithm proposed in this paper approximates the optimal strategy for any workload of linear counting queries. With no cost to the privacy guarantee, the mechanism improves significantly on prior approaches and achieves near-optimal error for many workloads, when applied under (e, δ)-differential privacy. The result is an adaptive mechanism which can help users achieve good utility without requiring that they reason carefully about the best formulation of their task.

Subfields: Artificial Intelligence, Computer Science Applications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

Citations in the corpus

A Simple and Practical Algorithm for Differentially Private Data Release (2010, methodology): “In Section 3.1 we turn to an empirical comparison of our algorithm with [18] and additional related work on range queries [25, 17, 18, 19, 20, 21].”
PrivBayes: private data release via bayesian networks (2014, background): “Once noise is added to x (or some transformation of it) to obtain another vector x∗, the noise com- pletely dominates the original signal, making the published vector x∗ next to useless.”
A Semi-Supervised Learning Approach to Differential Privacy (2013, background): “Experimental Setup: In general, many of the differential privacy-preserving mechanisms are known to yield accurate results when they are run in conjunction with large data sets [6], [4], [11].”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, methodology): “For this setting, Hardt et al. (2010) introduced MWEM-mechanism based on private multiplicative weights, Li & Miklau (2012)’s mechanism is based on Matrix Mechanisms; Dual Query by Balle & Wang (2018) algorithm views the synthetic data generation setup as a zero-sum game.”
Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing (2016, background): “…works have focused on this problem, where they seek to release a contingency table in a differentially private way that also sat-isﬁes some known consistency properties of the underlying data (Barak et al., 2007; Li et al., 2010; Hardt et al., 2012; Li and Miklau, 2012; Gaboardi et al., 2014).”
Differentially private histogram publication (2012, unknown): “[21][22].”
Private Heavy Hitters and Range Queries in the Shuffled Model (2019, methodology): “To turn this into a protocol with small maximum communication in the shufﬂed model, we develop an approach analogous to the matrix mechanism [39, 40].”
On the Power of Multiple Anonymous Messages (2019, unknown): “To turn this into a protocol with small maximum communication in the shuﬄe model, we develop an approach analogous to the matrix mechanism [74,75].”
EKTELO: A Framework for Defining Differentially-Private Computations (2018, background): “HR Thresholding SG Greedy-H 9 [22] DAWA PD TR SG LM LS”
A Data- and Workload-Aware Query Answering Algorithm for Range Queries Under Differential Privacy (2014, methodology): “Hence we extend ideas from prior work [16, 23] that efficiently compute approximately optimal query strategies.”
The matrix mechanism: optimizing linear counting queries under differential privacy (2015, methodology): “8b, the Gaussian mechanism with the matrix mechanism using the hierarchical strategy [19], the wavelet strategy [28], and the strategy generated using the eigen-design algorithm [21].”