On the Equivalence between Online and Private Learnability beyond Binary Classification
This work addresses a foundational problem in machine learning theory, extending theoretical understanding of learnability connections beyond binary classification, though it is incremental in building on prior results.
The paper investigates whether the equivalence between online learnability and private PAC learnability, known for binary classification, extends to multi-class classification and regression. It shows that private learnability implies online learnability in both settings, and while online learnability implies private learnability in multi-class classification, the equivalence for regression remains open with non-trivial sufficient conditions provided.
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.