Differentially Private Release and Learning of Threshold Functions
  We prove new upper and lower bounds on the sample complexity of $(\epsilon,
\delta)$ differentially private algorithms for releasing approximate answers to
threshold functions. A threshold function $c_x$ over a totally ordered domain
$X$ evaluates to $c_x(y) = 1$ if $y \le x$, and evaluates to $0$ otherwise. We
give the first nontrivial lower bound for releasing thresholds with
$(\epsilon,\delta)$ differential privacy, showing that the task is impossible
over an infinite domain $X$, and moreover requires sample complexity $n \ge
\Omega(\log^*|X|)$, which grows with the size of the domain. Inspired by the
techniques used to prove this lower bound, we give an algorithm for releasing
thresholds with $n \le 2^{(1+ o(1))\log^*|X|}$ samples. This improves the
previous best upper bound of $8^{(1 + o(1))\log^*|X|}$ (Beimel et al., RANDOM
'13).
  Our sample complexity upper and lower bounds also apply to the tasks of
learning distributions with respect to Kolmogorov distance and of properly PAC
learning thresholds with differential privacy. The lower bound gives the first
separation between the sample complexity of properly learning a concept class
with $(\epsilon,\delta)$ differential privacy and learning without privacy. For
properly learning thresholds in $\ell$ dimensions, this lower bound extends to
$n \ge \Omega(\ell \cdot \log^*|X|)$.
  To obtain our results, we give reductions in both directions from releasing
and properly learning thresholds and the simpler interior point problem. Given
a database $D$ of elements from $X$, the interior point problem asks for an
element between the smallest and largest elements in $D$. We introduce new
recursive constructions for bounding the sample complexity of the interior
point problem, as well as further reductions and techniques for proving
impossibility results for other basic problems in differential privacy.
