Optimizing error of high-dimensional statistical queries under differential privacy
By Ryan McKenna, Gerome Miklau, Michael Hay, Ashwin Machanavajjhala. 2018
126 citations recorded by the source corpus.
Differentially private algorithms for answering sets of predicate counting queries on a sensitive database have many applications. Organizations that collect individual-level data, such as statistical agencies and medical institutions, use them to safely release summary tabulations. However, existing techniques are accurate only on a narrow class of query workloads, or are extremely slow, especially when analyzing more than one or two dimensions of the data. In this work we propose HDMM, a new differentially private algorithm for answering a workload of predicate counting queries, that is especially effective for higher-dimensional datasets. HDMM represents query workloads using an implicit matrix representation and exploits this compact representation to efficiently search (a subset of) the space of differentially private algorithms for one that answers the input query workload with high accuracy. We empirically show that HDMM can efficiently answer queries with lower error than state-of-the-art techniques on a variety of low and high dimensional datasets.
Subfields: Artificial Intelligence
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
- Ashwin Machanavajjhala
- Michael Hay
- Ninghui Li
- Gerome Miklau
- Somesh Jha
- Tianhao Wang
- Ryan McKenna
- Xi He
Citations in the corpus
- An Economic Analysis of Privacy Protection and Statistical Accuracy as Social Choices (2018, neutral): “The matrix mechanism is also under active development for use by the Census Bureau (McKenna et al. 2018; Kuo et al. 2018).”
- 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].”
- PrivateSQL: A Differentially Private SQL Query Engine (2019, background): “This component is probably the most well understood as it is an instance of a common problem studied in the DP literature – answering a set of linear queries on a single table [22, 31, 39].”
- Answering Multi-Dimensional Analytical Queries under Local Differential Privacy (2019, methodology): “[25] propose a method to collectively optimize errors in high-dimensional queries of a given workload under the centralized setting of DP.”