  The problem of learning threshold functions is a fundamental one in machine
learning. Classical learning theory implies sample complexity of $O(\xi^{-1}
\log(1/\beta))$ (for generalization error $\xi$ with confidence $1-\beta$). The
private version of the problem, however, is more challenging and in particular,
the sample complexity must depend on the size $|X|$ of the domain. Progress on
quantifying this dependence, via lower and upper bounds, was made in a line of
works over the past decade. In this paper, we finally close the gap for
approximate-DP and provide a nearly tight upper bound of $\tilde{O}(\log^*
|X|)$, which matches a lower bound by Alon et al (that applies even with
improper learning) and improves over a prior upper bound of $\tilde{O}((\log^*
|X|)^{1.5})$ by Kaplan et al. We also provide matching upper and lower bounds
of $\tilde{\Theta}(2^{\log^*|X|})$ for the additive error of private
quasi-concave optimization (a related and more general problem). Our
improvement is achieved via the novel Reorder-Slice-Compute paradigm for
private data analysis which we believe will have further applications.
