Optimizing linear counting queries under differential privacy

By Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, Andrew McGregor. 2009

368 citations recorded by the source corpus.

Differential privacy is a robust privacy standard that has been successfully applied to a range of data analysis tasks. But despite much recent work, optimal strategies for answering a collection of related queries are not known. We propose the matrix mechanism, a new algorithm for answering a workload of predicate counting queries. Given a workload, the mechanism requests answers to a different set of queries, called a query strategy, which are answered using the standard Laplace mechanism. Noisy answers to the workload queries are then derived from the noisy answers to the strategy queries. This two stage process can result in a more complex correlated noise distribution that preserves differential privacy but increases accuracy. We provide a formal analysis of the error of query answers produced by the mechanism and investigate the problem of computing the optimal query strategy in support of a given workload. We show this problem can be formulated as a rank-constrained semidefinite program. Finally, we analyze two seemingly distinct techniques, whose similar behavior is explained by viewing them as instances of the matrix mechanism.

Subfields: Artificial Intelligence, Sociology and Political Science

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 Sociology and Political Science

Citations in the corpus

Functional Mechanism: Regression Analysis under Differential Privacy (2012, background): “In particular, Hay et al. [13], Li et al. [17], Xiao et al. [30], and Cormode et al. [6] present methods for minimizing the worst-case error of a given set of count queries; Barak et al. [2] and Ding et al. [8] consider the publication of data cubes; Xu et al. [31] and Li et al. [18] focus on…”
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].”
Differential Privacy for Deep and Federated Learning: A Survey (2022, background): “Li et al. [77] represent the main query as a set of linear base queries on the dataset’s attributes.”
Differentially private sequential data publication via variable-length n-grams (2012, background): “nisms, such as the matrix mechanism [13] and the MWEM mechanism [11].”
GUPT: privacy preserving data analysis made easy (2012, positive): “A number of advances in differential privacy have sought to improve the accuracy of very specific types of data queries such as linear counting queries [14], graph queries [12] and histogram analysis [11].”
On the Power of Multiple Anonymous Messages (2019, neutral): “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].”
Differentially Private High-Dimensional Data Publication via Sampling-Based Inference (2015, methodology): “There have been a series of techniques proposed for differentially private lowdimensional data publication [1,2,6,9,12,17,18,24,25,27,30].”
An Adaptive Mechanism for Accurate Query Answering under Differential Privacy (2012, methodology): “It is possible to compute an exact solution to OptStrat(W) by representing it as a convex optimization problem [14].”
EKTELO: A Framework for Defining Differentially-Private Computations (2018, methodology): “The rest of the plan follows the “select-measure-reconstruct” paradigm, an approach exemplified by the matrix mechanism [24, 27] and used in several state-of-the-art algorithms [17].”
Differentially Private Hierarchical Count-of-Counts Histograms (2018, background): “Extensions for optimizing various count queries have also been proposed [23, 10, 18].”
Towards Practical Differential Privacy for SQL Queries (2017, methodology): “The Matrix Mechanism [37] and MWEM [30] algorithms build an approximation of the true database using differentially private results from the underlying mechanism; the approximated database is then used to answer questions in the workload.”
A Data- and Workload-Aware Query Answering Algorithm for Range Queries Under Differential Privacy (2014, methodology): “According to [15], scaling up all queries in Yc by a positive constant does not change the mean squared error of answering any query using Yc.”
On significance of the least significant bits for differential privacy (2012, background): “The distribution of ˜ f ϵ on two inputs where f ( D ) = 0 and f ( D ′ ) = 1 is plotted in Figure 1.”
Compressive mechanism: utilizing sparse representation in differential privacy (2011, background): “, wavelets [20], trees [12] and linear summation basis [14, 10, 5].”
Differentially private histogram publication (2012, background): “[7] propose an approach that generalizes both Hay et al.”