Title: What Is The Sample Complexity of Differentially Private Learning?
Abstract: The increase in machine learning applications which involve private and personal data highlights the need for algorithms that handle the data *responsibly*. While this need has been successfully addressed by the field of differentially private machine learning, the cost of privacy remains poorly understood:
How much data is needed for differentially private learning?
How much more data does private learning require compared to learning without privacy constraints?
We will survey some of the recent progress towards answering these questions in the distribution-free PAC model, including the Littlestone-dimension-based *qualitative* characterization and the relationship with online learning. We will also discuss variants of this question in more general (distribution- and data-dependent) learning models.
Bio: Shay is a faculty member at the department of mathematics at the Technion. Most of his academic education Shay received at the Technion where he did his bachelor’s degree and PhD (BSc in math + BSc in computer-science in 2006-10 and PhD in 2013-16). Shay did his master’s degree at the university of Saarland in 2010-12. After finishing his doctorate, Shay was at the US between 2016 and 2020. During this time, he was affiliated with several institutions: Simons Institute at Berkeley, UCSD, Institute for Advanced Study, Princeton University, and Google Brain.