  In this work we describe the High-Dimensional Matrix Mechanism (HDMM), a
differentially private algorithm for answering a workload of predicate counting
queries. HDMM represents query workloads using a compact implicit matrix
representation and exploits this representation to efficiently optimize over (a
subset of) the space of differentially private algorithms for one that is
unbiased and answers the input query workload with low expected error. HDMM can
be deployed for both $\epsilon$-differential privacy (with Laplace noise) and
$(\epsilon, \delta)$-differential privacy (with Gaussian noise), although the
core techniques are slightly different for each. We demonstrate empirically
that HDMM can efficiently answer queries with lower expected error than
state-of-the-art techniques, and in some cases, it nearly matches existing
lower bounds for the particular class of mechanisms we consider.
