期刊
JOURNAL OF THE ACM
卷 69, 期 4, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3526074
关键词
Differential privacy; PAC learning; online learning; Littlestone dimension
类别
资金
- NSF [DMS-1855464, CCF-1947889]
- BSF [2018267, 2018385]
- CAREER award [CNS-2046425]
- ISF [2188/20, 1225/20]
- Tel Aviv University Center for AI and Data Science (TAD)
- NSF CAREER award [1553653]
- Minerva Research Foundation membership at IAS
- Azrieli Foundation
- initiative of AI and DS for social good
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [1553653] Funding Source: National Science Foundation
H, a binary-labeled concept class, can be PAC learned by an (approximate) differentially private algorithm if and only if it has a finite Littlestone dimension, showing a qualitative equivalence between online learnability and private PAC learnability.
Let H be a binary-labeled concept class. We prove that H can be PAC learned by an (approximate) differentially private algorithm if and only if it has a finite Littlestone dimension. This implies a qualitative equivalence between online learnability and private PAC learnability.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据
分享论文
