NeurIPS 2020

A Computational Separation between Private Learning and Online Learning

Meta Review

This work studies the relationship between private PAC learning and online learning from a computational perspective. The paper establishes a computational separation between the two problems by showing a class that is efficiently privately PAC learnable but not efficiently learnable in the online setting. This is an important theoretical result that resolves an open question in prior work, and will be of interest to the community.