An Improved Private Mechanism for Small Databases
This work provides an incremental improvement in differential privacy mechanisms for small databases, benefiting researchers and practitioners in data privacy.
The paper tackles the problem of answering linear queries on small databases under differential privacy constraints, improving the competitiveness ratio to be polynomial in log n and log |U| without dependence on |Q|, building on prior work by Nikolov, Talwar, and Zhang.
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~\cite{NTZ} 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 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.