Reviews: Locally Private Learning without Interaction Requires Separation

Summary of Contributions: UPDATE: I have read the author rebuttal and my review is unchanged. This work considers the role of interaction in (distribution-free) PAC learning with local differential privacy (LDP). In this model the learning algorithm only has access to examples that have been locally randomized in a differentially private way; the learner may specify the index of the example and the randomizer. If the learning algorithm makes all of its queries in advance, it is non-interactive, and if it makes its queries independent of the labels returned by the oracle, it is label-non-adaptive. The main results of this paper show that PAC learning with a label-non-adaptive LDP algorithm is characterized (up to polynomial factors) by the margin complexity MC(C) of the class, which is the inverse largest margin of separation achievable by linearly separable (into positive and negative examples) embedding of the domain.