Private and Online Learnability Are Equivalent

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

doi:10.1145/3526074

Private and Online Learnability Are Equivalent

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

Mathematics

Research output: Contribution to journal › Article › peer-review

35 Scopus citations

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 language	English (US)
Article number	28
Journal	Journal of the ACM
Volume	69
Issue number	4
DOIs	https://doi.org/10.1145/3526074
State	Published - 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
PAC learning
online learning

Access to Document

10.1145/3526074

Cite this

@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 = "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",

}

TY - JOUR

T1 - Private and Online Learnability Are Equivalent

AU - Alon, Noga

AU - Bun, Mark

AU - Livni, Roi

AU - Malliaris, Maryanthe

AU - Moran, Shay

PY - 2022/8/16

Y1 - 2022/8/16

N2 - 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.

AB - 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.

KW - Differential privacy

KW - Littlestone dimension

KW - PAC learning

KW - online learning

UR - https://www.scopus.com/pages/publications/85139218816

UR - https://www.scopus.com/pages/publications/85139218816#tab=citedBy

U2 - 10.1145/3526074

DO - 10.1145/3526074

M3 - Article

AN - SCOPUS:85139218816

SN - 0004-5411

VL - 69

JO - Journal of the ACM

JF - Journal of the ACM

IS - 4

M1 - 28

ER -

Private and Online Learnability Are Equivalent

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this