16887

Video URL

https://simons.berkeley.edu/talks/equivalence-between-private-classification-and-online-prediction

An Equivalence Between Private Classification and Online Prediction

(2020). An Equivalence Between Private Classification and Online Prediction. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/equivalence-between-private-classification-and-online-prediction

An Equivalence Between Private Classification and Online Prediction. The Simons Institute for the Theory of Computing, Dec. 18, 2020, https://simons.berkeley.edu/talks/equivalence-between-private-classification-and-online-prediction 

          @misc{ scivideos_16887,
            doi = {},
            url = {https://simons.berkeley.edu/talks/equivalence-between-private-classification-and-online-prediction},
            author = {},
            keywords = {},
            language = {en},
            title = {An Equivalence Between Private Classification and Online Prediction},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {dec},
            note = {16887 see, \url{https://scivideos.org/index.php/Simons-Institute/16887}}
          }
Shay Moran (Technion)
Talk number16887
Source RepositorySimons Institute
Subject

Abstract

Let H be a 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 an equivalence between online learnability and private PAC learnability.