Optimal error of query sets under the differentially-private matrix mechanism
Preprint
Abstract
A common goal of privacy research is to release synthetic data that satisfies a formal privacy guarantee and can be used by an analyst in place of the original data. To achieve reasonable accuracy, a synthetic data set must be tuned to support a specified set of queries accurately, sacrificing fidelity for other queries. This work considers methods for producing synthetic data under differential privacy and investigates what makes a set of queries "easy" or "hard" to answer. We consider answering sets of linear counting queries using the matrix mechanism, a recent differentially-private mechanism that can reduce error by adding complex correlated noise adapted to a specified workload. Our main result is a novel lower bound on the minimum total error required to simultaneously release answers to a set of workload queries. The bound reveals that the hardness of a query workload is related to the spectral properties of the workload when it is represented in matrix form. The bound is tight and, because it satisfies important soundness criteria, it can serve as a reliable numerical measure of the "error complexity" of a workload.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Differentially Private Spatial Decompositions2012
- Differential Privacy via Wavelet TransformsIEEE Transactions on Knowledge and Data Engineering, 2010
- Boosting and Differential Privacy2010
- A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis2010
- On the geometry of differential privacy2010
- Differentially Private Data Release through Multidimensional PartitioningLecture Notes in Computer Science, 2010
- Smooth sensitivity and sampling in private data analysis2007
- Our Data, Ourselves: Privacy Via Distributed Noise Generation2006
- Eigenvalues, invariant factors, highest weights, and Schubert calculusBulletin of the American Mathematical Society, 2000
- Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-TotalsData Mining and Knowledge Discovery, 1997