A Simple and Practical Algorithm for Differentially Private Data Release

By Moritz Hardt, Katrina Ligett, Frank McSherry. 2010

552 citations recorded by the source corpus.

We present a new algorithm for differentially private data release, based on a simple combination of the Multiplicative Weights update rule with the Exponential Mechanism. Our MWEM algorithm achieves what are the best known and nearly optimal theoretical guarantees, while at the same time being simple to implement and experimentally more accurate on actual data sets than existing techniques.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Privacy & Security

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 Computational Theory and Mathematics

In Privacy & Security

Citations in the corpus

Marginal Release Under Local Differential Privacy (2017, methodology): “The use of Hadamard transform for mate-rializing marginals was considered by early work in the centralized differential privacy model, but has fallen from favor in the centralized model, supplanted by more involved privacy mechanisms [7, 19, 34].”
Extremal Mechanisms for Local Differential Privacy (2014, methodology): “The typical recipe is to propose a differentially private mechanism inspired by [11, 13, 26, 20], and then establish its near-optimality by comparing the achievable utility to a converse, for example in principal component analysis [8, 5, 19, 24], linear queries [21, 18], logistic regression [7] and”
Differentially Private Password Frequency Lists (2016, background): “[16] found an alternative differentially private algorithm that can provide accurate answers to many queries given a very low dimensional dataset (e.”
Fingerprinting codes and the price of approximate differential privacy (2013, background): “Their work was improved on in several important aspects [16, 19, 30, 25, 22, 24].”
Differential Privacy: An Economic Method for Choosing Epsilon (2014, methodology): “For the budget constraint, we need(eε − 1)EN+ δWN≤ B. Suppose we are in the social network scenario we described in Section5, with the same budgetB = 2.0× 106 we used for the(ε ,0)-private MWEM algorithm.”
Proving Differential Privacy in Hoare Logic (2014, background): “…and its representation as a predicate on memori s. Contributions: The main contribution of the paper (§III ) is a program transformation that operates on programs built from sequential, non-probabilistic constructs and differentially private, probabilistic primitives—such as the Laplace and…”
Private Multiplicative Weights Beyond Linear Queries (2014, methodology): “Moreover, private multiplicative weights was shown to have a number of practical advantages [18], including good accuracy and running time in practice on low-dimensional datasets, parallelism, and simple implementation, all of which are preserved by our extension.”
The Staircase Mechanism in Differential Privacy (2015, background): “For example, Hardt and Talwar [42] study the tradeoff between privacy and error for answering a set of linear queries over a histogram in a differentially private way, where the error is defined as the worst expectation of the -norm of the noise among all possible query output.”
Differentially private model selection with penalized and constrained likelihood (2016, background): “…differentially private mechanisms and efficient algorithms for private data release, e.g. the Laplace noise perturbation mechanism (Dwork et al., 2006), the exponential mechanism (McSherry and Talwar, 2007), releasing contingency tables (Barak et al., 2007) and boosting (Hardt et al., 2012).”
PrivateSQL: A Differentially Private SQL Query Engine (2019, background): “, histograms, CDFs, marginals on a single table) [7,20,34,35,37,40], sub-graph queries (e.”
The Complexity of Differential Privacy (2017, background): “2) to identify queries that will generate an update (rather than wasting time on queries that do not generate an update) [61].”
Differentially Private Chi-squared Test by Unit Circle Mechanism (2017, methodology): “(Barak et al., 2007; Li et al., 2010; Hardt et al., 2012; Li & Miklau, 2012; Gaboardi et al., 2014) have suggested methods of calculating a differentially private contingency table while avoiding this problem.”
Differentially Private Mixture of Generative Neural Networks (2017, methodology): “4After clipping each record to have L1-norm avg||x||1 = 12, the sensitivity of queries is set to 12, and the iterations of the algorithm is set to 50 [13].”
Differentially private sequential data publication via variable-length n-grams (2012, background): “nisms, such as the matrix mechanism [13] and the MWEM mechanism [11].”