Differentially Private Query Release Through Adaptive Projection
  We propose, implement, and evaluate a new algorithm for releasing answers to
very large numbers of statistical queries like $k$-way marginals, subject to
differential privacy. Our algorithm makes adaptive use of a continuous
relaxation of the Projection Mechanism, which answers queries on the private
dataset using simple perturbation, and then attempts to find the synthetic
dataset that most closely matches the noisy answers. We use a continuous
relaxation of the synthetic dataset domain which makes the projection loss
differentiable, and allows us to use efficient ML optimization techniques and
tooling. Rather than answering all queries up front, we make judicious use of
our privacy budget by iteratively and adaptively finding queries for which our
(relaxed) synthetic data has high error, and then repeating the projection. We
perform extensive experimental evaluations across a range of parameters and
datasets, and find that our method outperforms existing algorithms in many
cases, especially when the privacy budget is small or the query class is large.
