  We study the problem of answering a workload of linear queries $\mathcal{Q}$,
on a database of size at most $n = o(|\mathcal{Q}|)$ drawn from a universe
$\mathcal{U}$ under the constraint of (approximate) differential privacy.
Nikolov, Talwar, and Zhang~\cite{NTZ} proposed an efficient mechanism that, for
any given $\mathcal{Q}$ and $n$, answers the queries with average error that is
at most a factor polynomial in $\log |\mathcal{Q}|$ and $\log |\mathcal{U}|$
worse than the best possible. Here we improve on this guarantee and give a
mechanism whose competitiveness ratio is at most polynomial in $\log n$ and
$\log |\mathcal{U}|$, and has no dependence on $|\mathcal{Q}|$. Our mechanism
is based on the projection mechanism of Nikolov, Talwar, and Zhang, but in
place of an ad-hoc noise distribution, we use a distribution which is in a
sense optimal for the projection mechanism, and analyze it using convex duality
and the restricted invertibility principle.
