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 -