label $\hat{y}_t\in\{\pm 1\}$, and finally learns whether its prediction was correct. The goal is to minimize the [*regret*]{}, namely the number of mistakes compared to the best expert in $\mathcal{H}$: $$\sum_{t=1}^T 1[y_t\neq \hat{y}_t] - \min_{h^*\in\mathcal{H}} \sum_{t=1}^T 1[y_t\neq h^*(x_t)].$$ In this context, a class $\mathcal H$ is said to be online learnable if for every $T$, there is an algorithm that achieves sublinear regret $o(T)$ against any sequence of $T$ examples. The [*Littlestone dimension*]{} is a combinatorial parameter associated to the class ${\mathcal{H}}$ which characterizes its online learnability [@Littlestone87online; @Bendavid09agnostic]: $\mathcal H$ is online learnable if and only if it has a finite Littlestone dimension $d<\infty$. Moreover, the best possible regret $R(T)$ for online learning of ${\mathcal{H}}$ satisfies $$\Omega (\sqrt{dT}) \leq R(T) \leq O(\sqrt{dT\log T}).$$ Furthermore, if it is known that if one of the experts never errs (i.e. in the realizable mistake-bound model), then the optimal regret is exactly $d$.

#### Stability.

While at a first glance it may seem that online learning and differentially-private learning have little to do with one another, a line of recent works has revealed a tight connection between the two [@Agarwal17dponline; @Abernathy17onlilnedp; @AlonLMM19; @bousquet2019passing; @NeelRW19; @Joseph2019TheRO; @Gonen19privateonline].

At a high-level, this connection appears to 