Timezone: »

 
Spotlight
On the Equivalence between Online and Private Learnability beyond Binary Classification
Young H Jung · Baekjin Kim · Ambuj Tewari

Mon Dec 07 07:00 PM -- 07:10 PM (PST) @ Orals & Spotlights: Representation/Relational
in Orals & Spotlights Track 01: Representation/Relational »

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.

Author Information

Young H Jung (Microsoft)
Baekjin Kim (University of Michigan)
Ambuj Tewari (University of Michigan)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors