TY - GEN
T1 - Faster private release of marginals on small databases
AU - Chandrasekaran, Karthekeyan
AU - Thaler, Justin
AU - Ullman, Jonathan
AU - Wan, Andrew
PY - 2014
Y1 - 2014
N2 - We study the problem of answering k-way marginal queries on a database D ∈ ({0,1}d)n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of the database's records x ∈ {0,1}d with a given value in each of a given set of up to k columns. Marginal queries enable a rich class of statistical analyses on a dataset, and designing efficient algorithms for privately answering marginal queries has been identified as an important open problem in private data analysis. For any k, we give a differentially private online algorithm that runs in time poly (n, 2°(d)) per query and answers any sequence of poly (n) many k-way marginal queries with error at most ±0.01 on every query, provided n ≳ d0.51. To the best of our knowledge, this is the first algorithm capable of privately answering marginal queries with a non-trivial worst-case accuracy guarantee for databases containing poly(d, k) records in time exp(o(d)). Our algorithm runs the private multiplicative weights algorithm (Hardt and Rothblum, FOCS '10) on a new approximate polynomial representation of the database. We derive our representation for the database by approximating the OR function restricted to low Hamming weight inputs using low-degree polynomials with coefficients of bounded L1-norm. In doing so, we show new upper and lower bounds on the degree of such polynomials, which may be of independent approximation-theoretic interest.
AB - We study the problem of answering k-way marginal queries on a database D ∈ ({0,1}d)n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of the database's records x ∈ {0,1}d with a given value in each of a given set of up to k columns. Marginal queries enable a rich class of statistical analyses on a dataset, and designing efficient algorithms for privately answering marginal queries has been identified as an important open problem in private data analysis. For any k, we give a differentially private online algorithm that runs in time poly (n, 2°(d)) per query and answers any sequence of poly (n) many k-way marginal queries with error at most ±0.01 on every query, provided n ≳ d0.51. To the best of our knowledge, this is the first algorithm capable of privately answering marginal queries with a non-trivial worst-case accuracy guarantee for databases containing poly(d, k) records in time exp(o(d)). Our algorithm runs the private multiplicative weights algorithm (Hardt and Rothblum, FOCS '10) on a new approximate polynomial representation of the database. We derive our representation for the database by approximating the OR function restricted to low Hamming weight inputs using low-degree polynomials with coefficients of bounded L1-norm. In doing so, we show new upper and lower bounds on the degree of such polynomials, which may be of independent approximation-theoretic interest.
UR - http://www.scopus.com/inward/record.url?scp=84893223230&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893223230&partnerID=8YFLogxK
U2 - 10.1145/2554797.2554833
DO - 10.1145/2554797.2554833
M3 - Conference contribution
AN - SCOPUS:84893223230
SN - 9781450322430
T3 - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
SP - 387
EP - 401
BT - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PB - Association for Computing Machinery
T2 - 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
Y2 - 12 January 2014 through 14 January 2014
ER -