Faster private release of marginals on small databases
|Speaker:||Professor Karthekeyan Chandraskearan|
|Room:||Mathematics and Computer Building (MC) 5158|
The goal of privacy-preserving data analysis is to enable rich statistical analyses on the database while protecting the privacy of the individual records. One of the most important classes of statistics on a dataset is its marginals. The answer to a k-way marginal query is the fraction of database's records with a given value in each of a given set of up to k attributes. In this work, we focus on the notion of differential privacy to answer marginal queries. Early work in differential privacy gave algorithms that are private provided the number of records in the database is comparable to (or larger than) the number of queries. Although a remarkable line of work improved this requirement to achieve privacy on small databases, this was at the expense of an exponential blow up in the run time.
In this work, we give an algorithm with improved run time (sub-exponential) for privately answering marginal queries on small databases. Our algorithm uses a new approximate representation of the database that is inspired by tools from learning theory. This representation is derived by approximating the disjunction on low Hamming weight inputs using low-degree polynomials with coefficients of bounded L1-norm. We show new upper and lower bounds for such polynomials. Our lower bound matches our upper bound and thus, exhibits the tightness of our approach when polynomials are used to derive the approximate representation of the database.
Joint work with J. Thaler, J. Ullman, and A. Wan.
200 University Avenue West
Waterloo, ON N2L 3G1