Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations

Consider a database of n people, each represented by a bit-string of length d corresponding to the setting of d binary attributes. A k-way marginal query is specified by a subset S of k attributes, and a |S|-dimensional binary vector β specifying their values. The result for this query is a count of the number of people in the database whose attribute vector restricted to S agrees with β. Privately releasing approximate answers to a set of k-way marginal queries is one of the most important and well-motivated problems in differential privacy. Information theoretically, the error complexity of marginal queries is well-understood: the per-query additive error is known to be at least Omega(min√n,d^frack2) and at most tildeO(min√n d1/4,d^frack2). However, no polynomial time algorithm with error complexity as low as the information theoretic upper bound is known for small n. In this work we present a polynomial time algorithm that, for any distribution on marginal queries, achieves average error at most tildeO(√n d^fraclceil k/2 rceil4). This error bound is as good as the best known information theoretic upper bounds for k=2. This bound is an improvement over previous work on efficiently releasing marginals when k is small and when error o(n) is desirable. Using private boosting we are also able to give nearly matching worst-case error bounds. Our algorithms are based on the geometric techniques of Nikolov, Talwar, and Zhang. The main new ingredients are convex relaxations and careful use of the Frank-Wolfe algorithm for constrained convex minimization. To design our relaxations, we rely on the Grothendieck inequality from functional analysis.