rule of the ${\mathsf{SOA}}$ to obtain $h_{t+1}$.

-   Else, set $h_{t+1}$ as follows: $h_{t+1}(x_{t+1}) = y_{t+1}$, and $h_{t+1}(x)=h_t(x)$ for every $x\neq x_{t+1}$.

Thus, upon observing a non-realizable sequence, this update rule locally updates the maintained predictor $h_t$ to agree with the last example.

Differential Privacy
--------------------

We use standard definitions and notation from the differential privacy literature. For more background see, e.g., the surveys [@DworkR14; @Vadhan17]. For $a, b, {\varepsilon}, \delta \in [0, 1]$ let $a\approx_{{\varepsilon},\delta} b$ denote the statement $$a\leq e^{{\varepsilon}}b + \delta ~\text{  and  }~   b\leq e^{\varepsilon}a + \delta.$$ We say that two probability distributions $p,q$ are [*$({\varepsilon},\delta)$-indistinguishable*]{} if $p(E) \approx_{{\varepsilon},\delta} q(E)$ for every event $E$.

\[def:private\] A randomized algorithm $$A: (X\times \{\pm 1\})^m \to \{\pm 1\}^X$$ is $({\varepsilon},\delta)$-differentially-private if for every two samples $S,S'\in (X\times \{\pm 1\})^n$ that disagree on a single example, the output distributions $A(S)$ and $A(S')$ are $({\varepsilon},\delta)$-indistinguishable.

We emphasize that $({\varepsilon}, \delta)$-indistinguishability must hold for every such pair of samples, even if they are not generated according to a (realizable) distribution.

The parameters ${\varepsilon},\delta$ are usually treated as follows: ${\varepsilon}$ is a small constant (say $0.1$), and $\delta$ is negligible, $\delta = n^{-\omega(1)}$, where $n$ is the input sample size. The case of 