Timezone: »

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

Mon Dec 07 09:00 PM -- 11:00 PM (PST) @ Poster Session 0 #81
in Poster Session 1 »

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