Private PAC learning implies finite Littlestone dimension

Alon, Noga; Livni, Roi; Malliaris, Maryanthe; Moran, Shay

计算机科学 > 机器学习

arXiv:1806.00949v3 (cs)

[提交于 2018年6月4日 (v1) ，最后修订 2019年3月8日 (此版本， v3)]

标题：私有PAC学习意味着有限的Littlestone维数

标题： Private PAC learning implies finite Littlestone dimension

Authors:Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran

摘要：我们证明了对于具有Littlestone维数~$d$的类$H$，每个近似差分私有学习算法（可能不正确）都需要$\Omega\bigl(\log^*(d)\bigr)$个样本。作为推论，阈值类在$\mathbb{N}$上不能以私有方式学习；这解决了[Bun等，2015，Feldman和Xiao，2015]提出的一个开放问题。我们留下一个开放问题，即每个具有有限Littlestone维数的类是否可以通过一个近似差分私有算法进行学习。

摘要： We show that every approximately differentially private learning algorithm (possibly improper) for a class $H$ with Littlestone dimension~$d$ requires $\Omega\bigl(\log^*(d)\bigr)$ examples. As a corollary it follows that the class of thresholds over $\mathbb{N}$ can not be learned in a private manner; this resolves open question due to [Bun et al., 2015, Feldman and Xiao, 2015]. We leave as an open question whether every class with a finite Littlestone dimension can be learned by an approximately differentially private algorithm.

评论：	STOC最终版
主题：	机器学习 (cs.LG) ; 人工智能 (cs.AI); 密码学与安全 (cs.CR); 逻辑 (math.LO); 机器学习 (stat.ML)
引用方式：	arXiv:1806.00949 [cs.LG]
	(或者 arXiv:1806.00949v3 [cs.LG] 对于此版本)
	https://doi.org/10.48550/arXiv.1806.00949

提交历史

来自： Shay Moran [查看电子邮件]
[v1] 星期一， 2018 年 6 月 4 日 04:35:29 UTC (532 KB)
[v2] 星期三， 2019 年 2 月 13 日 04:53:31 UTC (532 KB)
[v3] 星期五， 2019 年 3 月 8 日 16:12:06 UTC (532 KB)

计算机科学 > 机器学习

标题：私有PAC学习意味着有限的Littlestone维数

标题： Private PAC learning implies finite Littlestone dimension

提交历史

获取论文：

参考文献与引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

计算机科学 > 机器学习

标题： 私有PAC学习意味着有限的Littlestone维数 显示英文标题

标题： Private PAC learning implies finite Littlestone dimension

提交历史

获取论文：

参考文献与引用

BibTeX 格式的引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

标题：私有PAC学习意味着有限的Littlestone维数