Treffer: Unconditional differentially private mechanisms for linear queries

We investigate the problem of designing differentially private mechanisms for a set of d linear queries over a database histogram represented as a vector, while adding as little error as possible. Hardt and Talwar [HT10] related this problem to geometric properties of a convex body defined by the set of queries and gave a O(log 3 d)-approximation to the minimum ℓ 2 2 error, assuming a conjecture from convex geometry called the Slicing or the Hyperplane conjecture. In this work we give a mechanism that works unconditionally, and also gives an improved O(log 2 d) approximation to the expected ℓ 2 2 error. We remove the dependence on the Slicing conjecture by using a result of Klartag [Kla06] that shows that any convex body is close to one for which the conjecture holds; we modify this result to make sure this body satisfies central symmetry, and make this result constructive by using recent techniques of Dadush, Peikert and Vempala [DPV10]. The improvement in approximation ratio relies on a stronger lower bound we derive on the optimum. This new lower bound goes beyond the packing argument that has traditionally been used in Differential Privacy and allows us to add the packing lower bounds obtained from orthogonal subspaces. We are able to achieve this via a symmetrization argument which argues that there always exists a near optimal differentially private mechanism which adds noise that is independent of the input database! We believe this result should be of independent interest, and also discuss some interesting consequences.