  We study binary classification algorithms for which the prediction on any
point is not too sensitive to individual examples in the dataset. Specifically,
we consider the notions of uniform stability (Bousquet and Elisseeff, 2001) and
prediction privacy (Dwork and Feldman, 2018). Previous work on these notions
shows how they can be achieved in the standard PAC model via simple aggregation
of models trained on disjoint subsets of data. Unfortunately, this approach
leads to a significant overhead in terms of sample complexity. Here we
demonstrate several general approaches to stable and private prediction that
either eliminate or significantly reduce the overhead. Specifically, we
demonstrate that for any class $C$ of VC dimension $d$ there exists a
$\gamma$-uniformly stable algorithm for learning $C$ with excess error $\alpha$
using $\tilde O(d/(\alpha\gamma) + d/\alpha^2)$ samples. We also show that this
bound is nearly tight. For $\epsilon$-differentially private prediction we give
two new algorithms: one using $\tilde O(d/(\alpha^2\epsilon))$ samples and
another one using $\tilde O(d^2/(\alpha\epsilon) + d/\alpha^2)$ samples. The
best previously known bounds for these problems are $O(d/(\alpha^2\gamma))$ and
$O(d/(\alpha^3\epsilon))$, respectively.
