Theory Seminar, November 29th, 2:00pm
Warren Weaver Hall, Room 417

The Geometry of Differential Privacy: The Approximate and Sparse Cases
Aleksandr Nikolov, Rutgers University

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 the focus of a long line of work. For a given set of d linear queries over a database x drawn from a universe of size N, we seek to find the differentially private mechanism that has the minimum mean squared error. For pure differential privacy, Hardt and Talwar, and Bhaskara et al. give an O(\log^2 d) efficient approximation to the optimal mechanism. Our first contribution is to give an O(\log^2 d) approximation guarantee for the case of approximate (epsilon,delta)-differential privacy. Our mechanism is simple, efficient and adds carefully chosen correlated Gaussian noise to the answers. We prove its approximation guarantee relative to the hereditary discrepancy lower bound of Muthukrishnan and Nikolov, using tools from assymptotic convex geometry. We next consider this question in the case when the number of queries d exceeds the number of individuals n in the database. The lower bounds used in the previous approximation algorithm no longer apply, and in fact better mechanisms are known in this setting. Our second main contribution is to give an (epsilon,delta)-differentially private mechanism that, for a given query set A and an upper bound n on the size of the database, has mean squared error within polylog(d,N) of the optimal for A and n. This approximation is achieved by coupling the Gaussian noise addition approach with linear regression over a high-dimensional polytope. Our algorithm is the first efficient approximation to the optimal mechanism when database size is bounded. The connection between hereditary discrepancy and the privacy mechanism enables us to derive the first polylogarithmic approximation to the hereditary discrepancy of a matrix A. Joint work with Kunal Talwar and Li Zhang.