Abstract
We propose a private query release mechanism, related to private boosting, that solves the "dual" of the query release linear program. It is known that no private query release algorithm capable of accurately answering large numbers of general queries can run in polynomial time in the worst case, and our algorithm is no exception. The difference in our approach compared to private multiplicative weights is that the computational difficulty does not stem from needing to represent a large state, but instead the need to solve an NP-hard problem. Importantly, the hard problem that needs to be solved to run our algorithm does not need to be solved privately. As a result, we can attempt to solve it using existing optimization algorithms: we express it as an integer program, and solve it using CPLEX. We find that in practice, this hard problem is not to hard, and that our approach scales to high dimensional data on real datasets. We report the results of recent experiments we have run to privately compute marginal queries on real data sets.