Private and Online Learnability Are Equivalent

Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, Shay Moran

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Article number28
JournalJournal of the ACM
Volume69
Issue number4
DOIs
StatePublished - Aug 16 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Differential privacy
  • Littlestone dimension
  • online learning
  • PAC learning

Cite this