  We revisit the problem of differentially private release of classification
queries. In this problem, the goal is to design an algorithm that can
accurately answer a sequence of classification queries based on a private
training set while ensuring differential privacy. We formally study this
problem in the agnostic PAC model and derive a new upper bound on the private
sample complexity. Our results improve over those obtained in a recent work
[BTT18] for the agnostic PAC setting. In particular, we give an improved
construction that yields a tighter upper bound on the sample complexity.
Moreover, unlike [BTT18], our accuracy guarantee does not involve any blow-up
in the approximation error associated with the given hypothesis class.
  Given any hypothesis class with VC-dimension $d$, we show that our
construction can privately answer up to $m$ classification queries with average
excess error $\alpha$ using a private sample of size $\approx
\frac{d}{\alpha^2}\,\max\left(1, \sqrt{m}\,\alpha^{3/2}\right)$. Using recent
results on private learning with auxiliary public data, we extend our
construction to show that one can privately answer any number of classification
queries with average excess error $\alpha$ using a private sample of size
$\approx \frac{d}{\alpha^2}\,\max\left(1, \sqrt{d}\,\alpha\right)$. When
$\alpha=O\left(\frac{1}{\sqrt{d}}\right)$, our private sample complexity bound
is essentially optimal.
