  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 $\beta$ 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 $\beta$.
  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\{\sqrt{n},d^{\frac{k}{2}}\})$ and at most
$\tilde{O}(\min\{\sqrt{n} d^{1/4},d^{\frac{k}{2}}\})$. 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 $\tilde{O}(\sqrt{n} d^{\frac{\lceil k/2 \rceil}{4}})$. 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.
