boil down to the notion of stability, which plays a key role in both topics. On one hand, the definition of differential privacy is itself a form of stability; it requires robustness of the output distribution of an algorithm when its input undergoes small changes. On the other hand, stability also arises as a central motif in online learning paradigms such as [*Follow the Perturbed Leader*]{} [@Kalai02geometricalgorithms; @kalai05efficient] and [*Follow the Regularized Leader*]{} [@abernethy08competing; @Shalev07ftrl; @Hazan16oco].

In their monograph [@DworkR14], Dwork and Roth identified stability as a common factor of learning and differential privacy: [*“Differential privacy is enabled by stability and ensures stability… we observe a tantalizing moral equivalence between learnability, differential privacy, and stability.”*]{} This insight has found formal manifestations in several works. For example, Abernethy et al. used DP inspired stability methodology to derive a unified framework for proving state of the art bounds in online learning [@Abernathy17onlilnedp]. In the opposite direction, Agarwal and Singh showed that certain standard stabilization techniques in online learning imply differential privacy [@Agarwal17dponline].

Stability plays a key role in this work as well. Our main result, which shows that any class with a finite Littlestone dimension can be privately learned, hinges on the 