We prove that every concept class with finite Littlestone dimension can be
learned by an (approximate) differentially-private algorithm. This answers an
open question of Alon et al. (STOC 2019) who proved the converse statement
(this question was also asked by Neel et al.~(FOCS 2019)). Together these two
results yield an equivalence between online learnability and private PAC
learnability.
We introduce a new notion of algorithmic stability called "global stability"
which is essential to our proof and may be of independent interest. We also
discuss an application of our results to boosting the privacy and accuracy
parameters of differentially-private learners.
Description
[2003.00563] An Equivalence Between Private Classification and Online Prediction
%0 Journal Article
%1 bun2020equivalence
%A Bun, Mark
%A Livni, Roi
%A Moran, Shay
%D 2020
%K differential-privacy online-learning readings
%T An Equivalence Between Private Classification and Online Prediction
%U http://arxiv.org/abs/2003.00563
%X We prove that every concept class with finite Littlestone dimension can be
learned by an (approximate) differentially-private algorithm. This answers an
open question of Alon et al. (STOC 2019) who proved the converse statement
(this question was also asked by Neel et al.~(FOCS 2019)). Together these two
results yield an equivalence between online learnability and private PAC
learnability.
We introduce a new notion of algorithmic stability called "global stability"
which is essential to our proof and may be of independent interest. We also
discuss an application of our results to boosting the privacy and accuracy
parameters of differentially-private learners.
@article{bun2020equivalence,
abstract = {We prove that every concept class with finite Littlestone dimension can be
learned by an (approximate) differentially-private algorithm. This answers an
open question of Alon et al. (STOC 2019) who proved the converse statement
(this question was also asked by Neel et al.~(FOCS 2019)). Together these two
results yield an equivalence between online learnability and private PAC
learnability.
We introduce a new notion of algorithmic stability called "global stability"
which is essential to our proof and may be of independent interest. We also
discuss an application of our results to boosting the privacy and accuracy
parameters of differentially-private learners.},
added-at = {2020-03-04T18:53:13.000+0100},
author = {Bun, Mark and Livni, Roi and Moran, Shay},
biburl = {https://www.bibsonomy.org/bibtex/21ed035d79f5a115a0d8fede6e85538fb/kirk86},
description = {[2003.00563] An Equivalence Between Private Classification and Online Prediction},
interhash = {0ef61d76d8d532a0b6d90ec119dccb4d},
intrahash = {1ed035d79f5a115a0d8fede6e85538fb},
keywords = {differential-privacy online-learning readings},
note = {cite arxiv:2003.00563},
timestamp = {2020-03-04T18:53:13.000+0100},
title = {An Equivalence Between Private Classification and Online Prediction},
url = {http://arxiv.org/abs/2003.00563},
year = 2020
}