Fall 2020

An Equivalence Between Private Classification and Online Prediction

Friday, December 18th, 2020 9:30 am10:15 am

Add to Calendar


Shay Moran (Technion)

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.