Do You Pay for Privacy in Online Learning?

Let $\mathcal H$ be a hypothesis class on an instance space $\mathcal X$. For a horizon $T$, let $S_T=((x_1,h^*(x_1)),\ldots,(x_T,h^*(x_T)))$ be any realizable sequence with $h^*\in\mathcal H$. An online algorithm is $(\epsilon,\delta)$-differentially private if, for any two length-$T$ sequences differing in one entry and every measurable transcript event $E$,

$$\Pr(A(S_T)\in E)\leq e^\epsilon\Pr(A(S'_T)\in E)+\delta.$$

Determine whether online learnability and privately online learnability coincide. Equivalently, resolve one of the following alternatives.

Problem 1.

Exhibit an online-learnable class $\mathcal H$ for which every $(\epsilon,\delta)$-private online algorithm must make infinitely many mistakes in the regime of sufficiently small $\epsilon$, thereby separating private from non-private online learnability.

Problem 2.

Prove that for every online-learnable $\mathcal H$ there is a positive decreasing function $\gamma\colon\mathbb R_+\to\mathbb R_+$ such that, for all horizons $T$ and privacy levels $\gamma(T)\leq\epsilon\leq\sqrt T$, an $(\epsilon,\delta)$-private online algorithm makes finitely many mistakes on every realizable length-$T$ sequence. Characterize the achievable function $\gamma$.