Using Convex Relaxations for Efficiently and Privately Releasing Marginals
Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar · 2014
Differential privacy is a definition giving a strong privacy guarantee even in the presence of auxiliary information. In this work we pursue the application of geometric techniques for achieving differential privacy, a highly promising line of work initiated by Hardt and Talwar [26], focusing on the problem of marginal release. Here, a database is a collection of the data of n individuals, each characterized by d binary attributes. A k-way marginal query is specified by a subset S of k attributes, together with a |S|-dimensional binary vector β specifying their values. The true answer to this query is a count of the number of people in the database whose attribute vector restricted to S agrees with β.