Private PAC learning implies finite Littlestone dimension

DOI10.1145/3313276.3316312zbMath1434.68149arXiv1806.00949OpenAlexW2963384289MaRDI QIDQ5212825

Noga Alon, Shay Moran, Roi Livni, Maryanthe Malliaris

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1806.00949

zbMATH Keywords

PAC learningdifferential privacyLittlestone dimension

Mathematics Subject Classification ID

Computational learning theory (68Q32) Privacy of data (68P27)

Related Items

Unnamed Item, Unnamed Item, Differentially Private Learning of Geometric Concepts, Differential privacy in constant function market makers, On differential privacy and adaptive data analysis with bounded space, Learning privately with labeled and unlabeled examples