Principled Evaluation of Differentially Private Algorithms using DPBench

By Michael Hay, Ashwin Machanavajjhala, Gerome Miklau, Yan Chen, Dan Zhang. 2015

166 citations recorded by the source corpus.

Differential privacy has become the dominant standard in the research community for strong privacy protection. There has been a flood of research into query answering algorithms that meet this standard. Algorithms are becoming increasingly complex, and in particular, the performance of many emerging algorithms is data dependent, meaning the distribution of the noise added to query answers may change depending on the input data. Theoretical analysis typically only considers the worst case, making empirical study of average case performance increasingly important. In this paper we propose a set of evaluation principles which we argue are essential for sound evaluation. Based on these principles we propose DPBench, a novel evaluation framework for standardized evaluation of privacy algorithms. We then apply our benchmark to evaluate algorithms for answering 1- and 2-dimensional range queries. The result is a thorough empirical study of 15 published algorithms on a total of 27 datasets that offers new insights into algorithm behavior---in particular the influence of dataset scale and shape---and a more complete characterization of the state of the art. Our methodology is able to resolve inconsistencies in prior empirical studies and place algorithm performance in context through comparison to simple baselines. Finally, we pose open research questions which we hope will guide future algorithm design.

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

Citations in the corpus

Fair decision making using privacy-protected data (2019, methodology): “Maximizing the accuracy achievable under differentially privacy has been a major focus of recent privacy research, resulting in many sophisticated algorithmic techniques [16, 22].”
Bolt-on Differential Privacy for Scalable Stochastic Gradient Descent-based Analytics (2016, methodology): “This work was supported by NSF under award 1253942 and by a gift from Google.”
Optimizing error of high-dimensional statistical queries under differential privacy (2018, methodology): “For 1D and 2D cases, we use representative datasets from the DPBench study [18], Patent and BeijingTaxiE (which we call Taxi).”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, unknown): “Interesting work has been done in both theCDPmodel [8, 22, 30, 33, 34, 39, 54– 56, 58, 70, 71, 75, 85, 89, 90, 100–102, 104, 105, 107] and the LDP model [13, 32, 42, 44, 91, 95–97, 108].”
Practical Differential Privacy for SQL Queries Using Elastic Sensitivity (2017, background): “[23] define the term scale- exchangeability to describe the trend of decreasing error with increasing sample size.”
When Relaxations Go Bad: "Differentially-Private" Machine Learning (2019, unknown): “Orthogonal to our work, Ding et al. [13] and Hay et al. [27] evaluate the existing di ﬀ erential privacy implementations for the correctness of implementation.”
Finite Sample Differentially Private Confidence Intervals (2017, background): “(See Steinke and Ullman (2015) for a proof of such a statement for computing summary statistics of a dataset rather than inference, and Hay et al. (2016) for an informal claim along these lines.”
Towards Practical Differential Privacy for SQL Queries (2017, background): “[32] define the term scale- exchangeability to describe the trend of decreasing error with increasing population size.”
Synthetic Data for Social Good (2017, methodology): “In our work on DataSynthesizer we leverage recent advances in practical differential privacy [12] and privacy-preserving generation of synthetic datasets [16, 24].”
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].”
EKTELO: A Framework for Defining Differentially-Private Computations (2018, methodology): “4 that the algorithms from the DPBench benchmark [17] can be readily re-implemented in ✏ktelo.”