Journal
JOURNAL OF THE ACM
Volume 69, Issue 4, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3526074
Keywords
Differential privacy; PAC learning; online learning; Littlestone dimension
Categories
Funding
- 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
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
