Faster Private Release of Marginals on Small Databases

We study the problem of answering k-way marginal queries on a database D ∈ (0,1d)n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of the database's records x ∈ 0,1d 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 minexp(d^1-Omega(1/√k)), exp(d / log.99 d) per query and answers any (possibly superpolynomially long and adaptively chosen) sequence of k-way marginal queries up to error at most ± .01 on every query, provided n gtrsim d.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 on a database of size poly(d, k) in time exp(o(d)). Our algorithms are a variant of the private multiplicative weights algorithm (Hardt and Rothblum, FOCS '10), but using a different low-weight representation of the database. We derive our low-weight representation using approximations to the OR function by low-degree polynomials with coefficients of bounded L1-norm. We also prove a strong limitation on our approach that is of independent approximation-theoretic interest. Specifically, we show that for any k = o(log d), any polynomial with coefficients of L1-norm poly(d) that pointwise approximates the d-variate OR function on all inputs of Hamming weight at most k must have degree d^1-O(1/√k).