A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis

By Moritz Hardt, Guy N. Rothblum. 2010

473 citations recorded by the source corpus.

Subfields: Artificial Intelligence, 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 Privacy & Security

Citations in the corpus

Pure Differentially Private Summation from Anonymous Messages (2020, background): “Private summation is also closely related to functions in the widely studied class of counting queries (e.g., [Vad17, BLR08, HT10, HR10, NTZ13]).”
Differential Privacy for Growing Databases (2018, methodology): “In this section, we show how to modify the private multiplicative weights (PMW) algorithm for adaptive linear queries [HR10] to handle continuous data growth.”
Tight Lower Bounds for Differentially Private Selection (2017, background): “In particular, their work demonstrates that the private multiplicative weights algorithm [7] is nearly optimal.”
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”
Scalable Private Learning with PATE (2018, methodology): “There is previous work in differential privacy literature (Hardt & Rothblum, 2010; Roth & Roughgarden, 2010) where the mechanism first decides whether or not to answer a query, and then privately answers the queries it chooses to answer using a traditional noiseaddition mechanism.”
Advanced Probabilistic Couplings for Differential Privacy (2016, neutral): “The differential literature proposes several interactive algorithms; examples include private counters [14, 21], the Sparse Vector mechanism, and other algorithms using these mechanisms [30].”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “Convex optimization techniques have also played an important role in the development of algorithms for “simultaneous query release” (e.g., the line of work emerging from Hardt and Rothblum [24]).”
Minimax Optimal Procedures for Locally Private Estimation (2016, background): “…requires a formal definition of privacy, and differential privacy has been put forth as one such candidate (see, e.g., the articles Dwork et al. 2006; Blum, Ligett, and Roth 2008; Dwork, Rothblum, and Vadhan 2010; Hardt and Rothblum 2010; Hardt and Talwar 2010, and references therein).”
A learning theory approach to non-interactive database privacy (2008, neutral): “d in the course of a computation (which may be only polynomially many), as opposed to all queries which might potentially be asked, as is necessary for a non-interactive mechanism. Hardt and Rothblum [HR10] gave an improved mechanism for the interactive setting based on the multiplicative weights fr”
Calibration for the (Computationally-Identifiable) Masses (2017, methodology): “This implementation borrows ideas from the literature on diﬀerentially private query release and optimization [HR10, Ull15, HRRU14].”
Fingerprinting codes and the price of approximate differential privacy (2013, methodology): “[19] Dwork, C., Rothblum, G. N., and Vadhan, S. P. Boosting and differential privacy.”