Iterative Constructions and Private Data Release

By Anupam Gupta, Aaron Roth, Jonathan Ullman. 2011

224 citations recorded by the source corpus.

In this paper we study the problem of approximately releasing the cut function of a graph while preserving differential privacy, and give new algorithms (and new analyses of existing algorithms) in both the interactive and non-interactive settings. Our algorithms in the interactive setting are achieved by revisiting the problem of releasing differentially private, approximate answers to a large number of queries on a database. We show that several algorithms for this problem fall into the same basic framework, and are based on the existence of objects which we call iterative database construction algorithms. We give a new generic framework in which new (efficient) IDC algorithms give rise to new (efficient) interactive private query release mechanisms. Our modular analysis simplifies and tightens the analysis of previous algorithms, leading to improved bounds. We then give a new IDC algorithm (and therefore a new private, interactive query release mechanism) based on the Frieze/Kannan low-rank matrix decomposition. This new release mechanism gives an improvement on prior work in a range of parameters where the size of the database is comparable to the size of the data universe (such as releasing all cut queries on dense graphs). We also give a non-interactive algorithm for efficiently releasing private synthetic data for graph cuts with error O(|V|1.5). Our algorithm is based on randomized response and a non-private implementation of the SDP-based, constant-factor approximation algorithm for cut-norm due to Alon and Naor. Finally, we give a reduction based on the IDC framework showing that an efficient, private algorithm for computing sufficiently accurate rank-1 matrix approximations would lead to an improved efficient algorithm for releasing private synthetic data for graph cuts. We leave finding such an algorithm as our main open problem.

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

Tight Lower Bounds for Differentially Private Selection (2017, background): “Selection problems appear in many natural statistical problems, including private multiple hypothesis testing [1], sparse linear regression [2], [3], finding frequent itemsets [4], and as subroutines in algorithms for answering exponentially many statistical queries [5], [6], [7], [8], [9], approxim”
Distributed Private Heavy Hitters (2012, methodology): “In our analysis, we will also make use of a simple tail bound on the sums of Laplace random variables: Theorem 2.10 (See, e.g. [GRU12]) .”
Calibration for the (Computationally-Identifiable) Masses (2017, methodology): “Additionally, to avoid naively resampling but still guarantee good generalization from a small sample, we interact with the sample through a mechanism which we call a guess-and-check statistical query (similar in spirit to mechanisms proposed in [HR10, BH15, GRU12]).”
The geometry of differential privacy: the sparse and approximate cases (2012, methodology): “We prove its approximation guarantee relative to the hereditary discrepancy lower bound of [44], using tools from convex geometry.”
Fingerprinting codes and the price of approximate differential privacy (2013, methodology): “ogjXj˝jQjpoly(jXj). In this regime the best-known sample complexity will be achieved by the nal expression, corresponding to the private multiplicative weights algorithm [HR10] using the analysis of [GRU12]. In light of Lemma2.6, it is without loss of generality that we have stated these upper bound”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, background): “Other mechanisms for preserving differential privacy include the Exponential Mechanism of McSherry and Talwar [25], [5]; the recent Multiplicative Weights mechanism of Hardt and Rothblum [19] and its various extensions [17], [14], [15]; the Median Mechanism [28] and a boosting mechanism of Dwork et ”
Understanding the Sparse Vector Technique for Differential Privacy (2016, methodology): “3 is taken from [15], which in turn was abstracted from the algorithms used in [11, 12].”
Private Multiplicative Weights Beyond Linear Queries (2014, methodology): “Fortunately, for many interesting types of queries, there are remarkable differentially private algorithms [5, 12, 15, 26, 19, 17, 18] that are capable of giving accurate answers to exponentially many different queries—far greater than what can be achieved using straightforward composition.”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, methodology): “Their work was improved on in several important aspects [23, 27, 44, 35, 32, 34].”
Optimal private halfspace counting via discrepancy (2012, methodology): “Much subsequent work has focused on answering m arbitrary queries eﬃciently with squared error linear in n and polylogarithmic in m [16, 28, 20, 21, 19].”
Differentially Private Data Publishing and Analysis: A Survey (2017, unknown): “[18] presented a general iteration framework, termed iterative database construct (IDC), which implements other release mechanisms by using the framework.”
A Program Logic for Union Bounds (2016, unknown): “We will verify the Online Multiplicative Weights (OMW) algorithm ﬁrst proposed by Hardt and Rothblum [21] and later reﬁned by Gupta et al. [20].”
An Improved Private Mechanism for Small Databases (2015, background): “ted private mechanisms can achieve error not much larger than O( √ n). For instance, there exist (ε,δ)-diﬀerentially private mechanisms for linear queries that acheive average error O( √ nlog1/4 |U|) [GRU12]. There are sets of counting queries for which this bound is tight up to factors polylogarith”
Answering n{2+o(1)} counting queries with differential privacy is hard (2012, background): “that answers Ω̃(n(2)) queries and there exist interactive sanitizers that can answer nearly 2 queries in time poly(2, n) per query interactively [17, 14, 12].”