On the Equivalence between Online and Private Learnability beyond Binary
  Classification
  Alon et al. [2019] and Bun et al. [2020] recently showed that online
learnability and private PAC learnability are equivalent in binary
classification. We investigate whether this equivalence extends to multi-class
classification and regression. First, we show that private learnability implies
online learnability in both settings. Our extension involves studying a novel
variant of the Littlestone dimension that depends on a tolerance parameter and
on an appropriate generalization of the concept of threshold functions beyond
binary classification. Second, we show that while online learnability continues
to imply private learnability in multi-class classification, current proof
techniques encounter significant hurdles in the regression setting. While the
equivalence for regression remains open, we provide non-trivial sufficient
conditions for an online learnable class to also be privately learnable.
