论文标题
关于二进制分类以外的在线学习和私人学习之间的等效性
On the Equivalence between Online and Private Learnability beyond Binary Classification
论文作者
论文摘要
Alon等。 [2019]和Bun等。 [2020]最近表明，在线学习性和私人PAC可学习性在二进制分类中相当。我们研究这种对等是否扩展到多类分类和回归。首先，我们表明私人学习性意味着在两种情况下的在线学习性。我们的扩展涉及研究littlestone尺寸的新型变体，该变体取决于公差参数以及对二进制分类超出阈值函数的概念的适当概括。其次，我们表明，尽管在线学习性继续暗示多级分类中的私人学习性，但当前的证明技术在回归环境中遇到了重大障碍。尽管回归的等效性仍然开放，但我们为在线学习类提供了非平凡的足够条件，也可以私下学习。
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.
