The geometry of differential privacy: the sparse and approximate cases

By Aleksandar Nikolov, Kunal Talwar, Li Zhang. 2012

233 citations recorded by the source corpus.

We study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries and has been the focus of a long line of work. For a given set of d linear queries over a database x ∈ RN, we seek to find the differentially private mechanism that has the minimum mean squared error. For pure differential privacy, [5, 32] give an O(log2 d) approximation to the optimal mechanism. Our first contribution is to give an efficient O(log2 d) approximation guarantee for the case of (ε,δ)-differential privacy. Our mechanism adds carefully chosen correlated Gaussian noise to the answers. We prove its approximation guarantee relative to the hereditary discrepancy lower bound of [44], using tools from convex geometry. We next consider the sparse case when the number of queries exceeds the number of individuals in the database, i.e. when d > n Δ |x|1. The lower bounds used in the previous approximation algorithm no longer apply --- in fact better mechanisms are known in this setting [7, 27, 28, 31, 49]. Our second main contribution is to give an efficient (ε,δ)-differentially private mechanism that, for any given query set A and an upper bound n on |x|1, has mean squared error within polylog(d,N) of the optimal for A and n. This approximation is achieved by coupling the Gaussian noise addition approach with linear regression over the l1 ball. Additionally, we show a similar polylogarithmic approximation guarantee for the optimal ε-differentially private mechanism in this sparse setting. Our work also shows that for arbitrary counting queries, i.e. A with entries in {0,1}, there is an ε-differentially private mechanism with expected error ~O(√n) per query, improving on the ~O(n2/3) bound of [7] and matching the lower bound implied by [15] up to logarithmic factors. The connection between the hereditary discrepancy and the privacy mechanism enables us to derive the first polylogarithmic approximation to the hereditary discrepancy of a matrix A.

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

Tight Lower Bounds for Differentially Private Selection (2017, background): “Another line of work proves lower bounds in differential privacy via reconstruction attacks [13], [32], [33], [34], [35], [36], [37].”
To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout (2015, methodology): “Using the proof technique of Nikolov et al. [2013, Lemma 4] one can easily show that the theorem also holds for ( (cid:15), δ ) -local differential privacy at any given data set D ∈ D n , with η = max”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “Standard differential privacy arguments for Gaussian noise addition (see [34, 40]) will ensure that with probability 1− δ 2 (over the randomness of the random variables bt’s and conditioned on the randomness due to sampling),Wt ≤ 2 √ log(1/δ) for all t ∈ [n2].”
Robust Traceability from Trace Amounts (2015, background): “These attacks, which immediately give lower bounds on noise needed to avoid blatant non-privacy, have been extended in numerous works [4]–[11].”
Towards Practical Differentially Private Convex Optimization (2019, background): “3 for 3 < 1, we get the statement of the lemma from the guarantees of the Gaussian mechanism [38].”
Fingerprinting codes and the price of approximate differential privacy (2013, background): “Specifically, [28] give an (ε, δ)-differentially private algorithm that answers any family of queries Q on {0, 1}d with error α using a number of samples that is optimal up to a factor of poly(d, log |Q|) that is independent of α.”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, methodology): “In the most commonly used mechanisms [25, 56], this tradeo is explicit since noise is deliberately added to the output of a functionality before releasing it, so as to ensure privacy.”
The Optimal Noise-Adding Mechanism in Differential Privacy (2012, background): “[4] extend the result on the tradeoff between privacy and error to the case of ( , δ)-differential privacy.”
The Complexity of Differential Privacy (2017, methodology): “10 (hereditary discrepancy upper bound [84]).”
The matrix mechanism: optimizing linear counting queries under differential privacy (2015, background): “[24] show that the minimum error of the matrix mechanism is within a factor of O(log2 n) to the minimum noise of any data-independent algorithm under ( , δ)-differential privacy.”