@article{695e15b4855e434c869e1c414b68639f,
title = "Private and Online Learnability Are Equivalent",
abstract = "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.",
keywords = "Differential privacy, Littlestone dimension, PAC learning, online learning",
author = "Noga Alon and Mark Bun and Roi Livni and Maryanthe Malliaris and Shay Moran",
note = "Funding Information: N. Alon was supported in part by NSF grant DMS-1855464 and BSF grant 2018267. M. Bun was partially supported by NSF grant CCF-1947889 and CAREER award CNS-2046425. R. Livni was supported by ISF grant 2188/20 and a grant from Tel Aviv University Center for AI and Data Science (TAD) in collaboration with Google, as part of the initiative of AI and DS for social good. M. Malliaris was partially supported by NSF CAREER award 1553653 and a Minerva Research Foundation membership at IAS. S. Moran was supported i part by ISF grant 1225/20, BSF grant 2018385, and the Azrieli Foundation. Publisher Copyright: {\textcopyright} 2022 Association for Computing Machinery.",
year = "2022",
month = aug,
day = "16",
doi = "10.1145/3526074",
language = "English (US)",
volume = "69",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery (ACM)",
number = "4",
}