# An Improved Private Mechanism for Small Databases

arXiv: https://arxiv.org/abs/1505.00244 · HTML: https://mlsanity.com/paper/1505.00244/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2015.

## Built on by (most cited first, 1 of 1)

- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)

## Abstract (arXiv)

We study the problem of answering a workload of linear queries Q, on a database of size at most n = o(|Q|) drawn from a universe U under the constraint of (approximate) differential privacy. Nikolov, Talwar, and Zhang~citeNTZ proposed an efficient mechanism that, for any given Q and n, answers the queries with average error that is at most a factor polynomial in log |Q| and log |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 |U|, and has no dependence on |Q|. Our mechanism is based on the projection mechanism of Nikolov, Talwar, and Zhang, 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.