a globally-stable algorithm, and (ii) we then show how to generically obtain a differentially-private learner from any globally-stable learner.

Step 1: Finite Littlestone Dimension $\implies$ Globally-Stable Learning
------------------------------------------------------------------------

Let ${\mathcal{H}}$ be a concept class with Littlestone dimension $d$. Our goal is to design a globally-stable learning algorithm for ${\mathcal{H}}$ with stability parameter $\eta = \exp(-d)$ and sample complexity $n=\exp(d)$. We will sketch here a weaker variant of our construction which uses the same ideas but is simpler to describe.

The property of ${\mathcal{H}}$ that we will use is that it can be online learned in the realizable setting with at most $d$ mistakes (see Section \[sec:online\] for a brief overview of this setting). Let ${\mathcal{D}}$ denote a realizable distribution with respect to which we wish to learn in a globally-stable manner. That is, ${\mathcal{D}}$ is a distribution over examples $(x,c(x))$ where $c\in{\mathcal{H}}$ is an unknown target concept. Let $\mathcal{A}$ be a learning algorithm that makes at most $d$ mistakes while learning an unknown concept from ${\mathcal{H}}$ in the online model. Consider applying $\mathcal{A}$ on a sequence $S=((x_1,c(x_1))\ldots (x_n,c(x_n)))\sim{\mathcal{D}}^n$, and denote by $M$ the random variable counting the number of mistakes $\mathcal{A}$ makes in this process. The mistake-bound guarantee on ${\mathcal{A}}$ 