social networks). Consequently, a large body of practical and theoretical work has been dedicated to understand which learning tasks can be performed by DP learning algorithms. The simplest and most extensively studied model of learning is the private PAC model [@Valiant84; @KasiviswanathanLNRS11], which captures binary classification tasks under differential privacy. A partial list of works on this topic includes [@KasiviswanathanLNRS11; @BeimelBKN14; @BunNSV15; @FeldmanX15; @BeimelNS16; @BunDRS18; @Beimel19Pure; @AlonLMM19; @kaplan2019privately].

In this manuscript we make progress towards characterizing what tasks are DP PAC-learnable by demonstrating a qualitative equivalence with online-learnable tasks.

#### Online Learning.

Online learning is a well-studied branch of machine learning which addresses algorithms making real-time predictions on sequentially arriving data. Such tasks arise in contexts including recommendation systems and advertisement placement. The literature on this subject is vast and includes several books, e.g. [@cesabianchi06prediction; @Shalev-Shwartz12book; @Hazan16oco].

[*Online Prediction*]{}, or [*Prediction with Expert Advice*]{} is a basic setting within online learning. Let $\mathcal{H} = \{h:X\to \{\pm1\} \}$ be a class of predictors (also called experts) over a domain $X$. Consider an algorithm which observes examples $(x_1,y_1)\ldots (x_T,y_T)\in X\times\{\pm 1\}$ in a sequential manner. More specifically, in each time step $t$, the algorithm first observes the instance $x_t$, then predicts a 