The Geometry of Differential Privacy: The Small Database and Approximate Cases

By Aleksandar Nikolov, Kunal Talwar, Li Zhang. 2016

32 citations recorded by the source corpus.

In this work, 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 a focus of a long line of work. For a given set of $d$ linear queries $A$ over a database $x \in \mathbb{R}^N$, we seek to find the differentially private mechanism that has the minimum mean squared error relative to the true answer $Ax$. For pure differential privacy, Hart and Talwar and Bhaskara et al. give an $O(\log^2 d)$ approximation to the optimal mechanism. Our first contribution is to give an $O(\log^2 d)$ approximation guarantee for the case of $(\varepsilon,\delta)$-approximate differential privacy. Our mechanism adds carefully chosen correlated Gaussian noise to the answers and runs in time polynomial in $d$ and $N$. The mechanism is based on a recursive construction of a “small” enclosing ellipsoid of the sensitivity polytope $AB_1^N$, where $B_1^N$ denotes the $N$-dimensional $\ell_1$ b...

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

Citations in the corpus

The structure of optimal private tests for simple hypotheses (2018, background): “There are also several rich lines of work attempting to give tight instance-specific characterizations of the sample complexities of various differentially private computations, most notably linear query release [11, 43, 48, 57, 58] and PAC and agnostic learning [10, 39, 46].”
The Complexity of Differential Privacy (2017, methodology): “Remarkably, Nikolov, Talwar, and Zhang [85] showed that this bound is nearly tight:”