An Improved Private Mechanism for Small Databases

By Aleksandar Nikolov. 2015

12 citations recorded by the source corpus.

We study the problem of answering a workload of linear queries \(\mathcal {Q}\), on a database of size at most \(n = o(|\mathcal {Q}|)\) drawn from a universe \(\mathcal {U}\) under the constraint of (approximate) differential privacy. Nikolov, Talwar, and Zhang [NTZ13] proposed an efficient mechanism that, for any given \(\mathcal {Q}\) and \(n\), answers the queries with average error that is at most a factor polynomial in \(\log |\mathcal {Q}|\) and \(\log |\mathcal {U}|\) worse than the best possible. Here we improve on this guarantee and give a mechanism whose competitiveness ratio is at most polynomial in \(\log n\) and \(\log |\mathcal {U}|\), and has no dependence on \(|\mathcal {Q}|\). Our mechanism is based on the projection mechanism of [NTZ13], but in place of an ad-hoc noise distribution, we use a distribution which is in a sense optimal for the projection mechanism, and analyze it using convex duality and the restricted invertibility principle.

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].”
Lower Bounds for Differential Privacy from Gaussian Width (2016, methodology): “This result was subsequently improved by Nikolov [15], who showed that the log m factors can be replaced by log n .”
The power of factorization mechanisms in local and central differential privacy (2019, background): “In the central model, there has been dramatic progress on this question [HT10, BDKT12, NTZ16, Nik15, BBNS19], giving approximate characterizations for every workload of linear queries.”